城市機(jī)場(chǎng)接送服務(wù)中的車(chē)次調(diào)度問(wèn)題研究綜述*

安慶師范大學(xué)經(jīng)濟(jì)與管理學(xué)院 許爭(zhēng)爭(zhēng)

一、引言

目前，中國(guó)已成為世界上增長(zhǎng)最快的航空客運(yùn)市場(chǎng)之一，在此基礎(chǔ)上應(yīng)運(yùn)而生的機(jī)場(chǎng)接送服務(wù)已經(jīng)在中國(guó)很多城市展開(kāi)，如北京、上海、深圳和沈陽(yáng)等地，機(jī)場(chǎng)接送服務(wù)中的調(diào)度問(wèn)題不僅對(duì)各個(gè)航空票務(wù)公司具有重要作用，而且對(duì)各個(gè)航空公司的運(yùn)營(yíng)成功與否也具有密不可分的重要意義。

二、機(jī)場(chǎng)接送問(wèn)題概述

（1）車(chē)輛模式。機(jī)場(chǎng)接送服務(wù)中使用的車(chē)輛模式主要有三種：自有車(chē)輛、租用車(chē)輛、自有車(chē)輛和租用車(chē)輛并存。目前大部分大中型票務(wù)公司通常以使用自有車(chē)輛和租用車(chē)輛并存模式為主，在安排接送任務(wù)時(shí)以租用車(chē)輛為主，自有車(chē)輛主要用于突發(fā)狀況，以及為租用的車(chē)輛提供協(xié)助等；中小型票務(wù)公司以使用自有車(chē)輛為主，有個(gè)別公司與一些個(gè)人或車(chē)輛出租公司簽訂合作合同，當(dāng)自有車(chē)輛不足時(shí)，調(diào)用租用的車(chē)輛進(jìn)行服務(wù)。租用的車(chē)輛按照單次服務(wù)付費(fèi)，即每接送一次顧客到達(dá)機(jī)場(chǎng)給予一定的報(bào)酬，根據(jù)具體天氣條件等，每次費(fèi)用不等。

機(jī)場(chǎng)接送服務(wù)中使用的車(chē)輛類(lèi)型主要有小型轎車(chē)和中小型巴士?，F(xiàn)有機(jī)場(chǎng)接送服務(wù)中，大部分公司采用的車(chē)輛以小型轎車(chē)為主，也有部分公司擁有中小型巴士應(yīng)用于一些集體出游和顧客點(diǎn)比較集中的位置。

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

三、機(jī)場(chǎng)接送中的車(chē)次分配與調(diào)度問(wèn)題研究情況

機(jī)場(chǎng)接送中的車(chē)次分配與調(diào)度問(wèn)題是車(chē)輛路徑與調(diào)度問(wèn)題的延伸與擴(kuò)展，具有新的問(wèn)題和新的情況。目前國(guó)內(nèi)外的相關(guān)研究情況如下：

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

(1)考慮到達(dá)機(jī)場(chǎng)時(shí)間窗的VSAP問(wèn)題。Dong G等人[6]建立了最小化成本模型，提出了基于集劃分的精確算法求解考慮到達(dá)機(jī)場(chǎng)時(shí)間窗的VSAP，在計(jì)算過(guò)程中，第一階段生成了所有可行的車(chē)次，在第二階段通過(guò)優(yōu)化軟件Cplex對(duì)模型進(jìn)行求解，生成了最優(yōu)方案，該算法對(duì)于小規(guī)模的實(shí)例均可以較快求得最優(yōu)結(jié)果。

孔媛等人[7]考慮顧客滿意度以運(yùn)輸成本最小為目標(biāo)建立數(shù)學(xué)模型，提出了基于集劃分的啟發(fā)式算法求解考慮到達(dá)機(jī)場(chǎng)時(shí)間窗的VSAP，該算法采用兩階段求解的方法，第一階段采用廣度優(yōu)先搜索的策略，生成了所有可行路徑，第二階段采用啟發(fā)式策略，從所有可行路徑中找到可行解。

李佳[8]針對(duì)多行程模式的機(jī)場(chǎng)接送服務(wù)中車(chē)次分配與調(diào)度問(wèn)題，建立了面向行程的集劃分模型，基于該模型設(shè)計(jì)了精確算法，并對(duì)算法的精確性進(jìn)行了證明；接著將司機(jī)連續(xù)工作時(shí)長(zhǎng)作為一個(gè)約束條件考慮進(jìn)來(lái)，建立了基于行程鏈的集劃分模型，在該模型的基礎(chǔ)上，設(shè)計(jì)了基于標(biāo)簽和面向行程鏈集劃分模型的精確算法，通過(guò)大量的計(jì)算分析了考慮司機(jī)連續(xù)工作時(shí)長(zhǎng)下多行程模式與單行程模式對(duì)結(jié)果產(chǎn)生的影響，以及人工成本對(duì)計(jì)算結(jié)果的影響，并給出了相關(guān)的應(yīng)用建議；最后通過(guò)大量算例測(cè)試，分析了采用出租車(chē)接送的單行程模式與采用代駕租車(chē)接送的多行程模式之間存在著一個(gè)代駕租車(chē)日租費(fèi)用臨界值，在此臨界值以下采用多行程模式更加合適。

楊培穎等人[9]對(duì)機(jī)場(chǎng)接送服務(wù)中碳排放模型和成本模型進(jìn)行了全面的比較分析，提出了基于標(biāo)簽與集劃分的精確算法，通過(guò)比較分析兩模型在各影響因素下的測(cè)試結(jié)果，驗(yàn)證了不同模型的有效性和適用范圍。對(duì)機(jī)場(chǎng)接送服務(wù)中的車(chē)輛配置等提供了可供參考的意見(jiàn)。

楊培穎[10]針對(duì)大規(guī)模VASP，設(shè)計(jì)了最近點(diǎn)優(yōu)先的雙向極線掃描啟發(fā)式算法求解機(jī)場(chǎng)接送服務(wù)中碳排放最小化單車(chē)型模型，通過(guò)對(duì)該算法有效性和適用性的分析，表明了該算法具有較高的實(shí)用價(jià)值；針對(duì)多車(chē)型碳排放最小化模型，提出了改進(jìn)的基于標(biāo)簽與集劃分的精確算法，這種算法適用于中小規(guī)模顧客點(diǎn)情況。通過(guò)分析多車(chē)型情況下的車(chē)輛調(diào)度問(wèn)題，結(jié)果有效地說(shuō)明了研究機(jī)場(chǎng)接送服務(wù)中多車(chē)型分配與調(diào)度問(wèn)題的必要性和重要性。

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

劉秉星[13]針對(duì)顧客點(diǎn)預(yù)約時(shí)間窗的VSAP問(wèn)題，提出基于集劃分的精確算法求解VSAP。提出了范圍驗(yàn)證的方法來(lái)驗(yàn)證路線的有效性，克服了點(diǎn)對(duì)點(diǎn)驗(yàn)證方法容易遺漏的缺點(diǎn)，保證了求解結(jié)果的精確性和有效性。該文還分別考慮最小化成本和最小化車(chē)次兩個(gè)不同的目標(biāo)，設(shè)計(jì)了最近點(diǎn)優(yōu)先的雙向極線掃描啟發(fā)式算法，對(duì)中等規(guī)模與大規(guī)模VSAP問(wèn)題進(jìn)行求解，通過(guò)比較，結(jié)果要優(yōu)于SPTD算法，并得出結(jié)論：TSNP算法在顧客點(diǎn)人數(shù)差異不大時(shí)，適用于求解以最小化成本為目標(biāo)的優(yōu)化問(wèn)題；顧客點(diǎn)人數(shù)差異顯著時(shí)，適用于以最小化車(chē)次為優(yōu)化目標(biāo)。

孔媛[14]以最小化成本為目標(biāo)，考慮不同車(chē)型的情況，建立了接送顧客到機(jī)場(chǎng)的混合車(chē)次分配與調(diào)度問(wèn)題的數(shù)學(xué)模型，設(shè)計(jì)了自適應(yīng)鄰域搜索算法求解問(wèn)題，采用141組數(shù)據(jù)，其中中等企業(yè)72組，小型企業(yè)69組。大量的計(jì)算和實(shí)例測(cè)試顯示，算法能快速得到優(yōu)秀的解，并且算法的穩(wěn)定性高，不受數(shù)據(jù)類(lèi)型和規(guī)模的影響，通過(guò)變動(dòng)成本進(jìn)行的分析，當(dāng)單位座位的變動(dòng)成本率為-30%以下時(shí)，公司應(yīng)考慮減少購(gòu)置小轎車(chē)增加中小巴士的車(chē)型。

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

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