A two-stage algorithm with valid inequalities for the split delivery vehicle routing problem

摘要

This paper proposes a two-stage (TS) algorithm with valid inequalities (TSVI) to optimally solve the split delivery vehicle routing problem (SDVRP). The first stage in the TSVI creates clusters that cover all demand and establishes a lower bound. The second stage calculates the minimal distance traveled for each cluster by solving the corresponding traveling salesman problem (TSP). The sum of the minimal distance traveled over all clusters yields an upper bound. The minimal distance of each TSP is added as cuts (constraints) into the first stage for the vehicles visiting all the points covered by the TSP problem. This iterative procedure stops with an optimal solution when no new clusters are created in the first stage. The TS scheme provides opportunities to develop strong valid inequalities for the first stage to improve the overall computational speed. Seven valid inequalities are developed. One of the valid inequalities is created to address the symmetric nature of a solution caused by the index combinations of vehicles. Another strong valid inequality is created to provide a lower bound on the distance traveled for each subset of demand points. Conditions under which a delivery to a demand point is not split in an optimal solution are studied in order to create additional valid inequalities. The numerical experiments show that the TSVI significantly outperforms other exact solution approaches provided in the literature for the SDVRP.