面向接送机场服务最小化车次数的聚类算法  

Clustering algorithm for minimizing vehicle number of airport pickup and delivery service

作　　者：鲍宇[1] 唐加福[1] 刘黎黎[1] 

机构地区：[1]东北大学流程工业综合自动化教育部重点实验室,辽宁沈阳110819

出　　处：《计算机集成制造系统》2011年第2期442-447,共6页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(70625001;70721001);中央直属高校基本科研业务费资助项目(N090204001)~~

摘　　要：考虑航空票务公司接送机场服务背景下车次分配与调度问题具有多批次、小批量、时间要求高、需求个性化等特点,建立了考虑顾客满意度及绕行限制的租赁模式下的最小化车次数模型,并采用改进两阶段算法求解该模型。第一阶段采用基于时间窗逆序排列的聚类算法,生成初始车次及车次中顾客点的访问次序;第二阶段采用插入启发式算法,对初始解进行优化改进。通过计算实验与结果分析,验证了模型以及算法的有效性。Under the background of pickup and delivery service in flight ticket sales company,vehicle routing and scheduling problem was characterized by its multi-batch,small capacity,tight service time constraints and individualized requirements.A mathematical model of minimum vehicle number was established in vehicle-rental mode.With this model,customers＇ satisfaction and vehicles＇ circumvention were considered as constraints.To solve this model,a two-stage heuristic algorithm was proposed.The initial number of vehicles and the visit order of customer locations were generated in the first stage of this algorithm,which was based on clustering algorithm of time windows reversed permutation.In the second stage,the initial solution was improved and optimized via an insertion heuristic.Finally,effectiveness of this model and algorithm was verified through the simulation experiment and results analysis.

关 键 词：接送机场服务 车辆路径问题 调度 聚类算法 时间窗 最小化车次数 启发式算法 

分 类 号：N945[自然科学总论—系统科学]