關(guān)聯(lián)物流運(yùn)輸調(diào)度問題的改進(jìn)遺傳算法

湯雅連，蔡延光，趙學(xué)才

（廣東工業(yè)大學(xué) 自動(dòng)化學(xué)院，廣東 廣州 510006）

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

1 問題描述及數(shù)學(xué)模型的建立

1.1 問題描述

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

1.2 數(shù)學(xué)模型

有 l個(gè)客戶（1，2，…，l），第 i個(gè)客戶的需求量為 gi（i=1，2，…，l），需要從車場(chǎng)將貨物運(yùn)給客戶，可派出載重為qh的貨車，已知gi＜qh?？蛻粢笏拓浀臅r(shí)間窗為[eti，lti]，每小時(shí)等待費(fèi)用和延遲費(fèi)用分別為 s1和 s2，早到或者晚到都會(huì)受到懲罰。Ti表示車輛到達(dá)i的時(shí)間。以表示車場(chǎng) n中h類型的車輛k從i到j(luò)的運(yùn)輸成本（距離、費(fèi)用、時(shí)間等），=。每種類型的車為Knh，客戶 i，j之間的距離為 dij。rij表示 i貨物與 j貨物的關(guān)聯(lián)系數(shù)。目標(biāo)為考慮路況約束、載重約束、關(guān)聯(lián)約束、多車場(chǎng)、多車型、軟時(shí)間窗等情況下，使各車場(chǎng)的車輛能滿足所有用戶的需求，并使總運(yùn)輸成本最小。

假設(shè)客戶編號(hào)為 1，2，…，l，車場(chǎng)編號(hào)為 l+1，l+2，…，l+N。定義變量如下：

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

2 算法設(shè)計(jì)

2.1 編碼及初始種群的產(chǎn)生

本文采用參考文獻(xiàn)[6]提出的編碼方式及產(chǎn)生初始種群的方式。

2.2 適應(yīng)度值計(jì)算與選擇操作

fi=Z/Zi，即當(dāng)前群體中最佳染色體的目標(biāo)函數(shù)值z(mì)與當(dāng)前染色體的目標(biāo)函數(shù)值Zi的比值作為適應(yīng)度值。根據(jù)輪盤賭策略，按適應(yīng)度值的大小分配復(fù)制概率。

2.3 交叉

本節(jié)設(shè)計(jì)了與進(jìn)化代數(shù)相關(guān)而與個(gè)體適應(yīng)度無(wú)關(guān)的交叉概率計(jì)算公式（13）。t為當(dāng)前進(jìn)化代數(shù)，Tgen為預(yù)設(shè)的最大進(jìn)化代數(shù)，pcmax為預(yù)設(shè)最大概率，pcmin為預(yù)設(shè)最小概率，pc（t）為當(dāng)前種群的交叉概率。本文采取均勻交叉的方式。

2.4 變異

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

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

2.5 終止條件

當(dāng)算法運(yùn)行達(dá)到最大迭代次數(shù)或者多次產(chǎn)生同樣的最優(yōu)解，算法終止。

3 仿真分析

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

表1 車場(chǎng)位置信息

表2 客戶信息

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

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

表3 各配送車輛的配送數(shù)據(jù)

圖1 配送路徑示意圖

本文考慮了收斂精度與進(jìn)化代數(shù)的關(guān)系，混沌變異結(jié)合了“尺度收縮”思想，并采用了避免近親繁殖的策略，達(dá)到了提高算法性能的效果。實(shí)驗(yàn)證明，改進(jìn)的自適應(yīng)混沌遺傳算法求解此類問題是有效的。

[1]李臻，雷定猷.多車場(chǎng)車輛優(yōu)化調(diào)度模型及算法[J].交通運(yùn)輸工程學(xué)報(bào)，2004，4（1）：83-86.

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

[3]鐘石泉，王雪蓮.多車場(chǎng)集送一體化車輛調(diào)度問題及其遺傳算法研究 [J].西安電子科技大學(xué)學(xué)報(bào)，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]鐘石泉，賀國(guó)光.單車場(chǎng)復(fù)雜情況下的車輛調(diào)度[J].系統(tǒng)工程，2005（5）：29-31.

[6]楊元峰.多車場(chǎng)多車型車輛路徑問題的改進(jìn)遺傳算法 [J].計(jì)算機(jī)與現(xiàn)代化，2008（9）：10-12.