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

摘要： 针对道路行驶速度时变且软时间窗条件下的同时配集货车辆路径问题，以车辆派遣成本、时间窗惩罚成本以及车辆运输成本之和最小化为目标建立路径优化模型。根据问题特征设计了考虑时空距离的混合变邻域搜索遗传算法，采用时空距离对客户进行聚类生成初始解，提高算法求解质量；将变邻域搜索算法的深度搜索能力运用到遗传算法的局部搜索策略中，增强算法的局部搜索能力；提出自适应邻域搜索次数策略以及模拟退火的新解接受机制，平衡种群进化所需的广度和深度。通过多组不同规模的算例验证了本文模型及算法的有效性，研究成果不仅深化和拓展同时配集货车辆路径问题的相关研究，也为物流企业优化车辆调度方案提供理论依据。

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