王曉博，任春玉，李海晨

多車型開放式車輛路線問題的混合啟發(fā)式算法

王曉博，任春玉，李海晨

多車型開放式車輛路線問題，是物流配送優(yōu)化中不可缺少的環(huán)節(jié)。針對標準遺傳算法存在收斂速度慢，局部搜索能力差，易早熟的缺點，采用混合啟發(fā)式算法進行優(yōu)化求解。采用實數(shù)序列編碼，使問題變得更簡潔；有針對性地構(gòu)建初始解，提高了解的可行性；用基于排序的選擇與最佳保留相結(jié)合策略，保證群體的多樣性；引入部分算術交叉算子，加強染色體的全局搜索能力；利用模擬退火算法的Boltzmann機制，控制遺傳算法的交叉、變異操作，提高了算法的收斂速度和搜索效率。仿真結(jié)果表明混合啟發(fā)式算法在求解質(zhì)量和計算效率上好于標準遺傳算法。

多車型開放式車輛路線問題；實數(shù)序列編碼；部分算術交叉算子；Boltzmann機制；混合啟發(fā)式算法

1 引言

開放式車輛路線問題（Open Vehicle Routing Problem，OVRP）是經(jīng)典車輛路線問題（Vehicle Routing Problem，VRP）的拓展問題。OVRP和VRP最顯著的區(qū)別在于：車輛在服務完最后一個顧客點后，不要求其回到出發(fā)車場，若需要回到車場，則必須沿原路返回。

目前研究較多的是車輛路線封閉問題，就是大家所熟知的VRP問題，但對于開放的車輛路線安排問題的研究結(jié)果還不多。

OVRP問題研究方法主要有精確算法、啟發(fā)式算法和智能優(yōu)化方法。精確性算法在可以求解的情況下，其解通常要優(yōu)于人工智能算法；但其算法只能有效求解中小規(guī)模的OVRP問題[1]。

在解決實際較大規(guī)模的問題時，啟發(fā)式算法能夠在較少時間內(nèi)，求出滿足實際需要的滿意解，盡管這個解實際上不是最優(yōu)的。Bodin運用改進C-W節(jié)約算法來求解美國航空信件的郵遞問題[2]。Sariklis給出了一種新的兩階段啟發(fā)式算法：首先，考慮車載量的限制約束條件，先將顧客進行分組；其次，在每一組中確定最終的車輛路線；但其結(jié)果與最優(yōu)結(jié)果有比較大的偏差[3]。Repoussis采用改進的貪婪算法求解開放式車輛路徑問題[4]。Li提出基于掃描法和插入法的帶記錄效應啟發(fā)式算法，求解帶路程長度約束的OVRP問題[5]。

在求解大規(guī)模、復雜問題時，智能優(yōu)化算法應用更廣泛。Brandao通過最近鄰居法和K度方法產(chǎn)生初始解，用禁忌搜索算法求解一類有能力約束的OVRP問題[6]。Fu通過隨機的方法和最遠者優(yōu)先啟發(fā)式算法FFH（Farthest First Heuristic）產(chǎn)生初始解，提出了解決有容量和路程長度約束的OVRP的禁忌搜索算法[7]。文獻[8]利用禁忌搜索算法研究了無時間約束、有最大行駛時間約束和有時間窗約束的OVRP問題。鐘石泉提出了核心路徑的概念和原理，并設計有能力約束和距離約束的開放式車輛路徑問題的禁忌算法[9]。Yslo改進了標準的模擬退火算法以一定的概率來接受較差的解，通過設定一個閾值T來決定是否接受一個解，并建立了基于閾值接收算法（Threshold Accepting，TA）的啟發(fā)式算法[10]。Tarantilis在此基礎上設立一個閾值的列表，算法迭代時每次則從閾值表中選擇最大的元素作為閾值，算法迭代過程閾值列表不斷更新[11]。李相勇提出了一種混合蟻群優(yōu)化算法，其主體是一個在超立方框架下執(zhí)行的MAX-MIN螞蟻系統(tǒng)，計算結(jié)果表明該算法能有效地求解開放式車輛路徑問題[12]。肖天國通過應用交叉、變異概率的自適應機制和交叉算子等技術，構(gòu)造一個求解OVRP問題的遺傳算法[13]。鄧猛通過設計基于自然數(shù)編碼的遺傳算法來求解OVRP問題[14]。

然而，相對于OVRP，具有多車型的開放式車輛路徑問題（Heterogeneous Open Vehicle Routing Problem，HOVRP）的研究相對較少，其建模與求解也更加復雜和困難。在實際的運營中，多用一輛車帶來固定成本的增加遠遠比其因總里程縮短而減少的成本要大許多，因此減少服務的車輛數(shù)目是降低總成本的有效方法之一。

為此，本文以減少車輛數(shù)目為出發(fā)點，建立多車型的開放式車輛路徑問題數(shù)學模型，并從整體上設計了求解HOVRP問題的混合啟發(fā)式算法。

2 數(shù)學模型

式中，G{gr|r=1，2，…，R}為一系列可行R處的配送中心集合；H{hi|i=R+1，…，R+N}為一系列可行N處的客戶集合；S{G}∪{H}為所有配送中心和客戶總和；V{vlk|l= 1，2，…，L k=1，2，…，K}為L車型的運輸車輛K集合；qi為客戶需求量；為車輛類型的載重量；dij為客戶i到客戶 j的直線距離；為L車型的車輛K的最大行駛里程。

式（1）中，目標函數(shù)為求配送中心到客戶運輸里程的極小值；約束條件（2）確保每個客戶僅由一個類型的一個運輸車輛提供服務；約束條件（3）為運輸工具容量的約束條件，滿足在每條線路上行駛的車輛都不超過其載重量；約束條件（4）確保車輛最多只能到達某個客戶點一次；約束條件（5）確保某一輛車最多只能從某收貨點發(fā)出一次；約束條件（6）為運輸車輛行駛里程都不超過其最大行駛里程。

3 混合啟發(fā)式算法應用描述

3.1 實數(shù)序列編碼

對于多車型配送問題，編碼時考慮車輛的選取。因此，采用n位實數(shù)序列編碼，其中配送貨物的編號為n(1，2，…，n)，運輸車輛的編號為k(1，2，…，k)。具體編碼形式為(x1，x2，…，xi，…，xn)，每個基因的取值為 xi=k∈(1，2，…，k)。xi=k表示貨物i安排在第k輛車上。以n=9，k=3編碼(1，3，2，1，3，2，3，3，2)為例，編碼表示一種配送方案為：貨物(1，4)安排在1號車輛上；貨物(3，6，9)安排在2號車輛上；貨物(2，5，7，8)安排在3號車輛上。

3.2 初始解的形成

設hk為車輛k所運送的客戶點總數(shù)，集合Rk={yik|0≤i≤hk}對應第k輛車運送的客戶點，Yik表示車輛k服務于節(jié)點i，Y0k表示第k輛車的起始點為配送中心。初始解的形成步驟如下：

步驟2一條染色體上第i基因所對應的客戶需求量為qi，令k=1。

步驟5如果k＞K，則k=K；否則，k=k。

步驟6k=k+1，轉(zhuǎn)入步驟3。

步驟7i=i+1，轉(zhuǎn)入步驟2。

步驟8重復步驟2至步驟7，K記錄所用車輛總數(shù)，Rk記錄一組可行路徑。

3.3 適應度函數(shù)

采用輪盤賭選擇法，要求適應度函數(shù)為非負，通過下面的變化將目標函數(shù)轉(zhuǎn)化為適應度函數(shù)：

其中，fm為第m個染色體的適應度，n為一常數(shù)，z1為初始種群中最好染色體所對應的配送里程，zm為目前染色體所對應的配送里程。

3.4 選擇算子

為了能夠保持全局搜索能力，避免出現(xiàn)早熟現(xiàn)象，本文提出了一種將最佳個體保留與基于排序的選擇策略相結(jié)合的最佳保留選擇法。

表1 實驗數(shù)據(jù)

設a、b是一個常數(shù)，滿足關系b=2(a-1),1≤a≤2,文中取a=1.5,b=1。構(gòu)造線性函數(shù)其中i=1，2，…，N。具體步驟如下：

步驟1計算種群中每個個體的適應度值 fi，并按非遞增次序排序。

步驟2找出當前群體中適應度值最高的個體，令其為fbest。

步驟4隨機生成一個[0，1]之間的數(shù)δ,如果 p1+…+ pi-1＜δ＜p1+…+pi-1+pi,選擇個體i進入到下一代種群中，重復選擇N次，生成下一代種群的N個個體。

步驟5找出新種群中適應度值最高的個體 f′now1和適應度值最低的個體 f′now2。

步驟6如果 f′now1＞fbest，則 fbest=f′now1；否則，用最好個體 fnow1替換目前群體中的最差個體 fnow2。

3.5 交叉算子

針對實數(shù)序列編碼，采用部分算術交叉算子。部分算術交叉算子一方面保持了種群進化的多樣性，保證算法能夠收斂到全局最優(yōu)；另一方面，能夠保留雙親的優(yōu)良基因組片斷，限制不可行解出現(xiàn)，從而提高種群的收斂速度。

設兩個父代個體分別為x0=(x1，x2，…，xn)，y0=(y1，y2，…，yn)，經(jīng)交叉后得到的子個體為 x′=(x′1，x′2，…，x′n)和 y′= (y′1，y′2，…，y′n)。選擇父代個體中第k位以后基因作為交叉段，在（0，1）之間隨機生成n-k個隨機數(shù)ak+1，ak+2，…，an，經(jīng)交叉后得到的子個體定義為：

實驗表明，對于實數(shù)編碼，采用部分算術交叉算子比采用其他算子效率更高。

3.6 變異算子

對于變異操作，采用部分路徑翻轉(zhuǎn)的方式。經(jīng)過驗證，部分路徑翻轉(zhuǎn)的變異方式有利于跳出局部最優(yōu)解，這種變異操作可以改善算法的效率。

3.7 模擬退火操作

設某代產(chǎn)生個體的適應度值為 f1，經(jīng)過遺傳算法的選擇、交叉和變異，產(chǎn)生新個體的適應度值為 f2，設定Δf=f2-f1。

根據(jù)個體適應性的變異值Δf和概率值exp(-Δf/T)控制個體，具體步驟如下：

步驟1如果Δf＜0，適應度值 f2個體被保存在下一代里，并且適應度值 f1個體被從總體中刪除。

步驟2如果Δf＞0，計算exp(-Δf/T)。

步驟3當exp(-Δf/T)＞[0，1]間的隨機數(shù)，那么適應度值為 f1的個體保留在下一代中，適應度值為 f2的個體被刪除。

步驟4當exp(-Δf/T)≤[0，1]間的隨機數(shù)，那么適應度值為 f2的個體保留在下一代中，適應度值為 f1的個體被刪除。

4 實驗計算與結(jié)果分析

本實驗數(shù)據(jù)取自文獻[15]，并加以擴展。假設有18個顧客點，由中心派出車輛來完成各個顧客的需求。隨機產(chǎn)生中心坐標（50，69）和18個顧客的坐標，各個顧客的需求量在（0，1）區(qū)間內(nèi)隨機產(chǎn)生，如表1所示。車輛分為A、B、C三種。A類載重量為1，數(shù)量若干；B類載重量為1.5，數(shù)量為3輛；C類載重量為1.8，數(shù)量為2輛。各客戶之間與中心和客戶之間距離均采用直線距離。

圖1 中心和客戶位置圖

4.1 混合啟發(fā)式算法求解

經(jīng)反復實驗，采用以下參數(shù)：群體規(guī)模取80，最大迭代次數(shù)取500，交叉概率 pc=0.83，變異概率 pm=0.016，初始溫度T0=120℃，降溫系數(shù)δ=0.75。隨機求解10次，計算結(jié)果見表2。從表2中可以看出，在用本文設計的混合啟發(fā)式算法對實例的10次求解中，都得到了質(zhì)量較高的解，總里程的均值271.5 km，平均使用車輛5。算法的計算結(jié)果相當穩(wěn)定，最差解的總里程僅比最好的解多4.6%。從計算效率上看，10次求解中有3次達到了最好解，2次達到了次最好解，可見效率較高。

表2 混合啟發(fā)式算法求解HOVRP問題計算結(jié)果

其中，最好解的總里程266.6 km，具體行車路線見表3和圖2。

表3 優(yōu)化結(jié)果

圖2 配送路線圖

4.2 混合遺傳算法求解

[14-15]設計改進混合遺傳算法，求解OVRP問題。為對比測試需要，本文采用此算法來求解HOVRP問題。

隨機求解10次，計算結(jié)果見表4，其中，最優(yōu)里程為229 km，具體見表5和圖3。

4.3 兩種算法比較

如表6，本文設計的混合啟發(fā)式算法，無論在尋優(yōu)結(jié)果、計算效率，以及算法的穩(wěn)定性上均好于改進的遺傳算法。

表4 改進混合遺傳算法求解HOVRP問題計算結(jié)果

表5 車輛調(diào)度結(jié)果

圖3 配送線路示意圖

表6 改進混合遺傳算法和本文算法比較

5 結(jié)論

仿真實驗表明本文算法具有抗早熟能力強，收斂速度快和局部搜索能力強的特點，充分顯示了其良好的尋優(yōu)能力，大大提高了優(yōu)化質(zhì)量。本文算法為解決多車型開放式車輛調(diào)度問題提供了一個非常有效的求解方法。

參考文獻：

[1]Letchford A N，Lysgaard J，Eglese R.A branch and cut algorithm for the capacitated open vehicle routing problem[J]. Journal of the Operational Research Society，2007，58（12）：1642-1651.

[2]Bodin L，Golden B，Assad A，et al.Routing and scheduling of vehicles and crews：the state of art[J].Computers and Operations Research，1983，10：63-211.

[3]Sariklis D，Powell S.A heuristic method for the open vehicle routing problem[J].Journal of the Operational Research Society，2000，51：564-573.

[4]Repoussis P P，Tarantilis D，Ioannou G.The open vehicle routing problem with time windows[J].Journal of the Operational Research Society，2007，58（3）：355-367.

[5]Li F，Golden B，Wasil E.The open vehicle routing problem：algorithms，large-scale test problems，and computational results[J]. Computers and Operations Research，2007，34：2918-2930.

[6]Brandao J.A tabu search algorithm for the open vehicle routing problem[J].European Journal of Operational Research，2004，157（3）：552-564.

[7]Fu Z，Eglese R，Li L.A new tabu search algorithm for the open vehicle routing problem[J].Journal of the Operational Research Society，2005，56（3）：267-274.

[8]?zyurt Z，Aksen D，Aras N.Open vehicle routing problem with driver nodes and time deadline[J].Journal of the Operational Research Society，2007，58：1223-1234.

[9]鐘石泉，杜綱.基于核心路徑禁忌算法的開放式車輛路徑問題研究[J].計算機集成制造系統(tǒng)，2007，13（4）：827-832.

[10]Yslo M，Kowaklik J.Discrete optimization algorithms with pascal programs[M].Englewood Cliffs NJ：Prentice-Hall Inc，1983.

[11]Tarantilis C，Ioannou G，Kiranoudis C T，et al.Solving the open vehicle routing problem via a single parameter metaheuristic algorithm[J].The Journal of the Operational Research Society，2005，56：588-596.

[12]李相勇，田澎.開放式車輛路徑問題的蟻群優(yōu)化算法[J].系統(tǒng)工程理論與實踐，2008（6）：81-93.

[13]肖天國，符卓.求解帶軟時間窗的開放式車輛路徑問題的遺傳算法[J].鐵道科學與工程學報，2008，5（2）：79-83.

[14]鄧猛，肖輝君，楊豐梅.開放的車輛路線安排問題的模型與遺傳算法[J].北京化工大學學報，2006，33（4）：84-87.

[15]任春玉.開放式車輛路線問題的改進混合遺傳算法[J].控制工程，2010，17（3）：356-359.

WANG Xiaobo,REN Chunyu,LI Haichen

黑龍江大學 信息管理學院，哈爾濱 150080

School of Information Management,Heilongjiang University,Harbin 150080,China

Heterogeneous open vehicle routing problem is logistics optimization indispensable part.According to the standard genetic algorithm shortcomings of slowly convergent speed,weakly partial searching ability and easily premature,hybrid heuristic algorithm is used to optimize the solution.The paper uses sequence of real numbers coding so as to simplify the problem,constructs the targeted initial solution to improve the feasibility,adopts a choice based on sort of a combination with the best retention strategies to ensure the diversity of population,and uses some arithmetic crossover operator to enhance whole search ability of the chromosome.Using Boltzmann simulated annealing mechanism for controlling genetic algorithm crossover and mutation operations,it improves the convergence speed and search efficiency.Finally,the good performance can be proved by experiment calculation and concrete examples.

heterogeneous open vehicle routing problem;sequence of real numbers coding;some arithmetic crossover operator;Boltzmann simulated annealing mechanism;hybrid heuristic algorithm

A

TP29

10.3778/j.issn.1002-8331.1108-0218

WANG Xiaobo,REN Chunyu,LI Haichen.Hybrid heuristic algorithm for heterogeneous open vehicle routing problem. Computer Engineering and Applications,2013,49（7）：243-247.

黑龍江省教育廳科學技術研究項目（No.11551332）。

王曉博（1973—），男，博士，副教授，碩士生導師，主要研究方向為物流系統(tǒng)仿真了；任春玉（1974—），女，副教授，主要研究方向為電子商務物流；李海晨（1971—），男，博士，副教授，主要研究方向為電子商務研究。E-mail：wangxb2010@163.com

2011-09-07

2011-11-10

1002-8331（2013）07-0243-05

CNKI出版日期：2011-12-09 http://www.cnki.net/kcms/detail/11.2127.TP.20111209.1001.037.html