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

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