基于自適應遺傳算法的關聯運輸調度問題

廣東工業大學自動化學院 肖 丹 蔡延光 湯雅連 胡夏云 徐山峰

基于自適應遺傳算法的關聯運輸調度問題

廣東工業大學自動化學院 肖 丹 蔡延光 湯雅連 胡夏云 徐山峰

利用引入了混沌擾動的一種改進的自適應遺傳算法來解決一類關聯運輸調度問題IVRP（Incident Vehicle Routing Problem）模型。雖然M.Srinivas提出的自適應遺傳算法既保護了最優個體又加快了較差個體的淘汰程度，但不容易跳出局部最優解，相鄰進化代數間的參數缺乏連續性，所以，提出了一種新的自適應遺傳算法，為避免近親繁殖提出了改進策略，同時考慮到變異概率的大小可能導致破壞種群模式或減弱抑制早熟的能力，設計了相關的自適應變異概率。研究表明，該改進的算法在解決關聯物流運輸調度問題具有有效性和適用性。

關聯物流運輸調度；自適應；遺傳算法

1.引言

物流配送車輛調度問題[1]包括運輸路線安排問題（VRP）和車輛調度問題（VSP），被認為是NP-hard問題。運輸調度問題[2]的目的是在滿足一定的約束條件（如車輛限制、時間限制、載重限制、運輸能力限制等）下，組織適當的行車路線和任務分配，達到一定的目標（如成本極少、路程最短、時間最少、使用車輛數盡量少等）。

客戶通常將所有零件商品供貨交給一個物流運輸公司來為其配貨，而每個客戶所需貨物有一定的關聯性，物流公司須考慮怎樣進行車輛分配和尋求最優配送路線以達到最低的物流成本來為多個這種性質的客戶配送貨物，這樣的調度問題稱之為關聯物流運輸調度問題（Incident Vehicle Routing Problem）。國內外學者還沒有人對此問題進行研究，該問題是由蔡延光教授首次提出，因而具有理論研究意義和實際應用價值。研究學者們對VRP[3～8]、MVRP[9]（Multi-Depot Vehicle Routing）、AVRP[10，11]（Allied Vehicle Routing Problem）、DVRP[11，12]（Deterministic Vehicle Routing Problem）等問題的研究方法和已取得的成果對研究該問題都具有很大的借鑒意義。

由于車輛在配送過程中，會受到道路路況的影響，而單車場單車型是多車場多車型的基本模型，所以本章研究較簡單的模型——單車場單車型單配送中心帶軟時間窗和道路容量約束的RVRP，并提出了一種自適應遺傳算法來對所建立的模型求解。

2.單車場RVRP模型建立

2.1 問題描述及假設

本章研究的問題基于以下假設：

（1）1個車場，l個客戶（1，2，…，l），客戶需求已知，1個配送中心；

（2）每輛車有里程約束和載重約束，同種車型；

（3）非滿載，軟時間窗約束；

（4）道路容量動態約束，不考慮交叉口沖突模型等，車輛均在主干道上行駛，道路寬度恒定。

2.2 模型的建立

有l個客戶（1，2，…，l），第i個客戶的貨運量為 gi（ i ＝1,2,...l ），需要從車場0將貨物運到客戶位置，車場可派出載重為q的貨車，已知 gi＜ q ，客戶要求送貨的時間窗為[ ， ]，每小時等待費用和延遲費用分別為 c1和 c2，車輛早到或者晚到，都會受到懲罰。 t0i表示車輛從配送中心到i的時間。

預先估計車輛數[13]。可以按照式(1)估算車輛數。式中，[ ]表示不大于括號內數字的最大整數； 0 ＜α＜1，是對裝車（或卸車）的復雜程度及約束多少的估計。

以 cij表示為從點i到點j的運輸成本(距離、費用、時間等)， cij＝ cji。假設客戶i，j之間的距離為 dij。關聯系數為r， rij表示點i處的貨物與點j處貨物的關聯系數。為簡化問題，用 wij表示路況系數， wij越大，說明路況越差，交通越堵塞，車輛通過此段路的時間越長，成本越高；反之，成本越低。目標是使運輸成本最低。定義變量如下：

建立數學模型

目標函數式(4)表示總運輸成本最低， Ti表示到達客戶i的時間。(5)為車輛行駛里程約束，其中dijk表示車輛k從i行駛到j的路程，n是車輛k服務的客戶數目，最大為N。(6)和(7)表示兩個變量之間的關系。(8)表示車輛服務i后直接行駛到j為其服務。(9)表示每個客戶只由1輛車來服務且每個客戶都能得到服務。(10)表示每輛車所運送的貨物重量不能超過車輛載重限制。(11)表示每輛車的客戶總數小于等于總客戶數目。(12)為關聯系數 ijr的取值約束。(13)ijt表示從i到j的行駛時間，ijw為路況系數， ijw越大，表示路況越差；反之，越好。(14)表示行駛總時間，mt為卸貨時間。

3.自適應遺傳算法設計

本節設計的自適應遺傳算法[14]包括避免近親繁殖的雜交策略與改進的交叉概率。文獻[15]中提出到了M.Srinivas提出的自適應遺傳算法，該算法是根據每代個體適應度的改變來自適應地改變pc和 pm，既保護了最優個體又加快了較差個體的淘汰程度，但以個體單位改變它們缺乏整體協作精神，在某些情況下（如整體進化的停滯期），將不容易跳出局部最優解，相鄰進化代數間的參數缺乏連續性，所以，本節提出了一種新的自適應遺傳算法，采取在交叉操作后保留適應度值最大個體的策略，設計與進化代數相關的交叉概率和自適應變異概率。

3.1 交叉算子

交叉算子主要用于產生新個體，實現算法的全局搜索能力。考慮到整個種群的變化趨勢及每個個體的變異機會，本節設計了與進化代數相關而與個體適應度無關的交叉概率計算公式，如式(16)。t為當前進化代數， Tg en為預設的最大進化代數， pcmax為預設最大概率，pcmin為預設最小概率， pc( t)為當前種群的交叉概率。

3.2 變異算子

交叉算子起著全局搜索的作用，變異算子主要是產生新個體和抑制早熟。設計變異概率的總趨勢是逐漸減小而使群體迅速集中。下面是本節設計的自適應變異概率。maxmp 是預設的最大變異概率，minmp是預設的最小變異概率，）（tpm是第t代個體進行變異的概率。

3.3 隨機擾動[14]

Step1：對適應度較小的90%對應的優化變量按式（20）加一混沌擾動，按式（19）映射為優化變量，進行迭代計算。式（21）中的θ隨迭代次數增加為不斷變化，迭代向較優解逼近，直到滿足式（22）。k為迭代次數。

Step2：φ*為當前最優解[10](，…，)映射到[0，1]的向量，φk為迭代k次后的混沌向量，為隨機擾動后的混沌向量，θ取值為(0，1)，可由式（21）來計

表1 客戶信息一覽表

表2 貨物間的關聯系數

表3 客戶之間的道路路況系數

表4 本算法最優配送路徑

表5 兩種算法對比結果

算，m依目標函數而定，這里取5＝m。

Step3：對新產生的種群進行適應度值計算，若滿足終止條件，輸出最優值；否則，返回Step1。

3.4 自適應遺傳算法

自適應遺傳算法流程圖如圖1所示，具體步驟如下：

Step1：初始化。通過隨機發生器產生l個客戶的全排列，并將首末位置0，表示從車場出發最終回到車場。確定種群規模、交叉概率、變異概率、進化代數等參數，并均勻地隨機產生初始種群，其中包含m個染色體。

Step2：適應度值計算。計算相應的目標函數值以及適應度函數值jf，j=1，2，…，m。對于極大值問題，適應值就等于目標函數值。用當前群體中最佳染色體的目標函數值Z與當前染色體的目標函數值iZ的比值作為適應度值。

Step4：對選擇后的種群以改進的交叉概率和變異概率進行操作，生成新種群。

Step5：計算新種群中染色體對應的目標函數值及適應值，并對適應度較小的個體進行混沌擾動，若該新個體的適應度值大于原個體，則替換原個體，否則不變。迭代多次。

Step6：滿足條件，輸出最優解，算法終止；否則，轉步驟Step2。

4.仿真分析

某物流中心為9個客戶配送貨物，如表1所示。有載重為8噸的大型車輛，每輛車的最大里程為200km，車速為60km/h。貨物關聯系數如表2所示，路況系數如表3所示。等待費用和延遲費用分別為10元/h和100元/h，不考慮吃飯時間。車場為（0，0）。單位配送費用為1元/t*km。最早發車時間7:00。

5.結束語

本章研究了帶道路容量動態約束的關聯物流運輸調度問題。研究成果如下：

(1)為了整體把握算法，克服參數計算僅與每一代個體的情況有關，而相鄰代數之間的參數計算缺乏連續性的局限性，設計了一種改進的自適應遺傳算法，既避免了近親繁殖，又考慮了進化代數之間的關系，設計的相應的交叉概率和自適應變異概率；

(2)考慮了道路路況對配送時間的影響，最終體現在是否符合時間窗要求；

(3)考慮了貨物性質關聯對不同性質的貨物是否能同載的約束。用此算法對所建立的模型求解。實例證明，本章提出的自適應遺傳算法能有效求解此類問題，在下一步研究中，可以延伸至求解多個擴展特征(需求關聯、時間關聯等)的關聯運輸調度問題。

[1]張潛,高立群,胡祥培,等.物流配送路徑多目標優化的聚類-改進遺傳算法[J].控制與決策,2003,18(4):418-422.

[2]任中明.運輸調度問題的智能求解機制研究[D].廣州:廣東工業大學,2011.

[3]屈援,汪波,鐘石泉.單車場多送貨點車輛路徑問題的改進遺傳算法[J].計算機工程與應用,2007,43(25):237-239.

[4]G.B.Alvarenga,G.R.Mateus,G.de Tomi.A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows[J].Computers&Operations Research,34(2007)1561-1584.

[5]Hong Ma,Brenda Cheang,Andrew Lim,et al.An investigation into the vehicle routing problem with time windows and link capacity constraints[J].Omega,2012,40:336-347.

[6]Christian Prins.A simple and effective evolutionary algorithm for the vehicle routing problem[J].Computer&Operations Research 31(2004):1985-2002.

[7]Yanis Marinakis,Magdalene Marinaki,Georgios Dounias.A hybrid particle swarm optimization algorithm for the vehicle routing problem[J].Engineering Applications of Artif i cial Intelligence 23(2010):463-472.

[8]G.Nilay Yucenur,Nihan Cetin Demirel.A new geometric shape-based genetic clustering algorithm for the multi-depot vehicle routing problem[J].Expert Systems with Appications 38(2011):11859-11865.

[9]李敏,郭強,劉紅麗.多車場多配送中心的物流配送問題研究[J].計算機工程與應用,2007,43(8):202-204.

[10]蔡延光,李永生,林灼強,丁志勇.帶中轉點的聯盟運輸調度的遺傳算法研究[J].計算機應用研究,2007,24(11):82-84.

[11]陳金,蔡延光.帶時間窗的中轉聯盟運輸調度問題的混合算法研究[J].工業控制計算機,2010,23(1):70-72.

[12]Rita Macedo,Claudio Alves,J.M.Valerio de Carvaiho,Francois Clautiaux,Said Hanafi.Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudopolynomial model[J].European Journal of Operational Research,214(2011):536-545.

[13]王占鋒,張翠軍,許冀偉等.求解非滿載車輛調度問題的改進遺傳算法[J].計算機工程與設計,2008,29(15):3991-3994.

[14]魏明,蔡延光.一種基于混沌領域搜索的自適應遺傳算法[J].計算機應用研究,2009,26(2):465-467.

[15]李青欣.自動導引車路徑規劃遺傳算法研究[D].廣州:廣東工業大學,2011.

國家自然科學基金項目(61074147，60374062)；廣東省自然科學基金項目(S2011010005059)；廣東省教育部產學研結合項目(2011B090400460)；廣東省自然科學基金團隊項目(8351009001000002)。

肖丹（1987—），男，湖南永州人，碩士研究生，研究方向：物流信息技術與應用。

蔡延光（1963—），男，湖北咸寧人，廣東工業大學自動化學院教授，博士生導師，主要從事組合優化、人工智能、決策支持系統等的研究。

湯雅連（1986—），女，湖南常德人，碩士研究生，研究方向：物流信息技術與應用。

胡夏云（1987—），女，江西宜春人，碩士研究生，研究方向：物流信息技術與應用。

徐山峰（1987—），男，福建莆田人，碩士研究生，主要研究方向：物流信息技術 與應用。