Development and investigation of an exact algorithm for the generalized vehicle routing problem

Abstract

In this study, the exact algorithm of generalized vehicle routing problem for persistent UAV system is developed and investigated. Using the characteristics of UAVs a mixed linear integer programming is formulated. The MILP contains multiple depots, multiple trips, an initial condition, capacity, and distance constraints. The exact algorithm so solve MILP is developed based column generation. The master problem is a set partitioning problem which is identical with decomposition of VRPTW, while subproblem has more constraints which the UAV characteristics have to be reflected. The subproblem is a generalized version of elementary shortest path problem as it allows multiple reuse and initial condition. Solving subproblem spend most of the time in column generation. Therefore, we used a dynamic algorithm called label correcting algorithm. The branch-and-price showed a better performance than solving MILP directly, which was 50 times faster of execution time in best case. Branch-and-price showed better result in mixed type customer instance when problem size get bigger.