向 周 蔡延光 湯雅連

（廣東工業(yè)大學(xué) 自動(dòng)化學(xué)院，廣州 510006）

危險(xiǎn)品關(guān)聯(lián)運(yùn)輸調(diào)度問(wèn)題的優(yōu)化設(shè)計(jì)

向 周 蔡延光 湯雅連

（廣東工業(yè)大學(xué) 自動(dòng)化學(xué)院，廣州 510006）

針對(duì)帶硬時(shí)間窗的關(guān)聯(lián)運(yùn)輸調(diào)度問(wèn)題（Incident Vehicle Routing Problem with Hard Time Windows，IVRPHTW），聯(lián)系實(shí)際應(yīng)用中危險(xiǎn)品的車輛路徑問(wèn)題，介紹了混沌遺傳算法的基本原理，并對(duì)其進(jìn)行改進(jìn)，自適應(yīng)地調(diào)整交叉概率和變異概率，引進(jìn)了模擬退火機(jī)制，并用改進(jìn)的算法來(lái)對(duì)IVRPHTW求解，然后與遺傳算法求解此模型的結(jié)果相比較。實(shí)例證明該算法求解危險(xiǎn)品的關(guān)聯(lián)運(yùn)輸調(diào)度問(wèn)題是可行的，且優(yōu)于傳統(tǒng)的遺傳算法。

硬時(shí)間窗；關(guān)聯(lián)運(yùn)輸調(diào)度問(wèn)題；危險(xiǎn)品；混沌遺傳算法；模擬退火機(jī)制

帶危險(xiǎn)品的關(guān)聯(lián)運(yùn)輸調(diào)度問(wèn)題是基本物流運(yùn)輸調(diào)度問(wèn)題的拓展，是指若干個(gè)客戶對(duì)危險(xiǎn)品有一定的需求量，由配送中心為所有客戶提供配送服務(wù)，車場(chǎng)中車輛將貨物送到各個(gè)客戶，然后返回車場(chǎng)。要求對(duì)車場(chǎng)的車輛和行駛路線進(jìn)行合理安排，在滿足用戶需求的條件下，使配送成本最低。關(guān)聯(lián)運(yùn)輸調(diào)度問(wèn)題IVRP［1］（Incident Vehicle Routing Problem）根據(jù)車輛類型可以分為單車型IVRP和多車型IVRP，本文主要研究一個(gè)配送中心單車型的帶硬時(shí)間窗的關(guān)聯(lián)運(yùn)輸調(diào)度問(wèn)題。危險(xiǎn)貨物［2］是指具有爆炸、易燃、毒害、感染、腐蝕、放射性等危險(xiǎn)特性，在運(yùn)輸、儲(chǔ)存、生產(chǎn)、經(jīng)營(yíng)、使用和處置中，容易造成人身傷亡、財(cái)產(chǎn)損毀或環(huán)境污染而需要特別防護(hù)的物質(zhì)和物品，因而對(duì)配送時(shí)間有很相當(dāng)嚴(yán)格的要求。時(shí)間關(guān)聯(lián)關(guān)系可分為多種情況，如圖1所示，1～4屬于并行執(zhí)行，5～7屬于串行執(zhí)行。

圖1 task1和task2之間的時(shí)間關(guān)聯(lián)

高清平［2］研究了不確定條件下危險(xiǎn)貨物運(yùn)輸?shù)娘L(fēng)險(xiǎn)度量與分析、路徑選擇、網(wǎng)絡(luò)優(yōu)化問(wèn)題和設(shè)施選址問(wèn)題，并對(duì)危險(xiǎn)貨物的配送路徑和運(yùn)輸網(wǎng)絡(luò)進(jìn)行建模和仿真，取得了不錯(cuò)的效果；張恒海［3］對(duì)基本的蟻群算法進(jìn)行改進(jìn)，并將其運(yùn)用到危險(xiǎn)貨物運(yùn)輸路徑的模型中，具有一定的實(shí)用意義；張敏［4］等人用啟發(fā)式算法求解了危險(xiǎn)品集成物流管理系統(tǒng)選址-選線模型，具有研究?jī)r(jià)值；王瑞慶［5］研究了帶時(shí)間窗口的危險(xiǎn)品VRP問(wèn)題模型，并用領(lǐng)域搜索算法對(duì)其求解；C.D.Tarantilis和C.T.Kiranoudis［6］用元啟發(fā)式算法——基于接受閾值的列表方法研究了不同類型危險(xiǎn)物質(zhì)的運(yùn)輸問(wèn)題；Hakan ASLAM［7］基于博弈論的理論基礎(chǔ)提出了危險(xiǎn)品運(yùn)輸中的風(fēng)險(xiǎn)規(guī)避方法；Bin ZHEMG［8］提出了多目標(biāo)遺傳算法求解危險(xiǎn)品運(yùn)輸問(wèn)題模型，仿真實(shí)例表明該算法能避免傳統(tǒng)多目標(biāo)優(yōu)化方法的局限性；J.Karkazis和T.B.Boffey［9］以最下化損傷效益和最優(yōu)路徑為目標(biāo)，用分支定界法求解了現(xiàn)實(shí)環(huán)境中的危險(xiǎn)品運(yùn)輸優(yōu)化問(wèn)題模型。由于以上文獻(xiàn)沒(méi)有考慮到危險(xiǎn)品貨物間的性質(zhì)關(guān)聯(lián)和時(shí)間關(guān)聯(lián)，不同客戶需要的貨物可能為非同類型貨物，所以在前人的基礎(chǔ)上，研究帶硬時(shí)間窗的危險(xiǎn)品關(guān)聯(lián)運(yùn)輸調(diào)度問(wèn)題有一定的實(shí)用價(jià)值。

1 數(shù)學(xué)模型的建立

1.1 問(wèn)題描述及假設(shè)

帶硬時(shí)間窗的危險(xiǎn)品關(guān)聯(lián)運(yùn)輸調(diào)度問(wèn)題是指對(duì)于一系列危險(xiǎn)品需求點(diǎn)，組織適當(dāng)?shù)倪\(yùn)輸路線，使危險(xiǎn)品在滿足一定的約束條件（如運(yùn)輸量、硬時(shí)間窗、里程約束及載重約束等）下，達(dá)到目標(biāo)最優(yōu)（路程短、時(shí)間短、使用車輛數(shù)少、費(fèi)用低等）。問(wèn)題可以簡(jiǎn)單描述為，假設(shè)給定車場(chǎng)位置以及客戶的數(shù)量、位置和成品需求總量，車輛有載重約束、運(yùn)輸里程約束和道路約束，要求合理安排車場(chǎng)中的車輛和運(yùn)輸路線，使得配送成本最低。本章研究的問(wèn)題基于以下假設(shè):1）1個(gè)車場(chǎng)，l個(gè)客戶（i，j=1，2，…，l），客戶需求不確定；2）每輛車有最大配送距離約束、載重約束，同種車型；3）非滿載，硬時(shí)間窗約束；4）考慮貨物性質(zhì)關(guān)聯(lián)及時(shí)間序列關(guān)聯(lián)。

1.2 模型的建立

有l(wèi)個(gè)客戶，第i個(gè)客戶的需求量為gi，需要從車場(chǎng)將貨物運(yùn)給各客戶，有1個(gè)車場(chǎng)可派出載重量為q的貨車，已知gi＜q?？蛻粢笏拓洉r(shí)間窗為［Ai，Bi］。Ti表示車輛到達(dá)i的時(shí)間。不考慮服務(wù)時(shí)間和吃飯時(shí)間?？梢园凑帐剑?）估算車輛數(shù)。式中，［］表示不大于括號(hào)內(nèi)數(shù)字的最大整數(shù)；0＜α＜1，是對(duì)裝車（或卸車）的復(fù)雜程度及約束多少的估計(jì)。

以cijk表示為車輛k將貨物從點(diǎn)i送到點(diǎn)j的單位運(yùn)價(jià)。客戶i與j之間的距離為dij。關(guān)聯(lián)系數(shù)為r，rij表示點(diǎn)i處的貨物與點(diǎn)j處貨物的關(guān)聯(lián)系數(shù)。目標(biāo)為使車輛的總運(yùn)輸成本最小。nk表示第k輛車服務(wù)的客戶數(shù)。ck為啟用車輛的固定成本。

定義變量如下:

建立數(shù)學(xué)模型

目標(biāo)函數(shù):

約束條件:

目標(biāo)函數(shù)式（4）表示總運(yùn)輸成本最低。（5）為車輛行駛距離約束，其中dijk表示車輛k行駛了客戶i到j(luò)的路程。（6）和（7）表示兩個(gè)變量之間的關(guān)系。（8）表示車輛完成任務(wù)后，回到原車場(chǎng)。（9）表示當(dāng)某輛車配送客戶大于等于1時(shí)，則參與了配送服務(wù)，否則，沒(méi)有參與配送。（10）表示每個(gè)客戶都被服務(wù)到。（11）表示不能超過(guò)車輛載重量的限制。（12）表示保證每輛車的客戶總數(shù)小于等于總客戶數(shù)目。（13）表示到達(dá)客戶i的時(shí)間必須在時(shí)間窗內(nèi)，否則客戶拒絕配送。（14）表示到達(dá)j的時(shí)間為車場(chǎng)到i的時(shí)間T0i、客戶i處的卸貨時(shí)間tsi與客戶i到行駛到客戶j的時(shí)間tij之和。（15）Sa，Sb是配送的時(shí)間關(guān)聯(lián)序列，Sa≤Sb表示配送貨物到i的時(shí)間必須早于到客戶j的時(shí)間。

2 算法設(shè)計(jì)

2.1 算法思想

模擬退火算法（SA）［1，10-11］是一種基于熱力學(xué)的退火機(jī)理而建立的隨機(jī)搜索算法。模擬退火算法［1，12］的思想源于固體退火過(guò)程:將固體加溫至充分高，再讓其慢慢冷卻。加溫時(shí)，固體內(nèi)部粒子隨著溫度的升高表現(xiàn)出無(wú)序性，而在降溫時(shí)，漸趨有序，在降溫到一定程度時(shí)，內(nèi)能最小。根據(jù)Metropolis準(zhǔn)則，來(lái)決定是否接受新個(gè)體。本文算法是在混沌搜索產(chǎn)生初始種群后，對(duì)適應(yīng)度較小染色體進(jìn)行交叉和變異操作，然后將模擬退火機(jī)制引入，并與初次產(chǎn)生的種群合成新的種群，如此反復(fù)迭代進(jìn)行，直到滿足終止條件為止。

2.2 混沌遺傳算法參數(shù)設(shè)計(jì)

2.2.1 隨機(jī)擾動(dòng)的確定

利用混沌［12］對(duì)初始解敏感的特點(diǎn)，我們對(duì)全局最優(yōu)值X進(jìn)行混沌搜索，避免陷入局部最優(yōu)解。本章選用Logistic映射［4］產(chǎn)生混沌序列，如式（17）所示:

式中，i表示混沌變量的序號(hào)，i=1，2，…r；u表示種群序號(hào)，u=0，1，…n；βi表示混沌變量，0≤βi≤1；μi表示吸引子。當(dāng)μi=4時(shí)，Logistic映射完全處于混沌的狀態(tài)，此時(shí)產(chǎn)生的混沌變量βi具有很好的遍歷性。混沌變量映射到染色體基因座空間如下:

混沌領(lǐng)域搜索的基本步驟:

Step1:對(duì)式（16）賦予不同的初值，可以得到混沌變量βi。

Step2:令X=（x1，x2，…，xr），X＇=（…，，將映射到染色體基因座空間，對(duì)應(yīng)染色體基因片段X＇=（x＇1，x＇2，…，x＇r）。

2.2.2 交叉概率與變異概率的確定

交叉概率pc（t）和變異概率pm（t）由平均適應(yīng)度f(wàn)ave、最大適應(yīng)度f(wàn)max和最小適應(yīng)度f(wàn)min來(lái)衡量，如式（18）和式（19）。fmax和fmin的接近程度反映了整個(gè)群體的集中程度，兩者越接近，越容易陷入局部最優(yōu)解，其中0＜b＜1。fave和fmax的接近程度反映了群體內(nèi)部適應(yīng)度的分布情況，二者越接近，則表明此代中的個(gè)體越集中，其中0.5＜a＜1。

2.3 模擬退火混沌遺傳算法設(shè)計(jì)流程

Step1:初始化遺傳算法參數(shù)和模擬退火算法參數(shù)；

Step2:利用混沌遍歷性搜索有效基因，得到種群P（t）；

Step3:計(jì)算適應(yīng)度值，若達(dá)到給定迭代次數(shù)，轉(zhuǎn)Step7，否則，計(jì)算下一步；

Step4:根據(jù)適應(yīng)度集中程度，進(jìn)行自適應(yīng)交叉變異操作；

Step5:進(jìn)行模擬退火操作，計(jì)算適應(yīng)度增量Δf，根據(jù)Metropolis準(zhǔn)則判斷是否接受新點(diǎn)，產(chǎn)生新種群P＇（t）；

Step6:為保證種群的多樣性，將P（t）加入，則新群體P″（t）=P（t）+P＇（t）；

Step7:判斷是否滿足終止條件，若滿足，算法結(jié)束，否則轉(zhuǎn)Step3。

3 仿真分析

某供應(yīng)商有一個(gè)配送中心，配送中心就是車場(chǎng)，車場(chǎng)位置為（45，45），有同類型的車輛若干。所有客戶的客戶信息如表1所示。每輛車的最大配送里程為200千米，載重為5噸。cijk為1元/噸*千米，ck為20元/輛，v為60千米/時(shí)，卸貨時(shí)間為10分鐘，最早出發(fā)時(shí)間為5:00?？蛻羲柝浳镏g的貨物性質(zhì)關(guān)聯(lián)系數(shù)由Microsoft Visual C++6.0隨機(jī)產(chǎn)生。且存在客戶需求時(shí)間關(guān)聯(lián)S10＜S22＜S4＜S6，S15＜S14＜S20＜S2，S30＜S11＜S7＜S3。本文中的實(shí)驗(yàn)是在Intel（R）CoreTMi3 CPU2.53GHz、內(nèi)存為2.0G、安裝系統(tǒng)為win7的PC機(jī)上采用Microsoft Visual C++6.0編程實(shí)現(xiàn)。

表1 客戶信息表

假設(shè)初始溫度T=100，T0=0，α=0.8，φ=0.9，β=0.1，群體規(guī)模M=20，迭代次數(shù)為100，pc=0.8，pm=0.05。分別運(yùn)行程序20次，得出算法的運(yùn)行結(jié)果。在第20次迭代后，算法收斂。具體配送信息見(jiàn)表2，各車場(chǎng)分別派出一輛車，總配送距離為527.73千米，總配送費(fèi)用為664.73元。最優(yōu)配送網(wǎng)絡(luò)如圖2所示。兩種算法一次迭代的收斂情況如圖3所示，可見(jiàn)本算法優(yōu)于基本的遺傳算法。

圖2 最優(yōu)配送網(wǎng)絡(luò)

圖3 算法收斂情況

4 結(jié)語(yǔ)

本章研究了帶硬時(shí)間窗的具有時(shí)間關(guān)聯(lián)和貨物性質(zhì)關(guān)聯(lián)特征的危險(xiǎn)品運(yùn)輸調(diào)度問(wèn)題模型，并設(shè)計(jì)了一種改進(jìn)的混合混沌遺傳算法對(duì)所建立的模型求解，根據(jù)適應(yīng)度集中程度，自適應(yīng)地調(diào)整交叉概率和變異概率，然后引入了模擬退火機(jī)制，并加入了混沌擾動(dòng)。該混合算法，兼容了混沌遺傳算法和模擬退火算法的優(yōu)點(diǎn)，能有效地求解此類問(wèn)題。接下來(lái)可以進(jìn)一步考慮危險(xiǎn)品運(yùn)輸途中的風(fēng)險(xiǎn)問(wèn)題、道路約束、取送貨交叉問(wèn)題、需求量不確定問(wèn)題、速度約束和運(yùn)輸環(huán)境等問(wèn)題。

［1］ 湯雅連，蔡延光，徐山峰.帶道路容量動(dòng)態(tài)約束的關(guān)聯(lián)運(yùn)輸調(diào)度問(wèn)題［J］.微型機(jī)與應(yīng)用，2012，31（22）:73-76.

［2］ 高清平.不確定條件下危險(xiǎn)貨物公路運(yùn)輸風(fēng)險(xiǎn)分析、路徑選擇與網(wǎng)絡(luò)優(yōu)化研究［D］.四川:西南交通大學(xué).2010.

［3］ 張恒海.基于蟻群算法的危險(xiǎn)貨物運(yùn)輸路徑優(yōu)化研究［D］.西安:長(zhǎng)安大學(xué)，2007.

［4］ 張敏，楊超，楊珺，馬云峰.危險(xiǎn)品集成物流管理系統(tǒng)選址-選線模型研究［J］.管理科學(xué)學(xué)報(bào)，2008，11（1）:59-67.

［5］ 王瑞慶.一種帶時(shí)間窗口的危險(xiǎn)品VRP問(wèn)題及其算法［D］.上海:復(fù)旦大學(xué)，2007.

［6］ Tarantilis C D，Kiranoudis C T.Using the Vehicle Routing Problem for the Transportation of Hazardous Materials.Operational Research.An International Journal/Wol.1，Mo 1/January-April2001:67-78.

［7］ Aslan H.Safe Movement of Hazardous Materials through Heuristic Hybrid Approach:Tabu Search and Game Theory Aplication.Journal of Engineering Sciences，2008，14（3）:279-289.

［8］ ZHEMG Bin.Multi-objective Vehicle Routing Problem in Hazardous Material Transportation.ICLEM 2010:Logistics for Sustained Economic Development？2010 ASCE:3139-3145.

［9］ Karkazi J，Boffey TB.Optimal location of routes for vehicles transporting hazardous materials.European Journal of Operational Research，1995（86）:201-215.

［10］ 魏明，蔡延光.一種基于混沌搜索的自適應(yīng)遺傳算法［J］.計(jì)算機(jī)應(yīng)用研究，2009，26（2）:465-467.

［11］ 周麗，黃素珍.基于模擬退火的混合遺傳算法研究［J］.計(jì)算機(jī)應(yīng)用研究，2005（9），72-74.

［12］ 謝云.模擬退火綜述［J］.計(jì)算機(jī)應(yīng)用研究，1998（5）:6.

Optimal Design of Incident Vehicle RoutingProblem for Dangerous Goods

XIANG Zhou CAIYan.guang TANG Ya.lian
（School of Automation，Guangdong University of Technology，Guangzhou 510006，China）

Aiming at IVRPHTW（Incident Vehicle Routing Problem with Hard TimeWindows）and VRP（Vehicle Routing Problem）of dangerous goods in practical application，this paper introduces and modifies the fundamental principle of CGA（Chaos Genetic Algorithm）adjusting adaptively crossover probability and mutation probability，bringing simulated annealing mechanism in the algorithm，and applying cluster analysis and the modified algorithm to solve IVRPHTW，as well as compared with Genetic Algorithm（GA）.The results show that CGA is feasible to solve IVRP of dangerous goods，and better than GA during the optimization process.

hard time windows；IVRP；hazardous material；Chaos Genetic Algorithm；simulated annealing mechanism

TP301

A

1009-0312（2014）01-0051-06

2013-04-26

向周（1989—），男，湖南岳陽(yáng)人，碩士生，主要從事物流信息技術(shù)與智能決策支持系統(tǒng)研究。