AUT Journal of Electrical Engineering

AUT Journal of Electrical Engineering

Using a Tuning Parameter to Compromise Computation Time and Shipping Cost in an MDVRP

Document Type : Research Article

Authors
Mohammad Amin Zajkani
Reza Rahimi Baghbadorani
Mohammad Haeri
Department of Electrical Engineering, Sharif University of Technology, Tehran, Iran
10.22060/eej.2022.21404.5474
Abstract
Vehicle routing in last-mile delivery plays a decisive role in the new world of people’s 
lifestyles. At present, a growing number of people order their needs online, and this forces companies  to employ innovative delivery logistics to reduce their last-mile shipping costs. The goal is to minimize the cost of travel that depends on the Euclidean distance between customers. Companies require solving vehicle routing problems (VRP) in a reasonable time. In this paper, a new approach is introduced that solves the multi-depot vehicle routing problem (MDVRP) in real-time. We propose a new method by clustering and decomposing the main problem into smaller ones using a tuning parameter α . This approach could reduce the solution time noticeably (up to 95%) while the shipping cost is still reasonable.
Keywords
Vehicle routing problem
Tuning parameter
Computation time
Complexity
Clustering
Subjects
  1. Reyes, M. Savelsbergh, A. Toriello, Vehicle routing with roaming delivery locations, Transportation Research Part C: Emerging Technologies, 80 (2017) 71-91.
  2. Moghdani, K. Salimifard, E. Demir, A. Benyettou, The green vehicle routing problem: A systematic literature review, Journal of Cleaner Production, 279 (2021) 123691.
  3. Asghari, S.M.J. Mirzapour Al-e-Hashem, Green vehicle routing problem: A state-of-the-art review, International Journal of Production Economics, 231 (2021) 107899.
  4. Eksioglu, A.V. Vural, A. Reisman, The vehicle routing problem: A taxonomic review, Computers & Industrial Engineering, 57(4) (2009) 1472-1483.
  5. Zhang, H. Ge, J. Yang, Y. Tong, Review of vehicle routing problems: Models, classification and solving algorithms, Archives of Computational Methods in Engineering, 29(1) (2022) 195-221.
  6. -S. Pan, X. Wang, S.-C. Chu, T. Nguyen, A multi-group grasshopper optimisation algorithm for application in capacitated vehicle routing problem, Data Science and Pattern Recognition, 4(1) (2020) 41-56.
  7. Ochelska-Mierzejewska, A. Poniszewska-Marańda, W. Marańda, Selected genetic algorithms for vehicle routing problem solving, Electronics, 10(24) (2021) 3147.
  8. A. Islam, Y. Gajpal, T.Y. ElMekkawy, Hybrid particle swarm optimization algorithm for solving the clustered vehicle routing problem, Applied Soft Computing, 110 (2021) 107655.
  9. Delalić, E. Žunić, A. Alihodžić, E. Selmanović, A discrete bat algorithm for the rich vehicle routing problem, in: 2021 44th International Convention on Information, Communication and Electronic Technology (MIPRO), IEEE, 2021, pp. 1058-1063.
  10. Diastivena, S. Wahyuningsih, D. Satyananda, Grey wolf optimizer algorithm for solving the multi-depot vehicle routing problem and its implementation, Journal of Physics: Conference Series, IOP Publishing, 2021, pp. 012001.
  11. -H. Jia, Y. Mei, M. Zhang, A bi-level ant colony optimization algorithm for capacitated electric vehicle routing problem, IEEE Transactions on Cybernetics, (2021).
  12. B. Pratiwi, I.Y. Rakhmawati, E. Winarko, Flower pollination algorithm for vehicle routing problem with time windows (VRPTW), Tensor: Pure and Applied Mathematics Journal, 2(2) (2021) 45-52.
  13. Abualigah, M. Alkhrabsheh, Amended hybrid multiverse optimizer with genetic algorithm for solving task scheduling problem in cloud computing, The Journal of Supercomputing, 78(1) (2022) 740-765.
  14. Zhou, U. Benlic, Q. Wu, J.-K. Hao, Heuristic search to the capacitated clustering problem, European Journal of Operational Research, 273(2) (2019) 464-487.
  15. Paradiso, R. Roberti, D. Laganá, W. Dullaert, An exact solution framework for multi-trip vehicle-routing problems with time windows, Operations Research, 68(1) (2020) 180-198.
  16. Kozłowski, D. Mazurkiewicz, B. Kowalska, D. Kowalski, Binary linear programming as a decisionmaking aid for water intake operators, in: International Conference on Intelligent Systems in Production Engineering and Maintenance, Springer, 2017, pp. 199208.
  17. D. Konstantakopoulos, S.P. Gayialis, E.P. Kechagias, Vehicle routing problem and related algorithms for logistics distribution: A literature review and classification, Operational research, (2020) 1-30.
  18. F. Cordeau, M. Gendreau, G. Laporte, A tabu search heuristic for periodic and multi-depot vehicle routing problems, Networks: An International Journal, 30(2) (1997) 105-119.
  19. J. Negreiros, N. Maculan, P.L. Batista, J.A. Rodrigues, A.W. Palhano, Capacitated clustering problems applied to the layout of IT-teams in software factories, Annals of Operations Research, (2020) 1-29.
  20. Nunes Bezerra, M.J.F. Souza, S.R.d. Souza, V. Nazário Coelho, A VNS-based algorithm with adaptive local search for solving the multi-depot vehicle routing problem, in: International Conference on Variable Neighborhood Search, Springer, 2018, pp. 167-181.
  21. E.H. Sadati, D. Aksen, N. Aras, The r-interdiction selective multi-depot vehicle routing problem, International Transactions in Operational Research, 27(2) (2020) 835-866.
  22. B. Aruoba, J. Fernandez-Villaverde, A comparison of programming languages in economics (No. w20263), in, National Bureau of Economic Research Cambridge, 2014.