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

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

回溯法在物流車(chē)動(dòng)態(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)

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

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

1 引言

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

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

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

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

物流配送是一個(gè)TSP問(wèn)題，給定n個(gè)站點(diǎn)(1個(gè)倉(cāng)庫(kù)和n-1個(gè)客戶)間的權(quán)重ω(i,j),i,j∈{1,2,…,n}。如果ω(i,j)≠0，則物流車(chē)可以從站點(diǎn)i直接到達(dá)站點(diǎn)j；否則，物流車(chē)從站點(diǎn)i無(wú)法直接到達(dá)站點(diǎn)j，需要中轉(zhuǎn)其它站點(diǎn)才能到達(dá)。尋找一種遍歷所有站點(diǎn)且對(duì)每個(gè)站點(diǎn)僅訪問(wè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表示物流車(chē)的始發(fā)站點(diǎn)(倉(cāng)庫(kù))，xij∈V-{s}，j=2,…,n。且?k≠j，有xik≠xij。則物流配送問(wèn)題的數(shù)學(xué)模型表示如下：

(1)

(2)

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

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

(3)

(4)

(5)

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

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

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

設(shè)現(xiàn)有1個(gè)倉(cāng)庫(kù)和n-1個(gè)客戶，則可以對(duì)這n個(gè)位置編號(hào)為1,2,…,n。如果d(i,j)=w(i,j),?i,j∈{1,2,…,n}，則如果d(i,j)≠0，則表示位置i和位置j之間能夠相互直達(dá)。在物流車(chē)配送過(guò)程中，需要為其動(dòng)態(tài)選擇一個(gè)路徑best_xi，i=1,2,…,n，使得物流車(chē)在當(dāng)前時(shí)刻的行駛路徑總是最優(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)化算法

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

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

步驟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的過(guò)程如下：

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

(2)如果j

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

3.2 堵車(chē)時(shí)的TSP動(dòng)態(tài)回溯優(yōu)化算法

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

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

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

(8)

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

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

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

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

(9)

3.3 堵車(chē)解除時(shí)的TSP動(dòng)態(tài)回溯優(yōu)化算法

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

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

(10)

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

對(duì)物流車(chē)配送過(guò)程導(dǎo)航如下：

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

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

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

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

4 算法仿真及分析

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

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

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

圖1 倉(cāng)庫(kù)與客戶位置

圖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)。

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

圖2 沒(méi)有堵車(chē)的最優(yōu)路徑

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

針對(duì)目前的TSP算法無(wú)法解決物流車(chē)出現(xiàn)堵車(chē)時(shí)的最短路徑問(wèn)題，本文用回溯法實(shí)現(xiàn)了物流車(chē)的動(dòng)態(tài)優(yōu)化問(wèn)題。該算法的優(yōu)點(diǎn)是能夠得到物流車(chē)動(dòng)態(tài)導(dǎo)航的精確解，缺點(diǎn)是無(wú)法滿足客戶較多時(shí)的適時(shí)性要求。因此，用智能算法實(shí)現(xiàn)物流車(chē)的動(dòng)態(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] 賈瑞玉,李亞龍,管玉勇.求解旅行商問(wèn)題的混合量子蟻群算法[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(22):36-39.

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

[5] 王勝,譚家政.求解TSP問(wèn)題的改進(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] 柳寅,馬良.模糊人工蜂群算法的旅行商問(wèn)題求解[J].計(jì)算機(jī)應(yīng)用研究,2013,30(9):2694-2696.

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

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

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

[11] 尤夢(mèng)麗,雷秀娟. 改進(jìn)的細(xì)菌覓食算法求解TSP問(wèn)題[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