李紅啟，劉寅瑩，簡(jiǎn)曉榮

（北京航空航天大學(xué)交通科學(xué)與工程學(xué)院，北京 100191）

航空運(yùn)輸以其顯著的快速性，成為中高端快遞服務(wù)的首選運(yùn)輸手段；將地面車(chē)輛的集貨/配送環(huán)節(jié)與航空運(yùn)輸有效銜接，成為快遞企業(yè)的重要運(yùn)作模式。例如：中國(guó)郵政速遞物流公司（EMS）依托中國(guó)郵政航空公司，建立起以南京為集散中心的全夜航航空網(wǎng)，并配以2萬(wàn)余部攬收、投遞專(zhuān)用車(chē)輛；順豐速遞是國(guó)內(nèi)投遞速度最快的快遞公司之一，截至2015年7月，擁有1.6萬(wàn)臺(tái)地面運(yùn)輸車(chē)輛和40架全貨機(jī)（含租賃），并明確2021年運(yùn)營(yíng)196架全貨機(jī)的發(fā)展目標(biāo)。自營(yíng)全貨機(jī)機(jī)隊(duì)、有效銜接起航空運(yùn)力和地面運(yùn)力、充分發(fā)揮不同運(yùn)輸方式的技術(shù)經(jīng)濟(jì)優(yōu)勢(shì)、降低物流成本、提升服務(wù)時(shí)效性，是現(xiàn)階段中國(guó)物流快遞企業(yè)的追求目標(biāo)。由于地面車(chē)輛集、配貨結(jié)合航空運(yùn)輸?shù)目爝f網(wǎng)絡(luò)模式涉及的運(yùn)能資源多、運(yùn)輸組織環(huán)節(jié)多、協(xié)調(diào)作業(yè)多，航空快遞的地面集貨運(yùn)力與航空運(yùn)力協(xié)同調(diào)度問(wèn)題較傳統(tǒng)車(chē)輛調(diào)度問(wèn)題[1-2]更為復(fù)雜，主要體現(xiàn)在如何協(xié)調(diào)地面車(chē)輛路徑優(yōu)化和航空運(yùn)力運(yùn)用方式等方面。

對(duì)航空快遞地面集貨運(yùn)力與航空運(yùn)力協(xié)同調(diào)度問(wèn)題的研究具有重要參考意義的成果主要為兩類(lèi)：航空運(yùn)力調(diào)度問(wèn)題和兩級(jí)運(yùn)輸網(wǎng)絡(luò)上的車(chē)輛調(diào)度問(wèn)題。

1）學(xué)術(shù)界針對(duì)航空運(yùn)力調(diào)度問(wèn)題的研究成果可大致分為3類(lèi)：機(jī)隊(duì)和機(jī)型分配問(wèn)題，航班時(shí)刻和飛行路徑排定問(wèn)題，飛機(jī)排班問(wèn)題。如：Hane等[3]研究機(jī)隊(duì)分配問(wèn)題的整數(shù)規(guī)劃模型，對(duì)某家擁有11種機(jī)型、每日航班達(dá)2 500次的航空公司的機(jī)型分配問(wèn)題予以求解；Levin[4]在研究單機(jī)型的航班時(shí)刻優(yōu)化及飛機(jī)路徑安排問(wèn)題時(shí)引入了航班時(shí)刻窗的概念；Burke等[5]提出多目標(biāo)魯棒優(yōu)化的飛機(jī)調(diào)度模型，采用基因算法進(jìn)行求解；孫宏[6]以需用飛機(jī)數(shù)最少為目標(biāo)研究航班銜接問(wèn)題，以滿(mǎn)足飛機(jī)調(diào)度指令為目標(biāo)研究飛機(jī)排班模型和算法；付維方等[7]運(yùn)用深度優(yōu)先搜索算法生成可行航班串，通過(guò)整數(shù)規(guī)劃模型對(duì)可行航班串進(jìn)行篩選，以用于編制航班運(yùn)營(yíng)方案。

2）在兩級(jí)運(yùn)輸網(wǎng)絡(luò)上的車(chē)輛調(diào)度問(wèn)題（簡(jiǎn)稱(chēng)2EVRP問(wèn)題）中，貨物先由大型車(chē)輛從配送中心送至中轉(zhuǎn)站，再用小型車(chē)輛由中轉(zhuǎn)站配送至客戶(hù)點(diǎn)。Perboli等[8-9]給出2E-VRP問(wèn)題總成本最小化的優(yōu)化模型；Jepsen等[10]提出2E-VRP問(wèn)題的邊界流模型；Crainic等[11]分析了客戶(hù)點(diǎn)分布、配送中心和中轉(zhuǎn)站布局、中轉(zhuǎn)站與客戶(hù)點(diǎn)之間運(yùn)輸成本對(duì)總成本的影響；Crainic等[12]又分析了裝卸作業(yè)、交通擁堵等因素對(duì)中轉(zhuǎn)站布局的影響，并比較兩級(jí)網(wǎng)絡(luò)配送模式與單一層級(jí)網(wǎng)絡(luò)配送模式的效果；Baldacci等[13]將車(chē)輛使用的固定成本考慮在內(nèi)，分別建立兩級(jí)運(yùn)輸網(wǎng)絡(luò)上的可行路徑集；Soysal等[14]將分時(shí)段分路段的交通擁堵因素添加到2E-VRP問(wèn)題中，同時(shí)將駕駛員工資和車(chē)輛油耗成本考慮在內(nèi)，構(gòu)建混合整數(shù)線(xiàn)性規(guī)劃模型；Li等[15]提出時(shí)效要求下城際干線(xiàn)運(yùn)輸網(wǎng)絡(luò)銜接城市配送網(wǎng)絡(luò)的多類(lèi)型車(chē)輛調(diào)度問(wèn)題的混合整數(shù)規(guī)劃模型。

近30年來(lái)，航空快遞市場(chǎng)日趨龐大。如20世紀(jì)末美國(guó)貨運(yùn)業(yè)中發(fā)展最快的細(xì)分業(yè)務(wù)是零擔(dān)貨運(yùn)與空運(yùn)，F(xiàn)edEX和UPS等建立起系統(tǒng)完善的地面銜接航空運(yùn)輸網(wǎng)絡(luò)[16]。盡管針對(duì)車(chē)輛調(diào)度問(wèn)題的研究已有近60年，但尚未出現(xiàn)針對(duì)航空快遞活動(dòng)中公路運(yùn)力結(jié)合航空運(yùn)力的協(xié)同調(diào)度問(wèn)題研究成果。本研究旨在探討航空快遞的地面集貨運(yùn)力與航空運(yùn)力協(xié)同調(diào)度問(wèn)題，具有良好的理論價(jià)值和實(shí)踐指導(dǎo)意義：在建模過(guò)程中對(duì)地面集貨運(yùn)輸與航空運(yùn)輸?shù)臒o(wú)縫對(duì)接進(jìn)行刻畫(huà)，拓展不同類(lèi)型運(yùn)力匹配和運(yùn)輸時(shí)效銜接方式，這可補(bǔ)充和豐富車(chē)輛調(diào)度問(wèn)題的建模手段；模型求解方法和求解結(jié)論可為航空快遞企業(yè)提供重要的運(yùn)力使用策略，也為分析陸空聯(lián)運(yùn)協(xié)調(diào)性的決策提供參考。

1 混合整數(shù)規(guī)劃模型

1.1 問(wèn)題描述

航空快遞的地面集貨運(yùn)力與航空運(yùn)力協(xié)同調(diào)度問(wèn)題具有如下特點(diǎn)。

1）運(yùn)輸網(wǎng)絡(luò)有兩類(lèi)節(jié)點(diǎn)：起飛機(jī)場(chǎng)及其輻射服務(wù)范圍內(nèi)若干個(gè)有快遞發(fā)送需求的客戶(hù)點(diǎn)。其中，起飛機(jī)場(chǎng)為航空運(yùn)輸起點(diǎn)，也是地面集貨卡車(chē)的始發(fā)/終到點(diǎn)。

2）空運(yùn)運(yùn)力分為固定航班運(yùn)力（即全貨機(jī)）和備選航班運(yùn)力（即客機(jī)腹艙）。其中，全貨機(jī)在既定時(shí)刻起飛，備選航班運(yùn)力起飛時(shí)刻可有多種選擇。集貨卡車(chē)在全貨機(jī)起飛前完成的集貨量應(yīng)不少于全貨機(jī)的最低載貨量要求；備選航班運(yùn)力在全貨機(jī)起飛后才起飛，其起飛時(shí)刻可根據(jù)綜合運(yùn)力調(diào)度方案靈活選定，備選航班運(yùn)力沒(méi)有最低載貨量要求?？者\(yùn)成本和飛機(jī)類(lèi)型有關(guān)。

3）起飛機(jī)場(chǎng)的地面集貨作業(yè)區(qū)可用的集貨卡車(chē)數(shù)量充足、類(lèi)型豐富。

4）客戶(hù)點(diǎn)的快遞發(fā)送量已知、且不可拆分，每個(gè)客戶(hù)點(diǎn)的發(fā)貨量不超過(guò)集貨卡車(chē)的額定載貨量?？蛻?hù)點(diǎn)有服務(wù)時(shí)間窗限制。集貨過(guò)程中每個(gè)客戶(hù)點(diǎn)只能被訪(fǎng)問(wèn)一次。為降低機(jī)場(chǎng)的快遞分揀作業(yè)量，設(shè)定同一輛集貨卡車(chē)上的貨物必須裝載到執(zhí)飛同一架次航班的飛機(jī)上。

5）為確?？爝f服務(wù)的時(shí)效性，要求客戶(hù)點(diǎn)的貨物從被提取、進(jìn)入集貨過(guò)程開(kāi)始，直至飛機(jī)起飛，不能超過(guò)一定的時(shí)間長(zhǎng)度。

6）地面集貨成本主要考慮卡車(chē)行駛成本與固定成本，在考慮集貨環(huán)節(jié)的同時(shí)，需兼顧客戶(hù)點(diǎn)貨物落地后的配送成本。

7）問(wèn)題的目標(biāo)函數(shù)擬定為運(yùn)輸總成本的最小化。

圖1給出航空快遞地面集貨運(yùn)力與航空運(yùn)力協(xié)同調(diào)度問(wèn)題的一個(gè)示例。運(yùn)力調(diào)度方案包含兩部分：卡車(chē)的地面集貨路徑，航空運(yùn)力的類(lèi)型選擇。集貨卡車(chē)從機(jī)場(chǎng)出發(fā)，前往客戶(hù)點(diǎn)取貨，再依據(jù)快遞服務(wù)時(shí)效要求選擇合適的航班，整個(gè)過(guò)程需滿(mǎn)足時(shí)間窗、載運(yùn)能力等約束。例如：集貨卡車(chē)可從機(jī)場(chǎng)前往客戶(hù)點(diǎn)3，然后依次前往客戶(hù)點(diǎn)6、1、5，最后返回機(jī)場(chǎng)，該卡車(chē)上的貨物均被裝載至由全貨機(jī)執(zhí)飛的固定航班。

圖1 航空快遞的地面集貨運(yùn)力與航空運(yùn)力調(diào)度問(wèn)題示例Fig.1 Example of pickup-truck and aircraft scheduling problem in air express

1.2 模型構(gòu)建

在運(yùn)輸網(wǎng)絡(luò)G=（V，A）上，存在有節(jié)點(diǎn)集合V={0，1，2，…，n}，其中 0 表示起飛機(jī)場(chǎng)，V/{0}為客戶(hù)點(diǎn)，dij表示網(wǎng)絡(luò)節(jié)點(diǎn)之間的距離。qi為客戶(hù)點(diǎn)i的待運(yùn)貨物量，gi表示為了將客戶(hù)點(diǎn)i的貨物配送至收貨人所需耗用的成本（該成本發(fā)生在飛機(jī)降落后的地面配送作業(yè)過(guò)程）；[ei，li]為客戶(hù)點(diǎn)時(shí)間窗，其中 ei和 li分別為客戶(hù)點(diǎn)允許開(kāi)始集貨作業(yè)的最早和最晚時(shí)間；si表示集貨卡車(chē)在客戶(hù)點(diǎn)i的服務(wù)停留時(shí)間。K表示m種車(chē)型的集貨卡車(chē)集合，Qk表示集貨卡車(chē)k的額定載重量，αk表示集貨卡車(chē)k的實(shí)載率。ck表示集貨卡車(chē)k的行駛成本，fck表示集貨卡車(chē)固定成本，vk表示集貨卡車(chē)k的行駛速度。空運(yùn)運(yùn)力（即飛機(jī)）集合H={1，…，g，…，h}，其中 H={1，…，g}表示執(zhí)飛固定航班的全貨機(jī)，T表示固定航班的飛機(jī)起飛時(shí)刻；H{1，…，g}表示備選航班運(yùn)力；Ch表示空運(yùn)運(yùn)力的載貨量，βh表示全貨機(jī)起飛要求的最低載貨率，ach表示空運(yùn)運(yùn)力的變動(dòng)成本；dh表示空運(yùn)的運(yùn)距。T0表示換裝作業(yè)預(yù)留時(shí)間。L表示客戶(hù)點(diǎn)的貨物從被提取、進(jìn)入集貨過(guò)程開(kāi)始，直至飛機(jī)起飛的允許最長(zhǎng)時(shí)間。

設(shè)定：xijk，yk，uh，wih∈{0，1}為決策變量。對(duì)于 xijk，若集貨卡車(chē) k 經(jīng)過(guò)?。╥，j），取 1，否則取 0；對(duì)于 yk，當(dāng)使用集貨卡車(chē)k時(shí)，取1，否則取0；對(duì)于uh，當(dāng)機(jī)場(chǎng)使用備用航班運(yùn)力 h（h>g）時(shí)，取 1，否則取 0；對(duì)于 wih，若第i個(gè)客戶(hù)點(diǎn)的貨物裝載到第h架飛機(jī)上，取1，否則取0。此外，dtk表示集貨卡車(chē)k的發(fā)車(chē)時(shí)間，dtk≥0；atki表示集貨卡車(chē)k到達(dá)點(diǎn)i的時(shí)間，atki≥0；wtki表示集貨卡車(chē)k在點(diǎn)i的等待時(shí)間，wtki≥0；th表示空運(yùn)運(yùn)力 h 的起飛時(shí)刻（當(dāng) h∈{1，…，g}時(shí)，th=T）；常量 τ為集貨卡車(chē)等待時(shí)間的懲罰成本系數(shù)；M為足夠大的正數(shù)。

航空快遞的地面集貨運(yùn)力與航空運(yùn)力協(xié)同調(diào)度問(wèn)題混合整數(shù)規(guī)劃模型的目標(biāo)函數(shù)包含5部分：集貨卡車(chē)的行駛成本和固定成本、空運(yùn)成本、集貨過(guò)程的時(shí)間懲罰成本、配送環(huán)節(jié)需耗用的成本，表示為

混合整數(shù)規(guī)劃模型的約束條件包括：

1）與集貨環(huán)節(jié)相關(guān)的約束條件

約束（2）表示當(dāng)使用集貨卡車(chē)k時(shí)，集貨卡車(chē)k離開(kāi)機(jī)場(chǎng)的次數(shù)為1，結(jié)合約束（3）表示集貨卡車(chē)k進(jìn)出機(jī)場(chǎng)各1次；約束（3）表示集貨卡車(chē)k進(jìn)出某一節(jié)點(diǎn)的次數(shù)相等；約束（4）表示集貨卡車(chē)k進(jìn)出某一節(jié)點(diǎn)的次數(shù)最多為1次；約束（5）表示一個(gè)客戶(hù)點(diǎn)恰好被一輛集貨卡車(chē)服務(wù)1次；約束（6）確保每輛集貨卡車(chē)服務(wù)的客戶(hù)點(diǎn)的貨物總量不超過(guò)該集貨卡車(chē)的允許最大載貨量；約束（7）和約束（8）規(guī)定集貨卡車(chē)在客戶(hù)點(diǎn)和機(jī)場(chǎng)到達(dá)時(shí)間之間的關(guān)系；約束（9）和約束（10）刻畫(huà)了集貨卡車(chē)在兩個(gè)客戶(hù)點(diǎn)到達(dá)時(shí)間之間的關(guān)系；約束（7）～約束（10）描述集貨卡車(chē)到達(dá)各點(diǎn)的時(shí)間關(guān)系；約束（11）和約束（12）為客戶(hù)點(diǎn)的時(shí)間窗約束。

2）與空運(yùn)環(huán)節(jié)相關(guān)的約束條件

約束（13）表示對(duì)每個(gè)客戶(hù)點(diǎn)的貨物而言，都一定能趕上某一航班運(yùn)力；約束（14）確保了當(dāng)?shù)趇個(gè)客戶(hù)點(diǎn)的貨物被安排在航班運(yùn)力h上時(shí)，該航班運(yùn)力一定會(huì)被使用；約束（15）確保了一個(gè)被服務(wù)客戶(hù)點(diǎn)的貨物只能安排在一趟航班運(yùn)力上，也即客戶(hù)點(diǎn)貨物不可拆分；約束（16）和約束（17）要求同一輛集貨卡車(chē)上的貨物必須裝載到同一架飛機(jī)上；約束（18）表示固定航班運(yùn)力一定會(huì)被使用；約束（19）確保固定航班上的貨物量滿(mǎn)足全貨機(jī)起飛的最低載貨率要求；約束（20）要求每趟航班上的貨物量不超過(guò)其最大允許載貨量；約束（21）確保客戶(hù)點(diǎn)的貨物從被提取、進(jìn)入集貨過(guò)程開(kāi)始，直至飛機(jī)起飛，不能超過(guò)一定的時(shí)間長(zhǎng)度L；約束（22）確保服務(wù)客戶(hù)點(diǎn)的集貨卡車(chē)在航空運(yùn)力起飛前返回起飛機(jī)場(chǎng)；約束（23）表示使用的備選航班運(yùn)力在固定航班貨機(jī)起飛后一段時(shí)間才起飛，θ為常數(shù)；約束（24）表示固定航班運(yùn)力的起飛時(shí)間為既定時(shí)刻。

3）其他輔助約束

2 求解算法

既有研究通常使用精確算法或啟發(fā)式算法對(duì)車(chē)輛調(diào)度問(wèn)題及其變形形式進(jìn)行求解。精確算法主要包括分支定界法、列生成法、拉格朗日松弛法、D-W分解法、Benders分解法等，精確算法能在足夠的求解時(shí)間前提下獲得中小規(guī)模算例的最優(yōu)解。常用的啟發(fā)式算法包括節(jié)約算法、鄰域搜索算法、禁忌搜索算法、模擬退火算法、蟻群算法等。

同時(shí)采用精確算法與啟發(fā)式算法對(duì)所構(gòu)建的混合整數(shù)規(guī)劃模型進(jìn)行求解。精確算法選用Benders分解法。啟發(fā)式算法的求解過(guò)程分為兩個(gè)階段：使用貪婪算法構(gòu)造初始解，使用鄰域搜索算法對(duì)初始解進(jìn)行優(yōu)化。

2.1 Benders分解法

在構(gòu)建的混合整數(shù)規(guī)劃模型中，0-1變量包括xijk、yk、urh、wih，連續(xù)變量包括 dtk、atki、wtki、th，將 0-1 變量以及只含0-1變量的約束條件作為主問(wèn)題，包含連續(xù)變量的約束條件作為子問(wèn)題。

2.1.1 主問(wèn)題與子問(wèn)題

主問(wèn)題目標(biāo)函數(shù)中包含整數(shù)變量 xijk、yk、urh、wih。首先求解主問(wèn)題，獲得0-1變量的初始解及目標(biāo)函數(shù)值作為下界LB。

主問(wèn)題目標(biāo)函數(shù)為

約束條件包括式（2）～式（6）、式（13）～式（20）、式（25）。

子問(wèn)題目標(biāo)函數(shù)為

轉(zhuǎn)化為標(biāo)準(zhǔn)形式的約束條件包括

2.1.2 建立子問(wèn)題的對(duì)偶問(wèn)題

定義子問(wèn)題約束對(duì)應(yīng)的對(duì)偶變量分別為

將求解主問(wèn)題獲得的作為初始值帶入到子問(wèn)題的對(duì)偶問(wèn)題中，求解該對(duì)偶問(wèn)題。若子問(wèn)題有可行解，將獲得的目標(biāo)函數(shù)值與當(dāng)前UB值作比較，取較小的值作為上界，更新UB，然后比較上界和下界的值，若LB=UB，則算法停止。子問(wèn)題的對(duì)偶問(wèn)題如下：

子問(wèn)題的對(duì)偶問(wèn)題的目標(biāo)函數(shù)為

約束條件包括

2.1.3 重建主問(wèn)題

將生成的割約束加入到主問(wèn)題中，引入自由變量temp，重建Benders主問(wèn)題，原問(wèn)題的模型可寫(xiě)為

約束條件包括式（2）～式（6）、式（13）～式（20）、式（25）

約束（31）和約束（32）為求解對(duì)偶問(wèn)題后所添加的割約束，當(dāng)求解子問(wèn)題的對(duì)偶問(wèn)題有最優(yōu)解時(shí)，則向重建主問(wèn)題中添加最優(yōu)割約束（31）；當(dāng)求解子問(wèn)題的對(duì)偶問(wèn)題無(wú)界時(shí)，則向重建主問(wèn)題中添加可行割約束（32）。

2.2 兩階段啟發(fā)式算法

2.2.1 基于貪婪算法的初始解構(gòu)造

貪婪算法的主要特點(diǎn)是：在求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇，而不管這樣選擇出的結(jié)果是否全局最優(yōu)。本研究在構(gòu)造初始解時(shí)，先基于貪婪策略構(gòu)建地面集貨路徑，再確定航空運(yùn)力的運(yùn)用方案。

1）地面集貨過(guò)程

在構(gòu)造初始解的集貨路徑時(shí)，將每一個(gè)客戶(hù)點(diǎn)都視為一個(gè)候選元素。對(duì)每一候選元素，賦予一個(gè)貪婪函數(shù)值，該貪婪函數(shù)的形式為

貪婪函數(shù)式的分子組成：前兩部分分別為集貨過(guò)程的行駛成本與等待時(shí)間懲罰成本，第三部分為配送環(huán)節(jié)所耗用的成本；分母為客戶(hù)點(diǎn)的待運(yùn)貨物量。

集貨卡車(chē)從機(jī)場(chǎng)出發(fā)，將每一個(gè)客戶(hù)點(diǎn)都視為候選元素，比較其貪婪函數(shù)值。在每一次選擇中，盡量選擇貪婪函數(shù)值最小的客戶(hù)點(diǎn)作為下一個(gè)服務(wù)點(diǎn)，但同時(shí)需考慮到以下限制條件：每輛卡車(chē)的載貨量不能超過(guò)其額定載貨量，兼顧客戶(hù)點(diǎn)的服務(wù)時(shí)間窗要求，且每個(gè)客戶(hù)點(diǎn)恰好被服務(wù)1次。若在某次貪婪選擇過(guò)程中有違反上述某一或某幾條約束條件的情況，則將該點(diǎn)在本次構(gòu)造中刪除，選擇另一個(gè)函數(shù)值小的客戶(hù)點(diǎn)，直到?jīng)]有符合條件的客戶(hù)點(diǎn)可被服務(wù)為止。反復(fù)運(yùn)行該操作，可獲得可行解。

2）空運(yùn)過(guò)程

考慮到同一輛集貨卡車(chē)上的貨物須裝載在同一架次的飛機(jī)上，令cl為集貨部分構(gòu)造的初始路徑，將每條路徑中貨物所選擇的航班視為候選元素（本模型中候選元素有2個(gè)，即固定航班與備用航班）。對(duì)每個(gè)候選元素，賦予一個(gè)貪婪函數(shù)值，貪婪函數(shù)的形式為

貪婪函數(shù)值即為每條路徑的空運(yùn)成本。比較貪婪函數(shù)值，在每次選擇中，盡量選擇函數(shù)值小的航班，但同時(shí)需考慮以下約束條件：固定航班貨機(jī)起飛前完成的集貨量不少于固定航班貨機(jī)的最低載貨量，備選航班運(yùn)力無(wú)最低載貨要求，但每趟備選航班運(yùn)力上的貨物量不超過(guò)其最大載貨量；客戶(hù)點(diǎn)的貨物從被提取、進(jìn)入集貨過(guò)程開(kāi)始，直至飛機(jī)起飛，不能超過(guò)一定時(shí)間長(zhǎng)度；所用集貨卡車(chē)在航空運(yùn)力起飛前返回起飛機(jī)場(chǎng)；備選航班運(yùn)力在固定航班貨機(jī)起飛后才能起飛。

2.2.2 鄰域搜索

在借助鄰域搜索進(jìn)行初始解優(yōu)化時(shí)，首先針對(duì)地面集貨部分，以客戶(hù)點(diǎn)為移動(dòng)或交換操作對(duì)象。路徑內(nèi)的鄰域搜索算子主要有2-opt與Or-opt兩類(lèi)，但2-opt算子不能保持路徑上各點(diǎn)之間的時(shí)間連續(xù)性，不適合模型所包含的時(shí)間窗約束。綜合比選，最終采用的鄰域搜索算子包括：Or-opt算子、2-opt*算子、交換算子、1-0改進(jìn)算子、2-1改進(jìn)算子。

1）Or-opt算子 從既有路徑方案中隨機(jī)選取一條路徑，針對(duì)該路徑，隨機(jī)選擇由l個(gè)連續(xù)客戶(hù)點(diǎn)組成的片段在該路徑中進(jìn)行重定位。若對(duì)某條路徑進(jìn)行其內(nèi)部多個(gè)連續(xù)點(diǎn)的重定位，往往會(huì)出現(xiàn)違背時(shí)間順序的問(wèn)題，這里采用Or-opt算子，令l=1。若重定位操作后的路徑滿(mǎn)足模型的約束條件，則保留該次操作的結(jié)果；否則，再次隨機(jī)選取一條路徑進(jìn)行重定位操作。

2）2-opt*算子 從既有路徑方案中隨機(jī)選取2條路徑，針對(duì)這一對(duì)路徑，隨機(jī)選擇分別位于2條路徑內(nèi)的2條邊，斷開(kāi)這2條邊后，分別連接起第1條路徑的前半部分和第2條路徑的后半部分、第2條路徑的前半部分和第1條路徑的后半部分。若操作后2條路徑都滿(mǎn)足約束條件，則保留該交叉操作結(jié)果；否則，再次隨機(jī)選取2條路徑進(jìn)行交叉操作。

3）交換算子 從既有路徑方案中隨機(jī)選取2條路徑，針對(duì)這一對(duì)路徑，隨機(jī)選擇分別位于2條路徑內(nèi)的2個(gè)客戶(hù)點(diǎn)進(jìn)行交換操作。若交換操作后2條路徑都滿(mǎn)足約束條件，則保留該交換操作的結(jié)果；否則，再次隨機(jī)選取2條路徑進(jìn)行交換操作。

4）1-0改進(jìn)算子 從既有路徑方案中隨機(jī)選取2條路徑，針對(duì)這一對(duì)路徑，隨機(jī)選擇一條中的1個(gè)客戶(hù)點(diǎn)，插入到另一條路徑中。若操作后2條路徑都滿(mǎn)足約束條件，則保留操作結(jié)果；若操作后其中一條路徑中已無(wú)客戶(hù)點(diǎn)，則刪除該路徑；若操作結(jié)果不滿(mǎn)足約束條件，則再次隨機(jī)選取2條路徑重新進(jìn)行交換操作。

5）2-1改進(jìn)算子 從既有路徑方案中隨機(jī)選取2條路徑，針對(duì)這一對(duì)路徑，隨機(jī)選擇一條中的1個(gè)客戶(hù)點(diǎn)，與另一條路徑中的2個(gè)客戶(hù)點(diǎn)進(jìn)行交換操作。若操作后2條路徑都滿(mǎn)足約束條件，則保留操作結(jié)果；否則，再次隨機(jī)選取2條路徑進(jìn)行交換操作。

此外，若針對(duì)空運(yùn)過(guò)程進(jìn)行鄰域搜索，則需考慮以下因素：考慮到同一輛集貨卡車(chē)上的貨物必須裝載在同一架次的飛機(jī)上，路徑間的局部搜索可能會(huì)導(dǎo)致解不可行；由于只需確定空運(yùn)運(yùn)力類(lèi)型及部分運(yùn)力的起飛時(shí)刻，不必考慮路徑內(nèi)的局部搜索。綜合權(quán)衡，不再針對(duì)空運(yùn)運(yùn)力排定進(jìn)行鄰域搜索操作。

3 算例求解

測(cè)試算例以主營(yíng)航空快遞業(yè)務(wù)的某物流企業(yè)為參照，基于該企業(yè)布局于北京、上海和廣州的營(yíng)業(yè)網(wǎng)點(diǎn)坐標(biāo)，借助適當(dāng)方法來(lái)補(bǔ)充某些數(shù)據(jù)。為設(shè)計(jì)出不同規(guī)模的算例，從該企業(yè)布局在各個(gè)城市的營(yíng)業(yè)網(wǎng)點(diǎn)中隨機(jī)選擇m個(gè)點(diǎn)作為客戶(hù)點(diǎn)。構(gòu)造20個(gè)規(guī)模較小的算例和5個(gè)規(guī)模較大的算例。以“VRPTC-m-n”為算例編號(hào)，m表示客戶(hù)點(diǎn)數(shù)，n表示相同客戶(hù)點(diǎn)數(shù)下的算例序號(hào)。

3.1 主要參數(shù)取值

進(jìn)行算例求解運(yùn)算時(shí)，集貨卡車(chē)基本參數(shù)如表1所示。參考現(xiàn)階段中國(guó)航空快遞業(yè)所用主要空運(yùn)運(yùn)力狀況，擬定全貨機(jī)的起飛時(shí)刻為12∶00，其最大載貨量為14 t，其起飛要求的最低裝載率為50%，空運(yùn)變動(dòng)成本為1.8元/（t·km）；擬定航空快遞所能選用的客機(jī)運(yùn)力起飛時(shí)刻要比全貨機(jī)的起飛時(shí)刻至少晚2 h，客機(jī)腹艙的最大允許載貨量為3 t，空運(yùn)變動(dòng)成本為1.5元/（t·km）。此外，將快件在地面車(chē)輛和空運(yùn)運(yùn)力之間的換裝作業(yè)時(shí)間限制在2 h，將該類(lèi)航空快遞服務(wù)的承諾服務(wù)時(shí)效設(shè)定為8 h。

表1 算例運(yùn)算中所選用集貨卡車(chē)相關(guān)參數(shù)取值Tab.1 Parameter values for pickup-trucks in computational experiments

3.2 運(yùn)算結(jié)果

基于Benders分解法與啟發(fā)式算法涉及的各主要參數(shù)的擬定取值，對(duì)不同規(guī)模算例進(jìn)行求解運(yùn)算，記錄啟發(fā)式算法與Benders分解法求解小規(guī)模算例的結(jié)果（如表2所示）及啟發(fā)式算法求解大規(guī)模算例的結(jié)果（如表3所示）。表2包括10列內(nèi)容：第1列為算例編號(hào)，第2列與第3列分別為基于貪婪算法所構(gòu)造的初始解目標(biāo)函數(shù)值（ObjG）以及鄰域搜索后得到的滿(mǎn)意解目標(biāo)函數(shù)值（ObjG_LS），第4列為ObjG_LS相對(duì)于ObjG的優(yōu)化率（Gap1），第5列為啟發(fā)式算法的運(yùn)算時(shí)間（TG_LS），第6列與第7列分別為最優(yōu)解的集貨成本（ObjB-1）與空運(yùn)成本（ObjB-2），第 8列與第 9列為最優(yōu)解的目標(biāo)函數(shù)值（ObjB）及Benders分解法的運(yùn)算時(shí)間（TB），第10列為啟發(fā)式算法滿(mǎn)意解與最優(yōu)解之間的偏差（Gap2）。表3包括7列內(nèi)容：第1列為算例編號(hào)，第2列為基于貪婪算法所構(gòu)造的初始解目標(biāo)函數(shù)值（ObjG），第3列與第4列分別為鄰域搜索后得到滿(mǎn)意解的集貨成本（ObjG_LS-1）與空運(yùn)成本（ObjG_LS-2），第 5 列為滿(mǎn)意解目標(biāo)函數(shù)值（ObjG_LS），第6列為ObjG_LS相對(duì)于ObjG的優(yōu)化率（Gap1），第7列為啟發(fā)式算法的運(yùn)算時(shí)間（TG_LS）。

表2 小規(guī)模算例的精確算法與啟發(fā)式算法求解結(jié)果Tab.2 Exact and heuristic solutions for small-scale instances

表3 大規(guī)模算例的啟發(fā)式算法求解結(jié)果Tab.3 Heuristic solutions for large-scale instances

針對(duì)不同規(guī)模算例的求解運(yùn)算結(jié)果顯示：

1）Benders分解法與啟發(fā)式算法均能對(duì)模型進(jìn)行求解，表明所建模型和所用算法的準(zhǔn)確性和有效性。從求解結(jié)果的目標(biāo)函數(shù)值看，兩階段啟發(fā)式算法可獲得高質(zhì)量滿(mǎn)意解。在19個(gè)小規(guī)模算例中，啟發(fā)式算法能獲得9個(gè)算例的最優(yōu)解。啟發(fā)式算法所得滿(mǎn)意解相對(duì)理論最優(yōu)解的誤差（即Gap2）都在0.5%以?xún)?nèi)，Gap2平均值為0.1%，而在0.2%以?xún)?nèi)的有14個(gè)算例。

2）對(duì)于不同規(guī)模的算例，啟發(fā)式算法都能在較短時(shí)間內(nèi)給出較高質(zhì)量的滿(mǎn)意解。隨著算例規(guī)模增大，Benders分解法的求解時(shí)間明顯加長(zhǎng)，當(dāng)客戶(hù)點(diǎn)總數(shù)達(dá)到15時(shí)，求解時(shí)間已超過(guò)48 h?？梢?jiàn)，Benders分解法的求解能力有限。對(duì)于表2中的20個(gè)小規(guī)模算例，啟發(fā)式算法的平均運(yùn)算時(shí)間為3.3 s，運(yùn)算時(shí)間小于10秒的算例有19個(gè)，占95.0%。對(duì)于表3中的5個(gè)大規(guī)模算例，啟發(fā)式算法的平均計(jì)算時(shí)間為15.0 s。

3）兩階段啟發(fā)式算法能快速構(gòu)造初始解，在此基礎(chǔ)上，鄰域搜索過(guò)程能有效實(shí)現(xiàn)對(duì)初始解的優(yōu)化。啟發(fā)式算法對(duì)小規(guī)模算例的優(yōu)化率平均水平為0.3%，對(duì)大規(guī)模算例的優(yōu)化率平均水平為0.5%，在一定程度上表明本研究所設(shè)計(jì)的啟發(fā)式算法的穩(wěn)定性和高效性。

4）從所有算例的運(yùn)算結(jié)果看，地面集貨成本占總成本的平均比例為4.4%，空運(yùn)成本占總成本的平均比例為95.6%。在航空快遞的地面集貨運(yùn)力與航空運(yùn)力協(xié)同運(yùn)用中，空運(yùn)成本占據(jù)更大的成本支出比例，快遞企業(yè)應(yīng)優(yōu)先保證空運(yùn)運(yùn)力的有效運(yùn)用。

總體上看，所建立的航空快遞地面集貨運(yùn)力與航空運(yùn)力協(xié)同調(diào)度問(wèn)題的混合整數(shù)規(guī)劃模型能夠準(zhǔn)確刻畫(huà)出地面集貨運(yùn)輸與航空運(yùn)輸?shù)臒o(wú)縫對(duì)接過(guò)程，該模型主要運(yùn)用了服務(wù)時(shí)效約束與運(yùn)力匹配約束來(lái)銜接陸運(yùn)、空運(yùn)網(wǎng)絡(luò)上不同類(lèi)型的運(yùn)力。所提求解算法能給出小規(guī)模算例的精確解與大規(guī)模算例的滿(mǎn)意解。不同規(guī)模算例的求解結(jié)果能給出多車(chē)型地面車(chē)輛集貨路徑方案和航空運(yùn)力調(diào)度方案，這實(shí)際上就是航空快遞陸空網(wǎng)絡(luò)模式具體解決方案重要組成部分，可為航空快遞企業(yè)提供重要的運(yùn)力使用策略，也提供了用于分析陸空聯(lián)運(yùn)協(xié)調(diào)性的決策參考。

4 結(jié)語(yǔ)

面向航空快遞領(lǐng)域中的地面車(chē)輛集貨環(huán)節(jié)與航空運(yùn)輸環(huán)節(jié)的銜接問(wèn)題，利用服務(wù)時(shí)效約束與運(yùn)力匹配約束實(shí)現(xiàn)不同運(yùn)輸網(wǎng)絡(luò)上不同類(lèi)型運(yùn)力間的無(wú)縫對(duì)接，構(gòu)建航空快遞地面集貨運(yùn)力與航空運(yùn)力協(xié)同調(diào)度問(wèn)題的混合整數(shù)規(guī)劃模型，采用Benders分解法求解規(guī)模較小的算例；對(duì)規(guī)模較大的算例，采用兩階段啟發(fā)式算法予以求解：用貪婪算法構(gòu)造初始解，使用鄰域搜索算法來(lái)優(yōu)化初始解。以主營(yíng)航空快遞業(yè)務(wù)的某物流企業(yè)為參照設(shè)計(jì)各種規(guī)模的測(cè)試算例，運(yùn)算結(jié)果顯示，所用精確算法和啟發(fā)式算法均能對(duì)該混合整數(shù)規(guī)劃模型進(jìn)行求解，表明所建模型和所用算法的準(zhǔn)確性和有效性。此外，在航空快遞的地面集貨運(yùn)力與航空運(yùn)力協(xié)同調(diào)度中，快遞企業(yè)應(yīng)優(yōu)先運(yùn)用好空運(yùn)運(yùn)力。本研究拓展了不同類(lèi)型運(yùn)力匹配和運(yùn)輸時(shí)效銜接方式，這可豐富車(chē)輛調(diào)度問(wèn)題的建模手段，也提供了用于分析陸空聯(lián)運(yùn)協(xié)調(diào)性的決策參考；而算例運(yùn)算試驗(yàn)可為快遞企業(yè)提供運(yùn)力使用策略。

參考文獻(xiàn)：

[1]LAPORTE G.Fifty years of vehicle routing[J].Transportation Science,2009,43(4)：408-416.

[2]BALDACCI R,TOTH P,VIGO D.Recent advances in vehicle routing exact algorithms[J].4OR：A Quarterly Journal of Operations Research,2007,5(4)：269-298.

[3]HANE C A,BARNHART C,JOHNSON E L,et al.The fleet assignment problem：Solving a large-scale integer program[J].Mathematical Programming,1995,70(2)：211-232.

[4]LEVIN A.Scheduling and fleet routing models for transportation systems[J].Transportation Science,1971,5(3)：232-255.

[5]BURKE E K,CAUSMAECKER P D,MAERE G D,et al.A multiobjective approach for robust airline scheduling[J].Computers&Operations Research,2010,37(5)：822-832.

[6]孫 宏.航空公司飛機(jī)排班問(wèn)題：模型及算法研究[D].成都：西南交通大學(xué),2003.

[7]付維方,張偉剛,孫春林.航班排班中航班串生成與篩選問(wèn)題的算法與實(shí)現(xiàn)[J].中國(guó)民航大學(xué)學(xué)報(bào),2006,24(5)：4-6.

[8]PERBOLI G,TADEI R,VIGO D.The two-echelon capacitated vehicle routing problem：Models and math-based heuristics[J].Transportation Science,2009,45(3)：364-380.

[9]PERBOLI G,TADEI R,TADEI R.New families of valid inequalities for the two-echelon vehicle routing problem[J].Electronic Notes in Discrete Mathematics,2010,36：639-646.

[10]JEPSENM,SPOORENDONKS,ROPKE S.A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem[J].Transportation Science,2013,47(1)：23-37.

[11]CRAINIC T G,PERBOLI G,MANCINI S,et al.Two-echelon vehicle routingproblem：Asatellitelocationanalysis[J].Procedia-Social and Behavioral Sciences,2010,2(3)：5944-5955.

[12]CRAINIC T G,MANCINI S,PERBOLI G,et al.Impact of generalized travel costs on satellite location in the two-echelon vehicle routing problem[J].Procedia-SocialandBehavioralSciences,2012,39：195-204.

[13]BALDACCI R,CALVO R W.An exact algorithm for the two-echelon capacitated vehicle routing problem[J].Operations Research,2013,61(2)：298-314.

[14]SOYSAL M,BLOEMHOF J M,BEKTAS T.The time-dependent twoechelon capacitated vehicle routing problem with environmental considerations[J].International Journal of Production Economics,2015,164：366-378.

[15]LI HONGQI,ZHANG LU,LV TAN,et al.The two-echelon time-constrained vehicle routing problem in linehaul-delivery systems[J].Transportation Research Part B,2016,94：169-188.

[16]HALL R W,LO S C.Truck scheduling for ground to air connectivity：Final report[J].General Information,2002,7(6)：331-338.