关键词: 多车程, 多时间窗, 车辆路径问题, 自适应大邻域搜索

Abstract: Focusing on the multi-trip transportation of terminal logistics and the diverse demand of customers for service time, a vehicle routing problem with multiple trips and multiple time windows is studied. A bi-objective mixed integer programming model is established to minimize the number of vehicles and the total transportation cost, while an improved adaptive large neighborhood search algorithm is designed to solve the problem. In this algorithm, a variety of efficient destroy and repair operators based on three levels of routes, travel distances and customer points are constructed to expand the search space of solutions. An adaptive strategy is used to select efficient search operators and a simulated annealing rule is introduced to avoid the solution from falling into local optimum and improve the search efficiency. By analyzing the experimental results of instances with various scales, the advantages of the improved adaptive large neighborhood search algorithm are verified, and the positive impact of the model considering multiple trips on the total transportation cost is analyzed.

Key words: multiple trips, multiple time windows, vehicle routing problem, adaptive large neighborhood search