機場接送服務中基于車輛協(xié)作的車次分配與調度方法研究.pdf

1、隨著市場經(jīng)濟的快速發(fā)展和社會生活水平的逐步提高，人們出行不僅注重交通的快捷、方便，也注重出行的舒適感和滿意度，因此越來越多的人出行時選擇方便快捷的航空旅行。航空票務公司(Flight Tickets Sales Agency，F(xiàn)TSA)是為航空公司代售機票的服務型企業(yè)，近幾年隨著市場競爭的日趨激烈，各企業(yè)都紛紛推出各種增值服務來吸引顧客，接送機場服務應運而生。
　　接送顧客到機場的車輛調度問題(Vehicle Scheduling

2、 Problem for Air-passenger，VSPA)是車輛路徑問題(Vehicle Routing Problem，VRP)的一種延伸應用，它屬于車次分配與調度問題(Vehicle Allocation and Scheduling Problem，VASP)，是一類典型的優(yōu)化問題。但現(xiàn)有的VSPA研究都沒有考慮車輛間的協(xié)作關系，但在實際的車輛調度中，為了節(jié)約成本，航空票務公司通常會采用車輛協(xié)作(Vehicle Collab

3、oration)的方式接送顧客。
　　作為國家自然科學基金(No.61203182)、教育部博士點專項基金(20120042110023)和教育部直屬高?；究蒲袠I(yè)務費重點項目(No.90204001)的重要組成部分，本文在對機場接送服務進行深入調研分析的基礎上，針對目前采用的機場接送服務的特點，研究了基于車輛協(xié)作的車次分配與調度中若干優(yōu)化問題。主要包含以下六個方面內(nèi)容:
　　(1)針對機場接送服務的特點，提出了機場接送服務

4、中車輛協(xié)作的幾種典型方式和孤立顧客點等相關概念及相應的描述方法;提出了考慮協(xié)作的顧客滿意度函數(shù)表達式，并進行了深入的討論和分析。
　　(2)以最小化行駛里程為目標，在考慮顧客滿意度和繞行限制的約束條件下，提出了基于協(xié)作的兩階段啟發(fā)式算法。該算法第一階段對顧客點按時間窗進行聚類并生成基本路徑，在考慮繞行限制的約束條件下產(chǎn)生初步的孤立顧客點，并對其進行二次聚類，最終剩余的顧客點確定為孤立顧客點;該算法第二階段采用車輛協(xié)作的方式對初始解

5、進行優(yōu)化，生成協(xié)作車輛的路徑方案集合。最后對應用案例進行測試分析，結果表明了所提出算法的可行性和有效性。
　　(3)在基于協(xié)作的兩階段啟發(fā)式算法基礎上，分段建立了集劃分模型，提出了基于集劃分和協(xié)作的啟發(fā)式算法來求解小規(guī)模機場接送服務車次分配與調度問題，最后通過仿真實驗分析，驗證了算法對于小規(guī)模實例的有效性。
　　(4)根據(jù)航空票務公司在調用車輛時可能同時使用小轎車和中小巴士的實際情況，將單車型擴展到混合車型來研究機場接送服務

6、在混合車型下的車次分配與調度問題(Fleet Size and Mix VASP，F(xiàn)SMVASP)，建立了以最小行駛總里程數(shù)為目標的協(xié)作調度模型;根據(jù)該模型特點，提出了相應的啟發(fā)式優(yōu)化求解算法。該方法在初步規(guī)劃出基本路徑后，尋找出孤立點;通過分別考慮孤立點與基本路徑、剩余基本路徑與已被孤立點協(xié)作的基本路徑、最終剩余路徑間的協(xié)作方式，獲得混合車輛下的車輛調度方案。最后，通過實驗測試，驗證了所提出的協(xié)作調度模型及優(yōu)化算法能有效地降低機場接送

7、的運營成本。
　　(5)根據(jù)機場接送服務中接送車輛容量小，運輸任務行程短的特點，研究了多行程運輸模式下基于車輛協(xié)作的多行程車輛分配與調度問題(Multi-trips Vehicle Allocationand Scheduling Problem，MVASP)，設計了基于協(xié)作的三階段啟發(fā)式算法。該算法第一階段生成基本車輛路徑集合和孤立點集合;第二階段根據(jù)時間約束，產(chǎn)生基本車輛的行程鏈;第三階段找到協(xié)作點，生成協(xié)作車輛的行程鏈。實驗

8、測試對比分析了多行程中協(xié)作與不協(xié)作的情況，分析結果表明所提出算法能有效降低公司成本。最后，進一步對比分析了多行程與單行程中車輛協(xié)作的情況，實驗結果為航空票務公司選擇合適的運輸模式提供了有效的理論支持。
　　(6)針對自有車輛和租用車輛并存的情況，建立了最小成本模型，設計了相應的啟發(fā)式算法。該算法首先在考慮約束條件的基礎上求得基本車輛的最小車次解，然后對車次分配中需要單獨接送的孤立顧客點，利用協(xié)作車輛進行路徑優(yōu)化;通過對應用案例進行