基于禁忌搜索和Floyd 混合算法的物流配送路線規(guī)劃

喬仁杰，周思育，田 琪，宋庭新

（湖北工業(yè)大學(xué) 機(jī)械工程學(xué)院，湖北 武漢 430068）

基于禁忌搜索和Floyd 混合算法的物流配送路線規(guī)劃

喬仁杰，周思育，田 琪，宋庭新

（湖北工業(yè)大學(xué) 機(jī)械工程學(xué)院，湖北 武漢 430068）

以某醫(yī)藥集團(tuán)湖北配送業(yè)務(wù)為背景，采用禁忌搜索算法對(duì)藥品物流配送路線進(jìn)行了規(guī)劃，在此基礎(chǔ)上運(yùn)用Floyd算法對(duì)規(guī)劃的路線進(jìn)行路網(wǎng)匹配，生成與配送區(qū)域?qū)嶋H道路相吻合的最優(yōu)路徑。實(shí)際應(yīng)用表明，經(jīng)過這種混合算法生成的行車路線不僅與實(shí)際道路相匹配，而且大大減少了車輛行駛里程，節(jié)約了燃油和物流成本，在物流運(yùn)輸領(lǐng)域具有良好的經(jīng)濟(jì)和社會(huì)價(jià)值。

配送路線規(guī)劃；禁忌搜索算法；Floyd算法；物流

1 引言

物流路徑優(yōu)化問題最早是由Dantzig和Ramser在1959年提出的，即所謂的車輛調(diào)度問題（Vehicle Routing Problem，VRP）[1]。車輛調(diào)度問題的理論涉及多學(xué)科，很多實(shí)際問題都可以歸于這一類問題，應(yīng)用前景廣闊，所以成為運(yùn)籌學(xué)與組合優(yōu)化領(lǐng)域的研究熱點(diǎn)。近幾十年來，對(duì)車輛優(yōu)化調(diào)度問題的研究取得了很多有意義的成果，已經(jīng)廣泛應(yīng)用于生產(chǎn)、生活的各個(gè)方面。隨著經(jīng)濟(jì)發(fā)展，物流行業(yè)對(duì)社會(huì)的影響日益顯著，而配送是物流行業(yè)中的重要環(huán)節(jié)，配送路線的設(shè)計(jì)和選擇對(duì)物流公司的運(yùn)輸成本以及貨物的運(yùn)輸效率有著重要影響，因此選擇一條合理的配送路線是物流運(yùn)輸中需要研究的重要問題[2]。

本文運(yùn)用物流工程相關(guān)知識(shí)，以某醫(yī)藥集團(tuán)醫(yī)藥物流配送路線規(guī)劃問題為背景，選擇禁忌搜索和Floyd混合算法作為物流網(wǎng)絡(luò)模型優(yōu)化算法，提出一種解決物流配送路線規(guī)劃的方案，尋求最優(yōu)配送路徑，以達(dá)到提高物流效率和降低運(yùn)輸成本的目的。

2 車輛配送路徑優(yōu)化算法

車輛配送路徑優(yōu)化是NP-hard問題，使用的方法一般分為兩大類[3]：一類是精確搜索非精確解的方法，如C-W節(jié)約算法與禁忌搜索算法；一類為啟發(fā)式搜索方法，如ANT蟻群算法、AN模擬退火算法。其中，禁忌搜索算法是一種全局逐步尋優(yōu)算法，它通過引入靈活的存儲(chǔ)結(jié)構(gòu)和相應(yīng)的禁忌準(zhǔn)則來避免迂回搜索，并通過藐視準(zhǔn)則來赦免一些被禁忌的優(yōu)良狀態(tài)，進(jìn)而保證多樣化的有效探索，以最終實(shí)現(xiàn)全局優(yōu)化。禁忌搜索算法比較直觀，算法簡(jiǎn)單，可以回避局部臨域搜索陷入局部最優(yōu)的不足，克服其它算法爬山能力差的缺點(diǎn)，從而加快收斂速度，提高了解的質(zhì)量，也能夠滿足運(yùn)行路線和時(shí)間安排原則[4]。而在求解最短路線中，啟發(fā)式搜索算法與禁忌搜索算法相比準(zhǔn)確度不夠，過程較為繁瑣，所以本文選擇禁忌搜索算法來求解最優(yōu)車輛配送路徑。

2.1 禁忌搜索算法

首先，給定一個(gè)初始解和一種鄰域，然后在當(dāng)前解的鄰域中確定若干候選解；若最佳候選解對(duì)應(yīng)的目標(biāo)值優(yōu)于“best so far”狀態(tài)，則忽視其緊急特征，用其代替當(dāng)前解和“best so far”狀態(tài)，并將相應(yīng)的對(duì)象加入禁忌表，同時(shí)修改禁忌表中各對(duì)象的任期；若不存在上述候選解，則在候選解中選擇非禁忌的最佳狀態(tài)為新的當(dāng)前解，而無視它與當(dāng)前解的優(yōu)劣，同時(shí)將相應(yīng)的對(duì)象加入禁忌表，并修改禁忌表中各對(duì)象的任期。如此重復(fù)上述迭代搜索過程，直至滿足停止準(zhǔn)則。其算法步驟具體為：

（1）選定一個(gè)初始解xnow，置禁忌表H=?。

（2）若滿足終止規(guī)則，則終止計(jì)算；否則，在xnow的鄰域N(H,xnow)中選出滿足禁忌要求的候選集Can_N(xnow),在Can_N(xnow)中選一個(gè)評(píng)價(jià)值最佳的解xnext,令xnow=xnext，更新歷史記錄H，重復(fù)（2）。

禁忌搜索算法的流程如圖1所示。

圖1 禁忌搜索算法流程圖

2.2 Floyd算法

運(yùn)用禁忌搜索算法求解之后，雖然求出了經(jīng)過所有配送點(diǎn)的最短直線距離，但與能夠行走的實(shí)際路網(wǎng)并不匹配，需要結(jié)合實(shí)際路網(wǎng)把直線最短路線還原為實(shí)際路線，這里便需采用Floyd算法。Floyd算法是一種尋找給定的加權(quán)圖中頂點(diǎn)間最短路徑的算法，此算法可用來求解兩點(diǎn)間的實(shí)際最短路線，其基本思路是在兩個(gè)配送點(diǎn)之間根據(jù)實(shí)際路網(wǎng)插入若干中間節(jié)點(diǎn)，然后求解經(jīng)過這些中間節(jié)點(diǎn)的最短路線[5]。具體算法如下：

（1）首先根據(jù)模型中的點(diǎn)構(gòu)建一個(gè)鄰接矩陣A0，A0是對(duì)稱矩陣，即，然后取初值

（3）遞推產(chǎn)生一個(gè)矩陣序列A0,A1，...,An(1≤k≤n)。

（4）當(dāng)k=n時(shí)，就得到了最短路徑，即矩陣An就是各頂點(diǎn)間的最短路徑值，否則令k=k+1(k是迭代次數(shù))，轉(zhuǎn)第（2）步。

3 案例分析

3.1 背景介紹

為驗(yàn)證上述算法的有效性，本文選取某醫(yī)藥集團(tuán)在武漢市東西湖區(qū)常青花園一帶的配送點(diǎn)進(jìn)行建模。文中使用的配送點(diǎn)是依據(jù)該集團(tuán)LMIS系統(tǒng)中導(dǎo)出的2016年4月份湖北運(yùn)輸部的配送數(shù)據(jù)。東西湖區(qū)2016年4月的配送點(diǎn)有54個(gè)（如圖2所示），在調(diào)查過程中發(fā)現(xiàn)常青花園一帶配送量大，每次配送點(diǎn)多且集中，配送時(shí)可進(jìn)行協(xié)商，將部分連鎖藥店的配送工作轉(zhuǎn)交給藥店內(nèi)部調(diào)配，從而減少同一個(gè)區(qū)域的配送點(diǎn)。由于每次配送的地點(diǎn)是根據(jù)訂單臨時(shí)生成的，因此隨機(jī)選取了10個(gè)配送點(diǎn)進(jìn)行線路優(yōu)化，如圖2中圓圈所示。

圖2 武漢市東西湖區(qū)常青花園附近路網(wǎng)及配送點(diǎn)

3.2 用禁忌搜索算法求解最短路線

使用MatLab軟件編程調(diào)用禁忌搜索算法程序。在MatLab中，取已選定的10個(gè)點(diǎn)（圖2中圓圈所示，后同），在代碼中把索取到的點(diǎn)1、6、11、16、21、26、31、36、41、46，依次重新編號(hào)為1、2、3、4、5、6、7、8、9、10，進(jìn)行禁忌搜索計(jì)算后，得到巡回序列以及巡回距離，見表1。

從表1可知，求得的最短巡回距離為357.189 9km，由于起始點(diǎn)分別從3、4、5、6、7、8、9、10的巡回序列所走的巡回路徑是一樣的，且巡回路徑重復(fù)多次，說明所求路徑正是這些重復(fù)的路徑，因此用禁忌搜索算法取得的最短路徑為3-8-9-10-7-6-4-5-2-1-3，還原到地圖中的點(diǎn)為11-36-41-46-31-26-16-21-6-1-11，將這些點(diǎn)還原到地圖，依次連接得到路線如圖3所示。

表1 通過Matlab計(jì)算得到的巡回路線以及巡回距離

圖3 還原到地圖的最短路線

圖3所示的最短路線是各配送點(diǎn)直接相連得到的路線，與實(shí)際路網(wǎng)并不匹配，因此還需要使用Floyd算法對(duì)該路線進(jìn)一步進(jìn)行規(guī)劃。具體方法是根據(jù)實(shí)際路網(wǎng)，在相鄰兩配送點(diǎn)之間的實(shí)際道路上選取關(guān)鍵節(jié)點(diǎn)重新構(gòu)建兩點(diǎn)之間的最短路線。

3.3 使用Floyd算法構(gòu)建最短路線矩陣

取配送點(diǎn)6-21為例構(gòu)建鄰接矩陣。根據(jù)地圖中實(shí)際路網(wǎng)的分布，需要在6-21之間插入四個(gè)關(guān)鍵節(jié)點(diǎn)7，8，13，17，如圖4所示。構(gòu)建的鄰接矩陣如圖5所示。

圖4 還原路網(wǎng)后的實(shí)際路線

圖5 鄰接矩陣

上述鄰接矩陣的意義是：程序點(diǎn)中點(diǎn)6到點(diǎn)21的最短路線是這樣得到的，第6行第21列為7，第7行第21列為8，第8行第21列為13，第13行第21列為17，第17行第21列為21，則點(diǎn)6到點(diǎn)21的最短路線是6-7-8-13-17-21。

3.4 通過Floyd算法計(jì)算后的最短路線

在MatLab中編程調(diào)用Floyd算法程序，根據(jù)鄰接矩陣求出兩點(diǎn)之間的最短路線以及距離，并將距離相加求得距離之和，見表2。

表2 通過Floyd計(jì)算得到的最短路線及最短距離

根據(jù)表2得到的數(shù)據(jù)以及路線關(guān)系還原路網(wǎng)后的實(shí)際路線如圖4所示。

3.5 基于Floyd算法的路線優(yōu)化

在Floyd算法中，在上一次計(jì)算完成后，下次運(yùn)算就剔出已經(jīng)經(jīng)過的配送點(diǎn)。例如本模型中，從11-36，按照Floyd算法路線是11-29-31-38-37-36；從46-31，按照Floyd算法路線是46-47-43-41-38-31。但是顯然在11-36時(shí)已經(jīng)經(jīng)過了點(diǎn)31，故Floyd算法在計(jì)算46-26時(shí)將剔出點(diǎn)31，這樣就會(huì)形成一個(gè)比較好的串連路線46-47-48-49-32-28-27-26。故優(yōu)化后的最短總距離為：D=50.774 6+55.370 4+28.158 1+43.201 3+92.000 0+25.704 0+18.942 4+78.221 6+27.968 7=420.341 1。優(yōu)化后的實(shí)際線路如圖6所示。

圖6 優(yōu)化后的實(shí)際路線

3.6 路線優(yōu)化后的物流成本核算

優(yōu)化后的最短總距離D=420.341 1，所用地圖比例是1：23，故實(shí)際里程為D=420.341 1×23/1 000=10.2km。根據(jù)LMIS系統(tǒng)中的數(shù)據(jù)，該月使用依維柯車型配送的次數(shù)是46次，日均配送次數(shù)1.5次，配送行駛里程為3 288km，平均每次配送行駛73.07km，由于該醫(yī)藥物流配送中心設(shè)在漢陽(yáng)，漢陽(yáng)到所取模型區(qū)域配送行駛里程不會(huì)超過30km，也就是說按照路線優(yōu)化后的配送路線進(jìn)行配送可減少行駛公里數(shù)為S=73.07-30-10.2=32.87km。假設(shè)依維柯汽車每百公里平均耗油為8L，則路線優(yōu)化后每輛車每個(gè)區(qū)每次配送可節(jié)省燃油升數(shù)為l=32.87×0.08=2.63 L。每天上午和下午各配送一次則一天省油L=l×2=5.26L，第一季度節(jié)省燃油L1=L×（31+28+31）=473.4L，第二季度節(jié)省L2=L×（30+31+30）=478.66L，第三季度節(jié)省L3=L×（31+31+30）=483.92L，第四季度節(jié)省L4=L×（31+30+31）=483.92L，則一年節(jié)省的油費(fèi)約為（473.4+478.66+483.92+483.92）×5.7=10 934.43元，即一輛車一年節(jié)省的燃油費(fèi)約為1萬(wàn)元。該公司在武漢地區(qū)投入的配送車輛有24輛，因此僅武漢地區(qū)一年節(jié)約的燃油費(fèi)用就達(dá)到24萬(wàn)元。

4 結(jié)語(yǔ)

本文結(jié)合禁忌搜索算法與Floyd算法來規(guī)劃物流配送路線，先利用禁忌搜索算法規(guī)劃理想最短路線，再結(jié)合Floyd算法與實(shí)際網(wǎng)路的情況將理想最短路線還原為實(shí)際路線，最終得到具有實(shí)際意義的物流配送優(yōu)化路線。本方案在該醫(yī)藥集團(tuán)公司自實(shí)施至2016年9月底，效果顯著，公司物流成本明顯降低，配送效率得到明顯提升。因此，本文提出的路線規(guī)劃算法理論具有良好的實(shí)際運(yùn)用效果，可顯著提升物流配送效率。

[1]Cheng Guoniang,Zhuang Zhenquan.Theory and Application of the Genetic Algorithm[M].Posts&Telecom Press,1999.

[2]尚華艷.物流配送中車輛路徑問題研究[D].武漢:武漢理工大學(xué),2005.

[3]康曉軍,王茂才.基于遺傳算法的最短路徑問題求解[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(23):22-23.

[4]曹立斌,周建蘭.一種改進(jìn)的禁忌搜索法在函數(shù)優(yōu)化問題中的應(yīng)用[J].計(jì)算機(jī)技術(shù)與發(fā)展,2003,13(a02):39-42.

[5]樊蓉.物流配送中車輛調(diào)度算法的比較研究[D].南京:南京農(nóng)業(yè)大學(xué),2013.

Planning of Logistics Distribution Route Based on Tabu Search and Floyd Algorithm

Qiao Renjie,Zhou Siyu,Tian Qi,Song Tingxin
(School of Mechanical Engineering,Hubei University of Technology,Wuhan 430068,China)

In this paper,we applied the tabu search algorithm to the routing of the medicine logistics distribution business of a certain pharmaceutical group in Hubei;then on such basis,we iused the Floyd algorithm for the road network matching of the planned route to yield the optimal route that fitted most closely with the actual road condition of the distribution area;and at last,through a practical application,we demonstrated the economic and social value of the hybrid algorithm proposed in this paper.

distribution route planning;tabu search algorithm;Floyd algorithm;logistics

F224.0;F252.14

A

1005-152X(2017)10-0083-04

10.3969/j.issn.1005-152X.2017.10.017

2017-08-01

湖北省交通運(yùn)輸廳科技項(xiàng)目（鄂交科教2016-600-5-3）；國(guó)家級(jí)大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目（201610500037）

喬仁杰（1994-），男，湖北宜昌人，碩士研究生，研究方向：工業(yè)工程；宋庭新（1972-），男，湖北宜都人，教授，研究方向：工業(yè)工程。