Capacitated Vehicle Routing Problem Considering Cost of Vehicle Deployment

Document Type : Scientific - Research

Author

Assistant Professor, Civil Engineering Department, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran

Abstract

This paper proposes an integer linear mathematical formulation for Vehicle Routing Problem (VRP), where the capital cost for deploying each vehicle is minimized together with other on-link transportation costs. The model has been formulated as a multi-commodity network flow model with capacity constraints. It is well known that the computational complexity to this type of problems is NP-hard. Thus, the ACO algorithm, which has been known to be a powerful meta-heuristic algorithm for solving VRPs in large networks, has been adapted to solve the problem. Although the ACO algorithm has repeatedly been used to solve the capacitated VRP, it has a drawback that cannot consider the capital cost of each vehicle along with other operational costs of the vehicles (associated with the total distance traveled within a day) in its initial form. More specifically, naturally it assumes that each vehicle returns to the depot if it becomes full or the demand finishes, each met first; this paper seeks to propose an adapted ACO algorithm in which this assumption is released. To assess the capability of the proposed model in large-scale networks, the case study of Mashhad city, consisting of 253 traffic analysis zones and over than 3800 links, has been considered. Results show that the proposed algorithm converges to near-to-optimal solutions within two seconds of cpu time, which is encouraging.

Keywords

References

  • Babaei, M., & Rajabi-Bahaabadi, M. (2019). "School bus routing and scheduling with stochastic time-dependent travel times considering on-time arrival reliability." Computers & Industrial Engineering, Vol. 138, 106125.

 

  • Bell, J. E., & McMullen, P. R. (2004). “Ant colony optimization techniques for the vehicle routing problem.” Advanced Engineering Informatics, Vol. 18, No. 1, PP. 41-48.

 

  • Bullnheimer, B., Hartl, R. F., & Strauss, C. (1997). “Applying the ant system to the vehicle routing problem.” Second Metaheuristics International Conference, MIC’97, Sophia-Antipolis, France.

 

  • Cordeau, J.-F., Laporte, G., Savelsbergh, M. W., & Vigo, D. (2007). “Vehicle routing.” Transportation, handbooks in operations research and management science, Vol. 14, PP. 367-428.

 

  • Dantzig, G. B., & Ramser, J. H. (1959). "The truck dispatching problem." Management science, Vol. 6, No. 1, PP. 80-91.

 

  • Eksioglu, B., Vural, A. V., & Reisman, A. (2009). “The vehicle routing problem: A taxonomic review.” Computers & Industrial Engineering, Vol. 57, No. 4, PP. 1472-1483.

 

  • Elshaer, R., & Awad, H. (2020). “A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants.” Computers & Industrial Engineering, 140, 106242.

 

  • Gendreau, M., Hertz, A., & Laporte, G. (1994). “A tabu search heuristic for the vehicle routing problem.” Management science, Vol. 40, No. 10, PP. 1276-1290.

 

  • Gendreau, M., Potvin, J.-Y., Bräumlaysy, O., Hasle, G., & Løkketangen, A. (2008). “Metaheuristics for the vehicle routing problem and its extensions: A categorized bibliography.” Springer.

 

  • Golden, B. L., Raghavan, S., & Wasil, E. A. (2008). “The Vehicle Routing Problem: Latest Advances and New Challenges.” Springer.

 

  • Guo, N., Qian, B., Hu, R., Jin, H. P., & Xiang, F. H. (2020). “A Hybrid Ant Colony Optimization Algorithm for Multi-Compartment Vehicle Routing Problem.” Complexity.

 

  • Huang, S. H., Huang, Y. H., Blazquez, C. A., & Chen, C. Y. (2022). “Solving the vehicle routing problem with drone for delivery services using an ant colony optimization algorithm.” Advanced Engineering Informatics, Vol. 51, 101536.

 

  • Jia, Y. H., Mei, Y., & Zhang, M. (2021). “A bilevel ant colony optimization algorithm for capacitated electric vehicle routing problem.” IEEE Transactions on Cybernetics.

 

  • Laporte, G. (1992). “The vehicle routing problem: An overview of exact and approximate algorithms.” European Journal of Operational Research, Vol. 59, No. 3, PP. 345-358.

 

  • Laporte, G., Nobert, Y., & Desrochers, M. (1985). “Optimal routing under capacity and distance restrictions.” Operations research, Vol. 33, No. 5, PP. 1050-1073.

 

  • Leite, M. R., Bernardino, H. S., & Gonçalves, L. B. (2022). “A variable neighborhood descent with ant colony optimization to solve a bilevel problem with station location and vehicle routing.” Applied Intelligence, Vol. 52, No. 7, PP. 7070-7090.

 

  • Marinakis, Y., Marinaki, M., & Dounias, G. (2008). “Honey bees mating optimization algorithm for the vehicle routing problem Nature inspired cooperative strategies for optimization (NICSO 2007) (PP. 139-148): Springer.

 

  • Marinakis, Y., Marinaki, M., & Dounias, G. (2010). “A hybrid particle swarm optimization algorithm for the vehicle routing problem.” Engineering Applications of Artificial Intelligence, Vol. 23, No. 4, PP. 463-472.

 

  • Mutar, M., Burhanuddin, M., Hameed, A., Yusof, N., & Mutashar, H. (2020). “An efficient improvement of ant colony system algorithm for handling capacity vehicle routing problem.” International Journal of Industrial Engineering Computations, Vol. 11, No. 4, PP. 549-564.

 

  • Niu, Y., Yang, Z., Chen, P., & Xiao, J. (2018). "Optimizing the green open vehicle routing problem with time windows by minimizing comprehensive routing cost." Journal of cleaner production, Vol. 171, PP. 962-971.

 

  • Osman, I. H. (1993). “Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem.” Annals of operations research, Vol. 41, No. 4, PP. 421-451.

 

  • Potvin, J.-Y., Duhamel, C., & Guertin, F. (1996). “A genetic algorithm for vehicle routing with backhauling.” Applied Intelligence, Vol. 6, No. 4, PP. 345-355.

 

  • Rajabi-Bahaabadi, M., Shariat-Mohaymany, A., Babaei, M., & Vigo, D. (2021). "Reliable vehicle routing problem in stochastic networks with correlated travel times." Operational Research, Vol. 21, No. 1, PP. 299-330.

 

  • Taş, D., Dellaert, N., Van Woensel, T., & De Kok, T. (2013). "Vehicle routing problem with stochastic travel times including soft time windows and service costs." Computers & Operations Research, Vol. 40, No. 1, PP. 214-224.

 

  • Vidal, T., Laporte, G., & Matl, P. (2020). “A concise guide to existing and emerging vehicle routing problem variants.” European Journal of Operational Research, Vol. 286, No.2, PP. 401-416.

 

  • Wang, I. L. (2018). "Multicommodity network flows: A survey, Part I: Applications and Formulations." International Journal of Operations Research, Vol. 15, No. 4, PP. 145-153.

 

  • Wu, H., Gao, Y., Wang, W., & Zhang, Z. (2021). “A hybrid ant colony algorithm based on multiple strategies for the vehicle routing problem with time windows.” Complex & Intelligent Systems.

 

  • Xiang, X., Qiu, J., Xiao, J., & Zhang, X. (2020). “Demand coverage diversity based ant colony optimization for dynamic vehicle routing problems.” Engineering Applications of Artificial Intelligence, Vol. 91, 103582.

 

  • Zhao, P. X., Luo, W. H., & Han, X. (2019). "Time-dependent and bi-objective vehicle routing problem with time windows." Advances in Production Engineering & Management, Vol. 14, No. 2, PP. 201-212.
Quarterly Journal of Transportation Engineering
Volume 15, Issue 2 - Serial Number 59
January 2024
Pages 3509-3526

Files

History

  • Receive Date: 13 July 2022
  • Revise Date: 08 December 2022
  • Accept Date: 02 January 2023

Share

How to cite

Statistics