基于改良CW算法求解帶時間窗的烘焙食品的配送問題

卜尚勤 師梽源 劉宇航 王海玲

摘要：本文運用一種改良節約法求解帶時間窗的烘焙食品運輸過程中所產生的VRPTW問題。首先通過引入分割配送的思想計算出分割配送的反應值H，然后根據反應值的大小決定優先分割順序，最后結果提高了配送里程和裝載率，效果良好。

關鍵詞：時間窗；節約算法；配送問題

中圖分類號：TP301.6 文獻標識碼：B 文章編號：1672-9129（2019）04-0007-05

Abstract：This paper solved the problem of VRPTW in the process of baking food transportation with time window based on an improved saving method. Firstly， the response value H of segmented distribution is calculated by introducing the idea of segmented distribution. Then the priority division order is determined according to the size of the store's response value . Finally， the result improves the delivery mileage and loading ratio， and the effect is good.

Keywords：Time window；CW algorithm； VRPTW

引言

物流行業迅速發展的今天，像烘焙食品這樣需要嚴格上架時間的行業，需要更高效，更合理，更節省成本的配送方案，帶時間窗約束的路徑規劃問題由此提出。車輛路徑規劃不僅滿足嚴格的上架時間，還為食品廠商降低了運輸成本與人工費用。解決帶有時間窗的車輛路徑規劃問題時，需要分析的因素有很多，國內學者曾玉霞在CW算法的基礎上進行改進，得到了提高配送車輛載重率改進算法，并驗證了改進算法可行性和優越性[1]。王芳在節約算法的改進中加入了分割配送的想法，更接近于實際問題的考慮，得到了車輛路徑問題的滿意解[2]。邵俊崗，鄭芳瑜等人針對基于分割配送思想的改進節約算法中可能存在的交叉路徑導致增加運輸里程數的情況，對連接點選擇問題進行優化，得到優于CW算法的改進算法[3]。崔宏志，龔加安對帶時間窗的單類型車輛路徑問題進行深入研究，加入鄰域搜索的思想，為避免路徑交叉，提出了改進后的CW算法[4]。

本文通過改良的CW算法，結合分割配送的思想，解決一種是帶時間約束的硬時窗下的車輛路徑問題。

1 車輛調度問題概述

車輛調度問題最早是由Dantzig和Ramser于1959年提出來的[5]，并且許多現實生活中的的實際問題的理論都可以歸結于這一問題。由于應用前景廣闊，所以成為運籌學與組合優化領域的研究熱點[6]。

車輛運輸調度問題一般定義為：對一系列裝貨點和卸貨點規劃適當的行車路線，使車輛有序地通過它們，滿足一定的約束條件，如時間窗口約束、車輛容量限制、車輛行駛里程限制、司機最大工作時間限制等，達到一定的目標如：車輛行駛路程最短、運輸費用最少、使用車輛數最少、服務質量最高等[7]。

其中，車輛調度問題中最常見的問題之一就是VRP（Vehicle Routing Problem， 車輛路由問題），它是用來確定一些有容量限制的且同時必須滿足一系列的約束的車輛在配送過程中的最優路徑 [8]。VRP的解就是設計出一個或多個滿足這樣要求的最短配送路線，可以包括貨品體積約束、車輛需要進行保養和維護的里程數約束、車輛行駛路程約束、時間窗口約束等。

2 模型建立

以內蒙古呼和浩特市意林食品作為原型，挑選了位于動車站、學校聚集區、市中心、景區以及隨機兩個居民區的六家門店作為配送對象。以江淮帥鈴4.2m冷藏車（額定載重1495kg）作為運輸工具，每輛冷藏車運輸成本約每公里0.5元，以百度地圖所規劃的最短路線作為運輸路徑，以百度糯米店鋪流量作為店鋪需求量指標進行合理推測，人為規定時間窗范圍進行規劃。

為了使模型更直觀，工廠用0表示，門店用1-6示，即1：火車站店；2：昭烏達路店；3：

新華大街店；4：五塔寺店；5：竹園店；6：海西路店。具體位置如圖1所示。

工廠與門店間、門店與門店間的里程表如表1所示。

根據表1門店間里程表求解配送最短路，運用Dijkstra算法求解最短路步驟如表2所示。

根據表2可知，門店間里程即為門店間的最短路。門店需求量如表3所示。

2.1 模型的假設

為了使模型不會受到各種現實因素的影響，作出了如下假設：

（1）車輛運輸不受天氣或擁堵及紅綠燈等不受控因素的影響；

（2）門店之間的最短距離有且只有一條，不考慮城市單行線的情況；

（3）配送的烘焙食品可以混送；

（4）工廠擁有足夠配送的食品和配送車輛；

（5）配送車輛的速度恒定；

（6）車輛運費不隨貨物質量的變化而變化。

2.2 經典CW算法介紹

CW算法基本原理：依次將運輸問題中的兩個回路合并為一個回路，每次使合并后的總運輸距離減小的幅度最大，直到達到一輛車的裝載限制時，再進行下一輛車的優化。

具體求解步驟如下：當工廠為多個門店配送食品時，首先計算出各個門店間的節約里程，按照節約里程從大到小的順序依次將門店加入到行車路線中。同時判斷該門店需求量是否超過了當前車輛的額定載重，若超過則剔除該門店，結束本路徑規劃；若不超過則繼續安排剩余節約里程中最大的一條路線，以此類推，直到所有門店被安排到行車路線中。

2.3 經典CW算法模型求解

根據表1可計算出門店間的節約值如門店1、2間的節約值如式1所示。

以式1依次得到所有門店的節約值并降序排列，結果如表4所示。

根據表4開始構造行車路線，由表3的門店需求量是否超過車輛載重，依次加入到配送路徑中。由表3可知，節約值最大的路線為（4，6），連接（4，6）后得到的行車路線為0-4-6，這時的門店需求量為230+746=976<1495，未超過車輛額定載重；再由降序表加入路線（2，4）后得到的行車路線為0-2-4-6，這時的門店需求量為976+318=1294<1495；在由降序表加入路線（3，2）后得到行車路線0-3-2-4-6，這時門店的需求量為1294+436=1730>1495，這時門店需求量超過了車輛額定載重，因此這條路徑不能加入行車路線；再根據降序表分別依次加入（2，5）、（1，6）等路線會發現路線加入后的門店需求量均超過了車輛的額定載重，因此這些路徑都不能再加入到行車路線中。此時就規劃出了第一條行車路線0-2-4-6，這條行車路線的節約值為24.5+23.2=47.7km。

這時門店2、4、6都加入到了行車路線中，根據表3選出除了包含門店2、4、6的節約值最大路線（3，5），連接門店3、5后得到行車路線0-3-5，此時的門店需求量為436+738=1174<1495，未超過車輛額定載重；再由降序表加入路徑（1，3）后得到行車路線0-1-3-5，這時的門店需求量為1174+382=1556> 1495，這時門店需求量超過了車輛額定載重，因此這條路線不能再加入到行車路線中。此時就規劃出了第二條行車路線0-3-5-0，這條行車路線的節約值為14.2。此時只有門店1沒有加入行車路線，因此門店1只能單獨配送，得到第三條行車路線0-1-0。

綜上所述，意林工廠向其6個門店配送的路線一共有3條，分別是：

R1：0-2-4-6-0

R2：0-3-5-0

R3：0-1-0

運用經典CW算法求解VRP問題結果是：工廠需要2輛冷藏車進行配送，節約的里程為

（4.1+12.0+11.0+15.0+9.8+14.9）*2-（（12.0+3.8+5.4+14.9）+（11+6.6+9.8） +（4.1+4.1））=61.9km；如不對行車路線進行規劃，原運輸成本為（4.1+12.0+11.0+15.0 +9.8+14.9）*2*0.5=66.8元，進行路線規劃后，現在的運輸成本為（12.0+3.8+5.4+14.9）+ +（11+6.6+9.8） +（4.1+4.1））*0.5=35.85.9 元，節約成本為66.8-35.85=30.95元。

3 改良CW算法求解VRPTW模型

VRPTW模型在經典CW算法的基礎上增加車輛的行車速度40km/h，門店允許配送的時間范圍是9：00-9：30，卸貨時間根據即時門店需求量進行合理推斷，車輛裝載率需要高于90%。

3.1 改良CW算法求解步驟

在經典CW算法的基礎上通過改良求解思路結合分割配送的思想后，改良CW 算法的具體執行步驟如下：

步驟1：將門店解初始化。為每個門店都只分配一輛車進行單獨配送，使之成為只有一個門店的行車路線。

步驟2：計算門店間的節約里程，并按照降序排列構成降序表。

步驟3：回路合并。從降序表中找出節約值最大的路徑合并加入到行車路線中，這時也需要考慮卸貨時間為路徑規劃所帶來的影響，之后判斷此時門店需求量是否超過車輛額定載重，若超過額定載重則考慮分割配送；若不超過，則在節約里程表中去除該路徑，更新降序表后進行下一步。

步驟4：計算車輛從出發點到下一個門店的時間及門店卸貨時間t，若t超出硬時間窗范圍，剔除該客戶的路線合并；若沒超出，計算此時車輛載重率，若車輛載重率小于等于90%，返回上一步。若載重率超過90%，這條路線規劃完畢，開始規劃下一條行車路線

步驟5：考慮分割配送方案，首先根據層次分析法計算VRPTW問題中兩個約束條件里程c和行程時間t的權重a和b，再計算剩余客戶分割配送反應值H，按照H從大到小的順序決定分割配送哪個客戶需求，將客戶需求分為車輛剩余重量和其他，為剩余重量配送后，判斷時間t是否超出硬時間窗范圍，若沒超出，更新門店需求量，得到新路線，進行下一條路線規劃；若超出，取消本次分割配送。

步驟6：進行下一條路線的規劃，直到所有門店均被安排到配送路徑中，結束路徑規劃選擇。具體流程見圖2。

其中變量H代表分割配送反應值，從而根據反應值的大小決定門店分割配送的先后順序。即反應值越大，門店需求量越先被分割；反之，門店需求量越晚被分割。

分割配送反應值的表達式如下。

3.2 求解烘焙食品的VRPTW模型

門店需求量與門店間節約里程降序表如表3、4所示，車輛運輸時間表如表5所示。

運用改良CW算法求解烘焙食品運輸過程中的VRPTW問題步驟如下：

初始化解，工廠為每個門店分配一輛冷藏車進行單獨運輸，運輸成本為66.8元。

在表3中找到最大節約路徑（4，6），連接門店4、6后得到路線0-4-6，此時門店需求量為230+746=976<1495，未超過車輛額定載重；在判斷車輛的運輸時間，冷藏車均在9：00從工廠出發，有時間窗條件9：00-9：30可知，允許配送的時間為30min，卸貨時間3min，總時長10.5+3.78+3=17.28min<30min，車輛裝載率為65.3%<90%；接著在路線中加入路徑（2，4）后得到路線0-2-4-6，此時門店需求量為976+318=1294<1495，未超過車輛額定載重，卸貨時間為4.2+3=7.2min，總時長為8.4+2.66+3.78+7.2=22.04min<30min，車輛裝載率為86.6%；接著在路線中加入路徑（2，3）后得到路線0-3-2-4-6，此時門店需求量為1294+436=1730>1495，超過車輛額定載重，若考慮將門店3分割配送，考慮門店3在滿足額定載重的情況下最長卸貨時間為3min，此時總運輸時間為7.7+1.61+2.66+3.78+3+4.2+3=25.95min<30min，門店3這時滿足分割配送的條件，運輸里程與運輸時間的權重分別為0.75和0.25，將門店3到門店2的節約值、運輸里程與運輸時間帶入（2）中，此時門店3的反應值H3=9.80，這時將門店3的需求量分割為235和201，更新門店3需求量為235，此時車輛滿載，第一條路徑規劃結束，得到行車路線0-3-2-4-6-0。

繼續從剩余未被規劃完全的門店路徑節約值表中找到最大節約路徑（3，5），連接3、5得到路徑0-3-5，此時門店需求量為235+738=973<1495，這時沒有超重，車輛載重率為65.0%<90%，卸貨時間為3min，總運輸時間為7.7+4.62+3=15.32min；結合卸貨時間及節約值表，接著在路徑中加入（1，3），得到路徑0-1-3-5，門店需求量為382+973=1355<1495，車輛載重率為90.6%>90%，卸貨時間為4.2min，總運輸時間為2.87+7+4.62+4.2+3=21.69min。第二條路徑規劃結束，得到行車路線0-1-3-5-0

綜上所述，意林工廠向其6個門店配送的路線一共有2條，分別是：

R1：0-3-2-4-6-0

R2：0-1-3-5-0

運用改良CW算法求解VRPTW問題結果是：工廠需要2輛冷藏車進行配送，節約的里程為65.7km，如不對行車路線進行規劃，原運輸成本為（4.1+12.0+11.0+15.0+9.8+14.9）*2*0.5=66.8元，進行路線規劃后，現在的運輸成本為（（11+2.3+3.8+5.4+14.9）+（4.1+10+6.6+9.8））×0.5=33.95元，節約成本為66.8-33.95=32.85元。

4 結論

從運輸里程來看，經典CW算法的運輸里程為65.7km，改良CW算法計算出的運輸里程為61.9km，改良的算法比改良前節約了3.8km。相應的，經典CW算法的運輸費用為35.85元，改良CW算法計算出的運輸費用為33.95元，節約了1.9元。從車輛數目來看，原算法下工廠使用冷藏車3輛，改良后的算法中工廠只需要冷藏車2輛，較原算法節約了1輛。從裝載率比較，原算法下的車輛裝載率分別只有86%、78%和26%，改良算法下車輛裝載率分別為100%和90.6%，均超過90%，顯然在裝載率上改良CW算法較經典CW算法有了較大提高。

參考文獻：

[1] 曾玉霞.C-W節約算法的改進研究[A].北京：中國職協2015年度優秀科研成果獲獎論文集（中冊）.2015：6-13.

[2] 王芳.基于節約算法和改進節約算法的配送路線優化[J].商.2015，51：194.

[3] 邵俊崗，鄭芳瑜.車輛路徑問題的連接點選擇節約算法[J].佳木斯：佳木斯大學學報（自然科學版）.2015， 2：13-18.

[4] 崔宏志，龔加安.帶時間窗車輛路徑問題的改進節約算法[J].純粹數學與應用數學.2011，5：256-273.

[5] 鄧宇佑.求解醫院運輸部門運輸中心個數最佳化之研究（D）.成功大學工業管理研究所碩士論文，1991年.

[6] 劉洋. 一種應用于物料配送路徑選擇的改進CW算法.吉林大學，2017年

[7] 潘立軍.帶時間窗車輛路徑問題及其算法研究[J].長沙：中南大學.2012

[8] 張建同，馮子炎.求解車輛路徑問題的改進CW節約算法[A].北京：第十屆中國不確定系統年會、第十四屆中國青年信息與管理學者大會論文集.2012，7：75-83.