A more realistic variant of capacitated vehicle routing problem: Methodology and a case study

Motivated by a real-life daily urban logistics delivery task, we study a more realistic variant of capacitated Vehicle Routing Problem. It extends the existing most relevant research in four aspects, including consideration of heterogeneous fleet, time windows, multi-resource capacitated vehicles and accessibility restrictions. To the best of our knowledge, this variant has never been specifically focused on so far. It involves allocating customers’ orders to specific-type vehicles and arranging appropriate vehicle routes, with the pursuit of minimizing the delivery-related costs. We formulate this variant as a mixed integer linear program, and for small- and medium-sized problem instances, solutions can be directly obtained through using a commercial solver. To tackle large-sized problem instances, we propose a hybrid heuristic method that combines Genetic Algorithm (GA) and Variable Neighborhood Search (VNS). To be precise, first we use GA to generate the initial solution, with a novelty greedy-based decoding algorithm; second, through defining four different types of neighborhood structures, the GA-generated initial solution is iteratively improved through the VNS. Finally, we employ the commercial solver and conduct numerical experiments to evaluate our proposed approaches. Specifically, we first conduct numerical experiments on both newly generated random instances and existing benchmark instances to verify the efficiency and effectiveness of our approaches. Second, we conduct a case study from the Sinotrans Beijing Limited, and the results show that our approaches can effectively address real-world problems and while maintaining reasonable total logistics costs.