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

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

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

關(guān)鍵詞：時(shí)間窗；節(jié)約算法；配送問題

中圖分類號：TP301.6 文獻(xiàn)標(biāo)識碼：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

引言

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

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

1 車輛調(diào)度問題概述

車輛調(diào)度問題最早是由Dantzig和Ramser于1959年提出來的[5]，并且許多現(xiàn)實(shí)生活中的的實(shí)際問題的理論都可以歸結(jié)于這一問題。由于應(yīng)用前景廣闊，所以成為運(yùn)籌學(xué)與組合優(yōu)化領(lǐng)域的研究熱點(diǎn)[6]。

車輛運(yùn)輸調(diào)度問題一般定義為：對一系列裝貨點(diǎn)和卸貨點(diǎn)規(guī)劃適當(dāng)?shù)男熊嚶肪€，使車輛有序地通過它們，滿足一定的約束條件，如時(shí)間窗口約束、車輛容量限制、車輛行駛里程限制、司機(jī)最大工作時(shí)間限制等，達(dá)到一定的目標(biāo)如：車輛行駛路程最短、運(yùn)輸費(fèi)用最少、使用車輛數(shù)最少、服務(wù)質(zhì)量最高等[7]。

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

2 模型建立

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

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

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

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

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

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

2.1 模型的假設(shè)

為了使模型不會受到各種現(xiàn)實(shí)因素的影響，作出了如下假設(shè)：

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

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

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

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

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

（6）車輛運(yùn)費(fèi)不隨貨物質(zhì)量的變化而變化。

2.2 經(jīng)典CW算法介紹

CW算法基本原理：依次將運(yùn)輸問題中的兩個(gè)回路合并為一個(gè)回路，每次使合并后的總運(yùn)輸距離減小的幅度最大，直到達(dá)到一輛車的裝載限制時(shí)，再進(jìn)行下一輛車的優(yōu)化。

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

2.3 經(jīng)典CW算法模型求解

根據(jù)表1可計(jì)算出門店間的節(jié)約值如門店1、2間的節(jié)約值如式1所示。

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

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

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

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

R1：0-2-4-6-0

R2：0-3-5-0

R3：0-1-0

運(yùn)用經(jīng)典CW算法求解VRP問題結(jié)果是：工廠需要2輛冷藏車進(jìn)行配送，節(jié)約的里程為

（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；如不對行車路線進(jìn)行規(guī)劃，原運(yùn)輸成本為（4.1+12.0+11.0+15.0 +9.8+14.9）*2*0.5=66.8元，進(jìn)行路線規(guī)劃后，現(xiàn)在的運(yùn)輸成本為（12.0+3.8+5.4+14.9）+ +（11+6.6+9.8） +（4.1+4.1））*0.5=35.85.9 元，節(jié)約成本為66.8-35.85=30.95元。

3 改良CW算法求解VRPTW模型

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

3.1 改良CW算法求解步驟

在經(jīng)典CW算法的基礎(chǔ)上通過改良求解思路結(jié)合分割配送的思想后，改良CW 算法的具體執(zhí)行步驟如下：

步驟1：將門店解初始化。為每個(gè)門店都只分配一輛車進(jìn)行單獨(dú)配送，使之成為只有一個(gè)門店的行車路線。

步驟2：計(jì)算門店間的節(jié)約里程，并按照降序排列構(gòu)成降序表。

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

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

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

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

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

分割配送反應(yīng)值的表達(dá)式如下。

3.2 求解烘焙食品的VRPTW模型

門店需求量與門店間節(jié)約里程降序表如表3、4所示，車輛運(yùn)輸時(shí)間表如表5所示。

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

初始化解，工廠為每個(gè)門店分配一輛冷藏車進(jìn)行單獨(dú)運(yùn)輸，運(yùn)輸成本為66.8元。

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

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

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

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

R2：0-1-3-5-0

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

4 結(jié)論

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

參考文獻(xiàn)：

[1] 曾玉霞.C-W節(jié)約算法的改進(jìn)研究[A].北京：中國職協(xié)2015年度優(yōu)秀科研成果獲獎?wù)撐募ㄖ袃裕?2015：6-13.

[2] 王芳.基于節(jié)約算法和改進(jìn)節(jié)約算法的配送路線優(yōu)化[J].商.2015，51：194.

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

[4] 崔宏志，龔加安.帶時(shí)間窗車輛路徑問題的改進(jìn)節(jié)約算法[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué).2011，5：256-273.

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

[6] 劉洋. 一種應(yīng)用于物料配送路徑選擇的改進(jìn)CW算法.吉林大學(xué)，2017年

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

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