李孟良，王喜富，孫全欣,王 德

(1.北京交通大學 交通運輸學院，北京 100044;2.鐵道黨校 鐵路企業(yè)管理教研部，北京 100088)

公鐵聯(lián)運是指貨物運輸過程中采用公路和鐵路兩種運輸方式相結(jié)合，將貨物從供應(yīng)地運送到需求地的運輸組織形式，與傳統(tǒng)單一運輸方式相比，公鐵聯(lián)運具有全程性、通用性、簡便性、代理性和協(xié)同性的特點，可以降低運輸成本、節(jié)約運雜費用和提高運輸服務(wù)質(zhì)量[1]。公鐵聯(lián)運樞紐選址具有多式聯(lián)運樞紐選址的特點，與單運輸方式設(shè)施選址問題相比，公鐵聯(lián)運樞紐選址需要考慮公路與鐵路運輸模式選擇、銜接以及中轉(zhuǎn)費用等差異，由于鐵路運輸自身存在時刻表限制，因此在選址過程中服務(wù)時間也是一個重要考慮因素。選擇公鐵聯(lián)運網(wǎng)絡(luò)中重要城市節(jié)點作為樞紐，承擔貨物裝卸、搬運、中轉(zhuǎn)、倉儲、換裝以及信息服務(wù)等功能，經(jīng)營人將分散在各區(qū)域小批量貨流集中到樞紐站，組成大批貨流后，通過合適的運輸方式和轉(zhuǎn)載工具，將貨物按需分配。建立合理的貨運樞紐不僅能提高整個網(wǎng)絡(luò)服務(wù)效率，降低運輸網(wǎng)絡(luò)總成本，還可以節(jié)能減排，緩解交通壓力，實現(xiàn)對整個運輸系統(tǒng)的有效利用，達到更好地利用現(xiàn)有設(shè)施能力的目的，對交通運輸方式的可持續(xù)發(fā)展具有重要意義。

國外學者對多式聯(lián)運網(wǎng)絡(luò)樞紐選址研究較多，Racunica和Wynter[2]介紹鐵路網(wǎng)絡(luò)樞紐概念，基于增加列車頻率、降低人力成本和提高設(shè)備周轉(zhuǎn)率建立鐵路樞紐選址費用模型，通過減少決策變量，采用啟發(fā)式迭代方法求解。模型局限于解決單一鐵路網(wǎng)絡(luò)樞紐選址問題，只考慮樞紐運營費用。Limbourg和Jourquin[3]研究與本文相似的公鐵聯(lián)運樞紐選址問題，通過優(yōu)化公路樞紐位置及合理分配鐵路貨流降低運輸費用，提出啟發(fā)式方法求解，但缺少考慮樞紐選址固定成本和服務(wù)時間限制。Ishfaq和Sox[4]研究公鐵聯(lián)運物流網(wǎng)絡(luò)樞紐選址和路徑分配問題，模型考慮運輸費用、轉(zhuǎn)運成本、固定選址成本和服務(wù)時間限制，采用拉格朗日松弛和禁忌搜索算法求解模型。王雷等[5]基于Benders分解算法解決無容量限制多分配樞紐選址問題，該算法把選址問題分為樞紐選址和路徑分配兩個子問題進行求解，目標函數(shù)只考慮樞紐設(shè)置成本和網(wǎng)絡(luò)運營成本，側(cè)重介紹Benders分解算法。傅少川等[6]通過對比多分配多樞紐和單分配多樞紐軸輻式物流網(wǎng)絡(luò)建立單一運輸費用模型，得出單分配多樞紐軸輻式網(wǎng)絡(luò)更具有現(xiàn)實意義，采用改進的禁忌搜索智能算法進行求解。崔小燕等[7]針對無容量限制單分配軸輻式物流網(wǎng)絡(luò)，設(shè)計基于運輸費用最小的選址模型，重點介紹蟻群求解算法，沒有考慮樞紐建設(shè)固定成本和運輸時間限制影響，局限于公路運輸方式的選址問題。本文和以上文獻都以選址費用最小為目標函數(shù)，但本文綜合考慮上述文獻缺失的樞紐選址影響因素。

本文主要研究公鐵聯(lián)運網(wǎng)絡(luò)貨運樞紐選址模型及算法設(shè)計，創(chuàng)新點在于：

(1)同時考慮樞紐間運輸費用、樞紐固定運營成本、非樞紐之間直接運輸產(chǎn)生的費用、樞紐處轉(zhuǎn)運費用以及運輸時間限制，使模型更加符合實際情況；

(2)采用改進的禁忌搜索算法求解多分配p-樞紐中位公鐵聯(lián)運網(wǎng)絡(luò)樞紐選址模型。

1 問題描述

公鐵聯(lián)運網(wǎng)絡(luò)樞紐選址問題對降低運輸網(wǎng)絡(luò)物流費用極具重要性[1,8]，如何選擇公路與鐵路組成的物理網(wǎng)絡(luò)中關(guān)鍵節(jié)點作為公路樞紐、鐵路樞紐或者公鐵聯(lián)運樞紐將是本文研究的重要問題。本文研究的商品為綜合類商品，沒有詳細區(qū)分具體類別。設(shè)計公鐵聯(lián)運網(wǎng)絡(luò)圖如圖1所示。

圖1 公鐵聯(lián)運網(wǎng)絡(luò)圖

公鐵聯(lián)運網(wǎng)絡(luò)包括樞紐點、非樞紐點以及具有流量和時間權(quán)重的有向連接。其中k和k′分別是城市節(jié)點AA可能建設(shè)的公路樞紐和鐵路樞紐，m和m′是城市節(jié)點BB可能建設(shè)的鐵路樞紐和公路樞紐，城市間都有公路和鐵路連接。貨物從供應(yīng)地經(jīng)過樞紐中轉(zhuǎn)再到需求地過程中需要經(jīng)過集散貨運輸，存在7種運輸組織形式可供選擇：路徑①貨物直接通過公路運輸方式從供應(yīng)地Oi運輸?shù)叫枨蟮谼j，沒有經(jīng)過樞紐中轉(zhuǎn)；路徑②和⑥貨物經(jīng)過單個公路樞紐k或單個鐵路樞紐k′，通過公路運輸，并在樞紐處進行中轉(zhuǎn)；路徑③貨物通過兩個公路樞紐k和m′，全程采用公路運輸方式；路徑⑤貨物通過兩個鐵路樞紐k′和m運輸，在兩個鐵路樞紐之間采用鐵路運輸方式，從供應(yīng)地到第一個鐵路樞紐k′以及從第二個鐵路樞紐m到達需求地均采用公路運輸方式；路徑④貨物從供應(yīng)地依次通過公路樞紐k和鐵路樞紐m到達需求地，路徑⑦貨物從供應(yīng)地先后通過鐵路樞紐k′和公路樞紐m′到達需求地，這兩種組織形式均采用公路運輸。與文獻[8]相比，本文所提出的模型在目標函數(shù)選址費用方面考慮的更加全面，優(yōu)越性主要體現(xiàn)在考慮非樞紐間直接運輸費用、樞紐處轉(zhuǎn)運費用以及運輸時間限制方面，既有模型在這方面考慮的不夠具體。

2 公鐵聯(lián)運網(wǎng)絡(luò)的樞紐選址模型建立

本文考慮樞紐間運輸費用、樞紐固定運營成本、非樞紐間直接運輸費用、樞紐處轉(zhuǎn)運費用以及運輸時間限制等影響因素，建立公鐵聯(lián)運網(wǎng)絡(luò)總費用最小的樞紐選址模型。模型建立需要做三個假設(shè)：

(1)假設(shè)貨物由供應(yīng)地到需求地至多經(jīng)過兩個樞紐轉(zhuǎn)運；

(2)貨物從供應(yīng)地運輸?shù)降谝粋€樞紐以及由最后一個樞紐配送到需求地均采用公路運輸；

(3)同一城市最多只能建設(shè)一種類型的樞紐。

2.1 符號及參數(shù)

公鐵聯(lián)運網(wǎng)絡(luò)樞紐選址模型參數(shù)設(shè)置為

N：城市節(jié)點數(shù)；

i：供應(yīng)城市節(jié)點；

j：需求城市節(jié)點；

k,m：樞紐節(jié)點；

P：備選樞紐個數(shù)；

M：一個足夠大的正數(shù)；

S：運輸方式集合{0,1}，s∈S,s=0表示公路運輸，s=1表示鐵路運輸；

fij：供應(yīng)城市i到需求城市j的貨運量；

Fk：城市k選為樞紐的固定運營費用，包括人力、設(shè)備、租賃和資金占用費用等；

α：成本折扣系數(shù),0≤α≤1，可以實現(xiàn)貨物流在跨樞紐運輸時產(chǎn)生的成本節(jié)約，抵消建設(shè)樞紐的固定成本投資和運營費用，給經(jīng)營者帶來額外收益；

βs：樞紐間運輸方式為s的時間延遲因子，βs≥1，解決樞紐處中轉(zhuǎn)時間對模型的影響，更符合實際情況；

C(k,m,s)：貨物在樞紐(k,m)間由運輸方式s產(chǎn)生的運輸成本；

Tij：供應(yīng)城市i到需求城市j的服務(wù)時間限制。

0-1決策變量：

yk：城市k是否為樞紐；

2.2 模型構(gòu)建

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

目標函數(shù)(1)以運輸過程中總費用最小為目標，總費用包括第一項公路直接運輸費用、第二項和第三項通過樞紐對(k,m)運輸費用、第四項樞紐固定運營成本以及轉(zhuǎn)運費用；式(2)建設(shè)樞紐個數(shù)為p；式(3)和式(4)表示只有節(jié)點k,m建設(shè)為樞紐時，才有基于該樞紐的運輸路徑選擇；式(5)表示OD對之間運輸模式選擇約束，兩者之間只能選擇一種最優(yōu)的運輸路線；式(6)表示只有節(jié)點k選為樞紐才能選擇是否需要轉(zhuǎn)運；式(7)和式(8)分別表示樞紐對(k,m)由公路運輸和鐵路運輸產(chǎn)生的費用成本；式(9)表示OD對之間運輸時間不能大于最遲到達時間約束限制；式(10)表示決策變量為(0,1)變量。

3 模型求解算法

公鐵聯(lián)運網(wǎng)絡(luò)樞紐選址問題屬于NP-hard問題，文獻[9]提出用禁忌搜索算法解決此類問題，并找到誤差小于1%的最優(yōu)解。本文采用改進的禁忌搜索(TS)算法，通過設(shè)置禁忌表來禁忌過去的操作，利用特設(shè)準則來解禁一些優(yōu)良狀態(tài)，在一定程度上接受劣解，使其在搜索過程中跳出局部最優(yōu)解，實現(xiàn)全局優(yōu)化。具體求解思路和求解步驟如下。

3.1 禁忌搜索算法求解思路

禁忌搜索算法求解思路：首先按照隨機方法產(chǎn)生一個初始解yk作為當前解，采用鄰域優(yōu)先的搜索方法，將樞紐和非樞紐之間成對交換作為鄰域搜索方向，并在當前解的鄰域中搜索若干個解，取其中最優(yōu)解作為新的當前解。使用禁忌表記錄已搜索的局部最優(yōu)解的歷史信息，從而避免迂回搜索。為了能逃離局部最優(yōu)解，算法必須接受劣解，一旦接受劣解，迭代就可能陷入循環(huán)。算法將最近接受的一些移動放在禁忌表中，在以后的迭代中加以禁止，以此避免循環(huán)，即只有不在禁忌表中的較好解，才被接受作為下一次迭代的初始解。隨著迭代的進行，禁忌表不斷更新，經(jīng)過給定迭代次數(shù)后，最早進入禁忌表的移動就從禁忌表中解禁退出。當隨機產(chǎn)生初始解次數(shù)達到給定的次數(shù)后，禁忌搜索終止，輸出最優(yōu)解。

禁忌搜索算法參數(shù)設(shè)定

(1)解的表示

(2)初始解產(chǎn)生

(3)鄰域構(gòu)建及候選解集選擇

通過樞紐節(jié)點和非樞紐節(jié)點之間成對交換作為鄰域搜索方向，根據(jù)評價函數(shù)的優(yōu)劣構(gòu)造候選解，本文評價函數(shù)越小，候選解替代當前解的概率越大。

(4)評價函數(shù)構(gòu)建

本文將模型中目標函數(shù)作為評價函數(shù)，評價值minZ越小越好。

(5)禁忌表和禁忌長度

(6)特赦及停止準則

特設(shè)準則：采用評價函數(shù)值的特赦準則，候選解中所有解為禁忌解時，則解禁最好解。

停止準則：采用最大迭代次數(shù)Nmaxiter=10n。

3.2 禁忌搜索算法求解步驟

禁忌搜索算法包括全局多樣化搜索和區(qū)域強化搜索兩階段[10]。第一階段確定樞紐位置，第二階段進行網(wǎng)絡(luò)路徑分配。具體求解步驟如下：

步驟2判斷第一階段Rcount

步驟4禁忌表中除新加入OD對外，原有OD對(q,r)進行l(wèi)ength(q,r)=length(q,r)-1操作，如果length(q,r)=0，則(q,r)離開禁忌表。

步驟5判斷所有可能移動是否在禁忌表中，如果滿足，進一步判斷是否滿足特赦準則，本文采用的特設(shè)準則為候選解的適配值優(yōu)于歷史最優(yōu)值，否則更新Tabu_list、當前解；如果節(jié)點頻率大于給定的閾值(Freqlimit)，則在初始解中踢出該節(jié)點，置空Tabu_list，并更新當前解、初始解；如果nodefrequency≤Freqlimit，直接置空Tabulist，令當前解=初始解，返回步驟1。

步驟6當隨機產(chǎn)生初始解次數(shù)Rcount達到Mcount后，禁忌搜索終止，輸出最優(yōu)解

4 算例分析

4.1 數(shù)據(jù)描述

本文基于Rardin and Uzsoy[11]中算例構(gòu)建，數(shù)據(jù)滿足公路單位貨運成本高于鐵路，鐵路樞紐中轉(zhuǎn)時間大于公路樞紐中轉(zhuǎn)時間。選取20個城市節(jié)點作為算例，具體空間分布情況如圖2所示。

圖2 20個城市空間分布

表1 城市節(jié)點之間的貨流量

表2 影響因子設(shè)計[12]

4.2 結(jié)果與分析

(1)模型有效性驗證

為了驗證禁忌搜索算法求解模型的有效性，影響因子分別取表2集合中第一個元素，通過MATLAB編程將程序運行20次，選取最優(yōu)一次計算過程，其收斂情況如圖3所示。

圖3 禁忌搜索算法收斂優(yōu)化曲線

圖3中取最大迭代次數(shù)為100次，收斂曲線在35代附近開始趨于收斂，說明禁忌搜索算法初始收斂快，后期精度改善相對緩慢。最優(yōu)解和運行時間如圖4所示。

圖4 最優(yōu)解與運行時間對比

由圖4可以分析出目標函數(shù)最優(yōu)值集中在1 297 445，沒有出現(xiàn)明顯波動，說明模型的正確性和穩(wěn)定性；求解時間分布在[384.6 s,570.9 s]之間，平均時間為474.1 s，說明禁忌搜索算法可以在較短的時間得到最優(yōu)解。禁忌搜索算法與Lingo分支定界算法性能比較見表3。

表3 TS與Lingo結(jié)果對比

通過數(shù)據(jù)分析得到TS最優(yōu)值為1 295 502，與Lingo分支定界精確解僅相差0.15%，TS與Lingo求解間隙最大為0.68%，最小為0.15%，但TS求最優(yōu)解的時間僅是Lingo的22.5%，兩種求解方法得到最佳樞紐位置均為[1,3,5,14,17,18]。但Lingo在求解大規(guī)模網(wǎng)絡(luò)時存在數(shù)據(jù)容易溢出、運行時間較長的局限性，例如當P=9時，Lingo的運行時間超過3 600 s，仍未得到滿意的解，而禁忌搜索算法完全可以在較短時間內(nèi)找到滿意解，并且具有較強的穩(wěn)定性和收斂能力。

(2)成本折扣系數(shù)和公鐵單位成本比對選址結(jié)果影響分析

公鐵聯(lián)運網(wǎng)絡(luò)中，當貨物流的規(guī)模擴大時，運輸總成本隨著運量的增加呈現(xiàn)非線性緩慢增加，單位運輸成本隨之降低。通過成本折扣系數(shù)α可以實現(xiàn)貨物流在跨樞紐運輸時產(chǎn)生的成本節(jié)約，抵消建設(shè)樞紐的固定成本投資和運營費用，給經(jīng)營者帶來額外收益，成本折扣系數(shù)和公鐵單位成本比的大小直接影響選址結(jié)果。成本折扣系數(shù)α={0.5,0.7,0.9}和公鐵單位運輸成本CR={1.2,1.4,1.6}情況下對選址結(jié)果的影響如圖5所示。

圖5 成本折扣系數(shù)和公鐵單位成本比對選址結(jié)果的影響

圖5(a)表示成本折扣系數(shù)與公鐵單位成本比對目標函數(shù)最優(yōu)值的影響。在CR一定情況下，最優(yōu)值隨α增加而增大，這是因為跨樞紐城市間運輸成本折扣系數(shù)越大，所需要運輸費用越高，α=1取極值情況下，樞紐間運輸成本相當于直接運輸，沒有產(chǎn)生折扣，此時運輸費用最大；圖5(b)表明樞紐間折扣系數(shù)α越大，公鐵聯(lián)運最佳樞紐平均數(shù)越小，當公鐵單位成本比為1.2時，折扣系數(shù)α由0.5增加到0.9，最佳樞紐平均值則由8.2降低到3.5，減少了57.3%，當公鐵單位成本比為1.6時，最佳樞紐的平均值則由8.5減少到3.1，降低了65.9%，說明成本折扣系數(shù)對最佳樞紐平均值的影響程度遠大于公鐵單位成本比對最佳樞紐平均值的影響；圖5(c)表明公鐵單位成本比和成本折扣系數(shù)對單一公路樞紐所占比例的影響趨勢與圖5(d)相反；圖5(d)表明在α一定情況下，公鐵聯(lián)運樞紐所占比例隨著公鐵單位成本比的增加而增大，在CR一定情況下，公鐵聯(lián)運樞紐所占比例隨著成本折扣系數(shù)的增大而減小，進一步證明結(jié)果符合實際情況。

綜上所述，公鐵聯(lián)運網(wǎng)絡(luò)中鐵路運輸成本低所帶來的效益完全可以被成本折扣系數(shù)的規(guī)模效應(yīng)所抵消，因此，在公鐵聯(lián)運網(wǎng)絡(luò)中，選擇合適的樞紐位置及樞紐類型將會減少整個運輸過程中的總費用。

5 結(jié)束語

本文考慮樞紐間運輸費用、樞紐固定運營成本、非樞紐間直接運輸費用、樞紐處轉(zhuǎn)運費用以及運輸時間限制等多種影響因素，建立無容量限制多分配p-樞紐中位選址模型，運用改進的禁忌搜索元啟發(fā)式算法進行求解，研究公鐵聯(lián)運樞紐選址問題，并通過算例分析及算法比較驗證本文所提模型和算法可以有效用來解決公鐵聯(lián)運網(wǎng)絡(luò)的樞紐選址問題。本文所提方法對公鐵聯(lián)運樞紐選址具有一定借鑒意義，同時還可以擴展到公路水路聯(lián)運、鐵路水路聯(lián)運、鐵路公路水路聯(lián)運和公路航班聯(lián)運，以及在考慮樞紐容量限制情況下如何設(shè)計模型更加符合實際情況。

參考文獻：

[1]石小法. 貨運交通系統(tǒng)[M]. 上海:同濟大學出版社, 2013：23-30.

[2]RACUNICA I, WYNTER L. Optimal Location of Intermodal Freight Hubs[J]. Transportation Research Part B, 2005, 39(5): 453-477.

[3]LIMBOURG S. Jourquin B Optimal Rail-road Container Terminal Locations on the European Network[J]. Transportation Research E, 2009, 45(4):551-563.

[4]RAFAY Ishfaq, CHARLES R Sox.Hub Location-allocation in Intermodal Logistic Networks[J]. European Journal of Operational Research, 2011, 210:213-230.

[5]王雷，吳薇薇.Benders分解算法在多分配樞紐選址問題的應(yīng)用[J].信息技術(shù),2012,5(7):1-10.

WANG Lei, WU Weiwei. Benders Decomposition Algorithm for Multi-distribution Hub Location Problem[J].Information Technology, 2012,5(7):1-10.

[6]傅少川，胡夢飛，唐方成.禁忌搜索算法在單分配多樞紐軸輻式物流網(wǎng)絡(luò)中的應(yīng)用[J].中國管理科學, 2012, 20(3): 145-151.

FU Shaochuan, HU Mengfei, TANG Fangcheng. The Optimization of Hub and Spoke Logistics Network Design Based on Tabu Search Algorithm[J]. Chinese Journal of Management Science,2012, 20(3): 145-151.

[7]崔小燕，李旭宏，毛海軍，等. 無容量約束單分配軸-輻式物流網(wǎng)絡(luò)設(shè)計[J]. 交通運輸系統(tǒng)工程與信息, 2010, 10(5): 175-181.

CUI Xiaoyan, LI Xuhong, MAO Haijun, et al. Design of Uncapacitated Hub-and-Spoke Logistics Networks with Single Allocation [J]. Journal of Transportation Systems Engineering and Information Technology, 2010,10(5):175-181.

[8]RAFAY Ishfaq, CHARLES R Sox. Intermodal Logistics: The Interplay of Financial, Operational and Service Issues [J]. Transportation Research Part E, 2010, 46: 926-949.

[9]SKORIN Kapov D,SKORIN Kapov J,O'Kelly ME. Tight Linear Programming Relaxations of Uncapacitated P-hub Median Problems[J]. European Journal of Operational Research, 1996, 94(3): 582-593.

[10]汪定偉，王俊偉，王洪峰，等. 智能優(yōu)化方法[M]. 北京：高等教育出版社，2007：81-110.

[11]RARDIN R L, UZSOY R. Experimental Evaluation of Heuristic Optimization Algorithms: A tutorial[J]. Journal of Heuristics, 2001, 7: 261-304.

[12]SLACK, B. Intermodal Transportation in North America and the Development of Inland Load Centers[J]. Professional Geographer, 1990, 42(1): 72-83.