公鐵聯運網絡的樞紐選址模型及算法

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

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

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

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

本文主要研究公鐵聯運網絡貨運樞紐選址模型及算法設計，創新點在于：

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

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

1 問題描述

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

圖1 公鐵聯運網絡圖

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

2 公鐵聯運網絡的樞紐選址模型建立

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

(1)假設貨物由供應地到需求地至多經過兩個樞紐轉運；

(2)貨物從供應地運輸到第一個樞紐以及由最后一個樞紐配送到需求地均采用公路運輸；

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

2.1 符號及參數

公鐵聯運網絡樞紐選址模型參數設置為

N：城市節點數；

i：供應城市節點；

j：需求城市節點；

k,m：樞紐節點；

P：備選樞紐個數；

M：一個足夠大的正數；

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

fij：供應城市i到需求城市j的貨運量；

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

α：成本折扣系數,0≤α≤1，可以實現貨物流在跨樞紐運輸時產生的成本節約，抵消建設樞紐的固定成本投資和運營費用，給經營者帶來額外收益；

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

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

Tij：供應城市i到需求城市j的服務時間限制。

0-1決策變量：

yk：城市k是否為樞紐；

2.2 模型構建

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

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

3 模型求解算法

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

3.1 禁忌搜索算法求解思路

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

禁忌搜索算法參數設定

(1)解的表示

(2)初始解產生

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

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

(4)評價函數構建

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

(5)禁忌表和禁忌長度

(6)特赦及停止準則

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

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

3.2 禁忌搜索算法求解步驟

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

步驟2判斷第一階段Rcount

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

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

步驟6當隨機產生初始解次數Rcount達到Mcount后，禁忌搜索終止，輸出最優解

4 算例分析

4.1 數據描述

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

圖2 20個城市空間分布

表1 城市節點之間的貨流量

表2 影響因子設計[12]

4.2 結果與分析

(1)模型有效性驗證

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

圖3 禁忌搜索算法收斂優化曲線

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

圖4 最優解與運行時間對比

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

表3 TS與Lingo結果對比

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

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

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

圖5 成本折扣系數和公鐵單位成本比對選址結果的影響

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

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

5 結束語

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

參考文獻：

[1]石小法. 貨運交通系統[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分解算法在多分配樞紐選址問題的應用[J].信息技術,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]傅少川，胡夢飛，唐方成.禁忌搜索算法在單分配多樞紐軸輻式物流網絡中的應用[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]崔小燕，李旭宏，毛海軍，等. 無容量約束單分配軸-輻式物流網絡設計[J]. 交通運輸系統工程與信息, 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]汪定偉，王俊偉，王洪峰，等. 智能優化方法[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.