基于时间与地域约束的机场接送调度优化算法及适用性分析

论文摘要

近年来,随着服务业的蓬勃发展与市场竞争的日益激烈,很多航空票务公司对购票顾客提供免费接送机场的服务。这些公司基本都是依靠调度员的经验来对接送车辆作出调度,车辆的利用率并不高；同时在接送过程中对于接送时间准确度的把握也存在一定的问题,造成部分顾客的不满。基于此背景,本文研究了接送顾客到机场的车辆调度问题(VSAP)。根据顾客对于接送时间的不同要求,可将VSAP划分为三类：考虑到达机场时间窗的VSAP问题、考虑顾客点预约时间窗的VSAP问题、考虑双时间窗的VSAP问题。本文对这三类VSAP问题的实例进行了合理的设计与分类,为算法的比较分析提供公共测试实例。在此基础上,重点研究考虑顾客点预约时间窗的VSAP问题,先建立其数学模型,再设计开发两种启发式算法与精确算法对其进行求解。针对考虑顾客点预约时间窗的VSAP问题,首先提出了基于时间和地域划分的极线扫描启发式算法(SPTD)求解最小化成本模型。通过与以往提出的基于排序的聚类优先启发式算法(PBCPH)与Sweep算法进行比较与分析,结果表明：对中等规模以上实例该算法优于以往算法,并且对于大规模实例具有较好的效果；同时,对于多种地理分布类型的实例,该算法具有广泛的适用性。其次,针对SPTD算法本身的缺陷和其在中等规模实例求解中的效果并不令人满意的问题,提出了最近点优先的双向极线扫描启发式算法(TSNP)。通过与SPTD的比较分析,结果表明：对中等和大规模实例,TSNP算法优于SPTD算法；此外,通过对比TSNP算法求解最小化车次模型的结果,发现TSNP算法在顾客点人数差异显著情况下,该算法适用于求解最小化车次模型,且该算法对于不同分布类型的实例具有广泛的适用性。第三,提出了基于集划分的精确算法(EBSM),以弥补前两个算法对于求解小规模实例不能保证最优解的缺点。通过计算结果分析,该算法可以精确求解小规模甚至中等规模的实例；在计算时间可接受的范围,完全可以使用该算法求解中小规模的实例。最后,设计开发了算法应用模块,将设计的实例与上述算法集成,便于算法的计算实验与后续研究的进行。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题研究背景
• 1.2 课题研究意义
• 1.3 研究目标与内容
• 1.4 研究的技术路线与方法
• 1.5 全文总体结构与安排
• 第2章 相关知识与VSAP实例设计
• 2.1 相关知识
• 2.1.1 免费接送机场（FDCA）服务
• 2.1.2 机场接送问题的研究现状
• 2.1.3 路径优化与调度问题的优化算法研究简介
• 2.2 VSAP实例设计
• 2.2.1 考虑到达机场时间窗VSAP实例设计
• 2.2.2 考虑顾客点预约时间窗VSAP实例设计
• 2.2.3 考虑双时间窗VSAP实例设计
• 2.3 VSAP实例分类
• 2.4 本章小结
• 第3章 基于时间和地域划分的极线扫描启发式算法
• 3.1 考虑顾客点预约时间窗的VSAP数学模型
• 3.1.1 问题描述与假设
• 3.1.2 最小化成本模型VSAP-Mod1
• 3.2 基于时间和地域划分的极线扫描启发式算法（SPTD）
• 3.2.1 时间与地域规定
• 3.2.2 SPTD算法思想
• 3.2.3 SPTD算法流程图与步骤
• 3.3 计算实验与适用性分析
• 3.3.1 SPTD与PBCPH、Sweep算法比较
• 3.3.2 给定绕行系数、不同满意度水平下SPTD的适用性分析
• 3.3.3 给定满意度水平、不同绕行系数下SPTD的适用性分析
• 3.3.4 不同类型实例下SPTD的适用性分析
• 3.3.5 SPTD算法的适用性分析结论与应用建议
• 3.4 本章小结
• 第4章 最近点优先的双向极线扫描启发式算法
• 4.1 考虑顾客点预约时间窗的VSAP数学模型
• 4.1.1 最小化成本目标
• 4.1.2 最小化车次目标
• 4.2 最近点优先的双向极线扫描启发式算法（TSNP）
• 4.2.1 第一个接送顾客点的确定
• 4.2.2 TSNP算法思想
• 4.2.3 TSNP算法示例
• 4.2.4 算法流程图与步骤
• 4.3 计算实验与适用性分析
• 4.3.1 最小化成本目标下TSNP与SPTD算法比较
• 4.3.2 给定绕行系数、不同满意度水平下TSNP的适用性分析
• 4.3.3 给定满意度水平、不同绕行系数下TSNP的适用性分析
• 4.3.4 不同类型实例下TSNP的适用性分析
• 4.3.5 最小化车次目标下TSNP的适用性分析
• 4.3.6 TSNP算法的适用性分析结论与应用建议
• 4.4 本章小结
• 第5章 基于集划分的精确算法
• 5.1 问题背景
• 5.2 考虑顾客点预约时间窗的VSAP数学模型
• 5.3 基于集划分的精确算法（EBSM）
• 5.3.1 求解顾客最大满意度的局部最优目标--路线有效性判定
• 5.3.2 求解顾客最大满意度的局部最优目标
• 5.3.3 划分顾客点集合
• 5.3.4 第一阶段——生成车次集
• 5.3.5 第二阶段——集划分模型精确求解
• 5.4 计算实验与适用性分析
• 5.5 结论
• 第6章 求解VSAP问题的算法应用模块设计
• 6.1 算法应用模块的功能设计
• 6.2 算法应用模块的数据库设计
• 6.3 算法应用模块的部分实现
• 6.4 本章小结
• 第7章 论文总结与展望
• 7.1 论文工作总结
• 7.2 展望
• 参考文献
• 致谢
• 攻读硕士期间参加的科研项目与发表的论文