论文部分内容阅读
现代服务行业在社会经济活动中的地位越来越重要。作为服务行业一员的航空票务公司(Fight Tickets Sale Agencies,FTSA)为了提高服务质量、吸引更多潜在顾客提出了一项的增值服务,即机场接送服务(Pickup and Delivery of Customers to the Airport,PDCA)。该服务已经在中国的很多城市中开展,然而这种增值服务并不能产生直接的经济效益,反而会因为需要满足顾客更高的要求、提升服务质量而产生额外的费用。因此,如何在满足顾客满意度的情况下尽可能地降低成本,就成为该服务是否能够成功运营的关键所在。到目前为止,围绕PDCA问题的研究都是在单行程模式下展开的,然而经过调研和理论分析发现,多行程模式下的机场接送服务(Multi-trip Mode PDCA, MTM-PDCA)不仅能够减少车辆行驶总长度,而且能够减少车次数,从而降低了PDCA的整体运营成本。本文正是针对多行程模式下机场接送服务车次分配与调度问题展开的研究,旨在为决策者提供更加节约成本的解决方案,同时也从理论上丰富和发展了车辆路径与调度问题。本文的主要研究内容如下：(1)首次研究了多行程模式下的机场接送服务问题,并从理论上证明了多行程模式相对于单行程模式的优势。针对MTM-PDCA问题的特点,创新地提出了面向行程的集划分(Trips Oriented Set-Partitioning,TO-SP)模型,设计了求解该模型的精确算法,并给出了精确性的理论证明。针对不同的实例和参数进行了大量的实验,并与单行程进行比较,分析了多行程模式下的代驾租车固定费用、平均每顾客点顾客数量与车容量的比率、时间窗分布、地理分布对多行程优势的影响；最后给出了在什么情景下使用多行程模式能减少更多运营成本的建议。(2)考虑到道路交通安全以及司机身体健康等因素,将司机连续工作时长作为约束引入到MTM-PDCA问题中。针对考虑司机连续工作时长的MTM-PDCA (Duration Considered MTM-PDCA, DCMTM-PDCA)司题的特点,创新地提出了面向行程链的集划分模型(Trip-Chain Oriented Set-Partitioning, TCO-SP)。鉴于该模型的求解速度取决于行程链的数量,对行程链数量进行了理论研究,给出了最坏情况下行程链数量的数学表达公式,并分析了影响行程链数量的因素。为了快速求得精确解,针对该问题的特点,提出了基于改进标签和TOC-SP模型的三阶段精确算法,并给出了该算法精确性的理论证明。改进的标签算法(Improved Label Algorithm, ILA)位于整个精确算法的第二阶段,他可以在构造可行行程链的过程中去掉那些不可行行程链,使获得可行行程链的速度更快。该精确算法能够快速高效地求解较大规模的实例。针对不同的实例和参数进行了大量的实验,分析了DCMTM-PDCA问题中行程链的数量和特点；比较考虑司机连续工作时长的多行程模式与单行程模式的总成本,分析了参数、实例特点对多行程建模优势的影响,讨论了目标函数中的人工成本对调度结果的影响,并给出了相关的应用建议。本文理论上首次研究了多行程模式下的机场接送服务问题,并为建模和精确算法的设计提供了新思路；实际上为FTSA提供了多行程模式下的机场接送服务提供管理支持,使企业在保证满意度的情况下,减少了运营成本,提升市场竞争力。