A hybrid algorithm for the vehicle routing problem with compatibility constraints

This paper studies a vehicle routing problem with compatibility constraints (VRPCC). It is originated from an application of the cold-chain logistics where different types of cold-chain products may or may not be delivered at the same time. We provide a detailed description of the VRPCC and then propose a hybrid metaheuristic algorithm for solving it. The algorithm includes an ant colony optimization process, in which the new state transition probability formula and pheromone updating rule are applied. In addition, a tabu search process is involved to further improve the solution quality. We modify several VRP benchmark data to form VRPCC instances. The performance of the hybrid algorithm is evaluated and the parameter analysis is conducted. The results demonstrate the effectiveness and efficiency of the algorithm in solving the VRPCC.