基于协作的三阶段启发式算法求解多行程车辆行程问题  

Three-stage Algorithm to Multi-trip Vehicle Routing Problem Based on Coordination

作　　者：许争争[1] 唐加福[2] 

机构地区：[1]安庆师范学院经济与管理学院,安徽安庆246011 [2]东北财经大学管理科学与工程学院,辽宁大连116025

出　　处：《南开大学学报（自然科学版）》2015年第5期51-59,共9页Acta Scientiarum Naturalium Universitatis Nankaiensis

基　　金：国家自然科学基金(61203182);教育部博士点专项基金(20120042110023)

摘　　要：在一定顾客满意度下以绕行限制为约束条件,对城市中面向顾客车辆接送服务的基于协作的多行程车辆路径问题进行研究.对于不协作时需要单独接送的孤立顾客点,基本车辆和协作车辆考虑在某个合适的位置进行协作将孤立顾客点上的顾客从协作车辆上换乘到基本车辆上送到目的地,从而提出了一种基于协作的三阶段启发式算法.最后,以航空票务公司机场接送服务为应用案例进行仿真分析,仿真结果表明提出的启发式算法是可行和有效的,可以为实际的车辆安排提供较好的调度方案.Based on a certain customers＇ satisfaction degree, the multi-trip vehicle routing problem for the customer pickup and delivery service in a city is studied. Regarding the vehicles＇ circumvention as constraints, the isolated customer points are generated when vehicle coordination was not taken into account.In such a case, each customer at each isolated customer point is to be picked up and delivered to the destination independently. Different from previous method, the vehicle coordination is taken into consideration between basic vehicles and coordinative vehicles at a suitable location. According to this routing coordination, the customers in the coordinative vehicles are transferred into the basic vehicles and then are delivered to the destination. And a three-stage algorithm, which considers vehicle coordination, is proposed to solve multi-trip vehicle routing problem. Finally, the pickup and delivery service in Flight Ticked Sales Companies is used as a study case and simulations are conducted. Simulation results show that the coordination of intersection points is feasible and effective. It can provide better scheme for actual vehicle scheduling.

关 键 词：满意度 孤立顾客点 车辆协作 启发式算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]