A comparative analysis on undirected cut-based formulations of periodic vehicle routing problem

Official URL: https://risc01.sabanciuniv.edu/record=b2771072_(Table of contents)

The classical Vehicle Routing Problem (VRP) is a well-studied combinatorial optimization problem whose aim is to identify optimal routes for a fleet of homogeneous vehicles to satisfy the demands of a geographically dispersed set of customers, considering a single planning period. The Periodic Vehicle Routing Problem (PRVP) is a generalization of the classical VRP in which the planning horizon consists of multiple periods and each customer has a set of associated possible visit schedules. In the literature, there are many solution approaches proposed such as exact solution methods, heuristic algorithms, and metaheuristics. However, exact solution methods are much fewer in number compared to heuristic methods, and a comprehensive study focused on cut-based formulations of the problem is not available in the literature. In this thesis, we propose and study several cut-based formulations of the PVRP defined on an undirected network. Different versions of connectivity constraints and schedule selection constraints are used to develop alternative formulations. Moreover, new cut-based formulations which eliminates the use of vehicle indices are also introduced. Since the proposed formulations contain exponentially many connectivity constraints, we devise and implement branch-and-cut procedures to solve them exactly. The computational experiments are prepared and conducted for all of the formulations. The results of the experiments indicate that some of the alternative formulations have the potential to improve computational performance. The model without vehicle indices provides improvement in terms of reaching optimality and computation times, while the models with alternative schedule selection constraints provide promising results in terms of solution quality and average computation times.