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

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

考虑航空票务公司接送机场服务背景下车次分配与调度问题具有多批次、小批量、时间要求高、需求个性化等特点,建立了考虑顾客满意度及绕行限制的租赁模式下的最小化车次数模型,并采用改进两阶段算法求解该模型。第一阶段采用基于时间窗逆序排列的聚类算法,生成初始车次及车次中顾客点的访问次序;第二阶段采用插入启发式算法,对初始解进行优化改进。通过计算实验与结果分析,验证了模型以及算法的有效性。

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.