A mathematical model and an algorithm for solving a multi-depot vehicle routing problem with a single end point

Abstract

The article considers a multi-depot vehicle routing problem with a single end point. First, the key conditions reflecting the nature of the problem and the main constraints are determined. These conditions are used to create a mathematical model of the problem based on specially introduced Boolean variables specifying the mini-route. We also determine the redundant constraints, which may follow from the formulation of the problem, but have already been taken into account in other constraints. The article presents equivalent transformation theorems for the suggested mathematical model. Those theorems are necessary to calculate the estimates of the sets at each iteration of the algorithm. The theorems are also used to design an exact algorithm for solving the problem based on the branch-and-bound method. The article details each step of the algorithm. It also presents and analyses the results of a computational experiment. The results demonstrate that the algorithm managed to find optimal solutions. We also came to the conclusion that it is necessary to refine the methodology for calculating the set estimates. The key results of the study are the mathematical model and the exact algorithm for solving the problem.