A mixed integer linear programming model for vehicle routing problem for non-complete graphs: Behshahr (Iran) case study

Document Type : Research Article

Author

Department of Mathematics, University of Science and Technology of Mazandaran, P.O. Box: 48518-78195, Behshahr, Iran

Abstract

We consider Vehicle Routing Problem (VRP) for non-complete graphs. In order to avoid converting all networks to complete graphs, as in travelling salesman problem, we model VRP for non-complete graphs. Subtours are allowed in this model, since they are unavoidable in non-complete structure, while disconnected subtours   are not allowed. Since disconnected subtour elimination constraints are time-consuming, we provide a separation problem for these constraints and provide an extended formulation based on this separation problem. This extended formulation turns to be equivalent to the original model. In order to reduce the size of the graph, a blocking procedure is proposed in this paper. In addition, we provide two types of valid inequalities to strengthen the formulation. Finally we test our model on a real case study and compare it to the classical model for complete graphs.

Keywords

Main Subjects


[1] F. Alesiani, G. Ermis, K. Gkiotsalitis, Constrained clustering for the capacitated vehicle routing
problem, In 101st Transportation Research Board (TRB) Annual Meeting 2022.
[2] J. H. B¨uhrmann, F. Bruwer, K-medoid petal-shaped clustering for the capacitated vehicle routing
problem, S. Afr. J. Ind. Eng. 32 (2021) 33–41.
[3] E. Choi, D.W. Tcha, A column generation approach to the heterogeneous fleet vehicle routing
problem, Comput. Oper. Res. 34 (2007) 2080–2095.
[4] N. Christofides, A. Mingozzi, P. Toth, The Vehicle Routing Problem, University of Waterloo, 1979,
315–338.
[5] L. Costa, C. Contardo, G. Desaulniers, Exact branch-price-and-cut algorithms for vehicle routing,
Transp. Sci. 53 (2019) 946–985.
[6] R. Dantzig, J. Ramzer, The truck dispatching problem, Manag. Sci. 6 (1959) 81–91.
[7] A. Gunawan, AT. Widjaja, P. Vansteenwegen, F.Y. Vincent, A matheuristic algorithm for the vehicle
routing problem with cross-docking, Appl. Soft Comput. 103 (2021) 107163.
[8] D. Jayarathna, Survey on thirty years of vehicle routing problems: Mathematical models, solution
methods, and real-life applications, Int. J. Res. Sci. Innov. 11 (2024) 435–449.
[9] J.K. Lenstra, A.H.G. Rinnooy Kan, Complexity of vehicle routing and scheduling problems, Net-
works 11 (1981) 221–227.
[10] F. Liu, C. Lu, L. Gui, Q. Zhang, X. Tong, M. Yuan, Heuristics for vehicle routing problem: A survey
and recent advances, 2023, arXiv:2303.04147.
[11] K. E., Medarhri, R. Zine, A survey of the vehicle routing problem and its variants: formulations
and solutions, Math. Model. Comput. 11 (2024) 333–343.
[12] P. Munari, T. Dollevoet, R. Spliet, A generalized formulation for vehicle routing problems, 2017,
arXiv:1606.01935v2.
[13] E. Queiroga, R. Sadykov, E. Uchoa, RP. da P´atria, A modern POPMUSIC matheuristic for the ca-
pacitated vehicle routing problem, ech. rep. Caderno do LOGIS, Universidade Federal Fluminense,
2020.
[14] M. Sadat Emami Taba, Solving Travelling Salesman Problem With a non-complete Graph, Master’s
Thesis, Waterloo University, 2009.
[15] C. Shi, T. Li, Y. Bai, F. Zhao, A heuristics-based parthenogenetic algorithm for the VRP with
potential demands and time windows, Sci. Programming 2016 (1016) 8461857.
[16] A. Tuzemen, C. Yildiz, A Solution proposal to vehicle routing problem with integer linear pro-
gramming: A distributor company sample, Int. J. Contemporary Economics and Administrative
Sci., 9 (2019) 46–78.