翁克瑞，諸克軍，劉 耕

（中國地質(zhì)大學(xué) 經(jīng)濟(jì)管理學(xué)院，武漢 430074）

協(xié)同運輸是指將多個企業(yè)的運輸任務(wù)合并于少數(shù)路段集中運輸后，利用規(guī)模經(jīng)濟(jì)節(jié)約運輸成本。在當(dāng)前我國物流企業(yè)數(shù)量多、規(guī)模小、運輸滿載率低以及空載率高的背景下，協(xié)同運輸是整合物流資源、提高運輸效率、降低運輸成本的有效手段[1]。如圖1的運輸任務(wù)選擇圖2的協(xié)同運輸方案，合并于少量路段而節(jié)約成本。一個從節(jié)點i到j(luò)的運輸任務(wù)稱之為O-D流i→j；若大量的O-D流整合于路段（k，m），且（k，m）獲取規(guī)模經(jīng)濟(jì)、產(chǎn)生運輸成本折扣，則稱（k，m）為中樞路段，如圖2的路段（B，E）。協(xié)同運輸?shù)闹饕獌?yōu)勢在于中樞路段大規(guī)模運輸帶來的整合效益，這也暗示了中樞路段必須滿足規(guī)模條件：即中樞路段上匯集的流量必須達(dá)到規(guī)定的規(guī)模數(shù)量。

圖1 運輸任務(wù)Ⅰ

圖2 協(xié)同運輸路線

目前，關(guān)于協(xié)同運輸?shù)腛-D流路線優(yōu)化研究主要集中于軸輻式網(wǎng)絡(luò)設(shè)計問題（Hub-and-Spoke Network Design Problem，HASNDP），該問題的一般定義為：要求所有的O-D流都經(jīng)過1個或2個樞紐站，樞紐站之間的所有路段均具備運輸成本折扣的中樞路段，如何選擇樞紐站、安排O-D流的集散路線使總成本最小。HASNDP最初由O'Kelly提出，O'Kelly建立了一個二次規(guī)劃模型，并給出了兩類啟發(fā)式算法。近年來，許多研究仍在改進(jìn)模型與求解方案[2-5]；同時，一些學(xué)者研究HASNDP擴(kuò)展問題的模型及算法[6-10]。然而，HASNDP的研究存在一個嚴(yán)重的假設(shè)缺陷：只要O-D流全部經(jīng)過樞紐站，則樞紐站間的所有路段都可以獲得規(guī)模經(jīng)濟(jì)和成本折扣。這一假設(shè)并不符合某些實踐，許多學(xué)者研究[4，11-14]發(fā)現(xiàn)：樞紐站之間的某些路段可能并未增加流量，不具備規(guī)模條件。如圖3所示，HASNDP將選擇G、H、I為樞紐站，并假定G、H、I之間的所有路段都存在運輸成本折扣，形成的O-D流路線如圖4所示。實際上，圖4中路段（G，H）并未增加流量，不具備規(guī)模優(yōu)勢，可見現(xiàn)有研究受假設(shè)條件的限制，忽略了協(xié)同運輸?shù)囊?guī)模條件。

圖3 運輸任務(wù)Ⅱ

圖4 軸輻式網(wǎng)絡(luò)

因此，本文研究規(guī)模條件下的協(xié)同運輸集散路線優(yōu)化問題（Collaborative Transportation Route Optimization with Lower Bound Flows，CTROLBF）：給定的中樞路段集合，要求中樞路段上匯集的流量必須達(dá)到規(guī)定的上限，O-D流在滿足繞道距離約束下如何選擇直通運輸、單點中轉(zhuǎn)或兩點中轉(zhuǎn)的路線（稱集散路線），使得總成本最?。砍?guī)模條件外，協(xié)同運輸?shù)牧硪恢匾毕菔窃黾拥睦@道距離，如對圖1的運輸任務(wù)A→D來說，圖2的路線A→B→E→D距離顯然大于A→D的直通距離。本文希望繞道運輸?shù)木嚯x在某個可以承受的范圍以內(nèi)，于是要求O-D流的路線滿足繞道距離約束。

1 模 型

給定的連通網(wǎng)絡(luò)G（N，A），A為所有邊集合，N=｛1，2，…，n｝為所有節(jié)點的集合。對任意i≠j，令hij表示節(jié)點i到節(jié)點j的O-D流，Dij為流i→j的最大運輸距離，dkm為路段（k，m）上的單位流量成本，=dik+dkm+dmj為路線i→k→m→j的單位流量成本，Hub Arc為中樞路段集合，Mkm為中樞路段（k，m）要求的最低流量。令決策變量表示流i→j選擇路線i→k→m→j的流量。在以上定義下，CTROLBF的線性規(guī)劃模型P1如下：

≥0，?i，j，k，m∈N，k≠j；m≠i目標(biāo)函數(shù)式（1）表示總運輸費用最?。患s束式（2）表示所有的運輸任務(wù)都被滿足繞道距離約束的路線完成；式（3）表示中樞路段（k，m）上匯集的流量（包括選擇路線i→k→m→j，k→m→i→j，i→j→k→m的O-D流量）達(dá)到規(guī)模條件。模型中，對路線i→k→m→j，要求k≠j與m≠i是為了避免迂回運輸，如路線i→j→i→j或i→j→k→j是不允許的；表示流i→j在滿足繞道距離約束的路線i→k→m→j上的流量。

2 求解算法

然而，P1是一個大型、復(fù)雜的線性規(guī)劃模型，具備約n4個變量、2n2個約束式。即使只有10個節(jié)點，問題的決策變量超過1萬個；若有100個節(jié)點，則決策變量超過1億個。為此，對于大規(guī)模的CTROLBF，很難在滿足時間內(nèi)獲取最優(yōu)方案。但注意到，模型的約束式數(shù)量不多于2n2個，遠(yuǎn)遠(yuǎn)小于決策變量的個數(shù)。根據(jù)線性規(guī)劃理論，對于2n2個約束的線性規(guī)劃問題，最多只有2n2個基變量大于0，于是，利用Dantzig-Wolfe分解算法的技術(shù)，逐步增加變量。Dantzig-Wolfe分解算法的基本思想是：先選擇少數(shù)的變量，將原問題分解為容易求解的限制性主問題（RMP）和子問題；求解RMP和子問題，產(chǎn)生其他變量的判別數(shù)，如果判別數(shù)小于0則加入新的變量，反復(fù)迭代直到其他變量的判別數(shù)都不小于0為止。

在CTROLBF的最優(yōu)解中，O-D流i→j會選擇少數(shù)幾條成本最小的出行路徑，所以模型P1中變量只有少數(shù)幾個滿足距離約束的路徑發(fā)生作用。令P表示少數(shù)路徑的集合。則RMP可表示為模型P2：

求解RMP得到了原問題的可行方案，但RMP沒有考慮所有的出行路徑，所以需要判斷其他路徑能否節(jié)約成本。Dantzig-Wolfe分解算法利用列生成的思想，計算出行路徑i→k→m→j的判別數(shù)為

其中，wkm、σij分別為P2中約束式（5）、（6）的對偶變量。如果≤0，則說明選擇路徑i→k→m→j可節(jié)約成本，將路徑i→k→m→j加入P后重新計算RMP。對所有的O-D流i→j，求解以下子問題尋找小于0的判別數(shù)（P3）：

并且不同的O-D流相互獨立，于是可以按照最短路算法求解P3。在滿足距離約束的條件下，計算所有的O-D流i→j以（ckm-wkm）為邊權(quán)重的最短出行成本：

如果＜σij，則說明＜0，將路徑i→k*→m*→j加入P。Dantzig-Wolfe分解算法主程序如下：

算法1CTROLBF的Dantzig-Wolfe算法主程序。

（1）產(chǎn)生初始路徑集合P（由算法2得到）；

（2）求解模型P2，并得到約束式（5）、（6）的對偶變量wkm、σij，以及出行成本Z；

（3）對所有的O-D流i→j，按式（13）計算以（ckm-wkm）為邊權(quán)重的最短出行成本；

（4）對所有的O-D流，如果＜σij，則P=P∪（i→k*→m*→j）；

（5）判斷是否達(dá)到程序終止條件：對所有的O-D流i→j，如果所有的≥σij，則結(jié)束程序，更新出行路徑與出行成本Z；否則，返回（2）。

在算法1中，本文的初始路徑集合P必須滿足：①路段最低流量限制；②可安排所有的O-D流路線；③滿足出行距離約束。滿足以上3個條件才可以保證求解RMP得到可行解，產(chǎn)生過程如算法2。

算法2生成初始路徑集合P。

（1）初始化，令Rkm=Mkm表示剩余未滿足的流量規(guī)模；Tij=hij表示尚未分配的流量，P=?。

（2）對所有的路段（k，m），當(dāng)Rkm＞0時，如果Tij≥0且cik+ckm+cmj≤Dij且i≠m；j≠k，則P=P∪（i→k→m→j），

如果仍然存在Rkm＞0的路段，則說明問題無可行解，退出程序。

（3）對所有O-D流i→j，如果Tij＞0，則P=P∪（i→i→j→j），Tij=0。計算結(jié)束。

算法2中，步驟（2）保證中樞路段匯集的流量超過Mkm，步驟（3）保證所有剩余的O-D流被分配。算法結(jié)束時，已檢查完所有的路段（k，m）與O-D流i→j，說明當(dāng)前的路線集合P已經(jīng)滿足最低流量限制，并安排了所有O-D流的出行路線。

3 計算實驗

本文在VS2008上用C#編寫算法進(jìn)行計算實驗，使用Thinkpad x61筆記本電腦，配置主頻2.1GHz的Core2處理器與3GB內(nèi)存；實驗中，直接調(diào)用Gurobi（著名優(yōu)化軟件）求解模型P2。測試實例來自于OR-Library的AP數(shù)據(jù)包（http：//people.brunel.ac.uk/～mastjjb/），該數(shù)據(jù)包提供了澳大利亞200個城市間的郵包流量、距離等數(shù)據(jù)。在國內(nèi)外文獻(xiàn)中，AP數(shù)據(jù)包是此類問題算法測試的著名平臺，提供了hij、cij等參數(shù)。然而，AP數(shù)據(jù)包沒有Dij、Hub Arc與Mkm的數(shù)據(jù)。本實驗中，令Dij=1.5dij，Hub Arc=｛（k，m）|k≠m并且（k+m）為4的整數(shù)倍｝；如果（k，m）∈Hub Arc，則Mkm=βhij，并且（k，m）可以獲取0.8的成本折扣。這一實驗設(shè)定可以保證中樞路段上的流量至少是原來直通流量的β倍，并且路線距離不超過原來直通距離的50%。另外，本次實驗以AP數(shù)據(jù)包的前15，20，25，30，60個節(jié)點為對象，實驗中分別考慮β取值1.4，1.5，1.6的3種情況。

為了分析本文的算法績效，還運用Gurobi的單純形法求解模型P1，與算法1進(jìn)行比較，如表1所示。實驗顯示，算法1的計算效率明顯優(yōu)于Gurobi，其平均計算時間不到后者的4.63%，且都得到了最優(yōu)解。此外，當(dāng)問題規(guī)模達(dá)到（或超過）100個節(jié)點時（此時模型P1的變量數(shù)量超過1億個），Gurobi算法由于規(guī)模過大而無法求解模型P1（提示“error 10001”），而算法1耗費約70 s時間得到最優(yōu)解。

表1 AP 數(shù)據(jù)包算法實驗結(jié)果

4 我國中樞航線網(wǎng)絡(luò)應(yīng)用實例

航空運輸是協(xié)同運輸?shù)闹匾獞?yīng)用領(lǐng)域，其原理是：通過中轉(zhuǎn)、合并航線運輸，構(gòu)建中樞航線網(wǎng)絡(luò)，提高“中樞航線”的飛機(jī)滿載率，降低單位運輸成本。然而，只有當(dāng)運量達(dá)到一定規(guī)模條件時，中樞航線（航空運輸中的中樞路段）才能體現(xiàn)規(guī)模經(jīng)濟(jì)?；凇吨袊煌觇b》、《從統(tǒng)計看民航》中我國82個城市間客運量（hij）、運費（cij）等數(shù)據(jù)，這一小節(jié)研究帶規(guī)模條件的中國中樞航線網(wǎng)絡(luò)設(shè)計問題。翁克瑞[4]的研究顯示，如果中樞航線滿載率從65%提高到95%，則單位運輸成本可以降低30%。于是，令中樞航線的最低流量，即中樞航線的流量必須超過原來直通流量的1.46倍；并令中樞航線可以獲取0.7的運輸成本折扣。同時為減少繞道飛行距離，要求中轉(zhuǎn)飛行距離不超過直通飛行距離的30%，即Dij=1.3dij。Hub Arc選取翁克瑞[4]的研究結(jié)論：在不同的航空樞紐港數(shù)量下，北京、上海、廣州等城市之間的航線為中樞路段的集合。最后，將相關(guān)數(shù)據(jù)代入算法1的程序，計算結(jié)論如表2所示。表2中，第4列節(jié)約費用=直通運輸成本-目標(biāo)函數(shù)值，其中，直通運輸成本為我國82個主要城市直航網(wǎng)絡(luò)的年運輸費用為[4]

計算結(jié)果顯示，算法1能夠在5 s內(nèi)快速求解這一大規(guī)模實例；考慮規(guī)模條件后，中樞航線網(wǎng)絡(luò)仍然能夠有效地提高我國航空運輸效率，年節(jié)約80億元左右的費用；選擇9個航空樞紐港是更好的選擇；加入烏魯木齊后問題無可行解，說明烏魯木齊由于地理上處于我國版圖邊緣無法在1.3dij的繞道限制內(nèi)吸引非新疆城市的流量，同時，新疆的其他城市流量不足以使與烏魯木齊關(guān)聯(lián)的中樞航線（中樞路段）流量增加30%，因此考慮規(guī)模條件與繞道距離約束后烏魯木齊難以成為國內(nèi)航空中轉(zhuǎn)站（樞紐港）。

表2 規(guī)模條件下中國中樞航線網(wǎng)絡(luò)設(shè)計問題計算結(jié)果

5 結(jié)語

傳統(tǒng)的協(xié)同運輸研究忽略了中樞路段的規(guī)模條件，而適當(dāng)?shù)牧髁恳?guī)模是協(xié)同運輸降低成本的基本條件，為此本文研究規(guī)模條件下的協(xié)同運輸路線優(yōu)化問題。構(gòu)造了CTROLBF的線性規(guī)劃模型和Dantzig-Wolfe分解算法。實驗顯示，算法表現(xiàn)出了非常好的計算績效，能夠快速得到較大規(guī)模實例的最優(yōu)解。最后，也將模型與算法應(yīng)用于我國中樞航線網(wǎng)絡(luò)設(shè)計問題。結(jié)論顯示，算法仍然能夠在很短的時間內(nèi)求解這一大規(guī)模問題，并得到最優(yōu)解；考慮規(guī)模條件后，基于協(xié)同運輸?shù)闹袠泻骄€網(wǎng)絡(luò)能夠為我國航空運輸節(jié)約大量成本。然而，本文只考慮了一種流量規(guī)模和折扣效果。很多時候，就如小節(jié)1某物流公司的報價一樣，流量-運費常常表現(xiàn)為分段線性函數(shù)關(guān)系，不同的流量等級產(chǎn)生不同的折扣效果。于是，流量-運費分段線性函數(shù)下的協(xié)同運輸路線集散優(yōu)化問題將成為下一步的研究內(nèi)容。