1. Proceedings
  2. I3M
  3. 2019
  4. SESDE
  5. 10.46354/i3m.2019.sesde.004

Pollution routing problem with time window and split delivery

  • a Sameh M. Saad  , 
  • b Ramin Bahadori 
    • abDepartment of Engineering and Mathematics, Sheffield Hallam University, Howard Street, Sheffield, S1 1WB, UK
    Cite as
    Saad S. M., Bahadori R. (2019). Pollution routing problem with time window and split delivery. Proceedings of the 7th International Workshop on Simulation for Energy, Sustainable Development & Environment (SESDE 2019), pp. 23-29. DOI: https://doi.org/10.46354/i3m.2019.sesde.004

    Abstract

    In most classic vehicle routing problems, the main goal is to minimise the total travel time or distance while, the green vehicle routing problem, in addition to the stated objectives, also focuses on minimising fuel costs and greenhouse gas emissions, including carbon dioxide emissions. In this research, a new approach in Pollution Routing Problem (PRP) is proposed to minimise the CO2 emission by investigating vehicle weight fill level in length of each route. The PRP with a homogeneous fleet of vehicles, time windows, considering the possibility of split delivery and constraint of minimum shipment weight that must be on the vehicle in each route is investigated simultaneously. The mathematical model is developed and implemented using a simulated annealing algorithm which is programmed in MATLAB software. The generated results from all experimentsdemonstrated that the application of the proposed mathematical model led to the reduction in CO2 emission.

    References

    1. Bektaş, T. and Laporte, G., 2011. The pollution-routing problem. Transportation Research Part B:
      Methodological, 45(8), 1232-1250.
    2. Clarke, G. and Wright, J.W., 1964. Scheduling of vehicles from a central depot to a number of delivery points. Operations research, 12(4), 568-581.
    3. Dantzig, G.B. and Ramser, J.H., 1959. The truck dispatching problem. Management Science, 6(1), 80-91.
    4. Demir, E., Bektaş, T. and Laporte, G., 2011. A comparative analysis of several vehicle emission models for road freight transportation. Transportation Research Part D: Transport and
      Environment, 16(5), 347-357.
    5. Dror, M. and Trudeau, P., 1990. Savings by split delivery routing. Transportation Science, 23(2), 141-145.
    6. Dror, M., Laporte, G. and Trudeau, P., 1994. Vehicle routing with split deliveries. Discrete Applied Mathematics, 50(3), 239-254.
    7. Hill, N., Walker, H., Choudrie, S. and James, K., 2012. Guidelines to Defra/DECC’s GHG Conversion Factors for Company Reporting: Methodology Paper for Emission Factors, Department for Environment. Food and Rural Affairs (Defra).
    8. Kara, I., Kara, B. and Yetis, M.K., 2007. Energy minimizing vehicle routing problem. Combinatorial optimization and applications, 62-71. Springer, Berlin, Heidelberg.
    9. Kirkpatrick, S., Gelatt, C.D. and Vecchi, M.P., 1983. Optimization by simulated annealing. science, 220(4598), 671-680.
    10. Kuo, Y., 2010. Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem. Computers & Industrial Engineering, 59(1), 157-165.
    11. Laporte, G., 1992. The vehicle routing problem: An overview of exact and approximate algorithms. European journal of operational research, 59(3), 345-358.
    12. Maden, W., Eglese, R. and Black, D., 2010. Vehicle routing and scheduling with time-varying data: A case study. Journal of the Operational Research Society, 61(3), 515-522.
    13. Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H. and Teller, E., 1953. Equation of state calculations by fast computing machines. The journal of chemical physics, 21(6), 1087-1092.
    14. Mullaseril, P.A., Dror, M. and Leung, J., 1997. Splitdelivery routeing heuristics in livestock feed distribution. Journal of the Operational Research Society, 48(2), 107-116.
    15. Norouzi, N., Sadegh-Amalnick, M. and Tavakkoli-Moghaddam, R., 2017. Modified particle swarm optimization in a time-dependent vehicle routing problem: minimizing fuel consumption. Optimization Letters, 11(1), 121-134.
    16. Palmer, A. 2007.The development of an integrated routing and carbon dioxide emissions model for goods vehicles. PhD thesis, School of Management, Cranfield University, Bedford, United Kingdom.
    17. Peng, Y. and Wang, X., 2009, April. Research on a vehicle routing schedule to reduce fuel consumption. In Measuring Technology and Mechatronics Automation, 2009. ICMTMA'09.International Conference on (Vol. 3, pp. 825-827). IEEE.
    18. Potvin, J.Y. and Bengio, S., 1996. The vehicle routing problem with time windows part II: genetic search. INFORMS Journal on Computing, 8(2), 165-172.
    19. Reimann, M., Stummer, M. and Doerner, K., 2002, July. A savings based ant system for the vehicle routing problem. In Proceedings of the 4th Annual Conference on Genetic and Evolutionary Computation (pp. 1317-1326). Morgan Kaufmann Publishers Inc.
    20. Saad, S. and Bahadori, R., 2019. Development of a dynamic information fractal framework to monitor and optimise sustainability in the food distribution network. International Journal of Food Engineering, in press.
    21. Tavakkoli-Moghaddam, R., Safaei, N., Kah, M.M.O. and Rabbani, M., 2007. A new capacitated vehicle routing problem with split service for minimizing fleet cost by simulated annealing. Journal of the Franklin Institute, 344(5), 406-425.
    22. Xiao, Y., Zhao, Q., Kaku, I. and Xu, Y., 2012.Development of a fuel consumption optimization
      model for the capacitated vehicle routing problem.Computers & Operations Research, 39(7), 1419-1431.
    23. Yoshizaki, H.T.Y., 2009. Scatter search for a real-lifeheterogeneous fleet vehicle routing problem with time windows and split deliveries in Brazil. European Journal of Operational Research, 199(3), 750-758.