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

基于自適應(yīng)遺傳算法的關(guān)聯(lián)運(yùn)輸調(diào)度問題

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

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

關(guān)聯(lián)物流運(yùn)輸調(diào)度；自適應(yīng)；遺傳算法

1.引言

物流配送車輛調(diào)度問題[1]包括運(yùn)輸路線安排問題（VRP）和車輛調(diào)度問題（VSP），被認(rèn)為是NP-hard問題。運(yùn)輸調(diào)度問題[2]的目的是在滿足一定的約束條件（如車輛限制、時(shí)間限制、載重限制、運(yùn)輸能力限制等）下，組織適當(dāng)?shù)男熊嚶肪€和任務(wù)分配，達(dá)到一定的目標(biāo)（如成本極少、路程最短、時(shí)間最少、使用車輛數(shù)盡量少等）。

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

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

2.單車場RVRP模型建立

2.1 問題描述及假設(shè)

本章研究的問題基于以下假設(shè)：

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

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

（3）非滿載，軟時(shí)間窗約束；

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

2.2 模型的建立

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

預(yù)先估計(jì)車輛數(shù)[13]?？梢园凑帐?1)估算車輛數(shù)。式中，[ ]表示不大于括號內(nèi)數(shù)字的最大整數(shù)； 0 ＜α＜1，是對裝車（或卸車）的復(fù)雜程度及約束多少的估計(jì)。

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

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

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

3.自適應(yīng)遺傳算法設(shè)計(jì)

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

3.1 交叉算子

交叉算子主要用于產(chǎn)生新個(gè)體，實(shí)現(xiàn)算法的全局搜索能力?？紤]到整個(gè)種群的變化趨勢及每個(gè)個(gè)體的變異機(jī)會，本節(jié)設(shè)計(jì)了與進(jìn)化代數(shù)相關(guān)而與個(gè)體適應(yīng)度無關(guān)的交叉概率計(jì)算公式，如式(16)。t為當(dāng)前進(jìn)化代數(shù)， Tg en為預(yù)設(shè)的最大進(jìn)化代數(shù)， pcmax為預(yù)設(shè)最大概率，pcmin為預(yù)設(shè)最小概率， pc( t)為當(dāng)前種群的交叉概率。

3.2 變異算子

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

3.3 隨機(jī)擾動[14]

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

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

表1 客戶信息一覽表

表2 貨物間的關(guān)聯(lián)系數(shù)

表3 客戶之間的道路路況系數(shù)

表4 本算法最優(yōu)配送路徑

表5 兩種算法對比結(jié)果

算，m依目標(biāo)函數(shù)而定，這里取5＝m。

Step3：對新產(chǎn)生的種群進(jìn)行適應(yīng)度值計(jì)算，若滿足終止條件，輸出最優(yōu)值；否則，返回Step1。

3.4 自適應(yīng)遺傳算法

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

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

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

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

Step5：計(jì)算新種群中染色體對應(yīng)的目標(biāo)函數(shù)值及適應(yīng)值，并對適應(yīng)度較小的個(gè)體進(jìn)行混沌擾動，若該新個(gè)體的適應(yīng)度值大于原個(gè)體，則替換原個(gè)體，否則不變。迭代多次。

Step6：滿足條件，輸出最優(yōu)解，算法終止；否則，轉(zhuǎn)步驟Step2。

4.仿真分析

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

5.結(jié)束語

本章研究了帶道路容量動態(tài)約束的關(guān)聯(lián)物流運(yùn)輸調(diào)度問題。研究成果如下：

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

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

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

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

[2]任中明.運(yùn)輸調(diào)度問題的智能求解機(jī)制研究[D].廣州:廣東工業(yè)大學(xué),2011.

[3]屈援,汪波,鐘石泉.單車場多送貨點(diǎn)車輛路徑問題的改進(jìn)遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用,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]李敏,郭強(qiáng),劉紅麗.多車場多配送中心的物流配送問題研究[J].計(jì)算機(jī)工程與應(yīng)用,2007,43(8):202-204.

[10]蔡延光,李永生,林灼強(qiáng),丁志勇.帶中轉(zhuǎn)點(diǎn)的聯(lián)盟運(yùn)輸調(diào)度的遺傳算法研究[J].計(jì)算機(jī)應(yīng)用研究,2007,24(11):82-84.

[11]陳金,蔡延光.帶時(shí)間窗的中轉(zhuǎn)聯(lián)盟運(yùn)輸調(diào)度問題的混合算法研究[J].工業(yè)控制計(jì)算機(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]王占鋒,張翠軍,許冀偉等.求解非滿載車輛調(diào)度問題的改進(jìn)遺傳算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2008,29(15):3991-3994.

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

[15]李青欣.自動導(dǎo)引車路徑規(guī)劃遺傳算法研究[D].廣州:廣東工業(yè)大學(xué),2011.

國家自然科學(xué)基金項(xiàng)目(61074147，60374062)；廣東省自然科學(xué)基金項(xiàng)目(S2011010005059)；廣東省教育部產(chǎn)學(xué)研結(jié)合項(xiàng)目(2011B090400460)；廣東省自然科學(xué)基金團(tuán)隊(duì)項(xiàng)目(8351009001000002)。

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

蔡延光（1963—），男，湖北咸寧人，廣東工業(yè)大學(xué)自動化學(xué)院教授，博士生導(dǎo)師，主要從事組合優(yōu)化、人工智能、決策支持系統(tǒng)等的研究。

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

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

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