城市機場接送服務中的車次調度問題研究綜述*

安慶師范大學經濟與管理學院 許爭爭

一、引言

目前，中國已成為世界上增長最快的航空客運市場之一，在此基礎上應運而生的機場接送服務已經在中國很多城市展開，如北京、上海、深圳和沈陽等地，機場接送服務中的調度問題不僅對各個航空票務公司具有重要作用，而且對各個航空公司的運營成功與否也具有密不可分的重要意義。

二、機場接送問題概述

（1）車輛模式。機場接送服務中使用的車輛模式主要有三種：自有車輛、租用車輛、自有車輛和租用車輛并存。目前大部分大中型票務公司通常以使用自有車輛和租用車輛并存模式為主，在安排接送任務時以租用車輛為主，自有車輛主要用于突發狀況，以及為租用的車輛提供協助等；中小型票務公司以使用自有車輛為主，有個別公司與一些個人或車輛出租公司簽訂合作合同，當自有車輛不足時，調用租用的車輛進行服務。租用的車輛按照單次服務付費，即每接送一次顧客到達機場給予一定的報酬，根據具體天氣條件等，每次費用不等。

機場接送服務中使用的車輛類型主要有小型轎車和中小型巴士。現有機場接送服務中，大部分公司采用的車輛以小型轎車為主，也有部分公司擁有中小型巴士應用于一些集體出游和顧客點比較集中的位置。

（2）接送流程。顧客可以通過網絡、電話或者直接到票務公司柜臺訂票，顧客的所有基本信息包括姓名、聯系方式、航班號等將被記錄下來，如果顧客需要機場接送服務，那么他需要指定具體的接送地點。接送地點由顧客指定后，一般票務公司會判斷接送顧客時是否方便，比如是否在接送時間附近不方便停車等，在這些情況下，票務公司需要和顧客進行協商以確定接送地點。另外，從理論上說，顧客對時間的需求可能有兩個方面：一是車輛到達接送顧客的時間；另一個是車輛到達機場的時間。目前的車輛調度安排都是由比較有經驗的調度員在服務的前一天晚上作出。一般做法是，首先將計劃需要出港的顧客名單列出，然后根據出港時間進行安排，將時間和地理位置比較近的分在一組，最后將每組內的所有顧客進行排序，構成每個車次的接送順序。

三、機場接送中的車次分配與調度問題研究情況

機場接送中的車次分配與調度問題是車輛路徑與調度問題的延伸與擴展，具有新的問題和新的情況。目前國內外的相關研究情況如下：

接送顧客到機場的車輛調度問題(Vehicle Scheduling for Airpassenger，VSAP)是車輛路徑問題的擴展。屬于典型的NP難問題，由于國內外環境的差異，在國外鮮有這方面的研究，而與之相似的是國外關于Dial-A-Ride問題(Dial-A-Ride Problem，DARP)的研究，電話預約叫車服務問題[1]是指使用者(乘客)主動打電話到控制中心告知自己所在位置和需要接送的時間后，考慮時間窗、容量等約束要求由控制中心的調度人員規劃路線，指派車輛接送乘客，完成運送行為。電話預約服務主要分為兩種模式：一種是靜態模式，在靜態模式下所有要求是預先知道的，根據要求可以提前計劃好所有車輛的路線；另一種是動態模式，在動態模式下，車輛路線是根據用戶一天的需求實時構造，或者初始時把問題考慮成求一個靜態問題，以獲得一個初始解，稍后又按照新的要求對路徑進行修改。接送顧客到機場的車輛調度也是乘客打電話訂票并預約接送服務，調度員根據航班時間和顧客所在位置對顧客進行分組，規劃路線并指派車輛接送顧客，接送的終點是機場，而DARP中終點是不同的地點，別的假設和約束兩者相似。DARP早期的研究以靜態問題為主，側重于單車輛路徑問題。動態DARP[2]最早是由Psaraftis提出，他以總用時最少為目標，設計了一種精確的動態規劃算法，不考慮顧客提出的時間窗，顧客提出要求之后被立即服務，但是由于算法的復雜度較大，只對小規模的例子有效，算法只被用在了10個顧客的例子中。Psaraftis后來將原方法擴展到考慮出發時間窗和到達時間窗的雙時間窗約束中。Sexton等人[3]考慮單時間窗提出一種啟發式算法解決類似的問題，以車輛行駛的理想時間和實際所用時間的加權和為目標，對7到20個實際生活中的用戶進行了測試。Desrosiers等人[4]針對動態DARP提出了一種精確的列生成算法，應用于40個客戶的例子中。Coslovich等人[5]設計了兩階段插入算法應用于動態DARP。目前的研究集中在研究動態的DARP，提出了一些模型和啟發式算法。從時間窗的角度，VSAP問題主要可以劃分成三類：考慮到達機場時間窗的VSAP問題；考慮顧客點預約時間窗的VSAP問題；考慮雙時間窗的VSAP問題。目前已有的主要研究集中在考慮時間窗要求這一條件下的模型的建立和算法方面的設計。

(1)考慮到達機場時間窗的VSAP問題。Dong G等人[6]建立了最小化成本模型，提出了基于集劃分的精確算法求解考慮到達機場時間窗的VSAP，在計算過程中，第一階段生成了所有可行的車次，在第二階段通過優化軟件Cplex對模型進行求解，生成了最優方案，該算法對于小規模的實例均可以較快求得最優結果。

孔媛等人[7]考慮顧客滿意度以運輸成本最小為目標建立數學模型，提出了基于集劃分的啟發式算法求解考慮到達機場時間窗的VSAP，該算法采用兩階段求解的方法，第一階段采用廣度優先搜索的策略，生成了所有可行路徑，第二階段采用啟發式策略，從所有可行路徑中找到可行解。

李佳[8]針對多行程模式的機場接送服務中車次分配與調度問題，建立了面向行程的集劃分模型，基于該模型設計了精確算法，并對算法的精確性進行了證明；接著將司機連續工作時長作為一個約束條件考慮進來，建立了基于行程鏈的集劃分模型，在該模型的基礎上，設計了基于標簽和面向行程鏈集劃分模型的精確算法，通過大量的計算分析了考慮司機連續工作時長下多行程模式與單行程模式對結果產生的影響，以及人工成本對計算結果的影響，并給出了相關的應用建議；最后通過大量算例測試，分析了采用出租車接送的單行程模式與采用代駕租車接送的多行程模式之間存在著一個代駕租車日租費用臨界值，在此臨界值以下采用多行程模式更加合適。

楊培穎等人[9]對機場接送服務中碳排放模型和成本模型進行了全面的比較分析，提出了基于標簽與集劃分的精確算法，通過比較分析兩模型在各影響因素下的測試結果，驗證了不同模型的有效性和適用范圍。對機場接送服務中的車輛配置等提供了可供參考的意見。

楊培穎[10]針對大規模VASP，設計了最近點優先的雙向極線掃描啟發式算法求解機場接送服務中碳排放最小化單車型模型，通過對該算法有效性和適用性的分析，表明了該算法具有較高的實用價值；針對多車型碳排放最小化模型，提出了改進的基于標簽與集劃分的精確算法，這種算法適用于中小規模顧客點情況。通過分析多車型情況下的車輛調度問題，結果有效地說明了研究機場接送服務中多車型分配與調度問題的必要性和重要性。

(2)考慮顧客點預約時間窗的VSAP問題。唐加福等人[11]建立了顧客點滿意度和公司成本的多目標優化模型，并設計了基于C-W節約算法的兩階段啟發式算法求解考慮顧客點預約時間窗的VSAP。算法取得了較好的效果。Liu B X[12]考慮了顧客點預約時間窗的VSAP問題，建立了最小化成本模型，提出了一個基于時間和地域劃分的極線掃描啟發式算法，并采用多種算例將該算法與PCPH算法和Sweep算法進行了比較，證明了該算法在大規模求解問題時的優越性和可行性。

劉秉星[13]針對顧客點預約時間窗的VSAP問題，提出基于集劃分的精確算法求解VSAP。提出了范圍驗證的方法來驗證路線的有效性，克服了點對點驗證方法容易遺漏的缺點，保證了求解結果的精確性和有效性。該文還分別考慮最小化成本和最小化車次兩個不同的目標，設計了最近點優先的雙向極線掃描啟發式算法，對中等規模與大規模VSAP問題進行求解，通過比較，結果要優于SPTD算法，并得出結論：TSNP算法在顧客點人數差異不大時，適用于求解以最小化成本為目標的優化問題；顧客點人數差異顯著時，適用于以最小化車次為優化目標。

孔媛[14]以最小化成本為目標，考慮不同車型的情況，建立了接送顧客到機場的混合車次分配與調度問題的數學模型，設計了自適應鄰域搜索算法求解問題，采用141組數據，其中中等企業72組，小型企業69組。大量的計算和實例測試顯示，算法能快速得到優秀的解，并且算法的穩定性高，不受數據類型和規模的影響，通過變動成本進行的分析，當單位座位的變動成本率為-30%以下時，公司應考慮減少購置小轎車增加中小巴士的車型。

(3)考慮雙時間窗的VSAP問題。曹夏夏等人[15]設計了基于租賃模式下的雙時間窗基于集劃分的精確算法，在原有均衡模型的基礎上綜合考慮了顧客對接送時間窗、到達時間窗以及繞行限制的要求，通過實例分析驗證了算法的有效性。針對基于租賃車輛模式下的票務企業，建立了顧客滿意度和車次數的均衡模型，根據模型特點設計了一種基于集劃分的精確算法(EABSP)。

所以國內的研究主要可以概括為以下三個方面：考慮不同時間窗條件下，單行程或多行程中基于集劃分的精確算法的研究；考慮不同時間窗條件下，各種啟發式算法如節約—插入啟發式算法，掃描算法等算法的研究；除了最小化成本模型外，碳排放模型的建立或多目標均衡模型的建立。