The Multi-Trip Vehicle Routing Problem: Optimal vs. Heuristic

This thesis replicates the study of Fagerholt (2004) in which an exact algorithm for the the Multi-Trip Vehicle Routing Problem (MTVRP) with an heterogeneous fleet is studied. Next to a replication of the latter study, the performance of Fagerholt’s algorithm will be compared to an heuristic for the MTVRP, based on costs, feasibility, and computation time to find a solution. In the MTVRP one or multiple routes have to be assigned to the available ships in such a way that all ports are visited, capacity of the ships and time windows are taken into account, and overall costs are minimized. One part of Fagerholt’s algorithm requires solving numerous Traveling Salesman Problems (TSP), something which can be done by a Mixed Integer Linear Problem (MILP) algorithm or a Dynamic Programming (DP) algorithm. As both algorithms are exact, the minimum cost solution will be the same. However, as the computation time of the DP algorithm is up to 49 times lower, this algorithm is likely to perform best in (larger) real-life situations. In this paper the performance of the MILP and DP algorithm is compared with the performance of the heuristic of Olivera and Viera (2007) for the MTVRP problem with an homogeneous fleet. The latter heuristic uses an Adaptive Memory Procedure, along with a Sweep algorithm and Tabu-Search with as goal to find a feasible solutions with the lowest costs within a reasonable period of time. The heuristic was able to find an optimal solution for half of the cases, for the other cases the costs found were 0.37% up to 1.31% higher. The computation time of the heuristic was in almost all cases less than the computation time of the MILP algorithm. However, the DP algorithm is in all but one case faster than the heuristic whilst providing lower cost solutions and guaranteeing feasibility of the solution. Therefore, for the investigated instances, the DP algorithm outperforms the heuristic.