基于顾客点协作的车辆路径问题的两阶段算法

A Two-stage Algorithm to the Vehicle Routing Problem Based on Customer Point Coordination

研究城市中面向顾客车辆接送服务的车辆路径问题。通过介绍车辆协作的相关概念,提出了孤立顾客点的定义,讨论了车辆协作的分类。以顾客满意度和绕行限制为约束条件,考虑顾客点作为车辆协作点,提出了顾客换乘的车辆协作规则,并通过最优化理论,提出了一种基于顾客点协作的两阶段算法。该算法通过车辆协作规则,利用协作车辆将孤立顾客点的顾客通过协作方式在顾客点进行换乘后,与非孤立点顾客一起由基本车辆接送到指定目的地。最后,以航空票务公司机场接送服务为应用案例进行仿真分析,仿真结果表明提出的算法是可行和有效的。

This peper studies the vehicle routing problem in the pickup and delivery services for customers in a city.By introducing the concept about the vehicle coordination,the isolated customer point is defined and the classification of the vehicle coordination is discussed.Then the customers’satisfaction and vehicles’circumvention are regarded as constraints.By considering customer points as the vehicle coordination ones to be selected,the rules of the vehicle coordination for customer transfer are proposed.And by employing the optimal theory,a customer point based two-stage algorithm is presented.According to the vehicle coordination rules proposed in this paper,this algorithm can utilize the coordinative vehicle to transfer the customers in the isolated customer point at the customer point in a coordinative way.And these customers and those in non-isolated customer points are delivered to the given destination by the basic vehicle. Finally,the pickup and delivery service in Flight Ticked Sales Companies is used as a study case and a lot of simulations is conducted.Simulation results show that the algorithm presented in this paper is feasible and effective.