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

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

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

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

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

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

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