關聯物流運輸調度問題的改進遺傳算法

湯雅連，蔡延光，趙學才

（廣東工業大學 自動化學院，廣東 廣州 510006）

多車場多車型關聯物流運輸調度（RVRP）在現實生活中有很強的應用背景。針對多車場VRP問題，不少學者[1-4]已經做了很多研究，并取得了很好的成果，但是對于RVRP的探討甚少。一般是若干個客戶有一定的貨物需求且貨物之間有某種關聯性，有多個車場為所有客戶提供服務，車輛將貨物送到各個客戶地點，然后返回車場。由于車輛在行駛過程中，會受到路況[5]等因素的影響，所以本文主要考慮在路況約束下，對車輛和配送路線進行合理安排，滿足所有客戶要求的前提下，使配送成本最低。

1 問題描述及數學模型的建立

1.1 問題描述

道路容量約束的多車場、多車型關聯物流運輸調度問題簡單描述為，假設給定車場信息以及客戶信息（位置和貨物需求量等），貨物之間的關聯系數，不同類型車輛信息（載重約束、里程約束和容量約束等），要求合理安排車輛和運輸路線，在滿足所有客戶需求的前提下，使配送成本最低。

1.2 數學模型

有 l個客戶（1，2，…，l），第 i個客戶的需求量為 gi（i=1，2，…，l），需要從車場將貨物運給客戶，可派出載重為qh的貨車，已知gi＜qh。客戶要求送貨的時間窗為[eti，lti]，每小時等待費用和延遲費用分別為 s1和 s2，早到或者晚到都會受到懲罰。Ti表示車輛到達i的時間。以表示車場 n中h類型的車輛k從i到j的運輸成本（距離、費用、時間等），=。每種類型的車為Knh，客戶 i，j之間的距離為 dij。rij表示 i貨物與 j貨物的關聯系數。目標為考慮路況約束、載重約束、關聯約束、多車場、多車型、軟時間窗等情況下，使各車場的車輛能滿足所有用戶的需求，并使總運輸成本最小。

假設客戶編號為 1，2，…，l，車場編號為 l+1，l+2，…，l+N。定義變量如下：

目標函數式（3）表示成本最低，以 cnijh表示n車場h類型的車輛從i點到j點的費用，rij表示貨物之間關聯度越高，兼容性越好，懲罰費用越低。式（4）、式（5）表示每個客戶只能由一輛車服務；式（6）表示車場派出的車輛數不能超過該車場的車輛總數；式（7）表示 n車場 h類型車輛的里程約束；式（8）表示車輛必須回到原車場；式（9）表示不能從車場直接到車場；式（10）表示不能超過車輛載重限制；式（11）tij表示i到 j的行駛時間，wij為路段i與 j的路況系數，wij越大，說明路況越好，車輛行駛速度越快，時間越短；式（12）cs為單位配送費用。

2 算法設計

2.1 編碼及初始種群的產生

本文采用參考文獻[6]提出的編碼方式及產生初始種群的方式。

2.2 適應度值計算與選擇操作

fi=Z/Zi，即當前群體中最佳染色體的目標函數值z與當前染色體的目標函數值Zi的比值作為適應度值。根據輪盤賭策略，按適應度值的大小分配復制概率。

2.3 交叉

本節設計了與進化代數相關而與個體適應度無關的交叉概率計算公式（13）。t為當前進化代數，Tgen為預設的最大進化代數，pcmax為預設最大概率，pcmin為預設最小概率，pc（t）為當前種群的交叉概率。本文采取均勻交叉的方式。

2.4 變異

本文采用混沌變異策略，混沌變異形式如式（14）所示。 K（0，1）為（-2，2）按混沌規律變化的序列。

在進化初期采用逐漸縮小的變異尺度，利用參考文獻[3]提出的變異策略，如式（16）所示。k為當前代數，Gen為最大迭代次數，δ為當前群體中某個體的某分量的變異尺度，α、β、γ為控制尺度收縮參數。

2.5 終止條件

當算法運行達到最大迭代次數或者多次產生同樣的最優解，算法終止。

3 仿真分析

根據 Logistic映射[3]，如式（15）所示。 式中，u表示種群序號，u=0，1，…，n；β 表示混沌變量，0≤β≤1；μ 表示吸引子，當 μ 取 0～4時，Logistic映射為[0，1]間的不可逆映射，μ=4時，完全處于混沌的狀態，此時產生的混沌變量 β（u）具有很好的遍歷性。 β（u）經過放大和平移可得 K（0，1）。

表1 車場位置信息

表2 客戶信息

某供應處有3個車場，每個車場有不同類型的車輛，車場信息表見表1，客戶信息表見表2。每輛車的正常行駛速度為60 km/h，最大配送里程為200 km。單位配送費用為 1元/t×km，等待費用為 10元/h，延遲費用為 100元/h。最早發車時間為 7：00。

本文中的實驗是在 Intel（R）CoreTMi3 CPU2.53 GHz、內存2.0 GB的PC機上采用Microsoft Visual C++6.0編程實現。遺傳算法中參數設置：種群規模為100，最大迭 代 次 數 Gen=100，pcmax=0.1，pcmin=0.005， 變 異 概 率0.05，尺度收縮參數為 α=1，β=10，γ=0.5，δ=0.5。運行程序20次，得到該算法求解本算例的最優結果見表3，配送示意圖如圖1所示。

表3 各配送車輛的配送數據

圖1 配送路徑示意圖

本文考慮了收斂精度與進化代數的關系，混沌變異結合了“尺度收縮”思想，并采用了避免近親繁殖的策略，達到了提高算法性能的效果。實驗證明，改進的自適應混沌遺傳算法求解此類問題是有效的。

[1]李臻，雷定猷.多車場車輛優化調度模型及算法[J].交通運輸工程學報，2004，4（1）：83-86.

[2]李敏，郭強，劉紅麗.多車場多配送中心的物流配送問題研究[J].計算機工程與應用，2007，43（8）：202-204.

[3]鐘石泉，王雪蓮.多車場集送一體化車輛調度問題及其遺傳算法研究 [J].西安電子科技大學學報，2009，19（1）：63-68.

[4]YADLAPALLI S， BAE J， RATHINAM S，et al.Appriximation algorithms for a heterogeneous multiple depot hamiltonian path problem[C].2011 American Control Conference.2011.

[5]鐘石泉，賀國光.單車場復雜情況下的車輛調度[J].系統工程，2005（5）：29-31.

[6]楊元峰.多車場多車型車輛路徑問題的改進遺傳算法 [J].計算機與現代化，2008（9）：10-12.