劉亞娟+木仁

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

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

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

1 引 言

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

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

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

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

2 相關算法概述

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

2.1 窮舉法

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

2.2 改進窮舉法

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

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

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

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

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

2.3 隨機窮舉法

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

2.4 二次逐邊修正法

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

2.5 逐點調(diào)整法

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

2.6 兩點交換法

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

2.7 綜合法

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

3 結 論

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

參考文獻：

[1]袁慶達，閆昱，周再玲.TabuSearch算法在優(yōu)化配送路線問題中的應用[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)化問題研究[J].中國外資，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ōu)化研究[D].武漢：武漢理工大學，2007.

[8]張紅艷.關于物流配送中心車輛路徑優(yōu)化問題的研究[D].大連：東北財經(jīng)大學，2005.

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

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