关键词: 时空距离, 同时配集货, 时变路网, 异型车辆, 混合变邻域搜索遗传算法

Abstract: Aimed at the vehicle routing problem with simultaneous delivery and pickup in the time-dependent road speed and soft time window, a routing optimization model is established with the goal of minimizing the sum of vehicle dispatch cost, time window penalty cost, and vehicle transportation cost. According to the characteristics of the problem, a hybrid genetic algorithm with variable neighborhood search considering the temporal-spatial distance is designed. Customers are clustered according to the temporal-spatial distance to generate initial solutions, which improves the quality of the algorithm. The depth search capability of the variable neighborhood search algorithm is applied to the local search strategy of the genetic algorithm to enhance the local search capability of the algorithm. An adaptive neighborhood search number strategy and a novel solution acceptance mechanism of simulated annealing are proposed to balance the breadth and depth required for population evolution. The model and algorithm are verified by several sets of examples of different scales. The research results not only deepen and expand the relevant research on vehicle routing problem with simultaneous delivery and pickup, but also provide theoretical basis for logistics enterprises to optimize vehicle scheduling plan.

Key words: temporal-spatial distance, simultaneous delivery and pickup, time-dependent road network, hybrid genetic algorithm with variable neighborhood search