基于軟時間窗的產品配送與安裝相分離的車輛調度優化

龐海軍，丁以中

(上海海事大學 科學研究院，上海 201306)

0 引言

近些年，電子行業在售后服務方面發生巨大的變化，許多新興產品不僅需要配送，而且需要專業的安裝.它們包括掛壁式電視機(家庭影院系統)、洗衣機和干衣機、帶有凈水系統的冰箱、特殊烹調臺面、數控機、電腦服務器等.然而，由于維持全國配送和客戶服務網絡的費用太高，企業采取將配送業務外包給第三方物流企業的方法，僅保留自己的服務隊伍.于是，電子行業中出現產品配送與安裝相分離的現象.依據這一特點，本文研究一種變形的車輛調度問題(Vehicle Routeing Problem，VRP)，以滿足其獨特的物流配送需求.

KIM 等［1］首先對此種變形的VRP 進行研究.他假設安裝車輛必須在配送車輛訪問(或者到達)那個顧客之后，在服務水平之內訪問顧客，從而保證這兩種類型的車輛同步，以滿足顧客配送和安裝的服務質量.在他們的研究中，可以將服務水平看作是硬時間窗［2］VRP 的變形.當前，對此種變形的VRP 的研究都是在硬時間窗的約束條件下對模型進行的研究，然而在實際物流配送中其復雜程度遠超過于此.本文在前人研究的基礎上考慮在軟時間窗［3］約束下的VRP，因為軟時間窗與實際情況更接近.此約束條件既可滿足顧客的服務質量，同時又可兼顧企業的利潤最大化.

可以將此變形的VRP 看作是兩個傳統VRP 的組合:一個是配送車輛的VRP，它具有容量限制的VRP(Capacity VRP，CVRP)的特點［4-5］;另一個是安裝車輛的VRP，它具有帶時間窗VRP 的特點［6-7］.由于該模型的復雜程度遠遠超過經典VRP 模型的復雜程度，即使采用啟發式算法編程求解也很復雜，KIM 等［1］引入層次的概念將原問題劃分為若干子問題的組合，從而降低問題的規模.分層后的模型是早被國際證實的NP 難問題，采用正常方法求解十分困難，因此可利用遺傳算法(Genetic Algorithm，GA)在一個合理時間內有效解決所考慮的問題.

繼續采用層次的概念將原問題變為兩個子問題的組合，即:第一階段是配送車輛的VRP，確定配送車輛的路線和調度;第二階段是安裝車輛帶軟時間窗的VRP(VRP with Soft Time Window，VRPSTW)，基于第一階段的計算結果，獲得第二階段安裝車輛的路線和調度.對大量不同規模例子的的計算表明:文中所采用的分層GA 的可行性和有效性;第一階段的最好結果并不一定是原問題的最佳結果.該研究還可以對制訂配送車輛和安裝車輛調度的有效管理計劃提供幫助.

1 基于軟時間窗的配送和安裝車輛調度優化模型

1.1 問題描述與假設

給定一配送中心和多個不同的需求點，已知配送中心擁有兩種類型的最大車輛數，以及每個需求點(客戶)的位置，需求數量(不超過貨車最大載重量)及是否需要安裝.對于只需要配送的顧客點，只允許一輛配送車輛訪問一次;對于需要配送和安裝的顧客，只允許一輛配送車輛和一輛安裝車輛分別訪問一次.所有車輛開始從同一配送中心出發對顧客進行服務，安裝車輛可以在配送車輛之前訪問顧客，這就在對應的顧客位置產生安裝車輛的等待時間，超過規定時間就要受到一個與時間成正比的懲罰.如果安裝車輛在配送車輛之后訪問客戶，若不能在顧客可以忍耐的時間內到達，就要受到一個與時間成正比的懲罰.車輛完成服務后返回配送中心，所有客戶的需求都必須滿足.求:如何安排配送車輛和安裝車輛的路線，使整個服務過程總時間最少，總時間包括固定安裝時間、等待時間及懲罰時間、行駛時間.圖1 顯示服務水平為軟時間窗的VRP 的例子.

圖1 車輛路徑問題實例

對上述問題描述，假設以下幾點成立:

(1)不允許車輛超載;

(2)配送中心有足夠供調度的車輛，且每輛車有最大的運行時間;

(3)所有車輛單位時間內行駛的路程相同，且各客戶點與配送中心以直線連接;

(4)貨物的裝卸時間忽略不計.

1.2 符號說明

為了建立配送車輛和安裝車輛調度模型，設配送中心為0，顧客點為N(位置1 到N)，同時要求配送和安裝的顧客屬于A(|A|≤N)，定義以下參數:

N為顧客數量;K為配送車輛數量;S為安裝車輛數量;A為同時需要配送和安裝的顧客集合;Tij為車輛從顧客i 行駛到顧客j 的時間;Di為顧客i 的需求量;VC為配送車輛的容量;Ri為顧客i 處安裝所需時間，i∈A;OT為車輛循環一次的最大操作時間;M為一個很大的實數;ei為配送車輛到達顧客i 的時間，i∈N;fi為安裝車輛到達顧客i 的時間，i∈A;Pi為安裝車輛到達顧客i 的懲罰，i∈A;uip為配送車輛p 訪問位置i 的順序數;viq為安裝車輛q 訪問位置i 的順序數.

1.3 VRPSTW 模型

所考慮的問題可以用一個混合整數非線性規劃(Mixed-Integer Nonlinear Programming，MINP)模型描述，其目標是使所有配送車輛和安裝車輛的總運行時間最少，決策變量提供配送車輛和安裝車輛的最佳路徑和調度.模型如下:

在VRPSTW 數學模型中，將運行距離或運輸費用統一轉換成運行時間在模型中體現，目標函數是所有配送車輛和安裝車輛的總運行時間最小.式(2)和(12)限制從配送中心出發的車輛;約束(3)，(4)，(5)，(13)，(14)，(15)分別保證車輛都由配送中心出發并最終回到配送中心;約束(6)，(7)，(16)，(17)表示每個客戶只能受到一輛車服務并且每個客戶都得到服務;約束(8)表示每輛車所運送的貨物重量不能超過車輛載重的限制;約束(9)和(18)表示防止車輛在內部出現子循環;約束(10)和(19)表示車輛在客戶點不動時為零;(11)和(20)為變量取值約束;式(21)表示車輛從配送中心出發和安裝時間為零;約束(22)表示配送車輛p 到達顧客點i 的時間加上i 到j 的行駛時間，小于等于車輛到達j 的時間;約束(23)表示安裝車輛q 到達顧客點i的時間加上在i 處的等待時間、為顧客i 服務的時間、i 到j 的行駛時間總和，小于等于車輛到達j 的時間;約束(24)和(25)分別表示配送車輛和安裝車輛的最大操作時間;約束(26)為延遲懲罰函數.

圖2 懲罰函數

軟時間窗約束在這里被定義為一個懲罰函數，見圖2.

在這種懲罰函數中，安裝車輛只有在配送車輛到達時間ei之后才能開始服務，若提前到達將等待，當等待時間大于a 時，將有一個等待的機會成本發生.當車輛到達的時間在［ei-a，ei+b］范圍內無須罰款，而到達時間在ei+b 之后，將受到一個與遲到時間成正比的懲罰.當車輛到達時間早于ei-a 時，也將受到類似遲到的懲罰，其中:fi是安裝車輛到達顧客點i 的時間，M1和M2是等待或遲到時最低(固定)成本，u1是每單位等候時間的成本，u2是每單位時間的遲到罰款.

1.4 算法設計

由于VRP是世界公認的NP 難問題，本文所研究的變形VRP 更是在經典VRP 上的疊加，困難度遠超經典VRP.若采用直接的方法求解，很少的客戶點求解規模也很大，即使采用啟發式算法編程求解也非常復雜.為了獲得原始問題的良好解決方案，本文在文獻［1］的基礎上繼續引入分層思想將原問題分為兩個階段，每階段包括一個子問題.第一階段的子問題是一個配送車輛的VRP，解決配送車輛的路徑和時間安排;第二階段的子問題是一個安裝車輛的VRPSTW 問題.第一階段子問題是原問題的部分解決方案，同時也用作第二階段的子問題數據輸入部分.依據第一階段子問題提出的部分解決方案，確定第二階段子問題中安裝車輛的路徑和時間安排方案.安裝車輛的路徑和時間安排也是原問題的部分解決方案.解決第二階段的子問題后，兩種類型車輛的協同問題也就得到解決.最后，兩個子問題的部分解決方案也就是原來問題的解決方案.

通過分層方法將原問題劃分為兩個階段的子問題，從而簡化原問題的規模和復雜度.對于規模不太大的問題，可以通過LINGO 求得目標函數的精確解.但LINGO 不適用于大規模的問題，本文通過GA求解，只能得到近似解.通過利用LINGO 9.0和GA分別求得精確解和近似解，并對兩種結果進行比較分析.

2 算 例

設有1個配送中心和16個顧客點，其中有7個顧客點同時需要配送與安裝.假設所有客戶隨機位于50 ×50 的正方形上，并且將配送中心設在正方形的中心位置.為了便于對GA 以及分層方法進行檢驗，假設隨機產生的坐標點、每個客戶點的需求量以及客戶是否需要安裝見表1.假設配送車輛與安裝車輛的速度相同并且行駛時速度V=1 m/min 不變，配送車輛的最大載重單位為15個(不允許超載)安裝時間，R=10 min 不變.懲罰函數的參數如下:M1=M2=0，u1=2 min，u2=2 min，a=10 min，b=10 min.

表1 客戶點的編號、坐標、需求量、安裝與否

2.1 精確算法

所有求解計算都在CPU為酷睿雙核2.40 GHz，內存為4 GB 的計算機上實現，使用LINGO 9.0 編程求解算例.為了便于LINGO 9.0 求解并提高求解速度，對模型中的一些非線性約束進行變換，例如將約束(25)轉換成fj＜OT最終運行1 h 5 min 7 s，求解得目標函數值及配送車輛和安裝車輛的最優路徑結果見表2.

表2 最優解和近似解

2.2 GA 近似算法與近似解

由于精確算法的求解過程耗時過長，不適合實際配送企業的決策，本算例采用GA 進行求解.GA由HOLLAND(1975)首先提出.由于它能在一個合理的時間內取得解決復雜優化問題的良好結果，已被廣泛應用.特別是近幾年的基于GA 的啟發式搜索策略［8-10］，就是為了增強解決VRPSTW 問題的效果.

本文采用基于自然數的編碼方式［10］.由于車輛數可事先估出，故進化群體中的一個染色體可以表示為:(0，i11，i12，…，i1s，0，i21，…，i2t，0，…，0，im1，…，imv，0).其中，自然數ikj表示客戶點的編號，染色體的總長度為N+m+1，0 代表配送中心，一共有m+1個0 把整個染色體分成m 段，即代表m個路徑.

適應度函數的設計，對于第一階段的非滿載CVRP，將容量約束式(7)變換為目標函數的一部分:

對于第二階段的安裝車輛VRPSTW，使用如下目標函數式的一部分:

一般地，適應度函數要求非負，所以將目標函數變換為適應度函數，即fi=1/Zi.式中:fi為染色體i的適應值;Zi為染色體i 對應的經過約束處理后的目標函數式(27)或(28).

對于染色體的交叉與變異，采用文獻［11］中設計的最大保留交叉來保證群體多樣性，其具體操作過程為:如果染色體交叉點處的兩個基因為0，直接進行PMX［2］(部分匹配交叉)運算;如果染色體交叉點處的基因不全為0，則將交叉點左移(右移)，直到左右兩個交叉點處的基因都為0，再進行PMX 運算.變異采用文獻［12］中的2-交叉變異，即隨機選擇一個染色體的兩個非零元素，交換這兩個元素的位置生成新的染色體.

算法中的各參數:交叉率pc=0.85，變異概率pm=0.3，種群規模為30，最大迭代次數為100;計算過程使用C#語言編程求解，第一階段和第二階段的子問題分別經過42 次和31 次迭代，耗時分別為54 s和32 s，GA 的收斂過程見圖3，可行最優解見表2.

圖3 GA 的收斂過程

此外，為了進一步驗證采用分層的GA 的有效性和可行性，將算例中的客戶點增加至30個，其中需要安裝的客戶點為10個，每個顧客的需求量是1～4個，6 輛配送車輛和2 輛安裝車輛.求解過程中總的運算時間為125 s，運算結果為843.4 min，運行路徑見圖4(配送中心出發到客戶點和返回配送中心的路線省略).

圖4 車輛路徑計算結果

2.3 求解方法有效性分析

為了說明采用分層的GA 的有效性，首先用LINGO 9.0 求解出該算例以最小運行時間為目標函數的車輛行駛路徑結果;再用分層的方法將模型分為兩個子問題考慮;最后通過GA 求解近似結果.從圖3中可以看出，雖然近似解結果不如精確結果優異，但是可以說明采用分層的GA 所求結果的可行性.由于LINGO 9.0 只能求解較小規模的MINP 模型，且費時較長，在現實生活中物流配送量往往很大，要求在合理的時間得到配送方案，精確算法就不適合，而GA可以在一個合理的時間內得到一個較滿意的解.為了進一步對所提出的分層的GA 的有效性和可行性檢驗，文中隨機生成大量規模較大的MINP 模型進行求解計算，圖4 就是其中一個算例.計算結果表明:該分層算法可以在合理的時間內找到問題的最優解或者近似最優解;第二階段子問題的結果受第一階段子問題結果的影響，第一階段子問題的最優解決方案不能保證原問題的解決方案最優.

3 結束語

隨著現代物流配送的發展，不同行業對其要求不同，各有特點.本文依據電子行業配送的新特點，研究一種變形的VRP.所考慮的問題是兩種不同類型的配送服務:一種只需要配送服務，一種是配送與安裝都需要的服務.為了高效率地滿足顧客需求，企業采用兩種類型配送車輛分開運作的方式.在保證顧客的服務質量方面，所要考慮的問題是如何更好地解決兩種車輛的協同操作.本文在對所提出的模型求解時采用分層的方法進行求解，這將導致第二階段子問題的最優結果受第一階段子問題最優結果的影響，第一階段子問題的最優解決方案不能保證是原問題的最優解決方案.未來的研究可以同時考慮兩個子問題，在此模型的基礎上研究不確定因素下的模型等.

［1］KIM Kyoung Cheol，LEE Shiwoo.Hierarchical approach to vehicle routeing problem for delivery and installation［J］.Sci Direct，2010:7458-7471.

［2］van LANDEGHEM H R G.A bi-criteria heuristic for the vehicle routeing problem with time windows［J］.Eur J Operational Res，1988，36(2):217-226.

［3］KOSKOSIDIS Y A，POWELL W B，SOLOMON M M.An optimization-based heuristic for vehicle routeing and scheduling with soft time window constraints［J］.Transporting Sci，1992，26(2):69-85.

［4］CAMPOS V，MOTA E.Heuristic procedures for the capacitated vehicle routeing problem［J］.Computational Optimization ＆ Application，2000，16(3):265-277.

［5］PISINGER D，ROPKE S.A general heuristic for vehicle routeing problems［J］.Comput Operation Res，2007，34(8):2403-2435.

［6］ALVARENGA G B，MATEUS G R，de TOMI G.A genetic and set partitioning two-phase approach for the vehicle routeing problem with time windows［J］.Sci Direct，2007，34(6):1561-1584.

［7］CHENG Chibin，WANG Kengpin.Solving a vehicle routeing problem with time windows by a decomposition technique and a genetic algorithm［J］.Sci Direct，2009，36(4):7758-7763.

［8］TAN K C，LEE L H，OU K.Artificial intelligence heuristics in solving vehicle routeing problems with time window constraints［J］.Eng Applications of Artificial Intelligence，2001，14(6):825-837.

［9］BERGER J，BARKAOUI M，BRASY O.A route-directed hybrid GA approach for the VRPTW［J］.Inform Systems＆Operational Res，2003，41(2):179-194.

［10］盛麗俊，周溪召.帶有時間窗的車輛路徑問題優化［J］.上海海事大學學報，2007，28(4):64-67.

［11］李軍，謝秉磊，郭耀煌.非滿載車輛調度遺傳算法［J］.系統工程理論與實踐，2000，20(3):235-239.