包得海，管會(huì)生

（1．甘肅民族師范學(xué)院計(jì)算機(jī)與科學(xué)系，中國(guó)合作 747000;2．蘭州大學(xué)信息科學(xué)與工程學(xué)院，中國(guó)蘭州 730000）

一種求解貨物配送問(wèn)題的改進(jìn)算法

包得海1，管會(huì)生2*

（1．甘肅民族師范學(xué)院計(jì)算機(jī)與科學(xué)系，中國(guó)合作 747000;2．蘭州大學(xué)信息科學(xué)與工程學(xué)院，中國(guó)蘭州 730000）

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

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

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

由于超市配送問(wèn)題屬于車輛運(yùn)輸問(wèn)題，所以超市配送問(wèn)題屬于NP-hard問(wèn)題［1］，當(dāng)配送的超市點(diǎn)很多時(shí)，若仍使用傳統(tǒng)的數(shù)學(xué)模型求解，其求解時(shí)間將呈指數(shù)級(jí)別增長(zhǎng)．因此，本文構(gòu)建新的超市配送問(wèn)題的數(shù)學(xué)模型，并提出一種以蟻群算法為基礎(chǔ)并加入禁忌搜法思想的改進(jìn)蟻群算法．

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

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

1 數(shù)學(xué)模型

本文數(shù)學(xué)模型的建立考慮的參數(shù)及模型如下:

在該類問(wèn)題中，V為所有結(jié)點(diǎn)的集合，V={i}，i=0，1，2，…，n，i=0表示配送中心，i=1，2，3，…，n為超市需求點(diǎn);I表示所有超市需求點(diǎn)集合，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的旅行時(shí)間，i∈I，j∈I;tik表示車輛k離開超市i的時(shí)間，i∈I，k∈M; Sik表示車輛k在超市i的服務(wù)時(shí)間，i∈I，k∈M;Pijk表示從超市i到達(dá)超市j時(shí)車輛k上的送貨量，其中i，j∈I，k∈M;Dijk表示從超市i到達(dá)超市j時(shí)車輛k的取貨量，其中，i，j，k∈I，k∈M．

定義決策變量:

數(shù)學(xué)模型可表示為

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

2 算法描述

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

2．1 初始解生成

具體步驟如下:

①設(shè)定各參數(shù)的值．螞蟻的個(gè)數(shù)為s，最大進(jìn)化代數(shù)為tmax=2 000，當(dāng)前進(jìn)化代數(shù)t=0，信息素τ=1，禁忌表TSB全部置0．

②將s只螞蟻隨機(jī)放置于n個(gè)超市上，第w只螞蟻在t時(shí)刻在超市i選擇運(yùn)動(dòng)到超市j的概率為:

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

③每只螞蟻在構(gòu)造解的路徑時(shí)，對(duì)螞蟻?zhàn)哌^(guò)的路徑的信息素濃度采用局部更新規(guī)則來(lái)更新相應(yīng)路段上的信息素濃度，更新規(guī)則為:

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

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

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

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

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

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

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

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

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

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

2．2 改善初始解

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

本階段主要對(duì)剛?cè)〉玫某跏冀猓来芜\(yùn)用2-Exchange、2-Swap、2-opt及插入法4種移步法加以改善．

4種移步法則分別說(shuō)明如下:

（1）2-Exchange

設(shè)路經(jīng)0-1-2-3-4-5-0和0-6-7-8-9-10-0為選取的兩條不同路線，0表示配送點(diǎn)，在這兩條路線中各選擇一段路線，如分別為（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

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

（3）2-opt

設(shè)路經(jīng)0-1-2-3-4-5-6-0，0表示配送點(diǎn)，在這條路線中刪除（2，3）和（4，5）兩段路線，再增加兩段路線（2，4）和（5，3），則可得到一條新的路線0-1-2-4-3-5-6-0

（4）插入法

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

3 試驗(yàn)結(jié)果

為了測(cè)試算法的有效性，本文共對(duì)已知的15個(gè)國(guó)際算例進(jìn)行測(cè)試，并與目前已知的最好結(jié)果進(jìn)行了比較，測(cè)試結(jié)果如表1，測(cè)試中的參數(shù)取值分別為:α=4．0，β=1．0，ρ=0．9，τ=1，τ'=0．05，γ=1．

表1 本文算法測(cè)試結(jié)果與文獻(xiàn)結(jié)果比較

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

4 小結(jié)

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

［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

甘肅省教育廳科研基金資助項(xiàng)目（1012-06）

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

（編輯沈小玲）