郭紅霞，倪少權(quán)，賀裕雁

(1.西南交通大學，交通運輸與物流學院，成都 610031；2.廣西科技大學，經(jīng)濟與管理學院，廣西柳州 545006)

0 引言

公路港甩掛運輸網(wǎng)絡規(guī)模的擴大和甩掛運輸業(yè)務的不斷拓展使得公路港甩掛調(diào)度難度增加，是我國公路港亟待解決的重要問題之一。目前我國現(xiàn)有政策對甩掛運輸車輛類型進行了限制，卡車拖帶掛車的甩掛運輸車輛不允許在中國道路上運行，只允許牽引車加半掛車的形式(Tractor and Semitrailer)[1]，稱 為TSRP(Tractor and Semitrailer Routing Problem)，這與歐美國家存在較大差異。目前，我國甩掛運輸區(qū)域發(fā)展不平衡，發(fā)展較好的地區(qū)主要為華東、華南等經(jīng)濟發(fā)達區(qū)域，甩掛車輛主要從事以港口為核心的集裝箱軸輻式甩掛集疏運。我國的公路港甩掛運輸雖已得到足夠的重視，但仍以“點對點”運輸為主，兩點輻射的范圍也僅局限于某個區(qū)域內(nèi)，甩掛運輸效率不高?，F(xiàn)階段，我國開展公路港甩掛運輸?shù)能囆吞攸c決定了中長途干線運輸是其主要應用領域，中長途干線運輸以網(wǎng)絡化、規(guī)?；卣鞒蔀轶w現(xiàn)甩掛運輸高效性優(yōu)勢的依托條件，便于實現(xiàn)甩掛運輸貨源組織的規(guī)?；痆2]。政府的大力支持，公路港甩掛運輸網(wǎng)絡的漸次鋪開，貨源的日益充足穩(wěn)定以及企業(yè)信息化水平的提高，為公路港甩掛運輸企業(yè)在全國范圍內(nèi)開展調(diào)度提供了保障。因此，研究網(wǎng)絡條件下公路港甩掛調(diào)度優(yōu)化問題對企業(yè)的車輛資源配置優(yōu)化與運營具有重要的指導意義。

目前甩掛調(diào)度優(yōu)化研究主要集中在“一線兩點、兩端甩掛”“軸輻式甩掛”“循環(huán)甩掛”等組織模式，針對網(wǎng)絡條件的研究較少，且未考慮供需匹配問題。Li等[3]為解決“軸輻式甩掛”模式下的廢氣材料甩掛調(diào)度問題，以成本最小為優(yōu)化目標，提出車輛流規(guī)劃模型，設計了改進節(jié)約算法進行求解。Li等[4]針對“軸輻式甩掛”模式下的垃圾搜集甩掛調(diào)度問題，以總運行成本最小為目標函數(shù)，考慮時間窗、集裝箱裝卸時間等約束構(gòu)建數(shù)學模型，通過設計兩階段啟發(fā)式算法，實現(xiàn)裝載和空箱的同步調(diào)度。楊珍花等[5]以綜合成本最小化為目標，設計多階段動態(tài)優(yōu)化算法以解決“軸輻式甩掛”模式下甩掛車輛的動態(tài)調(diào)度優(yōu)化問題。彭勇等[6]針對“循環(huán)甩掛”模式下的同城甩掛運輸問題，為盡可能降低物流運輸成本的同時提高客戶滿意度，構(gòu)建了帶時間窗的具有多行程的交換箱甩掛運輸優(yōu)化模型，提出裝箱算法與遺傳算法混合的啟發(fā)式求解算法。Li等[7]基于“一線兩點、兩端甩掛”模式，為解決城際干線甩掛運輸問題，以噸公里CO2排放量為優(yōu)化目標，設計改進節(jié)約算法進行求解。李紅啟等[8]研究“一線兩點、兩端甩掛”模式下的城際干線甩掛運輸問題，以CO2排放量為優(yōu)化目標構(gòu)建模型，并設計模擬退火算法進行求解。Regnier 等[9]研究“循環(huán)甩掛”模式下的企業(yè)甩掛運輸調(diào)度問題，考慮時間窗等約束構(gòu)建模型，并運用動態(tài)離線式建模求解器進行求解。靳志宏等[10]研究“循環(huán)甩掛”模式下的滾裝甩掛碼頭牽引車調(diào)度問題，建立混合整數(shù)規(guī)劃模型，并設計遺傳算法求進行求解。楊珍花等[11]建立軸輻式與網(wǎng)絡型混合模式下的多車型甩掛調(diào)度模型，以成本最小為優(yōu)化目標構(gòu)建模型，設計混合模擬退火算法進行求解。余莉等[12]結(jié)合網(wǎng)絡條件下的甩掛運輸及滿載多車場車輛調(diào)度問題的特點，建立數(shù)學模型，并設計啟發(fā)式算法進行求解。王清斌等[13]建立“循環(huán)甩掛”模式下考慮新增運輸任務的干擾管理模型，設計遺傳算法進行求解。在車輛路徑優(yōu)化方面，供需未匹配問題研究較多，但在甩掛調(diào)度優(yōu)化方面較少。徐東洋等[14]以總成本最小為優(yōu)化目標，建立同時考慮客戶間供需未匹配和需求可拆分的取送貨車輛路徑問題模型，并設計基于大規(guī)模鄰域搜索的迭代局部搜索求解算法。Chen 等[15]建立同時考慮客戶間供需未匹配和分批交貨的取送貨車輛路徑問題模型，提出基于變鄰域搜索的局部搜索算法進行求解。Xu 等[16]建立同時考慮客戶間供需未匹配和多需求的取送貨車輛路徑問題模型，設計禁忌搜索算法進行求解。Tadumadze等[17]建立同時考慮勞動力規(guī)劃和卡車調(diào)度的混合整數(shù)模型，并設計啟發(fā)式算法進行求解。

在求解多車型調(diào)度優(yōu)化問題時，相關學者采用精確求解算法和啟發(fā)式算法。例如，Regnier等[9]針對實時動態(tài)優(yōu)化問題，采用CPLEX 求解小規(guī)模問題。Subramanian 等[18]用CPLEX 求解小規(guī)模問題，同時針對大規(guī)模問題設計了自適應記憶規(guī)劃算法進行求解。Villegas等[19]設計了一種基于貪婪隨機自適應搜索程序的兩階段啟發(fā)式算法。Tütüncü等[20]設計了貪婪的隨機自適應記憶搜索算法。Oliviu等[21]設計了遺傳算法和最鄰近法相結(jié)合的方法進行求解。Li 等[22]設計了自適應大鄰域啟發(fā)式搜索算法求解兩層級多車型車輛路徑問題。Ghannadpour 等[23]提出了非支配排序遺傳算法。Andre 等[24]針對兩級固定車隊異質(zhì)車輛路徑問題，提出一種基于局部搜索的Lin-Kernighan 啟發(fā)式算法。Srivastava等[25]設計了非支配排序遺傳算法、多鄰域自適應禁忌搜索算法和精英蟻群算法求解。Soares等[26]基于可變鄰域分解搜索下的固定與優(yōu)化原則，提出一種新的元啟發(fā)式算法求解大規(guī)模調(diào)度問題。

上述文獻大多是在單車場、單一需求、供需已匹配、需求均衡視角下建立的模型假設，忽略了多車場、多需求、需求不均衡和供需未匹配的現(xiàn)實需求。在算法求解方面，已有文獻證明甩掛運輸調(diào)度優(yōu)化問題屬于NP-Hard 問題[1]，因此大部分文獻采用元啟發(fā)式算法和啟發(fā)式算法進行求解，但在進行局部搜索時僅依靠理論而忽略了實際調(diào)研情況。因此，本文基于公路港作為甩掛作業(yè)場所和客戶需求點的特性，考慮公路港間甩掛需求與車輛裝載能力不匹配和多車型甩掛(即噸位大的牽引車可拖掛同車型或噸位小的半掛車)等現(xiàn)實需求，以網(wǎng)絡運營成本最小為優(yōu)化目標，建立網(wǎng)絡條件下供需未匹配的公路港多車型甩掛調(diào)度優(yōu)化模型，并根據(jù)實際調(diào)研設計基于節(jié)約里程法、動態(tài)規(guī)劃法和改進模擬退火算法的兩階段啟發(fā)式算法對模型進行求解。并與傳統(tǒng)運輸方式對比，證明多車型甩掛運輸優(yōu)勢明顯，為企業(yè)決策提供了支持。

1 問題描述

公路港甩掛運輸?shù)目焖侔l(fā)展使得路網(wǎng)不斷升級，公路港建設增多，線路間聯(lián)系緊密，其中每兩個公路港之間都有通道相連，多個公路港之間的甩掛運輸業(yè)務形成網(wǎng)絡，該甩掛運輸網(wǎng)絡向北輻射哈爾濱乃至整個東北地區(qū)，向南輻射廣州、深圳等地，向西輻射成都、重慶等地，向東輻射寧波、上海等地，在全國范圍內(nèi)開展甩掛。公路港甩掛運輸網(wǎng)絡內(nèi)，甩掛作業(yè)點提前將貨物裝上半掛車，裝貨完畢后由牽引車送至指定的公路港，牽引車無需等待卸貨作業(yè)，卸下重掛，繼續(xù)服務下一個客戶點(公路港)，直到運行時間內(nèi)完成最后一個甩掛任務后，停留于該公路港，即為網(wǎng)絡條件下的公路港甩掛調(diào)度方式。實踐調(diào)研發(fā)現(xiàn)，公路港甩掛運輸網(wǎng)絡中存在多個車場，公路港間甩掛需求不均衡，且存在多次甩掛和甩掛需求大于車輛裝載能力的情況，其具體供需匹配關系及牽引車和掛車配置數(shù)量未知，屬于多車場供需未匹配的調(diào)度問題。

本文在上述網(wǎng)絡條件下提出公路港多車型甩掛調(diào)度優(yōu)化，具體如圖1 所示。圖中，圓圈內(nèi)數(shù)字表示公路港編號，線上數(shù)字表示公路港之間的甩掛運輸量與所需車型。以甩掛運輸線路①→⑤→③→②→①為例，如果不同的車型之間不可以進行交叉甩掛，該條線路至少需要3輛35 t牽引車、2輛37 t 牽引車和5 輛40 t 牽引車，而且回程時均為空駛。但如果不同車型之間允許進行交叉甩掛，在連續(xù)工作時間內(nèi)，5輛40 t的牽引車從公路港1出發(fā)到達公路港5，其中2輛牽引車可以繼續(xù)完成公路港3到公路港2 和公路港2 到公路港1 的甩掛任務，將會減少2輛35 t和2輛37 t牽引車的使用，同時降低了回程空駛率，提高運輸效率，很明顯此種方案更優(yōu)。

圖1 網(wǎng)絡條件下供需未匹配的公路港多車型甩掛調(diào)度優(yōu)化示意圖Fig.1 Schematic diagram of multiple tractor-and-semitrailer scheduling with unmatched supply and demand under network condition

該公路港甩掛運輸網(wǎng)絡除了具有多車場、多需求、需求不均衡以及多車型甩掛的復雜性外，還具有如下特性：公路港之間的甩掛需求往往大于車輛最大裝載能力，需對公路港之間的甩掛需求進行拆分，并通過多輛不同類型牽引車共同完成甩掛任務，要求進行供需匹配，但匹配關系未知，研究如何以較低的運營成本進行公路港間的供需匹配決策和牽引車與掛車數(shù)量配置，屬于更難求解的NPHard問題。

2 模型建立

2.1 模型假設

根據(jù)公路港甩掛運輸特點，做出如下假設：

(1)網(wǎng)絡中所有牽引車、半掛車都屬于公路甩掛運輸推薦車型，但型號存在不一致情況，且牽引車只能牽引不大于自身準拖最大質(zhì)量的半掛車，牽引車類型和半掛車類型對應。

(2)不考慮空半掛車的調(diào)度。由于公路港同時又是掛車池，因此，網(wǎng)絡中各公路港有足夠多的半掛車，無需從其他公路港調(diào)度空半掛車。

(3) 兩個公路港間往返行駛的距離及時間相同。這一點主要與甩掛運輸車輛的運作相關，實踐中司機采用高德地圖推薦的路線開展甩掛運輸。

(4) 牽引車甩掛半掛車作業(yè)時間計入行駛時間。此假設與公路港甩掛的實際操作是一致的，故該假設合理。

(5)牽引車執(zhí)行“一車一掛”的滿載運輸，即牽引車一次只能拖帶一輛半掛車。這與我國公路港甩掛運輸運營實踐相符合。

(6)牽引車的起終點均為公路港，起始公路港和終止公路港可不一致。公路港內(nèi)可以停放牽引車和半掛車，因此不必考慮牽引車完成運輸任務后返回車場，這一點與我國公路港甩掛運輸實際調(diào)研相符合。

(7)公路港間的甩掛需求獨立，無時間和運輸先后順序限制。

(8)網(wǎng)絡中每天都產(chǎn)生甩掛需求，且每天的需求存在波動，企業(yè)可以根據(jù)每天實際需求安排調(diào)度，所有的需求都必須滿足。由于某些節(jié)點之間距離較遠，甩掛運輸不一定能夠在一天內(nèi)完成，因此假設前一天未完成的甩掛任務不影響后續(xù)調(diào)度。

2.2 符號說明

N——所有公路港的集合，共有n個公路港，N={1,2,…,n} ；

i,j,l——公路港的編號，i,j,l∈N；

K——牽引車的集合，K={1,2,…,k} ；

k——牽引車的編號，k∈K；

m——牽引車的類型，m∈{1,2,3} ；

mk——第m種類型牽引車k，k∈K；

dij——公路港i,j之間的距離(km)；

qij——公路港i,j之間的甩掛需求，用貨物噸位表示，由于需求不一定平衡，qij不一定等于qji；

T——牽引車連續(xù)工作的時間，規(guī)定所有牽引車每天連續(xù)工作的時間都相等；

Vm1,Vm2——m類型牽引車牽引重掛、空駛的速度(km·h-1)；

S——牽引車甩掛任務的集合，S={1,2,…,S,…} ；

a,b,s——牽引車甩掛任務的編號，a,b,s∈S；

P——較大值；

KZ——路網(wǎng)需要的牽引車總數(shù)。

2.3 數(shù)學模型

(1)目標函數(shù)

(2)約束條件

式(1)表示網(wǎng)絡運營成本由重掛行駛成本、空駛成本、固定成本和懲罰成本組成，且運營成本最??；式(2)表示每一個甩掛任務均被滿足，且只能由一輛牽引車服務；式(3)表示甩掛需求得到滿足；式(4)表示牽引車被使用后才可服務甩掛任務；式(5)表示當前牽引車不服務某個任務時順序為0；式(6)表示每輛牽引車服務任務順序的編號不同；式(7)表示每輛牽引車服務任務編號的取值范圍；式(8)表示每輛牽引車重載趟數(shù)；式(9)表示每輛牽引車空載趟數(shù)；式(10)表示每輛牽引車重掛是否經(jīng)過公路港行駛路線；式(11)表示每輛牽引車空掛是否經(jīng)過公路港行駛路線；式(12)和式(13)表示每個甩掛任務的始發(fā)公路港和終到公路港不相同；式(14)表示牽引車連續(xù)工作時間限制；式(15)表示懲罰成本，γ為使用高質(zhì)量牽引車牽引低質(zhì)量掛車的懲罰系數(shù)，也為不同牽引質(zhì)量牽引車成本極差系數(shù)；式(16)表示牽引車使用數(shù)量。

3 兩階段啟發(fā)式算法設計

網(wǎng)絡條件下供需未匹配的公路港多車型甩掛調(diào)度優(yōu)化屬于NP-Hard 問題[2]，在較短的時間內(nèi)很難獲取較為滿意的解。為此，本文設計兩階段啟發(fā)式算法進行求解，第1階段通過動態(tài)規(guī)劃法將甩掛需求分割成單個半掛車可以承載的重量，將其轉(zhuǎn)變?yōu)橐粋€或多個甩掛任務，將連續(xù)型問題轉(zhuǎn)變?yōu)殡x散型問題，以降低問題復雜度；第2 階段考慮到動態(tài)規(guī)劃拆分的甩掛任務數(shù)量較多，因此運用節(jié)約里程法對甩掛任務進行合并以減少解空間的數(shù)量，以得到較好的初始解，并設計改進的模擬退火算法進行求解。

3.1 動態(tài)規(guī)劃法設計

動態(tài)規(guī)劃法主要思想是將問題分解成若干個子問題，先求解子問題的最佳解，然后從這些子問題的解中得到原問題的最佳解。本文通過該算法解決不考慮任務合并的前提下甩掛需求的分割問題，屬于整數(shù)規(guī)劃問題。

3.2 改進模擬退火算法設計

(1)初始解的生成

本文運用節(jié)約里程法對甩掛任務進行合并以形成初始解，首先令一輛牽引車只服務一個甩掛任務，然后通過計算任意兩個任務在滿足約束下合并后節(jié)省的成本得到費用表，依據(jù)費用表更新節(jié)約成本最大的合并線路，并更新費用表，直到任意兩個任務無法合并或無法節(jié)約成本。

(2)解空間結(jié)構(gòu)設計

將合并后的甩掛任務分別編號以形成解空間。若H為甩掛任務數(shù)量，則編碼長度為H，設H=8，具體解空間結(jié)構(gòu)如圖2所示。

圖2 網(wǎng)絡條件下供需未匹配的公路港多車型甩掛調(diào)度解空間結(jié)構(gòu)圖Fig.2 Solution space structure diagram for multiple tractorand-semitrailer scheduling with unmatched supply and demand under network condition

(3)鄰域解構(gòu)造方法

基于“一個鄰域結(jié)構(gòu)的局部最優(yōu)解不一定是另一個鄰域結(jié)構(gòu)的局部最優(yōu)解”“全局最優(yōu)解是所有可能鄰域的局部最優(yōu)解”兩個實際理論，本文通過3 種鄰域結(jié)構(gòu)進行搜索以提高求解最優(yōu)解的可能性，分別是插入、交換和逆反。

(4)算法終止準則

改進模擬退火算法包括內(nèi)外兩個終止準則。

①內(nèi)循環(huán)終止準則，采用與問題規(guī)模相關聯(lián)的步數(shù)抽樣，即當內(nèi)循環(huán)次數(shù)達到與網(wǎng)絡規(guī)模乘某個系數(shù)值所對應的步數(shù)時，則該溫度下的內(nèi)循環(huán)終止。

②外循環(huán)終止準則，采用設置終止溫度閾值的方法，即當溫度下降到某一設定閾值時，算法終止并輸出結(jié)果。

4 算例分析

依托公路港甩掛運輸網(wǎng)絡，甩掛運輸企業(yè)在30個城市都具有公路港，如何在公路港網(wǎng)絡中安排車輛調(diào)度，使得整個網(wǎng)絡運營成本最低是企業(yè)管理者希望解決的技術問題。根據(jù)交通運輸部公布的3批公路甩掛運輸推薦車型，該企業(yè)使用的牽引車車輛及重掛空掛行駛成本、固定成本如表1 所示。假設同一類型不同型號牽引車行駛速度相同，重掛和空駛的速度分別為Vm1=50 km·h-1，Vm2=70 km·h-1，每天連續(xù)工作時間T=16 h，dij值根據(jù)高德地圖點擊導航，選擇高德地圖推薦的路線得出。γ可以直接由表1 計算得到。qij值使用Matlab 2010a軟件中的randint函數(shù)，在[0,100]內(nèi)生成30 個客戶點之間的甩掛任務，所有甩掛任務均為整數(shù)。改進的模擬退火算法(ISA)中，初始溫度設置為1000°C，算法結(jié)束溫度設置為0.1°C，溫度衰減參數(shù)ε為0.95，馬爾科夫鏈長度uk為50。算法運行30次，取其中的最優(yōu)值作為最終結(jié)果。

4.1 固定工作時長下的結(jié)果分析

通過計算，需要1447輛牽引車完成既定任務，每輛牽引車的編號如表2 所示。從表3 中可以看出，與傳統(tǒng)運輸方式相比，牽引車數(shù)量減少了7.30%，節(jié)約成本2.32%，甩掛比為1.00∶1.08，體現(xiàn)了多車型甩掛的優(yōu)越性。

表2 網(wǎng)絡條件下供需未匹配的公路港多車型甩掛調(diào)度運行結(jié)果Table 2 Results of multiple tractor-and-semitrailer scheduling optimization in highway port with unmatched supply and demand under network condition

表3 傳統(tǒng)運輸方式與多車型甩掛計算結(jié)果對比Table 3 Comparison of calculation results between traditional and common tractor and semi-semitrailer transportation

4.2 不同工作時長下的結(jié)果對比

隨著牽引車工作時長的增加，甩掛運輸會盡可能發(fā)揮長交路的優(yōu)勢，所服務的公路港數(shù)量隨之增加，進而形成不同的牽引車調(diào)度方案。為此，將延長算例中牽引車的工作時長，分別為16，32，48，72 h，具體計算結(jié)果如表4所示。

表4 不同牽引車工作時長下的結(jié)果對比Table 4 Comparison of results under different working hours

結(jié)果表明，牽引車使用數(shù)量、總成本、甩掛比與牽引車工作時長之間存在密切關系，具體如下：(1) 相較于我國2022 年的甩掛比1.00∶1.04，算例中的甩掛比均高于該數(shù)值，且與牽引車工作時長成正比。甩掛比越高，表示每輛牽引車路線能拖掛的半掛車數(shù)量越多，運輸網(wǎng)絡上牽引車的使用效果越好，車輛配置效率越高，網(wǎng)絡運營成本越低，證明了多車型甩掛的優(yōu)勢。(2) 牽引車工作時長越長，牽引車使用數(shù)量和總成本越小，甩掛比越大。(3)牽引車工作時長越長，牽引車數(shù)量減少比例和總成本節(jié)約率均呈現(xiàn)出梯度增加的趨勢，尤其當牽引車工作時長為72 h 時，多車型甩掛的優(yōu)勢凸顯。(4)不同工作時長下甩掛比合理值的確定，也為公路港甩掛運輸企業(yè)購置牽引車和半掛車方案提供了決策支持。

4.3 不同算法下的結(jié)果對比

為進一步驗證算法的性能，本文將改進蟻群算法(IACS)、改進粒子群算法(IPSO)和改進模擬退火算法(ISA)進行對比，3種算法采用相同的局部搜索策略。IACS算法中Nc_max為最大迭代次數(shù)，設置為600；α為信息素重要程度的參數(shù)，設置為1；β為啟發(fā)式因子重要程度的參數(shù)，設置為4。IPSO算法中的學習因子c1，c2均取1.5，粒子速度vmax=5，vmin=-5。目標函數(shù)最值對比如圖3所示。

圖3 多車型甩掛目標函數(shù)最值對比Fig.3 Comparison results of maximum objective function for common tractor and semitrailer transportation

由圖3 可知，IACS 算法的平均目標值均小于IPSO 和ISA，較IPSO 和ISA 分別降低了28.75%、1.5%，運行時間較IPSO 減少5.28%、較ISA 增加51.8%。通過對比可以看出，IACS算法的平均總運營成本略優(yōu)于ISA 算法，差距不大，但運行時間遠遠大于ISA算法。因此，綜合考慮認為采用ISA兩階段啟發(fā)式算法較優(yōu)，并證明了ISA算法在處理大規(guī)模問題時尋找最優(yōu)解的優(yōu)越性。

5 結(jié)論

多車型甩掛相比于單一車型運輸運營成本要低，說明多車型甩掛可以更恰當?shù)匕才胚\力，物盡其用；隨著牽引車工作時長的增加，多車型甩掛能夠在更大優(yōu)化空間內(nèi)提高甩掛比、降低牽引車空駛率和空載距離、提高牽引車的使用效率和優(yōu)化車輛配置，進而降低網(wǎng)絡運營成本。在未來的研究工作中將增加針對不同區(qū)域甩掛運輸?shù)乃憷?，為公路港甩掛運輸企業(yè)提供更為精細的指導。