彭 勇，高 鶴

(重慶交通大學(xué)交通運輸學(xué)院，重慶400074)

0 引 言

帶交換箱的甩掛運輸(Swap-body Vehicle Routing Problem,SB-VRP)由于具有對不同道路條件的靈活性、提高運輸效率、減少運輸成本的潛力而受到企業(yè)與學(xué)者關(guān)注.該問題可以看作是卡車和拖車路線問題(TTRP)的一個變體[1].本文研究的小型交換箱甩掛運輸車可以由一節(jié)交換箱組成的卡車去服務(wù)通行道路有限制(道路條件不允許較大車輛通行)的限制客戶點(限制點)，也可以由帶兩節(jié)交換箱組成的整車去服務(wù)通行道路沒有限制(道路條件允許較大型車輛通行)的靈活客戶點(靈活點)，交換箱可臨時存放于甩掛點.

在配送實踐中，客戶往往會要求在特定的時間窗內(nèi)為其提供配送服務(wù)，使帶時間窗的路徑優(yōu)化成為學(xué)者關(guān)注的內(nèi)容.大量學(xué)者開始研究VRPTW[2-3].另一方面，現(xiàn)實物流配送中，司機完成一次配送任務(wù)后可能距離下班還有一段時間，為充分利用司機日常工作時間，可安排新的配送任務(wù)(多行程)實現(xiàn)進一步的成本節(jié)約[4].關(guān)于帶時間窗的多行程路徑優(yōu)化問題，國內(nèi)外研究較少[5-7].

隨著甩掛運輸?shù)呐d起，學(xué)者開始注意到將甩掛或交換箱應(yīng)用到物流配送領(lǐng)域可帶來配送效率的提升.邊展用兩階段啟發(fā)式算法研究帶時間窗的甩掛運輸路徑優(yōu)化，對整車的實際配送有一定的使用價值[8].Túlio A.M.提出了啟發(fā)式的隨機局部搜索算法來研究SB-VRP[9].但已有的SB-VRP研究尚未同時考慮實際配送中可能存在客戶時間窗要求且企業(yè)允許多行程配送情況，本文將研究時間窗約束下多行程SB-VRP路徑優(yōu)化問題.

1 模型構(gòu)建

1.1 問題假設(shè)與符號說明

問題假設(shè)：

(1)限制點只能由卡車服務(wù)，靈活點既可以卡車服務(wù)也可以用整車服務(wù).

(2)每輛車每個任務(wù)的始發(fā)與結(jié)束都是在配送中心.

(3)本研究為小型交換箱，用于城市物流配送，通常單個客戶的需求量相對較小，假設(shè)每個客戶點被配送一次，同時要滿足每個客戶點的需求量.

(4)任一配送路線上客戶點的總需求量不超過所用運輸車最大允許載荷.

(5)每輛車的總工作時間不超過司機的單日工作時間.

(6)每輛車到達客戶點的時刻就是開始服務(wù)的時刻.

(7)不考慮道路擁堵及時變情況，車輛的平均行駛速度均相同.

圖1為車輛示意圖，圖2為SB-VRP 配送路徑的示意圖.

令有向網(wǎng)絡(luò)圖G=[N,A]，其中，N表示所有節(jié)點的集合，N=Ns+Nr+Nf+{0}，Ns表示甩掛點集合，Nr表示限制點集合，Nf表示靈活點集合，0代表配送中心，A為從客戶點i到客戶點j的邊集，A={(i,j)：i,j∈N,i≠j}.K為卡車集合，E為交換箱拖車集合，R為行程集合.

圖1 卡車與整車示意圖Fig.1 Truck and complete vehicle schematics

圖2 不同車輛的運輸路線圖Fig.2 Transport road map for different vehicles

(1)符號與集合.

i,j——節(jié)點，i,j∈N；

k——卡車，k∈K；

e——交換箱拖車，e∈E；

r——行程，r∈R.

(2)參 數(shù).

Cij——卡車從i點到j(luò)點的行駛時間；

bk，be——卡車、交換箱拖車行駛單位里程所需費用；

ck，ce——卡車、交換箱拖車的使用費用；

f——雇傭司機的費用；

Qk，Qe——卡車、交換箱拖車的額定裝載量；

qi——節(jié)點i的需求量；

Fdelay——車輛晚于客戶時間窗所產(chǎn)生的單位時間懲罰成本；

——節(jié)點i時間窗的上限；

——車輛到達節(jié)點i的時刻；

——車輛在i點的服務(wù)時間；

h——司機在1 d 允許工作的最長時間(h)；

v——車輛的平均速度；

σ——晚于時間窗60 min以后的懲罰系數(shù).

(3)變 量.

——0-1 變量，當邊（i,j）之間有直接路徑且屬于k的第r次行程時，1，否則0，?i,j∈N,?k∈K,r∈R；

——0-1 變量，當邊（i,j）之間有直接路徑且屬于k的第r次行程時，1，否則0，?i,j∈N,?e∈E,r∈R；

yk——0-1變量，卡車k被選中時，yk=1，否則yk=0；

ye——0-1變量，卡車e被選中時，ye=1，否則ye=0.

1.2 模型建立

目標函數(shù)為

約束條件為

式(1)為最小化整個配送過程中的成本，包括車輛派遣成本Z1、運輸成本Z2和時間懲罰成本Z3.式(2)為車輛派遣成本，包括卡車和交換箱拖車的啟動費用及司機工作費用.式(3)為運輸成本，包括卡車和整車運輸費用.式(4)為時間懲罰成本，即車輛到達客戶點的時刻晚于客戶時間窗上限會有不同的懲罰成本.式(5)為晚于客戶時間窗的懲罰成本.式(6)為車輛到達客戶點j的時間約束.式(7)為路網(wǎng)中任意客戶點(不包括甩掛點)有且僅有一條行程為一次的卡車服務(wù)路線.式(8)為該路徑是否為允許甩掛的路徑，若是僅有一次甩掛操作.式(9)為路網(wǎng)中經(jīng)過靈活點的交換箱拖車連線最多為1，也可能不存在.式(10)為車輛進出節(jié)點的平衡約束.式(11)為車輛每次行程最多能從配送中心出發(fā)一次.式(12)為路徑中交換箱拖車取值不大于1，卡車一定為1.式(13)為車輛載重約束.式(14)為卡車完成r次行程的總時間不得超過司機每日工作的最長時間.

2 算法設(shè)計

遺傳算法作為一種常用的全局優(yōu)化算法，在求解路徑優(yōu)化問題上具有較好的效果，故在傳統(tǒng)遺傳算法的基礎(chǔ)上提出基于裝箱算法和時間窗局部優(yōu)化策略的混合啟發(fā)式遺傳算法，對本文提出的問題進行求解.

2.1 編 碼

采用隨機小數(shù)編碼[10].假設(shè)一條路徑允許形成最多的任務(wù)數(shù)為ζ，限制點個數(shù)Nr，靈活點個數(shù)Nf，則染色體長度為(Nr+Nf+ζ-1).假設(shè)有11個客戶(包含5 個限制點客戶和6 個靈活點客戶)，最多有4 個配送任務(wù)，則染色體長度為11+4-1=14.以圖3給出的小數(shù)編碼為例，長度為14的小數(shù)向量表示一條染色體.

圖3 小數(shù)編碼示意圖Fig.3 Decimal coding schematic diagram

2.2 解 碼

(1)解碼產(chǎn)生初始路徑.

按升序規(guī)則，將對應(yīng)基因位的小數(shù)用順序號代替，將上述小數(shù)編碼映射為1到(Nr+Nf+ζ-1)的整數(shù)排列[11].令限制點的編號為1～Nr，靈活點的編號為Nr+1～Nr+Nf，分隔符編號為Nr+Nf+1～Nr+Nf+ζ-1.分隔符的作用在于將整條體染色體進行分割，分割之后的每一小段染色體都代表一條完整的配送路徑.以圖3為例，圖4給出了一個產(chǎn)生初始路徑的實例，規(guī)定小數(shù)排列的后三位為分隔符即12、13、14，對應(yīng)路徑如圖5所示.

圖4 初始路徑Fig.4 Initial path

圖5 初始路徑示意圖Fig.5 Initial path diagram

(2)客戶配送順序的優(yōu)化.

對于路徑中既有限制點又有靈活點，且配送總量超過卡車容量卻小于帶交換箱的整車容量，采取限制點優(yōu)先配送的方案，得出優(yōu)先配送限制點的路徑調(diào)整及路徑示意圖如圖6和圖7所示，在圖中1～5為限制點.

圖6 客戶順序優(yōu)化路徑調(diào)整Fig.6 Customer order optimization path adjustment

圖7 客戶順序優(yōu)化路徑示意圖Fig.7 Customer order optimization path diagram

(3)考慮車輛載重限制的優(yōu)化.

有甩掛操作的路徑中：首先，判斷配送任務(wù)中限制點總需求量是否超出Qk，將超出Qk的限制客戶點從該配送任務(wù)中拿出；然后，再將整個配送任務(wù)中超出Qk+Qe的靈活客戶點拿出；最后，找出限制點需求加起來小于Qk的任務(wù)，將上一步取出的限制點放入，對待靈活點同理，如果沒有符合要求的任務(wù)，則開啟一個新任務(wù)將其放入.考慮車輛載重限制的路徑調(diào)整及路徑示意圖如圖8和圖9所示，圖中數(shù)字分別代表不同的客戶，1 為超出Qk的客戶點，6為超出Qk+Qe的客戶點.

圖8 車輛載重優(yōu)化路徑調(diào)整Fig.8 Vehicle load optimization path adjustment.

圖9 車輛載重優(yōu)化路徑示意圖Fig.9 Diagram of vehicle load optimization path

(4)添加甩掛點.

對于既有限制點又有靈活點，且配送總量超過卡車容量卻小于帶交換箱的整車容量的路徑，在以上調(diào)整后，啟用距離第一個限制點最近的甩掛點作為該路徑的甩掛點.整車從配送中心出發(fā)到甩掛點將第二個交換箱放下，變成卡車去服務(wù)限制客戶點，完成配送后回到甩掛點拖帶上交換箱，形成整車繼續(xù)為靈活客戶點服務(wù)，路徑調(diào)整及車輛行駛路徑示意圖如圖10和圖11所示，圖中15代表甩掛點.

圖10 添加甩掛點路徑調(diào)整Fig.10 Add swing point path adjustment

圖11 添加甩掛點路徑示意圖Fig.11 Path diagram of adding swing point path

(5)任務(wù)安排策略.

為最大化利用司機的工作時間，采用一維裝箱算法對司機進行多配送任務(wù)指派.將司機1 d的工作時長看作是一個箱子容量，某司機在完成一個配送任務(wù)后返回配送中心的時刻距離下班時刻的這段時間，相當于裝箱后箱內(nèi)剩余容積.每個配送任務(wù)的總時間就相當于一件物品，將該物品放入箱中后，若該箱子還可以容納其他的物品，則將其他物品裝入該箱子，以此類推，但規(guī)定每個箱子最多裝3 個物品.2 個或3 個物品裝入一個箱子代表一個司機在1 d的工作時間內(nèi)要完成2個或3個配送任務(wù).多行程安排及配送路徑優(yōu)化示意圖如圖12和圖13所示.

圖12 任務(wù)安排策略路徑調(diào)整Fig.12 Task scheduling policy path adjustment

圖13 任務(wù)安排策略路徑示意圖Fig.13 Task scheduling policy path diagram

(6)時間窗局部優(yōu)化策略.

既要提高客戶滿意度，又要保證運輸成本最??；同時配送車輛到達客戶點的時刻不得超過客戶時間窗太久，否則會受到相當大的懲罰成本.因此，在圖2～圖9中采用時間窗局部優(yōu)化策略對路徑中客戶的時間窗進行排序.在不改變單個配送任務(wù)中需要配送的客戶點的基礎(chǔ)上，對時間窗較早的客戶點先配送.對應(yīng)添加甩掛點的配送路徑，對限制點和靈活點的時間窗分別調(diào)整.時間窗局部優(yōu)化策略路徑調(diào)整及配送路徑優(yōu)化如圖14和圖15所示.

圖14 時間窗局部優(yōu)化策略路徑調(diào)整Fig.14 Local optimization strategy path adjustment of time window

圖15 時間窗局部優(yōu)化策略路徑示意圖Fig.15 Schematic diagram of local optimization strategy path for time window

2.3 遺傳操作

選用輪盤賭進行個體選擇，選中概率與個體適應(yīng)度呈正相關(guān)，被選中的個體隨機配對；采用二進制單點交叉操作，將交叉點之前或之后的部分互換；使遺傳算法具備局部隨機搜索能力且維持群體多樣性，有效預(yù)防早熟收斂現(xiàn)象的產(chǎn)生.本文既要保留優(yōu)秀個體又要防止過早收斂采用單點變異操作.

3 數(shù)值實驗

3.1 算例描述

采用MATLAB2014b 編程，在一臺CPU 型號為Intel Core I5-8265U、8 G內(nèi)存、64位操作系統(tǒng)的計算機上運行.

采用Solomon標準實例數(shù)據(jù)集R101數(shù)據(jù)生成案例，如圖16所示，為驗證模型與算法的可靠性，增加多個數(shù)據(jù)集進行算例分析.將配送中心定為第121 個坐標點，依次選擇坐標點111～120 為甩掛點，坐標點1～40為靈活客戶點，坐標點41～90為限制客戶點.令卡車與帶交換箱的整車的最大裝載量分別為200和400，車輛平均行駛速度為1，卡車與交換箱的啟用成本均為1，單位行駛成本為1，帶交換箱的整車的單位行駛成本為1.5，甩掛點的啟用成本為5，司機日常允許的最長工作時間為8 h，單日薪資為10，時間窗調(diào)整為原數(shù)據(jù)的2.4 倍.時間懲罰成本呈折線型，單位時間的懲罰成本為0.8，晚于時間窗60 min后的懲罰系數(shù)為1.5.

3.2 有效性實驗

為驗證算法的有效性，初始種群的規(guī)模N=100，交叉概率Pc=0.9，變異概率Pm=0.4，最大迭代次數(shù)M=1 000.從圖17中看出，在迭代次數(shù)為450 次左右時，得到最優(yōu)解并進入收斂狀態(tài).算法連續(xù)運行10 次得到最優(yōu)解如表1所示，結(jié)果偏差為9.1%，在可以接受的范圍(15%).10 次最好解配送路徑如圖18所示.為更好地驗證算法的可靠性和適用性，增加多個數(shù)據(jù)集的對比實驗，實驗結(jié)果如表2所示.實驗結(jié)果表明，該算法針對所提出的問題，求解質(zhì)量和穩(wěn)定性都較好.

3.3 多行程策略有效性分析

在M=500，N=100 時，對比是否允許采用多行程策略的最優(yōu)配送路徑與迭代收斂圖，如圖19所示.采用多行程策略運輸路徑的最小總配送成本較小，啟用的車輛數(shù)目也會減少.從表3清晰地看出，運輸車輛采取多行程策略與未采取多行程策略得到的最優(yōu)路徑的平均運輸成本分別為1 562.3和3 295.5.結(jié)果說明，多行程策略對路徑優(yōu)化及司機工作時間的利用率影響明顯.

圖16 R101 實驗數(shù)據(jù)點分布圖Fig.16 Distribution of experimental data points

圖17 迭代收斂圖Fig.17 Iterative conver gence diagram

圖18 最優(yōu)配送路徑圖Fig.18 Optimal distribution path diagram

表1 求解最優(yōu)解結(jié)果Table1 Results of solving optimal solution

表2 不同數(shù)據(jù)集對比結(jié)果Table2 Comparison results of different data sets

圖19 有無多行程策略對比圖Fig.19 Comparison of multi-trip strategies

3.4 根據(jù)客戶時間調(diào)整策略有效性分析

如表4和圖20所示，對比是否采用客戶時間窗調(diào)整策略的最優(yōu)配送路徑與迭代收斂圖可以看出，算法中采用客戶時間窗調(diào)整策略后，在滿足時間窗的客戶點數(shù)量、最小運輸成本、運輸途中的總延誤時間這3個方面，都比不采用客戶時間窗調(diào)整策略算法得到的結(jié)果好.

表3 多行程策略結(jié)果Table3 Results of multi-stroke strategy

表4 客戶時間窗調(diào)整對比結(jié)果Table4 Comparative results of customer time window adjustment

圖20 客戶時間窗調(diào)整最優(yōu)解對比圖Fig.20 Comparison diagram of optimal solution for customer time window adjustment

3.5 時間懲罰系數(shù)靈敏度分析

對比分析不同時間懲罰系數(shù)得出，懲罰系數(shù)對最小運輸成本及最優(yōu)運輸路徑均有影響，如圖21和圖22所示.在現(xiàn)實生活中，不同客戶對時間窗需求的嚴格程度不同，可通過調(diào)整時間懲罰因子對路徑安排進行調(diào)整，在客戶滿意與運輸成本間尋求平衡.

4 結(jié) 論

在城市及近郊的物流配送環(huán)境背景下，研究帶時間窗的多行程SB-VRP 問題.為解決該問題，設(shè)計了基于遺傳算法和裝箱算法的混合啟發(fā)式算法，并結(jié)合時間窗、多行程等約束條件進行數(shù)學(xué)建模，使用經(jīng)典的Solomn數(shù)據(jù)集進行數(shù)值實驗，驗證所提算法具有較高的可行性和實用價值.

圖21 不同時間懲罰系數(shù)對比圖Fig.21 Comparison diagram of different time penalty factors

圖22 不同時間懲罰系數(shù)的路徑圖Fig.22 Path diagram of different time penalty coefficients

由于實際路徑的時間很大程度是受交通流影響的，影響因素有很多種，如時變、擁堵、交通事故、天氣原因等，將這些因素考慮在內(nèi)的話，優(yōu)化過程會比較復(fù)雜，后續(xù)可以繼續(xù)深入研究.同時求解路徑優(yōu)化的算法有很多種，比如蟻群算法、神經(jīng)網(wǎng)絡(luò)、局部搜索等，本文采用的遺傳算法是較為經(jīng)典與傳統(tǒng)的，后續(xù)研究可以進行多種方法對比與改進.