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

Journal of Mathematical Modeling
Volume 13, Issue 4
December 2025
Pages 787-801

Files

Share

How to cite

Statistics