陳婉茹，張得志，梁一婧，曹健

(1.中南大學(xué) 交通運輸工程學(xué)院，湖南 長沙 410075；2.南京大學(xué) 工程管理學(xué)院，江蘇 南京 210046)

隨著經(jīng)濟全球化和電商行業(yè)發(fā)展速度的加快，我國的快捷貨運市場愈發(fā)活躍。降低快捷貨運成本成為物流企業(yè)提高核心競爭力的重要途徑之一。快捷貨物運輸涉及城市間干線運輸及城市末端支線配送2個系統(tǒng)，“高成本、低效率”的問題在快捷貨物公路干線運輸中尤為突出?？旖葚浳锔删€運輸系統(tǒng)依托跨越省、區(qū)(市)的骨干公路線，網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜；貨物流量大，但在時空上的分布不均，對其進行協(xié)調(diào)調(diào)度具有很高的難度。目前快捷貨物干線運輸采用“點對點”直達運輸模式，該模式下車輛往返服務(wù)于固定的始發(fā)終到樞紐，操作簡單，適用于人工調(diào)度，但是靈活性較差。在實際運營過程中發(fā)現(xiàn)，由于周轉(zhuǎn)需要，車輛在到達卸貨地點后，往往沒有足夠的時間停留等待至下一批回程貨物的到達，而只能即刻空載返回出發(fā)樞紐，由此，所產(chǎn)生的運輸稱之為單邊運輸。單邊運輸是導(dǎo)致我國快遞企業(yè)運營車輛空駛率超40%的一大元兇[1]，它的存在大大增加了單位貨物運輸成本。如何在全國性路網(wǎng)的基礎(chǔ)上，從運輸組織優(yōu)化的角度出發(fā)，減少快遞干線單邊運輸，是一個亟待解決的現(xiàn)實難題。國內(nèi)外學(xué)者對快捷貨物干線運輸優(yōu)化展開了研究：趙晉等[2]從網(wǎng)絡(luò)總成本最低的視角出發(fā)，構(gòu)建了允許直達的混合軸幅式快貨運輸網(wǎng)絡(luò)規(guī)劃決策模型，提高了服務(wù)時效性和服務(wù)水平；YU等[3]建立了快遞企業(yè)運輸網(wǎng)絡(luò)的雙層優(yōu)化模型，上層模型以總運輸成本最小為目標設(shè)計運輸網(wǎng)絡(luò)和分配運輸能力，下層模型以用戶均衡為目標計算鏈路流量；李文莉等[4]構(gòu)建了帶分支流向約束的樞紐選址模型，通過改變現(xiàn)有網(wǎng)點的從屬關(guān)系，構(gòu)建了軸輻式快捷貨運網(wǎng)絡(luò)，并設(shè)計了相應(yīng)的禁忌搜索算法；裴利奇等[5]在需求不確定的情境下，構(gòu)建了雙目標整數(shù)規(guī)劃模型確定了快貨運輸樞紐的選址，運用NSGA-Ⅱ方法求解；ZHANG等[6]研究了多式聯(lián)運下多主體的軸輻式快貨運輸網(wǎng)絡(luò)，同時考慮了二氧化碳定價、網(wǎng)絡(luò)末端配送和樞紐選址；張得志等[7]構(gòu)建了基于低碳經(jīng)濟視角的多模式快捷貨物物流網(wǎng)絡(luò)優(yōu)化決策模型，并設(shè)計了遺傳算法進行求解；MARTIN等[8]研究了大規(guī)模快貨運輸網(wǎng)絡(luò)結(jié)構(gòu)與配送時間、相關(guān)的定價方案和負載計劃的聯(lián)合優(yōu)化問題，以實現(xiàn)總利潤的最大化；QU等[9]在貨運需求不確定的背景下，構(gòu)建了混合整數(shù)規(guī)劃模型，解決內(nèi)陸公路干線運輸與水運的一體調(diào)度優(yōu)化問題；DRAG‐OM IR等[10]研究了跨國跨區(qū)域的大規(guī)模包裹運輸路線和多式聯(lián)運方式的選擇問題。目前快捷貨物干線運輸?shù)难芯恐饕獓@服務(wù)網(wǎng)絡(luò)的設(shè)計展開，學(xué)者們通過確定物流節(jié)點的規(guī)模、數(shù)量、選址、內(nèi)部布局，構(gòu)建了具有點點式、軸輻式、混合式等不同特征的快貨運輸網(wǎng)絡(luò)，實現(xiàn)各節(jié)點、路徑的合理匹配，達到整個物流系統(tǒng)中物流成本最少的優(yōu)化目標[11]。在運輸組織方面的研究主要從公路干線與其他運輸方式和運輸工具協(xié)同配置優(yōu)化的角度出發(fā)，圍繞“公鐵”聯(lián)運、“公水”聯(lián)運展開，鮮有學(xué)者研究單純的公路干線運輸車輛網(wǎng)絡(luò)路徑規(guī)劃問題，而針對干線運輸中的單邊運輸問題更是有待進一步研究[12]。基于上述分析，本文研究快捷貨物公路干線運輸組織優(yōu)化，主要貢獻如下：1)在分析快捷貨物公路干線運輸特征的基礎(chǔ)上，提出提升干線運輸效率的運輸組織模式；2)將快捷貨物干線運輸組織優(yōu)化問題抽象為考慮時間窗與路由限制的多車場車輛路徑優(yōu)化問題，構(gòu)建決策分析模型并設(shè)計了基于時空的三維改進禁忌搜索算法；3)以順豐速運的公路干線網(wǎng)絡(luò)優(yōu)化為例進行相應(yīng)實證分析，結(jié)果表明，對干線運輸路徑的合理規(guī)劃能夠一定程度上幫助企業(yè)解決現(xiàn)有的單邊空載浪費問題。

1 快捷貨物公路干線運輸組織優(yōu)化對策分析

快捷貨物公路干線運輸中單邊運輸產(chǎn)生的根本原因在于：各城市OD對之間發(fā)送與到達的貨流量不是一對一平衡匹配的，從而導(dǎo)致了點對運輸模式下的回程空載浪費?？梢酝ㄟ^以下4種改進的干線運輸組織模式來降低空載浪費。模式1：全循環(huán)運輸——由不同單程運輸接續(xù)銜接出發(fā)地和目的地，在構(gòu)成的環(huán)形路徑中只包含載貨弧段，不含空載弧段。模式2：半循環(huán)運輸——區(qū)別于全循環(huán)運輸，半循環(huán)運輸模式下的車輛環(huán)路中允許包含一段空載弧段。模式3：對開運輸——合并始發(fā)地和目的地相反的兩段單程運輸。模式4：擺渡運輸——將兩段相向行駛且始發(fā)地與目的地距離較近的單程運輸進行短途接駁。上述運輸組織模式示意圖如圖1所示。但值得注意的是，在實際生產(chǎn)過程中，整合弧段的邊際管理成本將隨著車輛路由弧數(shù)量的增加而不斷提高，因此在進行優(yōu)化的過程中需要根據(jù)生產(chǎn)經(jīng)驗對最大路由弧段數(shù)進行限制。

圖1 4種改進的干線運輸組織模式示意圖Fig.1 Diagram of four improved transportation organizationmodes

2 問題描述

快捷貨物干線運輸優(yōu)化問題實際上是一個定義在一個有向圖上的考慮時間窗和路由限制的多車場弧路由問題(Multi-depot Arc Route Problem w ith Time Windows and Routing Constrains,MDARP-TW-RC)，即在滿足車輛路由弧段數(shù)量限制及服務(wù)時間窗的約束下，找到車輛路由單程的最佳組合，以達到最小化運輸成本的目的。圖2為一個擁有10個中轉(zhuǎn)樞紐點，8個單邊運輸任務(wù)的網(wǎng)絡(luò)實例，為了便于區(qū)分，用矩形代表車輛始發(fā)和終到的中轉(zhuǎn)樞紐。優(yōu)化后，該網(wǎng)絡(luò)包含由10-7-6構(gòu)成全循環(huán)運輸、由2-1-5構(gòu)成半循環(huán)運輸、由3-4構(gòu)成對開運輸以及未被整合的單邊運輸8-9。

圖2 單邊運輸優(yōu)化網(wǎng)絡(luò)示意圖Fig.2 Unilateral transportation optim ization network

一般地，長途干線運輸車輛所走行的公路徑路是固定的，可以認為單程運輸中與里程相關(guān)的變動成本是一定的，即圖3中r1與r2的運輸成本是已知的。從而，快捷貨物干線運輸優(yōu)化問題需要考慮的變動成本為單程運輸銜接時車輛走行r3，r4及在樞紐點換裝所產(chǎn)生的成本。經(jīng)過這樣的抽象，可以將一次單程運輸看作一個“點”，將單程運輸起始點的時間窗視作該“點”的時間窗，將車輛完成單程運輸?shù)臅r間視為車輛離開該“點”的時間，將車輛在樞紐處的裝卸成本與運輸成本看作車輛途經(jīng)該“點”的成本，從而將MDARP-TWRC轉(zhuǎn)化為考慮時間窗和路由限制的多車場車輛路徑問題(Multi-depot Vehicle Route Problem w ith Time Windows and Routing Constrains,MDVRPTW-RC)。

圖3 MDARP-TW-RC轉(zhuǎn)化為MDVRP-TW-RCFig.3 MDARP-TW-RC to MDVRP-TW-RC

3 優(yōu)化模型

將問題定義在有向圖G=(V,A)上，其中V是單程運輸點集，A是由兩兩單程運輸點連接構(gòu)成的弧集。特別地對于?i?V有A的子集Ai滿足Ai={(j,k)|(j,k)?A,k≠i}。R為單程運輸需求集合，，，ar，br分別表示運輸需求r的起止點和起止時間。TT1，TT2，TT3分別表示車輛卸裝、卸空、裝載所需要的時間。dij表示點i和點j之間的距離，S表示車輛的平均行駛速度，TC表示單位距離的運輸成本，WC表示等待成本。Q表示一次運輸所包含的弧的最大數(shù)量。表示在線路中(除最末外)增加一個單程運輸點而帶來的路由弧段數(shù)的增加，當(dāng)為1，否則為2。表示在線路最末端增加一個單程運輸點而帶來的路由弧段數(shù)的增加，當(dāng)為0，否則為1。本文從宏觀角度出發(fā)，對有利于運營的單程線路組合進行發(fā)掘，做出如下假設(shè)：

1)干線運輸車輛從某樞紐出發(fā)，完成運輸任務(wù)后需返回所屬樞紐；

2)車輛空載運輸成本為載貨運輸成本的一半；

3)每個單程運輸僅由一輛車服務(wù)，且默認車輛能夠滿足裝載需求；

4)不考慮不同車型車輛在載重和體積上的差異；

5)不考慮路況變化對車速的影響，即車輛在運輸過程中的行駛速度是恒定的；

6)車輛到達時間滿足軟時間窗，當(dāng)車輛在某分撥中心的等待時間大于12 h時需加以懲罰。

表示單程i到達單程j起點并完成換裝的時間，表示單程j返回單程i起點并完成換裝的時間。表示從至開始單程j的等待時長，表示從至開始單程i時間的等待時長。表示從前單程起點i到后單程起點j的運輸成本，表示從末單程終點j返回首單程起點i的運輸成本。在運輸成本的計算中直接考慮了軟時間窗的懲罰，建模如式(1)～(6)：

在建模過程中，本文以一天為一周期，并用1 440m in表示。式(1)和式(4)將單程i與單程j間的接續(xù)時間依據(jù)和的位置關(guān)系劃分為2種情況，若則無需空載，車輛直接在進行卸裝作業(yè)；若則車輛需要增加一段長度為dn+i,ni的空載路由，并在和分別完成卸空，裝載作業(yè)。式(2)和式(5)計算了車輛到達單程運輸點至開始服務(wù)需要等待的時間。式(3)和式(6)依據(jù)等待時間是否超過閾值，計算了由單程運輸點銜接所帶來的成本，其中包括與走行距離相關(guān)的行駛成本及等待成本。

結(jié)合所討論的干線單邊運輸實際問題，本文建立了干線運輸優(yōu)化決策模型，該模型的實質(zhì)是多車場帶時間窗的車輛路徑優(yōu)化模型的擴展。不同于一般的多車場問題，出發(fā)樞紐也在決策的范圍內(nèi)，因此本文設(shè)計有二元決策變量xi,j,k，當(dāng)以i為起始點的運輸包含弧(j,k)時取1，否則取0。此外，還設(shè)計有整數(shù)決策變量oi，用以表示車輛途經(jīng)i點時已路由的弧段數(shù)。具體模型如式(7)～(13)：

模型的目標函數(shù)(7)為最小化運輸成本，采用逐弧段疊加的方法進行計算；約束條件(8)表示每個單程運輸點被且僅被訪問一次；約束條件(9)為流平衡約束，表示對于每個分撥中心而言到達車輛數(shù)等于出發(fā)車輛數(shù)；約束條件(10)和(11)對車輛路由弧段的數(shù)量加以限制；約束條件(12)和(13)對決策變量的取值進行了規(guī)定。本文所建立的非線性模型可以通過大M法轉(zhuǎn)化為混合整數(shù)線性規(guī)劃模型，但本研究的目的在于解決實際背景下的大規(guī)模優(yōu)化問題，無法用求解器在可接受的時間內(nèi)求得全局最優(yōu)解，因此不對其做過多贅述。

4 求解算法

本文研究的干線運輸優(yōu)化問題是多車場帶時間窗的VRP的延伸，屬于NP-hard問題。根據(jù)GENDREAU等[13-14]對求解VRP的一些現(xiàn)代啟發(fā)式算法的綜述，禁忌搜索是目前求解VRP的較為有效的方法。另外，禁忌搜索算法在求解多車場車輛路徑問題中也不斷得到成功的應(yīng)用[15-16]。因此，本文研究選擇設(shè)計禁忌搜索算法進行求解，并通過設(shè)計有效的初始解生成算法、鄰域結(jié)構(gòu)和禁忌規(guī)則，增強了搜索的多樣性，從而克服了啟發(fā)式算法容易過早收斂的缺點[17]。

4.1 初始解構(gòu)造

使用Clarke andW right節(jié)約算法[18]可以快速獲得一個初始解。首先，將單程點按照發(fā)車時間先后排列，并為每個單程點分派一輛車。然后，按照順序不斷嘗試合并2條路線，在尊重路由弧段數(shù)約束的情況下獲得最大的節(jié)約。當(dāng)沒有可行的合并時結(jié)束迭代，即得到初始解。

4.2 鄰域移動

為了盡可能擴大解的搜索范圍，在本文中，同時采用2個路徑間算子：點插入和點交換，對當(dāng)前解進行鄰域搜索。點插入算子將將某路徑的一個單程點插入另一路徑中，如圖4(a)所示，該操作可能產(chǎn)生或刪除路徑。點交換算子交換某路徑中的一個單程點與另一路徑中的一個單程點。如圖4(b)所示。

圖4 算子示意圖Fig.4 Diagram of operators

4.3 基于時空的禁忌規(guī)則

初始解的優(yōu)劣會直接影響算法的效率，但通過有效的禁忌規(guī)則可以降低搜索過程對初始解的依賴性[19]。本文設(shè)計了基于時空的禁忌規(guī)則，不同于傳統(tǒng)的禁忌規(guī)則，采用三維禁忌表，記錄改進發(fā)生時所作操作的客戶點及路徑。如圖5所示，每個點對應(yīng)一張n×n的禁忌表，一旦有改進操作發(fā)生在某點的某路徑組合間，則置相應(yīng)表中相應(yīng)組合的禁忌周期為禁忌期限TT。在下次迭代中，禁止點的操作發(fā)生在禁忌周期不為0的路徑組合間，除非改進后的解優(yōu)于歷史最優(yōu)解。每次迭代后，更新禁忌周期，釋放周期為0的路徑組合。

圖5 三維禁忌表示意圖Fig.5 Three-dimensional tabu list

4.4 解的評價函數(shù)及接受準則

每次迭代后，需要對所得到的鄰域解進行評估，以決定是否接受它，而只接受改進解的一般做法容易導(dǎo)致過早的收斂。本文采用Dueck提出的Record-to-Record Travel，RRT算法[20]定義一個鄰域解的閾值接受準則。設(shè)s*是歷史最優(yōu)解，s'是鄰域解。F(Δ)是解的評價函數(shù)，本文中直接采用優(yōu)化模型的目標函數(shù)對解進行評價。若F(s')

4.5 算法流程

為了描述方便，定義以下變量：當(dāng)前的迭代步數(shù)iter；最大的迭代步數(shù)max-iter；候選解集cand-list；當(dāng)前解S；最佳候選解S'；歷史最優(yōu)解S*。

算法流程如下。

步驟1：用節(jié)約算法得到初始可行解，并將其作為s和s*。

步驟2：初始化禁忌表，置iter為0。

步驟3：對s進行點插入鄰域搜索，并將產(chǎn)生的可行解放入cand-list中。

步驟4：對s進行點交換鄰域搜索，并將產(chǎn)生的可行解放入cand-list中。

步驟5：若cand-list為空則終止算法，否則轉(zhuǎn)步驟6。

步驟6：若cand-list存在優(yōu)于s*的禁忌解，則解禁該解作為s'；若整個cand-list都被禁忌，則解禁其中評價函數(shù)值最小的解作為s'；否則，從cand-list中選擇評價函數(shù)值最小的非禁忌解作為s'；根據(jù)RRT準則判斷是否接受s'作為當(dāng)前解s，更新禁忌表，iter的值加1。

步驟7：若F(s')

步驟8：若iter<=max-iter，則轉(zhuǎn)步驟3；否則，終止算法。

5 數(shù)值實驗

為了驗證本文提出的優(yōu)化方法的合理性和實用性，選取順豐速運部分干線單程運輸數(shù)據(jù)進行優(yōu)化決策，部分算例數(shù)據(jù)如表1所示。

表1 順豐干線網(wǎng)基礎(chǔ)數(shù)據(jù)Table 1 Basic data of SF trunk line network

結(jié)合實際生產(chǎn)運作過程對模型涉及參數(shù)進行標定：卸車作業(yè)的中轉(zhuǎn)時長為120m in，裝車作業(yè)及卸裝作業(yè)的中轉(zhuǎn)時長為240m in；車輛的平均行駛速度為1.167 km/m in，單位運輸成本為1元/km；每次運輸所包含的弧段(包括空駛)應(yīng)小于4段；等待成本為130元。置最大迭代次數(shù)設(shè)置為500，禁忌期限為10。

5.1 求解結(jié)果

輸入228條順豐速運干線運輸中的單程運輸數(shù)據(jù)，若未經(jīng)優(yōu)化，這些單程運輸均以“點對點”直達運輸?shù)哪Ｊ竭M行，其總運輸成本達388 637.92元。依據(jù)本文所提出的模型算法對上述算例進行優(yōu)化，算法運行10次后，得到最優(yōu)解的路徑數(shù)目為201條，總運輸成本降低至373 751.56元，節(jié)省了14 886.36元，節(jié)省率達3.83%，且得到最優(yōu)解的最優(yōu)計算時間為5.87 s。

最終輸出的線路中，包含18條半循環(huán)模式線路，4條擺渡模式線路，將部分優(yōu)化后的線路羅列如表2。若將上述結(jié)果應(yīng)用到快遞企業(yè)自有車輛的常態(tài)化運行中，將帶來非?？捎^的運輸成本節(jié)省。此外，隨著包裹量的不斷增加，快遞企業(yè)自有車輛承擔(dān)著巨大的運輸壓力。作為應(yīng)對策略，公司可以使用第三方物流(3PL)供應(yīng)商使用外包車輛。在一定的車輛租借成本下，快遞企業(yè)需要從戰(zhàn)略層出發(fā)，確定外包路線的外包策略，而上述結(jié)果可以很好地輔助相關(guān)物流企業(yè)進行干線外包路線規(guī)劃的決策。

表2 部分優(yōu)化結(jié)果Table 2 Partialoptim ization results

5.2 敏感性分析

干線運輸主要依托于高速公路，其路況有所波動，例如，在節(jié)假日的時候整體路況都較為擁堵，車輛的到車時間會相較于平均時間有所延誤，而在平日，路況更為通暢時，車輛的到車時間會相較于平均時間有所提前。基于此，本文對所有車輛的到車時間均提早1 h和2 h，及所有車輛到車時間延遲1 h和2 h的4種不同情況進行了分析。如圖6所示，整合線路數(shù)量和總成本隨著到車時間的變化在一定水平上波動。但運輸成本和優(yōu)化線路在不同到車時間下無明顯變化規(guī)律。究其原因，到車時間的提早和推遲都會改變單程接續(xù)的等待時間，從而影響整合優(yōu)化的最終方案。到車時間對優(yōu)化的影響體現(xiàn)在最終線路的優(yōu)化方案上，將提前2 h的整合結(jié)果與推遲2 h的結(jié)果進行可視化，如圖7所示。上述結(jié)果共同表明快捷貨物干線運輸?shù)膭討B(tài)優(yōu)化值得進一步探討。

圖6 線路數(shù)和成本的變化趨勢Fig.6 Changing trendsof the total costand the number of routes

圖7 不同到車時間下優(yōu)化方案的示意圖Fig.7 Diagram of the optim ization scheme fordifferentvehicle arrival time

6 結(jié)論

1)在全國性路網(wǎng)的基礎(chǔ)上，將單程運輸整合成全循環(huán)、半循環(huán)、對開、擺渡等不同模式，可以有效降低車輛的空載率，從而降低運輸成本。

2)快捷貨物干線運輸優(yōu)化問題經(jīng)過合理的簡化和抽象，可以轉(zhuǎn)化為一個多車場車輛路徑擴展問題，并借助弧流模型進行表述。

3)快捷貨物干線運輸優(yōu)化問題是NP難問題，需要借助啟發(fā)式算法進行求解。在順豐大規(guī)模干線運輸網(wǎng)絡(luò)的實例測試中，本文所設(shè)計的基于時空的三維改進禁忌搜索算法可以在5.87 s左右就求得該算例的滿意解，且結(jié)果顯示優(yōu)化方案的運營成本比實際運營方案節(jié)約3.83%。

4)路況會對車輛的到車時間產(chǎn)生直接的影響，從而影響整合優(yōu)化的最終方案。動態(tài)環(huán)境下的快捷貨物公路干線運輸組織優(yōu)化值得進行更加深入的研究。