基于交汇点协作的车辆调度问题的两阶段算法  

Two-stage algorithm to vehicle scheduling problem based on intersection coordination

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

机构地区：[1]东北大学工商管理学院,辽宁沈阳110819 [2]流程工业综合自动化国家重点实验室,辽宁沈阳110819

出　　处：《系统工程学报》2013年第5期573-580,共8页Journal of Systems Engineering

基　　金：国家创新研究群体科学基金资助项目(71021061);教育部博士点专项基金资助项目(2012004;2110023)

摘　　要：针对城市中面向顾客车辆接送服务实践中车辆相互协作的要求,研究基于协作的带时间窗的车辆调度问题.通过介绍车辆协作的相关概念和孤立顾客点的定义,提出了产生孤立顾客点的方法,并以交汇点作为车辆协作点,提出了一种求解车辆调度问题的两阶段算法.第一阶段对顾客点按时间窗进行聚类生成基本路径,在考虑绕行限制的务件下产生孤立顾客点;第二阶段采用优化模型求解最优的交汇点,生成协作车辆的路径方案集合.最后,以航空票务公司机场接送服务为应用案例进行测试分析,仿真表明了基于交汇点协作的可行性和有效性.This paper studies the coordination-based vehicle routing and scheduling problem with time windows for coordinative requirements of vehicles in the process of the customer pickup and delivery service in a city. After introducing the concept of vehicle coordination and the definition of an isolated customer point, this paper proposes a method to generate an isolated customer point. Further, a two-stage algorithm, which regards the intersection points as the location of vehicle coordination, is presented to solve the vehicle routing and scheduling problem. In the first stage of the algorithm, the basic route is built by clustering customer points via the time window. Then the isolated customer points are established through taking into account the vehicles＇ circumvention. In the second stage, an optimal model is used to find the optimal intersection point. Thus, the route set of coordination vehicles is established. Finally, the actual pickup and delivery service in flight ticked sales companies is used as a case and simulations are conducted. The simulation results show that the coordination of intersection points is feasible and effective.

关 键 词：接送服务 车辆协作 满意度 孤立顾客点 两阶段算法 

分 类 号：C934[经济管理—管理学]