Abstract: Aiming at the split delivery vehicle routing problem with simultaneous delivery and pick-up and time windows preference, a mathematical model is established to minimize the sum of dispatch cost, tally cost, time window penalty cost and fuel consumption cost. A hybrid genetic-variable neighborhood search algorithm is designed to solve it. The concept of temporal-spatial distance is introduced into the algorithm. First, the nearest neighbor insertion method and logistic mapping equation are used to generate the initial population. Then the depth search ability of the variable neighborhood search algorithm is used to optimize the algorithm. An adaptive search strategy is proposed to balance the breadth and depth of population evolution. We design split criteria, and set different split services for each customer. A time difference pass method is designed to determine optimal departure times of vehicles, reducing waiting times of vehicles at customers. Finally, the numerical results show that the model and algorithm are effective.

Key words: vehicle routing problem, time windows preference, split delivery, simultaneous delivery and pick-up, hybrid genetic-variable neighborhood search algorithm

摘要： 针对带时间窗偏好的同时配集货且需求可拆分车辆路径问题,最小化派遣成本、理货成本、时间窗惩罚成本以及油耗成本之和,建立数学模型。设计混合遗传变邻域搜索算法求解问题,在算法中引入时空距离的理念,首先用最近邻插入法和Logistic映射方程生成初始种群;然后利用变邻域搜索算法的深度搜索能力优化算法;提出自适应搜索策略,平衡种群进化所需的广度和深度;设计拆分准则,为各客户设置不同的拆分服务量;提出确定车辆最优出发时间的时差推移法,减少车辆在客户处的等待时间;最后通过多组算例验证本文模型和算法的有效性。

关键词: 车辆路径问题, 时间窗偏好, 需求可拆分, 同时配集货, 混合遗传变邻域搜索算法