物流配送線路優(yōu)化Matlab算法研究

劉亞娟+木仁

[摘 要]“最后一公里”的配送問(wèn)題屬于物流配送車(chē)輛路徑優(yōu)化問(wèn)題。針對(duì)物流配送線路選取過(guò)程中所缺乏的可嵌入系統(tǒng)的簡(jiǎn)易優(yōu)化算法的缺陷，提出了基于逐點(diǎn)調(diào)整法、雙點(diǎn)交換法的綜合算法。該方法通過(guò)對(duì)單個(gè)節(jié)點(diǎn)進(jìn)行位置調(diào)整和任意調(diào)整兩個(gè)節(jié)點(diǎn)位置的綜合運(yùn)用，不僅可取得較優(yōu)的配送線路，且在算法的可推廣應(yīng)用方面具備較強(qiáng)優(yōu)勢(shì)。

[關(guān)鍵詞]線路優(yōu)化；最短路線；綜合算法；Matlab

[DOI]10.13939/j.cnki.zgsc.2016.32.041

1 引 言

“最后一公里”的派件問(wèn)題屬于物流配送車(chē)輛路徑優(yōu)化問(wèn)題。物流配送車(chē)輛路徑優(yōu)化問(wèn)題（Vehicle Routing Problem，VRP）是以最少車(chē)輛數(shù)、最小車(chē)輛總行程完成貨物的配送任務(wù)，從而達(dá)到成本最小或時(shí)間最短等目標(biāo)。[1]它最早是由Dantizg和Ramser[2]于1959年首次提出的。由于VRP問(wèn)題是一個(gè)NP難問(wèn)題，采用精確優(yōu)化算法對(duì)其進(jìn)行求解，計(jì)算量與問(wèn)題的規(guī)模呈指數(shù)增加關(guān)系，因此當(dāng)規(guī)模增大時(shí)，計(jì)算機(jī)計(jì)算復(fù)雜度相當(dāng)大，實(shí)際中其應(yīng)用范圍比較有限。[3]

在國(guó)外，Vinicius W.C.Morais，Geraldo R.Mateus，Thiago F.Noronha（2014）[4]發(fā)現(xiàn)大多數(shù)的作品在研究VRPCD問(wèn)題時(shí)是基于禁忌搜索，而他們并沒(méi)有局限于禁忌搜索，而是只探索可行的空間解決方案。由于沒(méi)有計(jì)算努力花在不可行解決方案上的時(shí)間，從而使得運(yùn)算結(jié)果更有效。Fatma Pinar Goksal，Ismail Karaoglan和Fulya Altiparmak（2013）[5]提出了一種基于離散粒子群優(yōu)化（PSO）和變鄰域搜索算法的混合搜索算法來(lái)解決同時(shí)派件和收件的車(chē)輛路徑問(wèn)題，其具有很好的優(yōu)化能力，但是，當(dāng)節(jié)點(diǎn)較多時(shí)，算法運(yùn)行卻是一個(gè)相當(dāng)耗費(fèi)時(shí)間的過(guò)程。Mohamed Cheikh，Mustapha Ratli，Omar Mkaouar，Bassem Jarboui（2015）[6]提出了一種基于四個(gè)不同的領(lǐng)域結(jié)構(gòu)的變鄰域搜索算法來(lái)找到合適的旅行路線。鄰域結(jié)構(gòu)1和3旨在最小化旅行路線和時(shí)間，鄰域結(jié)構(gòu)2和4旨在最小化時(shí)間。結(jié)果表明，此算法給出的運(yùn)算結(jié)果質(zhì)量較高。

在國(guó)內(nèi)，陳韋志（2007）[7]從考慮最短的運(yùn)輸路徑與最少的運(yùn)輸費(fèi)用兩個(gè)角度建立車(chē)輛路徑規(guī)劃（VRP）模型。構(gòu)造出最大——最小蟻群算法，避免了傳統(tǒng)蟻群算法易陷入局部最優(yōu)解、求解速度較慢的缺陷，體現(xiàn)了改進(jìn)蟻群算法的相對(duì)優(yōu)越性。但是，其研究的VRP對(duì)于時(shí)間上的要求并不是很高，而且所考慮的客戶點(diǎn)規(guī)模并不是特別大。張紅艷（2005）[8]建立了考慮線路安排的物流配送方案模型，并提出了求解該問(wèn)題的一種自適應(yīng)遺傳算法，模擬結(jié)果表明改進(jìn)的遺傳算法明顯增強(qiáng)了群體演化的質(zhì)量，提高了算法的收斂速度，求得了問(wèn)題的優(yōu)良解。許國(guó)平、葉效鋒、鮑立威（2004）[9]將模擬退火和遺傳算法相結(jié)合的進(jìn)化算法用于解決車(chē)輛路徑問(wèn)題。避免了遺傳算法中存在的早熟收斂問(wèn)題，增強(qiáng)了算法的全局收斂性，并且提高了算法的收斂速度。王華東、李巍（2012）[10]指出傳統(tǒng)算法搜索最優(yōu)路線時(shí)間長(zhǎng)，難以找到最優(yōu)配送路線，導(dǎo)致物流配送成本高。針對(duì)此缺陷，提出了一種動(dòng)態(tài)的慣性權(quán)值ω非線性變化PS粒子群算法，提高了物流配送路徑優(yōu)動(dòng)態(tài)的化成功率。

針對(duì)物流派件線路選取過(guò)程中所缺乏的簡(jiǎn)易優(yōu)化方法的缺陷，同時(shí)滿足調(diào)度需求越快越好的要求，在此提出了基于逐點(diǎn)調(diào)整法和雙點(diǎn)交換法的綜合算法。該算法不僅簡(jiǎn)單，優(yōu)化效果較好，而且穩(wěn)定性較強(qiáng)。在錄入一定的業(yè)務(wù)量、車(chē)輛數(shù)量和區(qū)域信息后，會(huì)快速地規(guī)劃出合理的派送路線，應(yīng)急有效，比傳統(tǒng)的憑人工經(jīng)驗(yàn)選擇路線要好很多，且在算法的可推廣應(yīng)用方面具備較強(qiáng)優(yōu)勢(shì)。

2 相關(guān)算法概述

目前比較常用的簡(jiǎn)單而有效的算法主要有：窮舉法、改進(jìn)窮舉法、隨機(jī)窮舉法、二次逐邊修正法、逐點(diǎn)調(diào)整法、兩點(diǎn)交換法和綜合法。

2.1 窮舉法

在Matlab中通過(guò)perms命令可以生成指定向量的所有可能的排列，而每一組排列可對(duì)應(yīng)一個(gè)可能的派件方案，在所有這些排列中一定存在一組排列的總派件里程是最短的，從而我們就可以找到最優(yōu)派件方案。

2.2 改進(jìn)窮舉法

在Matlab中通過(guò)perms命令至多可以生成向量長(zhǎng)度不超過(guò)9的全排列，因此當(dāng)節(jié)點(diǎn)個(gè)數(shù)多于9個(gè)節(jié)點(diǎn)時(shí)利用perms命令將無(wú)法直接獲取到最優(yōu)解。屆時(shí)考慮到對(duì)于節(jié)點(diǎn)進(jìn)行合并后再利用窮舉法。節(jié)點(diǎn)的合并原則如下：

定義1 在一個(gè)城區(qū)交通網(wǎng)絡(luò)布局下派件節(jié)點(diǎn)集合X中的兩個(gè)節(jié)點(diǎn)a和b稱為可合并的，如果X中不存在任何節(jié)點(diǎn)與a或b之間的距離小于2倍的a與b之間的距離。

改進(jìn)窮舉法基本思想：為了增加利用窮舉法派件過(guò)程中的節(jié)點(diǎn)個(gè)數(shù)，利用上述定義可對(duì)節(jié)點(diǎn)進(jìn)行合并，在未合并節(jié)點(diǎn)及合并節(jié)點(diǎn)集合個(gè)數(shù)總和不超過(guò)9，且每個(gè)合并節(jié)點(diǎn)集合中的節(jié)點(diǎn)個(gè)數(shù)不超過(guò)10的前提下繼續(xù)使用窮舉法生成一個(gè)優(yōu)化派件順序。具體步驟如下：

（a）利用窮舉法生成節(jié)點(diǎn)及合并節(jié)點(diǎn)集合的優(yōu)化派件順序，在這里我們從所有合并節(jié)點(diǎn)集合中任意選擇一個(gè)節(jié)點(diǎn)并與未合并節(jié)點(diǎn)構(gòu)成集合后窮舉獲得派件順序。

（b）根據(jù)在（a）中所獲得的優(yōu)化派件順序確定臨近派件順序并確定合并節(jié)點(diǎn)集合中的節(jié)點(diǎn)派件順序。

2.3 隨機(jī)窮舉法

在利用窮舉法或改進(jìn)窮舉法依然無(wú)法計(jì)算獲得優(yōu)化派件順序時(shí)，可通過(guò)Maltab中的隨機(jī)實(shí)驗(yàn)來(lái)獲取較優(yōu)結(jié)果。其基本思想是利用Matlab中隨機(jī)排列生成命令randperm生成一個(gè)隨機(jī)排列，并通過(guò)不斷的優(yōu)勝劣汰的方式獲取到較優(yōu)派件順序，當(dāng)實(shí)驗(yàn)次數(shù)充分多時(shí)就可以獲取到較優(yōu)派件結(jié)果。

2.4 二次逐邊修正法

當(dāng)節(jié)點(diǎn)個(gè)數(shù)較多時(shí)利用隨機(jī)窮舉法所獲取到的結(jié)果與最優(yōu)派件結(jié)果之間的差距依然巨大，甚至都沒(méi)有基于臨近派件原則（每次總找到最近的未派件節(jié)點(diǎn)進(jìn)行派件）獲取到了結(jié)果好。為了獲取到更好的派件結(jié)果，需要對(duì)隨機(jī)窮舉法獲取到的每次派件結(jié)果進(jìn)行進(jìn)一步的優(yōu)化，目前較常用的優(yōu)化方法是二次逐邊修正法。

2.5 逐點(diǎn)調(diào)整法

通過(guò)利用二次逐邊法優(yōu)化出的派件結(jié)果不僅受初始派件順序的影響，同時(shí)也與各節(jié)點(diǎn)的交換順序存在較強(qiáng)關(guān)系。在很多情況下利用二次逐邊修正法所能夠優(yōu)化的里程并不多，因此為了更進(jìn)一步進(jìn)行優(yōu)化，考慮對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行逐個(gè)調(diào)整。算法基本思路就是對(duì)已有派件線路中的各節(jié)點(diǎn)進(jìn)行位置調(diào)整，如果節(jié)點(diǎn)調(diào)整位置后總派件距離得到改進(jìn)，則新位置將替代原位置并進(jìn)行不斷的循環(huán)改進(jìn)，直到對(duì)所有節(jié)點(diǎn)的位置調(diào)整均不能改進(jìn)總派送距離為止。

2.6 兩點(diǎn)交換法

鑒于二次逐邊修正法僅能調(diào)整鄰近節(jié)點(diǎn)位置的缺陷，利用窮舉法可調(diào)整任意兩個(gè)節(jié)點(diǎn)的位置，從而優(yōu)化結(jié)果能夠更加全面。

2.7 綜合法

通過(guò)交替使用逐點(diǎn)調(diào)整法及兩點(diǎn)交換法，可不斷對(duì)派件線路進(jìn)行優(yōu)化，進(jìn)一步為了獲取到更優(yōu)的派件結(jié)果，可添加節(jié)點(diǎn)插入及交換隨機(jī)因子，以保證窮舉的全面性。

3 結(jié) 論

“最后一公里”的派件問(wèn)題實(shí)際上歸屬于行遍性問(wèn)題，即派件員派件時(shí)，從配送中心出發(fā)，經(jīng)過(guò)他所派送范圍內(nèi)的所有客戶節(jié)點(diǎn)，然后返回配送中心。相關(guān)學(xué)者雖然提出了蟻群算法、遺傳算法、模擬退火等方法，但是此類算法迭代速度過(guò)緩、耗費(fèi)時(shí)間長(zhǎng)，可推廣性不強(qiáng)。針對(duì)此類缺陷，本文提出了基于逐點(diǎn)調(diào)整法和雙點(diǎn)交換法的綜合算法。采用此種方法進(jìn)行優(yōu)化，大大增強(qiáng)了獲取最優(yōu)解的可能性。同時(shí)，既解決了現(xiàn)有算法存在的缺陷，又大大提高了派件速度，具有很強(qiáng)的現(xiàn)實(shí)應(yīng)用價(jià)值。

參考文獻(xiàn)：

[1]袁慶達(dá)，閆昱，周再玲.TabuSearch算法在優(yōu)化配送路線問(wèn)題中的應(yīng)用[J].計(jì)算機(jī)工程，2001（11）：86-89.

[2]Dantzig G B，Ramser J H.The Truck Dispatching Problem[J].Management Science，1959，6（1）：80-91.

[3]程明輝，齊名軍.基于粒子群算法的物流配送路徑優(yōu)化問(wèn)題研究[J].中國(guó)外資，2008（8）：254.

[4]Morais V W C，Mateus G R，Noronha T F.Iterated Local Search Heuristics for the Vehicle Routing Problem with Cross-Docking[J].Expert Systems with Applications，2014，41（16）.

[5]Goksal F P，Karaoglan I，Altiparmak F.A Hybrid Discrete Particle Swarm Optimization for Vehicle Routing Problem with Simultaneous Pickup and Delivery[J].Computers & Industrial Engineering，2013，65（1）： 39-53.

[6]Cheikh M，Ratli M，Mkaouar O，et al.A Variable Neighborhood Search Algorithm for the Vehicle Routing Problem with Multiple Trips[J].Electronic Notes in Discrete Mathematics，2015，47： 277-284.

[7]陳韋志.配送中心的運(yùn)輸路徑優(yōu)化研究[D].武漢：武漢理工大學(xué)，2007.

[8]張紅艷.關(guān)于物流配送中心車(chē)輛路徑優(yōu)化問(wèn)題的研究[D].大連：東北財(cái)經(jīng)大學(xué)，2005.

[9]許國(guó)平，葉效鋒，鮑立威.基于模擬退火遺傳算法的車(chē)輛路徑問(wèn)題研究[J].工業(yè)控制計(jì)算機(jī)，2004（6）：49-50.

[10]王華東，李巍.粒子群算法的物流配送路徑優(yōu)化研究[J].計(jì)算機(jī)仿真，2012（5）：243-246.