基于遺傳蟻群算法的帶時間窗多車場車輛調度問題

馬洪坤，楊　偉，趙　佳，郝海彬

(西華大學交通與汽車工程學院，四川 成都　610039)

?

基于遺傳蟻群算法的帶時間窗多車場車輛調度問題

馬洪坤，楊偉*，趙佳，郝海彬

(西華大學交通與汽車工程學院，四川 成都610039)

摘要：給出帶單邊硬時間窗的多車場車輛調度問題的數學模型，并提出一種遺傳蟻群融合算法。該算法在遺傳算法的基礎上加入蟻群路徑搜索和自適交叉變異來提高算法搜索能力，并且采用模擬退火個體接受方式接受蟻群路徑搜索產生的新個體，從而使算法提高了跳出局部最優點能力。結合算例計算驗證了算法的有效性和正確性。

關鍵詞：遺傳蟻群算法； 自適應； 多車場； 時間窗； 車輛調度問題

車輛路徑優化問題是一個經典NP難題[1]，該問題是指在已知配送中心、客戶位置和需求量的前提下，在滿足運輸容量和送達時間約束的基礎上，規劃出一條或者若干條運輸時間或運輸距離最小的路徑。該問題具有比較大的現實意義，現實中很多客戶對貨物的需求時間都比較嚴格，因而都可以歸結為帶硬時間窗的多車場車輛調度問題；但是該問題是一個NP難度問題，一般優化算法難以得到問題的最優解。近年來，遺傳算法和蟻群算法等啟發式算法在該類問題的求解中得到成功應用[2-4]，但算法優化結果還有進一步提高的空間。

遺傳蟻群算法結合了遺傳算法和蟻群算法的優點，是一種優化能力較好的啟發式算法。本文從遺傳自適應搜索和模擬退火向后搜索機制兩方面改進該算法，較好地提高了算法的搜索效率和搜索結果。仿真實驗表明，該算法在帶時間約束多車場車輛調度問題中能得到較好的結果。

1問題描述和數學模型

(1)

(2)

(3)

m∈{N+1,N+2,…,N+M}，

(4)

(5)

m∈{N+1,N+2,…,N+M},

(6)

m∈{N+1,N+2,…,N+M},

(7)

(8)

tik≤Di。

(9)

其中：式(1)為模型目標函數，即車輛運行的最短路徑；式(2)、(3)表示每個客戶只能被一輛車服務一次；式(4)表示車輛都是從自己車場出發最后返回各自車場；式(5)表示每個車場派出的車輛數目不能超過自身擁有的車輛數目；式(6)表示車輛容量限制，即每輛車的載重量不能超過其載重能力；式(7)表示車輛不能從車場到車場；式(8)、(9)表示貨物送到時間滿足最晚時間窗約束。

2遺傳蟻群算法

2.1算法概述

遺傳算法和蟻群算法是路徑優化方法中常用的2種啟發式規劃算法；但是這2種算法對于多車場多車輛調度問題來說都具有一定的局限性[5-6]，主要體現在遺傳算法難以得到較好的路徑優化結果，蟻群算法難以解決車場對于客戶的選擇配送。針對這個問題，本文提出一種基于改進遺傳蟻群算法的多車場多車輛路徑優化算法。該算法首先構建遺傳算法優化初始客戶分配和初始路徑，從而得到初始種群，然后以個體初始客戶分配為基礎，采用蟻群算法優化初始路徑，得到新的個體，比較新個體和舊個體適應度值的大小，如果新個體適應度值優于舊個體，則用新個體取代舊個體，否則以一定概率取代舊個體。

2.2算法改進和步驟

2.2.1染色體編碼

遺傳算法中每個染色體都是問題的一個潛在解，本文的染色體采用雙層編碼的方式，在車場數量為M，客戶數量為N的前提下，染色體長度為2N，其中1-N代表客戶分配方案，N+1-2N代表客戶路徑優先級，優先級值越小則表示客戶越早被車輛服務，然后按照車載能力約束將客戶按照服務的優先級加入路徑中，如滿足車載能力約束則將此客戶加入到路徑中，否則以此客戶為第一個服務客戶重新構造路徑，直至所有客戶都被服務。例如，假設M=2，N=6，染色體為[1 2 1 1 2 2 5 2 3 4 1 6]，該染色體表示車場1對應的客戶運輸順序為客戶3-客戶4-客戶 1，車場2對應的客戶運輸順序為 客戶5-客戶2-客戶6。客戶3、4滿足第1輛車的車容量約束，而加上客戶1則不滿足，則車場1的車輛路徑為車場1-客戶3-客戶4-車場1，車場1-客戶1-車場1。

2.2.2適應度函數

適應度函數的計算在解碼的基礎上按照式(1)計算個體適應度值，適應度值越小，運輸時間越短，個體越優。染色體在解碼的過程中，首先根據染色體1-N基因位置解碼出每個車場分配的客戶，再根據染色體N+1-2N解碼出客戶運輸順序，然后車輛從車場出發把貨物依次運送給客戶。在運送的過程中，根據式(9)實時計算當前時間，如果一輛車的貨物已經全部派送完，則返回后派出下一輛車繼續運送。在解碼的過程中，需要確保滿足客戶送到時間約束，采用懲罰函數處理時間約束問題，如果客戶達到時間不滿足時間約束要求，則在個體適應度上加入一個比較大的值，從而使該個體在進化的過程中被逐漸淘汰，適應度計算方法如式(10)所示。

(10)

式中P為懲罰值，滿足約束條件下為0，不滿足約束條件下為一個極大值。

2.2.3遺傳算子

選擇算子采用輪盤賭選擇方式，個體適應度值越低，被選中的概率越大[7]。交叉算子在隨機選擇兩個交叉個體之后，采用隨機初始化交叉位置后染色體基因互換方式進行交叉，變異算法在隨機選擇1個變異個體之后，采用隨機初始化變異位置后基因變異方式進行變異。

在交叉和變異操作中，一般認為被選中參與個體適應度值越差，越應該進行交叉和變異操作，從而能夠產生新的個體，適應度值越好，越應該避免進行交叉和變異操作[8]，從而能夠把該個體保留到下一代中。借鑒上述交叉和變異操作的思想，本文提出了一種自適應交叉和操作方法。該方法初始化了3個從大到小交叉概率和變異概率調整參數，且Pc1>Pc2>Pc3，Pm1>Pm2>Pm3。在每次選擇交叉或變異的個體之后，根據選擇個體的適應度值來計算實際交叉概率和變異概率，從而促使適應度值低的個體以更高概率參與交叉和變異操作來產生更好的個體，交叉和變異概率計算公式如式(11)、(12)所示。

(11)

(12)

式中：f′為參與交叉個體中適應度最大值；favg為種群平均適應度值；f為參與變異個體適應度值；fmax是當前種群中染色體適應度最大值；fmin是當前種群中染色體適應度最小值。

2.2.4蟻群算法優化路徑

在遺傳算法搜索得到客戶分配以及運輸路徑之后，采用蟻群算法優化每個車場配送路徑。蟻群優化路徑包括個體解碼、適應度計算、信息素初始化、狀態轉移概率和信息素更新5個環節。

個體解碼：根據遺傳染色體個體解碼出每個車場的配送客戶和初始配送路徑，蟻群算法每次只優化配送路徑。

適應度計算：蟻群算法適應度值是每個車場所有客戶配送路徑長度，如式(13)所示。

(13)

式中：n是車場分配客戶數量；Li為客戶間距離。

信息素初始化：信息素矩陣C是蟻群算法搜索依據，按照遺傳初始優化結果初始化信息素矩陣，初始路徑包含節點對應的信息素較大，從而使遺傳優化方案更容易被選擇。

狀態轉移概率矩陣：對于當前節點，蟻群算法選擇下一個節點的狀態轉移概率矩陣如式(14)所示。

(14)

信息素更新：蟻群算法每迭代一次之后，都按照當前最優路徑更新信息素，信息素更新如式(15)所示。

(15)

式中：ρ為信息素揮發速度；Qa為信息素增加量。

2.2.5模擬退火個體采納

把模擬退火算子引入到遺傳蟻群算法中，算法在迭代計算開始時初始化溫度T0，該溫度在每次迭代中按照一定比例下降，每次蟻群算法生成的個體，都按照模擬退火個體采納方法判斷是否取代原始個體，從而讓算法具有跳出局部最優解的能力。模擬退火個體采納公式如式(16)所示。

(16)

式中：df為蟻群優化個體和原始遺傳個體適應度值差；T為當前模擬退火溫度，該溫度按照遺傳算法迭代以q值速度進行降溫。

2.3算法流程

本文構建的改進遺傳蟻群算法的計算流程如圖1所示。

圖1　算法流程

3算例分析

采用本文提出的優化算法優化3個車場和25個客戶的帶時間約束路徑優化問題，每個車場都具有5輛運輸車輛，每輛車的載質量為20 t，車輛行駛速度為勻速60 km/h，每個客戶都有一定的需求量和送達時間要求，車場和客戶信息分別如表1、2所示。

分別采用普通遺傳算法、遺傳蟻群算法和改進遺傳蟻群算法優化該問題，問題參數為：遺傳算法種群個數為20，遺傳迭代次數為100，交叉概率數組為[0.2 0.3 0.4]，變異概率數組為[0.2 0.3 0.4]，初始溫度為1 000，溫度降溫速率為0.9，蟻群算法種群個數為10，蟻群迭代次數為50，優化過程比較如圖2所示。改進遺傳蟻群的最優結果如表3所示。采用上述3種算法反復計算100次，3種算法的優化結果比較如表4所示。

由圖11和圖12可以發現，不同開挖深度加載對圍護樁的水平位移影響較大。隨著基坑開挖深度增大而進行加載，圍護樁最大位移逐漸減小，且加載時的開挖深度越大，圍護樁最大水平位移減小量越大，基坑未開挖之前進行加載圍護樁產生的水平位移最大。因此，在實際工程中，基坑應盡早施工并開挖至坑底，減少斜拱樁基施工產生的大水平推力對深基坑圍護樁變形的影響。

從圖2、表4可以看出，在使用相同的種群規模、交叉變異參數的條件下,本文提出的改進遺傳蟻群算法函數適應度在第20代收斂于1 039，使用遺傳算法適應度值在第56代收斂于1 151，使用遺傳蟻群算法函數適應度值在第78代收斂于1 073。本文提出的算法收斂速度和優化結果都優于另兩種方法。車輛速度為60 km/h，所以車輛行駛時間就等于行駛路程。從表2和表3對照可以看出，計算的優化路徑都能使每個客戶需求點滿足時間窗要求，又因算法本身就滿足車載能力約束，所以本算法的結果都能夠滿足約束條件。本文提出的改進遺傳蟻群算法通過加入蟻群路徑搜索、退火向后搜索、自適應交叉變異等方法提高了算法全局搜索能力，具有較好的優化能力。

表1　車場信息

表2　客戶信息

圖2　優化結果

表4　優化結果比較

4結束語

本文根據帶時間窗的多車場多車輛路徑優化問題的優化難點，構建了一種改進的遺傳蟻群算法，通過加入蟻群路徑搜索、退火向后搜索、自適應交叉變異算子等方法提高了算法全局搜索能力，并且通過仿真實驗驗證了該算法的有效性和正確性。

參考文獻

[1]李軍，郭耀煌．物流配送車輛優化調度理論與方法[M]．北京：中國物資出版社，2001：3-6.

[2]謝秉磊，李軍． 有時間窗的非滿載車輛調度問題的遺傳算法[J]．系統工程學報，2000， 15(3):290.

[3]TAN K C，CHEW Y H，LEE L H． A Hybrid Multi-objective Evolutionary Algorithm for Solving Truck and Trailer Vehicle Routing Problems[J].European Journal of Operational Research，2006，172:855.

[4]蔣毅．基于蟻群優化算法的車輛路徑問題研究[D]．長春：吉林大學，2007．

[5]丁建立, 陳增強, 袁著祉. 遺傳算法與螞蟻算法的融合[J]. 計算機研究與發展, 2003，40(9):1351.

[6]劉勇,崔炳謀,王小東,等. 物流配送路徑優化問題的模型及改進混合算法[J].物流科技,2008(4):26.

[7]楊元峰．多車場多車型車輛路徑問題的改進遺傳算法[J]．計算機與現代化，2008(9):10.

[8]占焱發. 基于遺傳算法的物流配送車輛路徑問題研究[D]. 西安：長安大學，2010.

(編校：夏書林)

Study on Multi-distribution Vehicle Scheduling with Time Window Based on Genetic Algorithm-ant Colony Algorithm

MA Hongkun，YANG Wei*，ZHAO Jia ，HAO Haibin

(SchoolofTransportationandAutomobileEngineering,XihuaUniversity,Chengdu610039China)

Abstract:The multi-distribution centers vehicle scheduling model with a single time window was built in this paper. A new hybrid algorithm combining Ant colony algorithm with genetic algorithm was proposed. In order to improve the Search ability of the algorithm, a colony algorithm and a adaptive for adjusting and mutation probability were combined based on the genetic algorithm. To improve the ability of algorithm to avoid being premature, a way with Simulated annealing algorithm was utilized to accept new member produced by Ant colony algorithm. Finally，the effectiveness and validity of the algorithm were tested through simulation.

Keywords:genetic algorithm-ant colony algorithm; adaptive; multi-depot; time window; vehicle routing problem

收稿日期：2015-11-11

*通信作者：楊偉(1965—)，男，教授，博士，主要研究方向為汽車被動安全技術。E-mail:yw@mail.xhu.edu.cn

中圖分類號：U491

文獻標志碼：A

文章編號：1673-159X(2016)03-0031-5

doi:10.3969/j.issn.1673-159X.2016.03.007

·新能源汽車與低碳運輸·