危險品關聯(lián)運輸調度問題的優(yōu)化設計

向 周 蔡延光 湯雅連

（廣東工業(yè)大學 自動化學院，廣州 510006）

危險品關聯(lián)運輸調度問題的優(yōu)化設計

向 周 蔡延光 湯雅連

（廣東工業(yè)大學 自動化學院，廣州 510006）

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

硬時間窗；關聯(lián)運輸調度問題；危險品；混沌遺傳算法；模擬退火機制

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

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

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

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

1.1 問題描述及假設

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

1.2 模型的建立

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

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

定義變量如下:

建立數(shù)學模型

目標函數(shù):

約束條件:

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

2 算法設計

2.1 算法思想

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

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

2.2.1 隨機擾動的確定

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

式中，i表示混沌變量的序號，i=1，2，…r；u表示種群序號，u=0，1，…n；βi表示混沌變量，0≤βi≤1；μi表示吸引子。當μi=4時，Logistic映射完全處于混沌的狀態(tài)，此時產生的混沌變量βi具有很好的遍歷性?；煦缱兞坑成涞饺旧w基因座空間如下:

混沌領域搜索的基本步驟:

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

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

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

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

2.3 模擬退火混沌遺傳算法設計流程

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

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

Step3:計算適應度值，若達到給定迭代次數(shù)，轉Step7，否則，計算下一步；

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

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

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

Step7:判斷是否滿足終止條件，若滿足，算法結束，否則轉Step3。

3 仿真分析

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

表1 客戶信息表

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

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

圖3 算法收斂情況

4 結語

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

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

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

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

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

［5］ 王瑞慶.一種帶時間窗口的危險品VRP問題及其算法［D］.上海:復旦大學，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］ 魏明，蔡延光.一種基于混沌搜索的自適應遺傳算法［J］.計算機應用研究，2009，26（2）:465-467.

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

［12］ 謝云.模擬退火綜述［J］.計算機應用研究，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—），男，湖南岳陽人，碩士生，主要從事物流信息技術與智能決策支持系統(tǒng)研究。