回溯法在物流車動態(tài)導(dǎo)航中的應(yīng)用

王防修,王曉娜,祁華清,趙杰梅

(1.武漢輕工大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院,湖北 武漢 430023;2.武漢輕工大學(xué) 經(jīng)濟(jì)與管理學(xué)院,湖北 武漢 430023)

回溯法在物流車動態(tài)導(dǎo)航中的應(yīng)用

王防修1,王曉娜1,祁華清2,趙杰梅1

(1.武漢輕工大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院,湖北 武漢 430023;2.武漢輕工大學(xué) 經(jīng)濟(jì)與管理學(xué)院,湖北 武漢 430023)

研究物流車的動態(tài)導(dǎo)航問題。由于物流車在配送過程中經(jīng)常會遇到堵車情況，如果物流車仍按照原最優(yōu)路徑進(jìn)行配送，則會降低物流車的配送效率。傳統(tǒng)的TSP算法只能為物流車規(guī)劃一個靜態(tài)最優(yōu)路徑，一旦物流車遇到堵車就無法調(diào)整，這樣的導(dǎo)航不能提高物流車的配送效率。為了避免上述缺陷，提出了一種用回溯法實(shí)現(xiàn)物流車配送的動態(tài)優(yōu)化算法。首先，利用回溯法實(shí)現(xiàn)物流車配送的靜態(tài)優(yōu)化，將該路徑作為物流車的初始路徑。如果物流車行駛路徑的前方出現(xiàn)堵車，則用回溯法對物流車未配送的客戶重新規(guī)劃一條新的最短路徑，通過避開堵車路段來提高物流車的配送效率。如果某個路段的堵車解除而該路段兩端的客戶還未被配送，則用回溯法對未配送的客戶重新規(guī)劃最短路徑來提高配送效率。實(shí)驗(yàn)結(jié)果表明，利用本文算法進(jìn)行物流車配送的動態(tài)優(yōu)化算法，能夠有效提高物流車的配送效率。

回溯法；動態(tài)導(dǎo)航；最優(yōu)路徑；物流車配送；配送效率

1 引言

伴隨市場經(jīng)濟(jì)的高速發(fā)展，物流配送業(yè)發(fā)展迅猛。合理選擇配送路徑，對配送效率提高、服務(wù)質(zhì)量提升、配送成本降低及經(jīng)濟(jì)效益增加都有重要影響。配送路徑的優(yōu)化問題是影響物流車合理配送過程中的一個重要環(huán)節(jié)，它可以使物流配送以最低的成本、最快的響應(yīng)速度、最短的運(yùn)輸時間，把貨物運(yùn)至客戶手中，而后兩個指標(biāo)與第一個指標(biāo)之間存在著一定的制約關(guān)系，無法達(dá)到總體最優(yōu)，因此，這實(shí)際是一個多目標(biāo)的優(yōu)化問題。

進(jìn)行物流配送時，物流車裝載需要配送的貨物從倉庫出發(fā)，按事先規(guī)劃好的最優(yōu)配送路徑為每個客戶進(jìn)行配送，最后返回倉庫。因此，在配送之前，需要根據(jù)客戶的配送地址計(jì)算出一條最優(yōu)配送路徑。然而，這種路徑優(yōu)化算法并沒有考慮物流車在實(shí)際配送過程中有可能遇到諸如堵車或臨時管制等異常情況。如果此時仍然按照事先規(guī)劃好的路線進(jìn)行配送，顯然會降低配送效率。總之，現(xiàn)有物流配送的路徑優(yōu)化算法[1-11]都是靜態(tài)的，不具有根據(jù)實(shí)際情況進(jìn)行動態(tài)調(diào)整的功能。

因此，需要設(shè)計(jì)一個動態(tài)優(yōu)化算法：一旦物流車在配送過程中出現(xiàn)還未經(jīng)過的某路段發(fā)生堵車事件時，可以重新對物流車的配送路徑進(jìn)行規(guī)劃，以便物流車在剩余的路徑上仍是最優(yōu)的。本文針對此問題進(jìn)行研究并設(shè)計(jì)了一個基于回溯法的物流車動態(tài)導(dǎo)航算法。先利用靜態(tài)回溯算法對物流車出發(fā)前進(jìn)行一次靜態(tài)優(yōu)化，一旦物流車在配送過程中出現(xiàn)堵車或堵車解除，則用動態(tài)回溯算法對物流車剩余路徑進(jìn)行優(yōu)化，使得物流車的配送效率在當(dāng)前時刻總是最優(yōu)的。

2 動態(tài)優(yōu)化物流配送的數(shù)學(xué)模型

物流配送是一個TSP問題，給定n個站點(diǎn)(1個倉庫和n-1個客戶)間的權(quán)重ω(i,j),i,j∈{1,2,…,n}。如果ω(i,j)≠0，則物流車可以從站點(diǎn)i直接到達(dá)站點(diǎn)j；否則，物流車從站點(diǎn)i無法直接到達(dá)站點(diǎn)j，需要中轉(zhuǎn)其它站點(diǎn)才能到達(dá)。尋找一種遍歷所有站點(diǎn)且對每個站點(diǎn)僅訪問一次的路徑，如果總路徑的權(quán)重之和最小，則稱該路徑為最優(yōu)路徑。

2.1 物流配送的靜態(tài)優(yōu)化模型

設(shè)G=(V,E)是賦權(quán)圖，V={1,2,…,n}為站點(diǎn)集，E為站點(diǎn)間的邊集，站點(diǎn)間的權(quán)重ω(i,j)≥0,i,j∈V，設(shè)路徑Xi=sxi2…xin，其中s∈V表示物流車的始發(fā)站點(diǎn)(倉庫)，xij∈V-{s}，j=2,…,n。且?k≠j，有xik≠xij。則物流配送問題的數(shù)學(xué)模型表示如下：

(1)

(2)

2.2 物流配送的動態(tài)優(yōu)化模型

假設(shè)物流車出發(fā)前規(guī)劃好的最優(yōu)路徑為Xi=sxi2…xin，而在物流車行進(jìn)的過程中，最優(yōu)路徑的某一路段xijxij+1出現(xiàn)堵車，則此時就需要對規(guī)劃好的剩余路徑進(jìn)行重新優(yōu)化，以便使接下來路徑仍是最優(yōu)的。設(shè)物流車目前正行進(jìn)在xikxik+1上，則物流配送重新優(yōu)化的數(shù)學(xué)模型如下：

(3)

(4)

(5)

其中X′表示剩余頂點(diǎn)的全排列。

3 基于回溯法的動態(tài)TSP優(yōu)化算法原理

在為客戶進(jìn)行配送時，為了使物流車的運(yùn)輸成本最小，導(dǎo)航系統(tǒng)必須為物流車選擇一條從倉庫出發(fā)，經(jīng)過要配送的每個客戶一遍，最后回到倉庫的路線，使物流車的總的運(yùn)輸成本最小。如果物流車在配送的路徑上沒有堵車發(fā)生，則這是一個靜態(tài)的TSP優(yōu)化問題。然而，在經(jīng)濟(jì)高速發(fā)展而交通運(yùn)輸壓力日益加重的今天，堵車是經(jīng)常發(fā)生的事情。因此，雖然物流車在出發(fā)前已經(jīng)接收到導(dǎo)航系統(tǒng)的路徑安排，但一旦物流車行進(jìn)的路線上出現(xiàn)堵車事件，則要求導(dǎo)航系統(tǒng)為物流車由于避開堵車路段而需要為未配送完的客戶重新選擇一條最優(yōu)路徑。因此，要使導(dǎo)航系統(tǒng)能為物流車提供遍歷客戶的最短路徑，則導(dǎo)航系統(tǒng)必須滿足：1)物流車在出發(fā)前，導(dǎo)航系統(tǒng)根據(jù)物流車的倉庫位置和配送的各客戶位置以及客戶間路線權(quán)重，為物流車選擇一條初始的TSP優(yōu)化路徑；2)如果在物流車事先規(guī)劃的某個路線上出現(xiàn)堵車，則導(dǎo)航系統(tǒng)需要對物流車未遍歷的客戶重新規(guī)劃路徑；3)如果某個路段的堵車解除，則導(dǎo)航系統(tǒng)對物流車的剩余路徑需要重新優(yōu)化?？傊?，導(dǎo)航系統(tǒng)保證物流車在當(dāng)前時刻的配送路徑總是最優(yōu)的。

設(shè)現(xiàn)有1個倉庫和n-1個客戶，則可以對這n個位置編號為1,2,…,n。如果d(i,j)=w(i,j),?i,j∈{1,2,…,n}，則如果d(i,j)≠0，則表示位置i和位置j之間能夠相互直達(dá)。在物流車配送過程中，需要為其動態(tài)選擇一個路徑best_xi，i=1,2,…,n，使得物流車在當(dāng)前時刻的行駛路徑總是最優(yōu)的。因此，令xi=i,i=1,2,…,n表示當(dāng)前路徑，cur_c表示回溯法的當(dāng)前累加值，best_c表示當(dāng)前最優(yōu)值。

3.1TSP的靜態(tài)回溯優(yōu)化算法

在物流車出發(fā)前，需要為其規(guī)劃一個最優(yōu)路徑。如果s是倉庫所在地，則需要找到一個從s出發(fā)再回到s的最短路徑。

為了使用回溯法求最優(yōu)路徑，首先使x1=s和xs=1，表示物流車從倉庫出發(fā)。因此，需要依次搜索x2,x3,…,xn，使得(1)最小。如果x1x2…xi-1已經(jīng)選定，則xixi+2…xn的選擇過程如下：

步驟1:如果i=n，d(xn-1,xn)≠0，d(xn,x1)≠0，cur_c+d(xn-1,xn)+d(xn,x1)

best_xj=xj,j=1,2,…,n。

(6)

best_c=cur_c+d(xn-1,xn)+d(xn,x1)

(7)

步驟2:如果i≠n，則從選擇依次選擇xj,j=i,i+1,…,n的過程如下：

(1)如果d(xi-1,xi)≠0和cur_c+d(xi-1,xj)

(2)如果j

由于x1作為倉庫已經(jīng)確定，故該算法是依次確定x2,x3,…,xn。

3.2 堵車時的TSP動態(tài)回溯優(yōu)化算法

設(shè)當(dāng)前物流車的最優(yōu)路徑為x1x2…xnx1，而物流車正在行駛的路段為xi-1xi，此時路段xjxj+1出現(xiàn)了堵車。如果路段xjxj+1出現(xiàn)在路徑xi…xnx1中，則需要對物流車還沒有配送的客戶重新優(yōu)化一個路徑xi+1…xnx1，使得堵車前物流車已經(jīng)通過的路徑x1…xi和xi+1…xnx1構(gòu)成堵車后的最優(yōu)路徑。因此，優(yōu)化過程如下：

步驟1:由于路段xjxj+1堵車，為方便優(yōu)化，故使

d(xj-1,xj)=d(xj,xj-1)=0

(8)

步驟2:由于物流車正在行駛的路段為xi-1xi，故需要從xi+1開始優(yōu)化，以便得到一個新的xi+1…xnx1。故優(yōu)化過程為：

(1)準(zhǔn)備工作。best_c=cur_c=0，而best_xi=xi,i=1,2,…,n。

(2)從xi+1開始優(yōu)化最優(yōu)路徑，其優(yōu)化過程如算法3.1中的步驟2。

步驟3:從步驟2中可以得到新的xi+1…xnx1和best_c。由于x1…xi跟優(yōu)化前一樣，故

(9)

3.3 堵車解除時的TSP動態(tài)回溯優(yōu)化算法

如果xi-1xi是物流車正在行駛的路段，而物流車未通過的堵車路段xjxj+1已經(jīng)恢復(fù)通車。在優(yōu)化之前，必須恢復(fù)堵車前路段信息，即

d(xj-1,xj)=d(xj,xj-1)=w(xj,xj+1)

(10)

至于接下來的優(yōu)化過程，與算法3.2的步驟2和步驟3完全一樣。

對物流車配送過程導(dǎo)航如下：

步驟1:物流車出發(fā)前，用算法3.1物流車規(guī)劃一個最短路徑。

步驟2:如果物流車配送過程中出現(xiàn)前方堵車，則用算法3.2對未遍歷的客戶點(diǎn)規(guī)劃一個最短路徑。

步驟3:如果物流車配送過程中出現(xiàn)兩個未遍歷的客戶間的路段堵車解除，則用算法3.3為未遍歷的客戶規(guī)劃一個最短路徑。

步驟4:重復(fù)步驟2和步驟3，直到物流車返回倉庫為止。

4 算法仿真及分析

算例 客戶數(shù)據(jù)：(1)用戶在軟件界面上隨機(jī)標(biāo)注倉庫與客戶的地址(不少于10個客戶)；(2)客戶的地址表示采用Window設(shè)備坐標(biāo)系?？蛻舻刂烽g的距離采用設(shè)備坐標(biāo)像素間距模擬。動態(tài)導(dǎo)航要求：(1)模擬車輛從倉庫出發(fā)，沿著規(guī)劃的配送路線行進(jìn)，最后返回倉庫；(2)在配送過程中模擬前方行進(jìn)路線堵車事件，軟件能夠繞開堵車路段動態(tài)規(guī)劃配送路線。

使用VC6.0作為仿真工具，在CPU為3.2GHz和內(nèi)存為1.86GB的個人臺式電腦上完成仿真[12]。

在軟件界面上隨機(jī)選擇倉庫和客戶的位置如圖1所示。其中V4是倉庫所在地，其他12個頂點(diǎn)是客戶所在地。

圖1 倉庫與客戶位置

圖1所示頂點(diǎn)V1～V13的坐標(biāo)依次為：(91,172)(363,392)(355,183)(118,405)(220,305)(217,197)(107,310)(355,307)(238,407) (157,242)(298,246)(296,360)(180,362)。

如果物流車在行駛的過程中未出現(xiàn)堵車事件，則導(dǎo)航系統(tǒng)為其規(guī)劃的最優(yōu)路徑如圖2。

圖2 沒有堵車的最優(yōu)路徑

圖2中物流車的行駛路徑為：V4-V13-V5-V9-V12-V2-V8-V3-V11-V6-V1-V10-V7-V4。此時最短路徑的最優(yōu)值為1191.27。

當(dāng)物流車行駛在V5-V9路段時，路段V3-V11發(fā)生了堵車，則導(dǎo)航系統(tǒng)為物流車重新優(yōu)化的路徑如圖3所示。

圖3 路段V3-V11堵車的最優(yōu)路徑

圖3中物流車的行駛路徑為：V4-V13-V5-V9-V12-V2-V11-V8-V3-V6-V1-V10-V7-V4。此時最短路徑的最優(yōu)值為1308.27811。

當(dāng)物流車行駛在V9-V12路段時，路段V1-V10發(fā)生了堵車，則導(dǎo)航系統(tǒng)為物流車重新優(yōu)化的路徑如圖4所示。

圖4 路段V1-V10堵車的最優(yōu)路徑

圖4中物流車的行駛路徑為：V4-V13-V5-V9-V12-V2-V3-V8-V11-V10-V6-V1-V7-V4。此時最短路徑的最優(yōu)值為1393.276585。

當(dāng)物流車行駛在V12-V2路段時，路段V3-V11的堵車解除，而路段V1-V10的堵車保持，則導(dǎo)航系統(tǒng)為物流車重新優(yōu)化的路徑如圖5所示。

圖5 路段V3-V11堵車解除的最優(yōu)路徑

圖5中物流車的行駛路徑為：V4-V13-V5-V9-V12-V2-V8-V3-V11-V10-V6-V1-V7-V4。此時最短路徑的最優(yōu)值為1270.97146。

從上述導(dǎo)航系統(tǒng)對物流車的動態(tài)導(dǎo)航可以發(fā)現(xiàn)，導(dǎo)航系統(tǒng)總是使物流車在當(dāng)前時刻的行駛路徑是最優(yōu)的。只要在物流車將要通過而未通過的路段上發(fā)生堵車，則導(dǎo)航系統(tǒng)就會為物流車余下的路線重新規(guī)劃一個最短路徑。同樣，當(dāng)某個堵車路段的堵車解除而該路段兩端的客戶都未遍歷，則航系統(tǒng)也會為物流車余下的路線重新規(guī)劃一個最短路徑。

從導(dǎo)航系統(tǒng)為物流車進(jìn)行導(dǎo)航的算法可知，導(dǎo)航系統(tǒng)先要為物流車進(jìn)行一次靜態(tài)回溯優(yōu)化，而是否需要動態(tài)回溯優(yōu)化取決于物流車在行駛過程中是否發(fā)生堵車事件。只有當(dāng)物流車在規(guī)劃的路線前方出現(xiàn)堵車時，導(dǎo)航系統(tǒng)才需要為物流車余下的路線進(jìn)行重新規(guī)劃。因此，物流車在最好的情況下，也需要進(jìn)行一次靜態(tài)回溯優(yōu)化。靜態(tài)回溯在最壞情況下可能需要更新當(dāng)前最優(yōu)解O((n-1)!)，每次更新最優(yōu)解需O(n)，從而整個算法的時間復(fù)雜度為O(n!)。

一旦發(fā)生堵車情況，則導(dǎo)航系統(tǒng)所花費(fèi)的時間就一定大于O(n!)。算法仿真發(fā)現(xiàn)，當(dāng)n>14時，靜態(tài)導(dǎo)航就無法滿足導(dǎo)航的適時性要求?？傊诨厮莘ǖ膶?dǎo)航系統(tǒng)只適于n?14的情形。算法的優(yōu)點(diǎn)是能夠計(jì)算出物流車的最優(yōu)路徑而不是近似最優(yōu)路徑，缺點(diǎn)是不適合客戶點(diǎn)較多的情形。

5 結(jié)論

針對目前的TSP算法無法解決物流車出現(xiàn)堵車時的最短路徑問題，本文用回溯法實(shí)現(xiàn)了物流車的動態(tài)優(yōu)化問題。該算法的優(yōu)點(diǎn)是能夠得到物流車動態(tài)導(dǎo)航的精確解，缺點(diǎn)是無法滿足客戶較多時的適時性要求。因此，用智能算法實(shí)現(xiàn)物流車的動態(tài)導(dǎo)航是筆者下一步研究的重點(diǎn)。

[1] 王勝訓(xùn),李艷穎.一種求解TSP的自適應(yīng)蟻群優(yōu)化算法[J].西安工程大學(xué)學(xué)報(bào),2013, 27(6):840-844.

[2] 謝曼.一種混合粒子群優(yōu)化算法在TSP中的應(yīng)用 [J].太原理工大學(xué)學(xué)報(bào),2013,44(4):506-509.

[3] 賈瑞玉,李亞龍,管玉勇.求解旅行商問題的混合量子蟻群算法[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(22):36-39.

[4] 趙俊生.求解TSP問題的新型量子一蟻群算法[J].自動化與儀器儀表,2013,14(4):194-195.

[5] 王勝,譚家政.求解TSP問題的改進(jìn)蟻群算法[J].武漢理工大學(xué)學(xué)報(bào),2013,35(3):340-344.

[6] 李鼎,孟杰.求解TSP的改進(jìn)模擬退火算法研究[J].科學(xué)技術(shù)與工程,2013,13(25):7552-7556.

[7] 柳寅,馬良.模糊人工蜂群算法的旅行商問題求解[J].計(jì)算機(jī)應(yīng)用研究,2013,30(9):2694-2696.

[8] 徐京雷,趙洪超,劉希玉.旅行商問題的閉環(huán)DNA算法[J].計(jì)算機(jī)工程與科學(xué), 2014,36(1):111-114.

[9] 郭小燕,王聯(lián)國,代永強(qiáng).基于分段混合蛙跳算法的旅行商問題求解[J].計(jì)算機(jī)工程, 2014,40(1):191-198.

[10] 于瑩瑩,陳燕,李桃迎.改進(jìn)的蟻群遺傳算法求解旅行商問題[J].計(jì)算機(jī)仿真,2013,30(11):317-320.

[11] 尤夢麗,雷秀娟. 改進(jìn)的細(xì)菌覓食算法求解TSP問題[J].廣西大學(xué)學(xué)報(bào),2013,38(6):1436-1443.

[12] 王防修,劉春紅.基于哈夫曼編碼的選擇算法.武漢輕工大學(xué)學(xué)報(bào),2016,35(2):79-82。

Application of backtracking in logistics vehicle dynamic navigation

WANGFang-xiu1,WANGXiao-na1,QIHua-qing2,ZHAOJie-mei1

(1.School of Mathematics and Computer Science Wuhan Polytechnic University, Wuhan 430023, China; 2.School of Economics and Management,Wuhan Polytechnic University,Wuhan 430023,China)

In this paper,dynamic navigation problem of a Logistics vehicle is researched. Because a logistics vehicle often encounters a traffic jam situation in the distribution process，so if the car still distributes in accordance with the original optimal path, it will reduce the distribution efficiency of the logistics vehicle. Traditional TSP algorithm can only supply a static optimal route for a logistics vehicle.Once the logistics vehicle is jammed in traffic,the route can’t be adjusted so that the navigation can’t improve the distribution efficiency of the logistics vehicle. To avoid this shortcoming, this paper presents a backtracking to achieve dynamic optimization distribution algorithm for the logistics vehicle. First, it uses the backtracking to achieve static optimization distribution route for the logistics vehicle and this path is regarded as the initial path of the logistics vehicle. If there is a traffic jam in the path in front of the logistics vehicle, it uses the backtracking to re-plan a new shortest path to improve the distribution efficiency for the logistics vehicle. If a section of the road is jammed and the both ends customers of the line has not been visited, it uses the backtracking to re-plan shortest path for the unvisited customers to improve the delivery efficiency. Experimental results show that the proposed algorithm can effectively improve the distribution efficiency for the logistics vehicle.

backtracking; dynamic navigation; optimal path；logistics vehicle distribution；distribution efficiency

2017-02-13.

王防修(1973-),男,副教授,E-mail:wfx323@126.com.

糧食公益性行業(yè)科研專項(xiàng)(201513004-3);湖北省自然科學(xué)基金項(xiàng)目(2016CFB273);校立大學(xué)生科研項(xiàng)目(xsky2016036).

2095-7386(2017)02-0073-05

10.3969/j.issn.2095-7386.2017.02.014

TP391

A