一種求解貨物配送問題的改進算法

包得海，管會生

（1．甘肅民族師范學院計算機與科學系，中國合作 747000;2．蘭州大學信息科學與工程學院，中國蘭州 730000）

一種求解貨物配送問題的改進算法

包得海1，管會生2*

（1．甘肅民族師范學院計算機與科學系，中國合作 747000;2．蘭州大學信息科學與工程學院，中國蘭州 730000）

針對貨物配送問題，建立問題的數學模型，提出一種基于禁忌搜索的蟻群算法．并結合超市配送問題，對算法進行測試，測試結果表明，該算法具有收斂速度快、不易陷入局部最優(yōu)、求解精度高的特點，能夠有效地解決超市配送問題．

超市配送問題;蟻群算法;車輛路徑問題;禁忌搜索;局部搜索

傳統(tǒng)的貨物配送問題是在假定先送貨后取貨的情況下建立的數學模型，這與現時代的實際問題并不相符．本文以超市配送問題為例，如有些超市同時具有送貨及取貨的需求，又如，從一些超市取出的貨物可以配送到另一些超市中．本研究針對傳統(tǒng)的超市配送問題加以修改，允許先取貨后送貨，并把每個超市都設為具有送貨、取貨或者二者兼有，并允許貨物被重復利用．

由于超市配送問題屬于車輛運輸問題，所以超市配送問題屬于NP-hard問題［1］，當配送的超市點很多時，若仍使用傳統(tǒng)的數學模型求解，其求解時間將呈指數級別增長．因此，本文構建新的超市配送問題的數學模型，并提出一種以蟻群算法為基礎并加入禁忌搜法思想的改進蟻群算法．

在過去國內外學者相關研究中Clark-Wright［2］提出節(jié)省法研究車輛途程問題;Deif和Bodin［3］在文獻［2］的基礎上，加入獎懲值的觀念;Goetschalckk和Jacobs-Blech［4］提出兩階段的啟發(fā)算法;otvin及Laporte［5］使用基因演化算法來求解．文獻［6］和［7］分別使用簡單近鄰法來研究可變速的車輛路徑問題和一般車輛路徑問題;文獻［8］在文獻［2］的基礎上加入可變速的思想;文獻［9］將禁忌搜索方法應用到帶時間窗口的可變速車輛路徑中．文獻［10］利用禁忌搜索算法分兩階段來研究時變速車輛運輸問題．上述文獻都假設要先送貨后取貨，且沒有考慮可對同一需求點同時做取貨與送貨的服務，這與實際情況不相符．

蟻群算法是M．Dorigo等人最早提出的，該算法是從蟻群覓食過程中得到啟發(fā)而構造出的一種算法，但該算法具有易于過早收斂于局部最優(yōu)解的缺陷．為了改善上述缺陷，本文算法將禁忌搜索思想引入到蟻群算法中，構造出一種新的算法，并把該算法運用到超市配送問題中，以國際算例為例，進行測試，實驗結果表明，該算法具有收斂速度快、不易陷入局部最優(yōu)、求解精度高的特點，能夠有效地解決超市配送問題．

1 數學模型

本文數學模型的建立考慮的參數及模型如下:

在該類問題中，V為所有結點的集合，V={i}，i=0，1，2，…，n，i=0表示配送中心，i=1，2，3，…，n為超市需求點;I表示所有超市需求點集合，I={i}，i=1，2，…，n，V=I∨{0}，0表示配送中心;M表示所有車輛的集合，M={k}，k=1，2，…，m;Q表示車輛的最大載重量，本文中假定所有車輛的載重量相同;Cij表示兩超市i與j之間的距離，其中，Cii=∞，C00=0，i∈V，j∈V;Pi表示超市的取貨量，i∈I;di表示超市i的送貨量，i∈I;tij表示超市i至超市j的旅行時間，i∈I，j∈I;tik表示車輛k離開超市i的時間，i∈I，k∈M; Sik表示車輛k在超市i的服務時間，i∈I，k∈M;Pijk表示從超市i到達超市j時車輛k上的送貨量，其中i，j∈I，k∈M;Dijk表示從超市i到達超市j時車輛k的取貨量，其中，i，j，k∈I，k∈M．

定義決策變量:

數學模型可表示為

其中，式（1）和（2）為目標函數，其目標使總運送成本最小;式（3）保證每個超市被服務一次且僅為一次，且僅有一輛車服務;式（4）至式（7）保證車輛任何時間所載貨物不能超過其最大能力，式（4）中P0jk表示從配送中心到達超市j時車輛k上的送貨量;式（8）保證車輛出發(fā)前收集需求為零;式（9）保證回到配送中心時送貨需求為零;式（10）和（11）保證離開配送中心的車輛數等于回到配送中心的車輛數;式（12）表示車輛在超市間行駛時間與與離開某超市和該超市服務時間的關系;式（13）表示相鄰結點組成的路段集;式（14）表示所有結點的可行路線組成的鏈路集．

2 算法描述

本算法使用基于禁忌搜索的蟻群算法求得初始解，在此基礎上，進行了第二階段的優(yōu)化，采用移步法加以優(yōu)化．

2．1 初始解生成

具體步驟如下:

①設定各參數的值．螞蟻的個數為s，最大進化代數為tmax=2 000，當前進化代數t=0，信息素τ=1，禁忌表TSB全部置0．

②將s只螞蟻隨機放置于n個超市上，第w只螞蟻在t時刻在超市i選擇運動到超市j的概率為:

式中aij是第w只螞蟻可選的與超市i相連的超市集合，τij（t）表t時刻邊（i，j）上的信息素濃度;ηij（t）是一個啟發(fā)式因子，表示在t時刻螞蟻從超市i轉移到超市j的期望程度，在本算法中取ηij（t）=Dijk;α和β分別表示路徑上信息量和啟發(fā)式因子的重要程度，對于每個邊（i，j），r是常數，λij（t）代表邊（i，j）的使用頻率，λij（0）=1，每當邊（i，j）被走過一次后λij（t）就增加1．

③每只螞蟻在構造解的路徑時，對螞蟻走過的路徑的信息素濃度采用局部更新規(guī)則來更新相應路段上的信息素濃度，更新規(guī)則為:

式中ρ表示遺忘因子;τij（t）表t時刻邊（i，j）上的信息素濃度;τij（t+1）表t+1時刻邊（i，j）上的信息素濃度;

式中τ為開始設置的每條邊上的信息素濃度，是個常數，本算法中τ=1，cij表示（i，j）之間的距離．

④當每只螞蟻都構造完成各自的解之后，記錄當前最優(yōu)化路徑，并對最優(yōu)化路徑上的邊信息素再次更新，更新公式為:

式中l(wèi)min表示當前最短路徑，τ'為更新前最優(yōu)路徑上信息素濃度．

⑤禁忌搜索:若當前最優(yōu)解ri=xk（i=1，2，…，n），則修改禁忌表，將禁忌表中對應的元素置1，否則執(zhí)行禁忌搜索算法中的特赦規(guī)則，將禁忌路段中那些使用率較低或幾個路段使用率相同時，優(yōu)先解禁最短者，將禁忌表相應位置置0，重復步驟⑤，其中使用率由下式決定:

其中τij（t）表示t時刻路段（i，j）上的信息素濃度;γ，δ為設計參數，表示路段使用次數的影響因子;mij表示路段（i，j）總的使用次數;lmin表示當前最短路徑;τ為當前路徑上信息素濃度．

⑥若滿足輸出條件（如達到最大進化代數tmax=2 000），則輸出最優(yōu)解，否則t=t+1，轉②．

⑦依式Savc（i，j）=2c0c－（cic+cjc－cij）（其中i，j兩點為⑥中最優(yōu)解中的送貨超市點，c點為欲插入最優(yōu)解中的取貨超市點，cij為i，j兩點間的距離），計算出插入節(jié)省值大小順序，將取貨超市點插入距離送貨路段中最近的路段．

⑧判斷是否超出容量限制，若是，轉步驟⑨，否則返回步驟⑦．

⑨節(jié)省值次大者，將取貨點插入到符合其他路段中，依次類推，若所有取貨點都已經插入各路段中，則結束程序，否則轉⑦．

2．2 改善初始解

建立初始解階段獲得的解為起始解，利用各種移步法則可以求得更佳的區(qū)域解．

本階段主要對剛取得的初始解，依次運用2-Exchange、2-Swap、2-opt及插入法4種移步法加以改善．

4種移步法則分別說明如下:

（1）2-Exchange

設路經0-1-2-3-4-5-0和0-6-7-8-9-10-0為選取的兩條不同路線，0表示配送點，在這兩條路線中各選擇一段路線，如分別為（2，3）和（7，8），將此兩段路線刪除，另外增加兩段路線（2，8）和（7，3），則可得到兩條新的路線0-1-2-8-9-10-0和0-6-7-3-4-5-0．

（2）2-Swap

設路經0-1-2-3-4-5-0和0-6-7-8-9-10-0為選取的兩條不同路線，0表示配送點，在這兩條路線中各選擇一個節(jié)點，如分別為2和7，將此兩節(jié)點互換，則可得到兩條新的路線0-1-7-3-4-5-0和0-6-2-8-9-10-0

（3）2-opt

設路經0-1-2-3-4-5-6-0，0表示配送點，在這條路線中刪除（2，3）和（4，5）兩段路線，再增加兩段路線（2，4）和（5，3），則可得到一條新的路線0-1-2-4-3-5-6-0

（4）插入法

設路經0-1-2-3-4-5-0和0-6-7-8-9-10-0為選取的兩條不同路線，0表示配送點，在這兩條路線中選擇一個節(jié)點和一段路線，如分別為2和（7，8），將節(jié)點2插入到路線（7，8）內，則可得到兩條新的路線0-1-3-4-5-0和0-6-7-2-8-9-10-0通過上述4種移步法則，對初始解路經進行了改善．

3 試驗結果

為了測試算法的有效性，本文共對已知的15個國際算例進行測試，并與目前已知的最好結果進行了比較，測試結果如表1，測試中的參數取值分別為:α=4．0，β=1．0，ρ=0．9，τ=1，τ'=0．05，γ=1．

表1 本文算法測試結果與文獻結果比較

由表1測試的結果顯示，本文所提算法均可得到最佳解，對小規(guī)模問題的求解與現有文獻的最優(yōu)解相差無幾，但隨著問題規(guī)模增大，本文所提算法優(yōu)勢明顯．

4 小結

本文將禁忌搜索思想引入到蟻群算法中，提出一種改進算法，并與國際算例相結合，加以驗證．仿真結果表明，該算法在保證收斂速度的同時，大大提高了解的質量，對于不同規(guī)模的問題，算法性能良好．

［1］REINGOLD E M，NEIVERGELT J，DEO N．Combinatorial algorithms:theory and practice prentice-hall［M］．New Jersey: Prentice-Hall，1977．

［2］CLARKE G，WRIGHT J W．Scheduling of vehicles from a central depot to a number of delivery points［J］．Oper Res，1964，12 （4）:568-581．

［3］DEIF I，BODIN L．Extensoin of the clarke and wright algorithm for solving the vehicle routing problem with backhauling:Proceedings of the Babson Conference on software in Trandportation and Logistic Management，Babson Park，MA，1984［C］．MA: Babson Park，1984．

［4］GOETSCHALCKX M，JACOBS-BLECHA C．The vehicle routing problem with backhauling［J］．Eur J Oper Res，1989，42（1）: 39-51．

［5］POTVIN J Y，LAPORTE G．Genetic algorithm for the traveling salesman problem［J］．Ann Operat Res，1996，63:339-370．

［6］HILL A C，BENTON W C．Modeling intra-city time-dependent travel speeds for vehicle scheduling problems［J］．J Oper Res Soc，1992，43（4）:343-351．

［7］MALANDRAKI C，DASKIN M S．Time dependent vehicle routing problems:formulation，properties and heuristic algorithms［J］．Trans Sci，1992，26（3）:185-200．

［8］PARK R B，Song S H．Vehicle scheduling problems with time-varying speed［J］．Comput Ind Eng，1997，33（3-4）:853-856．

［9］ICHOUA S，GENDREAU M，POTVIN J Y．Vehicle dispatching with time-dependent travel times［J］．Eur J Oper Res，2003，144（2）:379-396．

［10］DUHAMEL C，POTVINN J Y，ROUSSEAU J M．A tabu search heuristic for the vehicle routing problem with backhauls and time windows［J］．Trans Sci，1997，31（1）:49-59．

［11］DORIGO M，MANIEZZO V，COLORNI A．The ant system:optimization by a colony of cooperating agents［J］．IEEE Trans SMC，Part B，1996，26（1）:29-41．

An Improved Algorithm of Solving Goods Distribution Problem

BAO De-hai1，GUAN Hui-sheng2*
（1．Department of Computer Science，Gansu Normal University for Nationalities，Hezuo 747000，China; 2．School of Information Science and Engineering，Lanzhou University，Lanzhou 730000，China）

A mathematical model for Goods Distribution Problem is constructed and an ant colony algorithm with tabu search is put forward．The algorithm is tested in combination with Supermarket Distribution Problem．The experimental results indicate that the algorithm solves Supermarket Distribution Problem effectively with quick convergence，avoid local optimum，high precision solution characteristics．

supermarket distribution problem;ant colony algorithm;VRP;tabu search;local search

TP301．6

A

1000-2537（2011）05-0012-05

2010-11-16

甘肅省教育廳科研基金資助項目（1012-06）

*通訊作者，E-mail:hzmtcb@126．com

（編輯沈小玲）