基于客戶(hù)分類(lèi)時(shí)間窗車(chē)輛路徑問(wèn)題的多種群遺傳算法

[摘要] 本文從顧客差異化的角度出發(fā)，利用聚類(lèi)分析對(duì)客戶(hù)分類(lèi)，提出了基于客戶(hù)分類(lèi)時(shí)間窗約束的車(chē)輛配送路徑數(shù)學(xué)模型，該模型克服了傳統(tǒng)時(shí)間窗車(chē)輛配送模型對(duì)各個(gè)客戶(hù)不加區(qū)分的不合理性。根據(jù)此模型，本文設(shè)計(jì)了多種群并行遺傳算法進(jìn)行求解。實(shí)驗(yàn)結(jié)果表明，該算法相對(duì)于標(biāo)準(zhǔn)遺傳算法，有效地克服容易早熟收斂的缺點(diǎn)，其結(jié)果更加接近最優(yōu)解。

[關(guān)鍵詞] 客戶(hù)分類(lèi) 時(shí)間窗 車(chē)輛路徑問(wèn)題 多種群并行遺傳算法

一、引言

車(chē)輛路徑問(wèn)題（VRP）是1959年由Dantzig GB等首次提出，它是個(gè)NP難問(wèn)題，只有當(dāng)客戶(hù)和路段較少時(shí)，才能求得精確解。啟發(fā)式算法成了求解該問(wèn)題的重要方向，國(guó)內(nèi)外學(xué)者已經(jīng)提出了多種求解該問(wèn)題的啟發(fā)式算法，如禁忌搜索算法、節(jié)約算法、蟻群算法、模擬退火算法、神經(jīng)網(wǎng)絡(luò)算法以及混合啟發(fā)式算法。但是這些算法都只能求出該問(wèn)題的某一特殊類(lèi)型或規(guī)模較小時(shí)的近似最優(yōu)解或最優(yōu)解。由于VRP問(wèn)題的特殊性，利用遺傳算法的搜索能力解決此類(lèi)問(wèn)題是很自然的想法。

可是傳統(tǒng)的標(biāo)準(zhǔn)遺傳算法有兩個(gè)嚴(yán)重的缺點(diǎn)：容易早熟收斂以及在進(jìn)化后期搜索效率較低。為此，本文提出一種改進(jìn)的遺傳算法——多種群并行遺傳算法。在大多數(shù)情況下，相比較于單種群遺傳算法，多種群遺傳算法得以實(shí)現(xiàn)多種群的協(xié)同進(jìn)化，具有更好的全局搜索能力，有效地避免了早熟收斂。

本文從顧客差異化的角度出發(fā)，利用聚類(lèi)分析對(duì)客戶(hù)進(jìn)行分類(lèi)，研究基于客戶(hù)分類(lèi)的時(shí)間窗約束的車(chē)輛配送路徑問(wèn)題，根據(jù)其特點(diǎn)，構(gòu)造了求解該問(wèn)題的數(shù)學(xué)模型，該模型克服了傳統(tǒng)時(shí)間窗車(chē)輛配送模型對(duì)各個(gè)客戶(hù)不加區(qū)分，進(jìn)行同等處理的不合理性，并使用多種群的并行遺傳算法進(jìn)行計(jì)算。通過(guò)實(shí)驗(yàn)計(jì)算，證明了該算法的良好尋優(yōu)性能。

二、基于客戶(hù)分類(lèi)的帶時(shí)間窗VRP問(wèn)題的數(shù)學(xué)模型

有時(shí)間窗的車(chē)輛路徑問(wèn)題描述為:一個(gè)配送中心，擁有一定數(shù)量容量為q的車(chē)輛，負(fù)責(zé)對(duì)N個(gè)客戶(hù)進(jìn)行貨物配送工作，客戶(hù)i的貨物需求為gi，且gi

在以上的做法中，處理時(shí)間約束時(shí)，對(duì)于所有的客戶(hù)來(lái)說(shuō)，都是同等處理，這顯然不符合實(shí)際情況。不同的客戶(hù)對(duì)于時(shí)間限制有不同的要求，而對(duì)于配送方來(lái)說(shuō)，對(duì)于不同的客戶(hù)，也應(yīng)采取不同的配送優(yōu)先級(jí)別。在這里，根據(jù)客戶(hù)的訂貨量，貨物對(duì)于客戶(hù)的重要性，客戶(hù)的業(yè)務(wù)需求拓展?jié)摿Φ纫蛩?，利用聚?lèi)分析的方法將客戶(hù)分成三類(lèi)，第一類(lèi)是優(yōu)先客戶(hù)，貨物必須在規(guī)定的時(shí)間范圍內(nèi)到達(dá)，配送方如果違反規(guī)定，將很可能失去此客戶(hù)或者支付極高的違約金;第二類(lèi)是重要客戶(hù)，他們的要求沒(méi)有優(yōu)先客戶(hù)高，允許配送時(shí)間偶爾超出規(guī)定的時(shí)間范圍；第三類(lèi)是一般客戶(hù)，他們對(duì)時(shí)間限制的要求相對(duì)是最低的。

根據(jù)以上的分類(lèi)，分別對(duì)不同類(lèi)別的客戶(hù)調(diào)整時(shí)間窗的約束范圍。對(duì)于第一類(lèi)客戶(hù)，必須嚴(yán)格遵守時(shí)間窗范圍的約束;對(duì)于第二類(lèi)客戶(hù)，允許在原有時(shí)間窗范圍的基礎(chǔ)上，進(jìn)行一定的調(diào)整（允許偶爾延遲若干小時(shí)）；對(duì)于第三類(lèi)客戶(hù)，則不考慮其時(shí)間約束。

設(shè)配送中心編碼為0。客戶(hù)編碼為1，2，……，n。其中第一類(lèi)客戶(hù)的編碼為1，2，……，h;第二類(lèi)客戶(hù)的編碼為h+1，h+2，……m;第三類(lèi)客戶(hù)的編碼為m+1，m+2，……，n。定義變量

其中:s為車(chē)輛數(shù)目;n為客戶(hù)數(shù)目;cij為車(chē)輛單位運(yùn)距從i到j(luò)的運(yùn)費(fèi);d和e為懲罰系數(shù)，第二類(lèi)客戶(hù)的時(shí)間窗約束允許在原來(lái)基礎(chǔ)上分別調(diào)整u和v個(gè)小時(shí)；gi為客戶(hù)i的貨物需求量;q為車(chē)輛的容量:tij為連接客戶(hù)i和客戶(hù)j的行駛時(shí)間;ti為到達(dá)客戶(hù)i處的時(shí)間;ETi為到達(dá)客戶(hù)i處的規(guī)定最早到達(dá)時(shí)間;LTi為到達(dá)客戶(hù)i處的規(guī)定最晚到達(dá)時(shí)間;wi為客戶(hù)i處的服務(wù)時(shí)間。在上述模型中，式(2)表示目標(biāo)函數(shù);式(3)表示每輛車(chē)的配送量不超過(guò)其相應(yīng)的容量約束;式(4)和(5)表示每個(gè)客戶(hù)只能被一輛車(chē)服務(wù)一次;式(6)表示車(chē)輛從倉(cāng)庫(kù)出發(fā)并且最后回到倉(cāng)庫(kù);式(7)表示車(chē)輛到達(dá)客戶(hù)j的時(shí)間的計(jì)算公式;式(8)表示時(shí)間約束。

三、求解帶時(shí)間窗的VRP問(wèn)題的多種群并行遺傳算法

由于標(biāo)準(zhǔn)遺傳算法具有容易過(guò)早收斂以及在進(jìn)化后期搜索效率較低的缺點(diǎn)，本文引入多種群并行遺傳算法。其基本思想是：用多個(gè)子種群代替單一種群，每個(gè)子種群按一定的進(jìn)化策略，遺傳算子并行進(jìn)化，用多個(gè)子種群代替原始種群在可行解空間進(jìn)行搜索。不同子種群各自獨(dú)立進(jìn)化，每進(jìn)化若干代（子種群獨(dú)立進(jìn)化的代數(shù)）就按照一定的遷移策略交換子種群中的個(gè)體。如此反復(fù)，直至找到最優(yōu)解。以下是算法的步驟:

1.初始化

(1)編碼

本文采用自然數(shù)編碼。在使用s輛車(chē)訪問(wèn)n個(gè)客戶(hù)的問(wèn)題中，將染色體設(shè)計(jì)成長(zhǎng)度為s+n-1的字符串，每個(gè)基因的取值范圍是[1，s+n-1]，即是用1，2，……，n表示客戶(hù)，用n+1，n+2，……，s+n-1來(lái)表示配送中心。

(2)產(chǎn)生初始群體

考慮到問(wèn)題的約束條件式(3），種群用隨機(jī)方法生成，首先隨機(jī)生成n個(gè)客戶(hù)的排列，然后對(duì)各車(chē)輛依次分配客戶(hù)，直到已分客戶(hù)的需求量之和剛好小于該車(chē)的載重容量為止。

(3)適應(yīng)度函數(shù)的確定

染色體在進(jìn)行交叉、變異后會(huì)出現(xiàn)一些不滿足問(wèn)題中車(chē)輛裝載容量約束的要求，因此對(duì)不滿足要求的給予一定的懲罰。令

k=1，2，……s

則第i個(gè)染色體的適應(yīng)度為fi=1/(Z+M)。

2.遺傳算子設(shè)計(jì)

本文采用隨機(jī)遍歷抽樣進(jìn)行選擇操作，而交叉和變異則采用了單點(diǎn)交叉和均勻多點(diǎn)變異。由于使用了代溝，子代的數(shù)量比當(dāng)前種群數(shù)量要小，因此要使用基于適應(yīng)度的重新插入。

3.種群的遷移

在各子種群進(jìn)行獨(dú)立的遺傳操作（適應(yīng)度計(jì)算、選擇、交叉、變異、重插入）一定的代數(shù)以后，選擇子種群中最適應(yīng)的一定數(shù)量的個(gè)體進(jìn)行遷移。最鄰近的子種群在它們之間交換個(gè)體，均勻地重插入移民個(gè)體。

四、實(shí)例計(jì)算與分析

某配送中心為8個(gè)客戶(hù)提供配送服務(wù)。這里，先根據(jù)各個(gè)客戶(hù)的貨物需求量，貨物對(duì)于客戶(hù)的重要性，客戶(hù)的業(yè)務(wù)需求拓展?jié)摿Φ热齻€(gè)因素（如表1所示）使用K-均值聚類(lèi)法進(jìn)行客戶(hù)分類(lèi)，通過(guò)SPSS12.0分析可得，客戶(hù)3和客戶(hù)6為第一類(lèi)客戶(hù)，客戶(hù)4、客戶(hù)7和客戶(hù)8 為第二類(lèi)客戶(hù)，其余為第三類(lèi)客戶(hù)。參考文獻(xiàn)的實(shí)例數(shù)據(jù)，確定服務(wù)時(shí)間和客戶(hù)規(guī)定的時(shí)間范圍，以及配送中心與各個(gè)客戶(hù)之間的距離。出車(chē)時(shí)間為早上6∶00，每輛車(chē)的平均行駛速度為60公里/小時(shí)，i到j(luò)的行駛時(shí)間可以由式tij=dij/60求出，假設(shè)各點(diǎn)之間的距離即為運(yùn)輸費(fèi)用。而完成該配送任務(wù)所需的車(chē)輛數(shù)s可由下式估計(jì)確定，α為裝車(chē)復(fù)雜性系數(shù)，取值為[0.5，1] 。每輛車(chē)的最大載重量為10噸。求，如何安排車(chē)輛的行駛路線，使得總運(yùn)行費(fèi)用最低。

注:用取值范圍在[0，1]之間的數(shù)表示貨物對(duì)于客戶(hù)的重要性和客戶(hù)的業(yè)務(wù)需求拓展?jié)摿?，取值越大表示程度越高?/p>

令裝車(chē)復(fù)雜性系數(shù)為α＝0.8，因此，所需車(chē)輛為3輛，則染色體為1～10的自然數(shù)的排列（其中9和10為虛擬的配送中心）。懲罰系數(shù)d=100，e=200。

根據(jù)問(wèn)題的特點(diǎn)，本文在利用多種群并行遺傳算法求解該問(wèn)題時(shí)，算法參數(shù)設(shè)定如下:群體規(guī)模m=20;個(gè)體基因串長(zhǎng)度為l=10;最大進(jìn)化代數(shù)gmax=100;子種群數(shù)為nsub=10，每隔20代相鄰的子種群中最適應(yīng)的20%的個(gè)體進(jìn)行交換；交叉概率pc=0.8；變異概率pm=0.03。

根據(jù)給出的例子，用Matlab編寫(xiě)程序來(lái)實(shí)現(xiàn)以上的遺傳算法，我們進(jìn)行了10次求解，計(jì)算結(jié)果如表2所示。10次費(fèi)用的平均值為157，其中第3次和第6次的計(jì)算結(jié)果最好，滿意解為6-7-4-9-1-5-3-10-8-2和1-5-3-9-6-7-4-10-2-8，費(fèi)用為153，對(duì)應(yīng)的車(chē)輛行駛路徑均為0-6-7-4-0，0-1-5-3-0，0-8-2-0。將其結(jié)果與標(biāo)準(zhǔn)遺傳算法做比較，可以發(fā)現(xiàn)多種群改進(jìn)遺傳算法可以得到較好的計(jì)算結(jié)果。

五、結(jié)束語(yǔ)

綜上所述，本文對(duì)傳統(tǒng)的帶時(shí)間窗約束的車(chē)輛配送路徑問(wèn)題進(jìn)行了改進(jìn)，建立了基于客戶(hù)分類(lèi)的帶時(shí)間窗約束的車(chē)輛配送路徑模型，該模型相對(duì)于傳統(tǒng)模型而言，可以更好地反映客戶(hù)之間的差別，并且提高了車(chē)輛配送的靈活性。另外根據(jù)該問(wèn)題的特點(diǎn)，我們應(yīng)用多種群并行遺傳算法進(jìn)行求解。計(jì)算結(jié)果表明，該算法相比較標(biāo)準(zhǔn)遺傳算法，搜索能力得到加強(qiáng)，收斂性也提高了，能夠得到更好的結(jié)果。

參考文獻(xiàn)：

[1]Dantzig G B，Ramser J H. The Truck Dispatching Problem[J].Management Science，1959，10(6):80-91.

[2]陳湘州楊勇王俊年:一種改進(jìn)的自然數(shù)編碼遺傳算法在非滿載時(shí)間窗車(chē)輛優(yōu)化調(diào)度問(wèn)題中的應(yīng)用[J].長(zhǎng)沙電力學(xué)院學(xué)報(bào)，2004，19(2):57

[3]王 薇吳敏等：基于多種群并行遺傳算法的原料庫(kù)存的優(yōu)化[J].控制工程，2003，10(1):33

[4]Eshelman L， Schaffer J D.Real-coded genetic algorithms and interval schemata[A].In Whitley L D (Ed.)， Foundations of Genetic Algorithms 2[C].Los Altos，CA，Morgan Kaufmann，1993，187-202.

[5]雷英杰張善文李續(xù)武等:MATLAB遺傳算法工具箱及應(yīng)用[M].西安電子科技大學(xué)出版社，2005

[6]宋松柏蔡煥杰康艷:約束優(yōu)化問(wèn)題的遺傳算法求解[J].西北農(nóng)林科技大學(xué)學(xué)報(bào)(自然科學(xué)版)，2005，33(1):152

[7]張文彤:SPSS統(tǒng)計(jì)分析高級(jí)教程[M].高等教育出版社，2004

[8]宋厚冰蔡遠(yuǎn)利:帶時(shí)間窗的車(chē)輛路徑混合遺傳算法[J].交通運(yùn)輸工程學(xué)報(bào)，2003，3(4):114

[9]宋偉剛張宏霞佟玲:有時(shí)間窗約束非滿載車(chē)輛調(diào)度問(wèn)題的遺傳算法[J].系統(tǒng)仿真學(xué)報(bào)，2005，17(10):2594

[10]Malmborg，Charles. Genetic Algorithm for Service Level Based Vehicle Scheduling[J].European Journal of Operational Research，1996，93(1)

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”