多行程模式下機場接送服務車次分配與調(diào)度問題的精確算法研究.pdf

1、現(xiàn)代服務行業(yè)在社會經(jīng)濟活動中的地位越來越重要。作為服務行業(yè)一員的航空票務公司(Fight Tickets Sale Agencies，F(xiàn)TSA)為了提高服務質(zhì)量、吸引更多潛在顧客提出了一項的增值服務，即機場接送服務(Pickup and Delivery of Customers to the Airport，PDCA)。該服務已經(jīng)在中國的很多城市中開展，然而這種增值服務并不能產(chǎn)生直接的經(jīng)濟效益，反而會因為需要滿足顧客更高的要求、提升服

2、務質(zhì)量而產(chǎn)生額外的費用。因此，如何在滿足顧客滿意度的情況下盡可能地降低成本，就成為該服務是否能夠成功運營的關鍵所在。到目前為止，圍繞PDCA問題的研究都是在單行程模式下展開的，然而經(jīng)過調(diào)研和理論分析發(fā)現(xiàn)，多行程模式下的機場接送服務(Multi-trip Mode PDCA，MTM-PDCA)不僅能夠減少車輛行駛總長度，而且能夠減少車次數(shù)，從而降低了PDCA的整體運營成本。
　　本文正是針對多行程模式下機場接送服務車次分配與調(diào)度問題

3、展開的研究，旨在為決策者提供更加節(jié)約成本的解決方案，同時也從理論上豐富和發(fā)展了車輛路徑與調(diào)度問題。本文的主要研究內(nèi)容如下：
　　(1)首次研究了多行程模式下的機場接送服務問題，并從理論上證明了多行程模式相對于單行程模式的優(yōu)勢。針對MTM-PDCA問題的特點，創(chuàng)新地提出了面向行程的集劃分（Trips Oriented Set-Partitioning，TO-SP）模型，設計了求解該模型的精確算法，并給出了精確性的理論證明。針對不同的

4、實例和參數(shù)進行了大量的實驗，并與單行程進行比較，分析了多行程模式下的代駕租車固定費用、平均每顧客點顧客數(shù)量與車容量的比率、時間窗分布、地理分布對多行程優(yōu)勢的影響;最后給出了在什么情景下使用多行程模式能減少更多運營成本的建議。
　　(2)考慮到道路交通安全以及司機身體健康等因素，將司機連續(xù)工作時長作為約束引入到MTM-PDCA問題中。針對考慮司機連續(xù)工作時長的MTM-PDCA(DurationConsidered MTM-PDCA，

5、DCMTM-PDCA)問題的特點，創(chuàng)新地提出了面向行程鏈的集劃分模型（Trip-Chain Oriented Set-Partitioning，TCO-SP）。鑒于該模型的求解速度取決于行程鏈的數(shù)量，對行程鏈數(shù)量進行了理論研究，給出了最壞情況下行程鏈數(shù)量的數(shù)學表達公式，并分析了影響行程鏈數(shù)量的因素。為了快速求得精確解，針對該問題的特點，提出了基于改進標簽和TOC-SP模型的三階段精確算法，并給出了該算法精確性的理論證明。改進的標簽算法(

6、Improved Label Algorithm，ILA)位于整個精確算法的第二階段，他可以在構造可行行程鏈的過程中去掉那些不可行行程鏈，使獲得可行行程鏈的速度更快。該精確算法能夠快速高效地求解較大規(guī)模的實例。針對不同的實例和參數(shù)進行了大量的實驗，分析了DCMTM-PDCA問題中行程鏈的數(shù)量和特點;比較考慮司機連續(xù)工作時長的多行程模式與單行程模式的總成本，分析了參數(shù)、實例特點對多行程建模優(yōu)勢的影響，討論了目標函數(shù)中的人工成本對調(diào)度結果的