郭羽含，張美琪，周 楠

(遼寧工程技術(shù)大學(xué) 軟件學(xué)院，遼寧 葫蘆島 125105)

(*通信作者電子郵箱1515120191@qq.com)

基于偏好矩陣遺傳算法求解長期車輛合乘問題

郭羽含*，張美琪，周 楠

(遼寧工程技術(shù)大學(xué) 軟件學(xué)院，遼寧 葫蘆島 125105)

(*通信作者電子郵箱1515120191@qq.com)

針對長期車輛合乘問題(LTCPP)，提出帶有偏好矩陣的遺傳算法(PMGA)，將擁有私家車且目的地相同的用戶群體分配到產(chǎn)生總花費最少的合乘小組。首先，建立計算基于全體用戶費用成本的目標(biāo)函數(shù)，構(gòu)建以用戶時間窗和車容量為約束的長期車輛合乘模型；然后，結(jié)合模型特點，在傳統(tǒng)遺傳算法(GA)的基礎(chǔ)上，通過在交叉算子與變異算子中添加偏好矩陣記錄并更新用戶間的偏好信息來提高可行解的數(shù)量和質(zhì)量。實驗結(jié)果表明，在相同計算環(huán)境下，當(dāng)用戶數(shù)量小于200時，通過PMGA所獲得的20個解中的最優(yōu)解的值與最優(yōu)化算法相同；而處理大規(guī)模的實例時，PMGA可以獲得更高質(zhì)量的解。所提算法可以明顯提高長期車輛合乘問題的求解質(zhì)量，在降低汽車尾氣污染和減少交通擁擠等方面具有重要作用。

組合優(yōu)化；車輛調(diào)度問題；啟發(fā)式算法；遺傳算法；長期車輛合乘問題

0 引言

隨著社會經(jīng)濟(jì)持續(xù)快速發(fā)展，我國城市私家車保有量持續(xù)大幅增長。私家車的大量使用所引發(fā)的交通擁堵、環(huán)境污染等問題日益嚴(yán)重[1-3]，因此車輛合乘問題成為近年來研究的熱點。目前車輛合乘問題的研究多是單次車輛合乘問題，具有隨機性和臨時性。本文所提出的長期車輛合乘是為大中型企事業(yè)單位、政府機關(guān)設(shè)計的一種長期而固定的合乘方式，旨在減少職工上下班時駕駛的私家車道路行駛數(shù)量，進(jìn)而提高城市運輸效率，緩解城市交通壓力。

關(guān)于車輛合乘問題的研究，多數(shù)采用依據(jù)距離將客戶配對的方法，缺乏全局優(yōu)化[4]。較少研究提出了全局優(yōu)化的方法，如Yan等[5]提出了一種基于拉格朗日松弛的分組方法用于求解長期車輛合乘問題(Long-Term Car Pooling Problem， LTCPP)，采用網(wǎng)絡(luò)流技術(shù)，系統(tǒng)地開發(fā)了一個長期的多到多的汽車模型。拉格朗日松弛方法解決模型證實了實用性模型和啟發(fā)式算法在實踐中是可用的。Maniezzo等[6]提出了一種蟻群優(yōu)化(Ant Colony Optimization, ACO)算法和變鄰域搜索結(jié)合的復(fù)合算法，提出了以時間池和車容量為約束的車模型。Barrero等[7]提出了基于量子進(jìn)化算法的車輛共享模型，這種模型主要取決于電容量和車載荷量，與帶有時間窗和車容量的條件意義相同。王萬良等[8]在區(qū)域-區(qū)域匹配算法的基礎(chǔ)上提出了基于交通路網(wǎng)的合乘路徑匹配算法，對種群的大小有嚴(yán)格的控制，不能對現(xiàn)有的資源進(jìn)行最優(yōu)化的利用。張潛等[9]提出了基于聚類分析的多目標(biāo)車輛路徑優(yōu)化模型，通過控制開關(guān)計算算子解決種群的復(fù)雜性。遺傳算法(Genetic Algorithm, GA)作為一種被廣泛應(yīng)用的啟發(fā)式算法，常被用來解決帶有時間窗的車輛路徑問題[10-12]。但現(xiàn)有研究對于大規(guī)模算例均存在求解效率低和質(zhì)量差的問題，本文通過引入容量約束和時間窗約束構(gòu)建了長期車輛合乘模型，并提出一種基于偏好矩陣的遺傳算法。測試結(jié)果表明，該算法與傳統(tǒng)的遺傳算法和蟻群算法相比不僅可以提高合乘匹配的成功率，還能有效降低總體的花費成本。

1 問題的定義和描述

長期車輛合乘問題(LTCPP)假設(shè)每個合乘參與者都擁有自己的車輛，并且每個合乘參與者的上下班時間接近，其目標(biāo)是將具有相同目的地的用戶分為若干個合乘小組，每天輪流由組內(nèi)的一名成員駕車依次接載組內(nèi)其他成員共同前往工作地點，并在下班后將其依次送返。形成合乘小組后，每組的成員組合短期內(nèi)將不再改變。假設(shè)如圖1所示。

圖1 長期車輛合乘示意圖

1.1 目標(biāo)函數(shù)

LTCPP是一個多目標(biāo)函數(shù)問題，其目標(biāo)如下：

1)最大化車輛利用率，降低往返于公共目的地的車輛數(shù)量;

2)最小化所有用戶的行駛路徑之和。

為降低優(yōu)化難度，本文研究為單獨駕車的用戶引入懲罰值概念，將以上兩個目標(biāo)統(tǒng)一為求解全部出行者的總花費成本最低的單一目標(biāo)函數(shù)問題。因此，LTCPP可以被轉(zhuǎn)化為以下的整數(shù)規(guī)劃問題。

LTCPP可以利用有向圖G=(C∪{0},A)的方法來進(jìn)行建模，其中：C是所有用戶的集合；節(jié)點0代表其共同目的地即工作地點；集合A代表用戶之間的連通路徑，每條路徑對應(yīng)一個行駛費用cost(基于距離D)和一個行駛時間T。

設(shè)k為一組用戶的集合，|k|為該組用戶的數(shù)量，hp(i,k)為有向圖G的一條哈密頓路徑，從節(jié)點i∈k出發(fā)，通過所有節(jié)點j∈k﹨{i}，到達(dá)節(jié)點o結(jié)束。在∣k∣≤δi(δi為提供服務(wù)的組員的車容量)并滿足所有用戶的時間約束時，hp(i,k)是一條可行路徑，最短路徑min_path(i,k)即為i(i∈k)的最短可行的哈密頓路徑，則一個合乘小組的費用為各位組員作為司機時所產(chǎn)生的成本費用之和。設(shè)costi0為一名用戶直接獨自駕車去工作地點的花費，pi為一名用戶獨自駕車的懲罰值，因此未參加任何合乘小組的用戶會因懲罰而被增加額外的費用，調(diào)整懲罰值的大小可影響用戶參加合乘小組時最多需額外行駛的距離。只為獨自駕車的用戶設(shè)置懲罰值既可使更多用戶組成合乘小組，又不會鼓勵將一人以上但未滿員的小組合并從而使其行車成本相對合并前升高。合乘小組k的成本費用cost(k)可以被定義如下:

(1)

所有合乘小組的成本費用之和cost(σ)為：

(2)

本文利用這種方法同時優(yōu)化了上文提到的兩個目標(biāo)。

為了使更多用戶可以與其他用戶形成合乘小組，本文對該問題給出了懲罰值大于零的前提假設(shè)。懲罰值大于零時，只有一個用戶的合成小組花費會增加，計算花費成本最低的單一問題函數(shù)問題時，為使得費用減少，可能避免只有一名用戶的合成小組的情況。

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

本文問題數(shù)學(xué)模型中決策變量如下：

數(shù)學(xué)模型中常量如下：

目標(biāo)函數(shù)：

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

yik∈{0,1};i∈C,k∈K

(19)

ζi∈{0,1};i∈C

(20)

(21)

(22)

(23)

(24)

式(4)表示如果司機h經(jīng)過i點，則將用戶i加入到合乘小組K中；式(5)中的j同理；式(6)表示連續(xù)性約束；式(7)使得每個用戶或者被分入一個小組或者接受懲罰；式(8)、(9)分別代表載客量和最大行程時間約束；式(10)和(12)分別限定了用戶最早離家時間和最晚離家時間，其中M為一個極大常數(shù)；式(13)和(14)分別限定了最早到達(dá)工作地點時間和最晚到達(dá)工作地點時間；同樣式(11)～(17)是對于用戶從工作地點返回時的時間窗約束；約束條件(18)～(20)是二進(jìn)制的完整性約束，同時式(21)～(24)為非負(fù)約束。

2 基于偏好矩陣的遺傳算法

2.1 偏好矩陣遺傳算法

由于LTCPP的時間窗較嚴(yán)格，經(jīng)典遺傳算法的交叉和變異算子的隨機性會產(chǎn)生大量不可行解，因此算法需要花費大量時間進(jìn)行修復(fù)來獲得可行解。如果在每一代的遺傳操作中都可以產(chǎn)生更多的可行解，算法的計算效率將會有很大程度的提高。為了實現(xiàn)這一目標(biāo)，本文在傳統(tǒng)的遺傳算法基礎(chǔ)上引入了針對長期車輛合乘問題的偏好決策機制，形成一種基于偏好矩陣的遺傳算法(PreferenceMatrixbasedGeneticAlgorithm，PMGA)。

2.2 染色體編碼

根據(jù)LTCPP的特點，本文采用雙層編碼的方法。如圖2所示:第一層編碼中每個數(shù)字代表每名用戶的位置，d表示所有用戶的共同目的地;第二層編碼為一層中的用戶作為司機時接載其他組員的路線和其小組內(nèi)每名成員的出發(fā)時間。如第一個合乘小組中的用戶1的行駛路徑為1—4—6—7，出發(fā)時間為7:10,到達(dá)其他成員所在地點的時間分別為7:20、7:25和7:40。依此類推，一層中的每名用戶都有其所對應(yīng)的二層數(shù)據(jù)。

圖2 染色體編碼結(jié)構(gòu)

2.3 生成初始種群

為保證生成解的多樣性，本文采用隨機生成個體和結(jié)構(gòu)化個體的混合種群作為初始種群。

本文采用掃描法[13]生成結(jié)構(gòu)化個體，以任一用戶所在區(qū)位為起點，在時間窗與車容量及個體適應(yīng)度值fitnessn的約束下，按順時針方向?qū)ζ渌脩暨M(jìn)行掃描分組。

2.4 選擇

選擇的過程是隨機的，本文采用輪盤賭選擇法來獲得最優(yōu)解。在該方法中，每個個體的選擇概率與其適應(yīng)度值成比例，其中個體的適應(yīng)度值計算方法如下：

(25)

式(25)中的符號含義與式(3)相同。選擇出的優(yōu)化解通常是那些具有低費率和最低懲罰值的個體。

2.5 偏好矩陣

偏好矩陣(Preference Matrix, PM)為用于記錄用戶偏好信息的n×n矩陣，n為一個實例中用戶的數(shù)量，矩陣中的每一個值代表一名用戶愿意與另一名用戶分到同一組的偏好值。每當(dāng)有新的個體生成時，矩陣中的偏好信息就會被更新。

在遺傳操作開始之前，需要根據(jù)用戶之間的距離差和出發(fā)時間的時間差將偏好矩陣初始化，初始值initialij的計算如下：

initialij=α/dij+β/|ei+tij-ej|

(26)

其中:dij為位點i與位點j之間的距離；ei和ej為位于這兩點的用戶可接受的最晚離家時間；tij為位點i與位點j之間的駕駛時間；|ei+tij-ej|為用戶i到用戶j可接受的時間與實際從用戶i到用戶j的行駛時間的偏差；α和β是權(quán)衡這兩部分重要程度的權(quán)重因子。

在迭代過程中，當(dāng)有m個最優(yōu)個體被選中時，對于被選中的個體k所包含的合乘小組中用戶間的偏好值φk會通過因子ωij來增大。偏好值φk的計算如下：

(27)

2.6 偏好交叉算子

本文采用錦標(biāo)賽法作為雙親的選擇方案，隨機地選擇兩個父代個體通過兩點交叉法生成子代。在交叉操作過程中，每個父代的交配區(qū)域都是隨機選擇的。如圖3所示，生成的子代1分別由父代1和父代2的交配區(qū)域交叉組合而成，其中對于交叉位點1和交叉位點2兩個位點的選擇必須保證一個合乘小組的完整性。當(dāng)雙親中被選定的兩部分基因進(jìn)行重組時，剔除父代2的交配區(qū)域中與父代1中重復(fù)的基因值，然后根據(jù)偏好矩陣選擇雙親交配區(qū)域以外的用戶插入子代1中人數(shù)未滿的合乘小組，對于交配區(qū)域外的用戶i能夠插入合乘小組h的偏好值preferenceih的計算如下：

(28)

其中:wik是偏好矩陣中用戶i對用戶k的偏好值；K為合乘小組h中所有用戶的集合。

用戶i被插入合乘合乘小組h中的概率pih為：

(29)

其中N為人數(shù)未滿的合乘小組的集合。

子代2由父代另一部分基因區(qū)域交叉組合而成，然后與子代1作同樣處理。

圖3 交叉算子

2.7 偏好變異算子

在PMGA中給出了相似交換(SimilarClientExchange,S-CM)和重插入(ReinsertingCustomer,R-CM)兩種變異算子。

S-CM變異算子(如圖4)是隨機選取n個合乘小組并在其中隨機選擇m個用戶，根據(jù)用戶的偏好信息搜索相似的用戶，然后嘗試將其交換。即當(dāng)合乘小組h中的用戶i被選中時，其他合乘小組的用戶按照與合乘小組h的偏好值由大到小的順序排列，算子將選擇與i的偏好信息差異最小的用戶來與i進(jìn)行交換。

圖4 SC-M變異算子

R-CM變異算子(如圖5)重點研究對本組偏好值最小的用戶。算子隨機地選擇n個合乘小組并將對自己合乘小組偏好值最小的用戶在該組內(nèi)剔除，這樣，違反時間窗約束的用戶就會在進(jìn)行修復(fù)之前被移出合乘小組。然后算子根據(jù)偏好矩陣嘗試將這些用戶重新插入其他合乘小組。被剔除的用戶被插入其他任何一個合乘小組的概率值的計算方法如式(28)～(29)。新的合乘小組可以增加解的可行性。

2.8 PMGA算法描述和分析

PMGA算法偽代碼的設(shè)計如下。

輸入 交叉發(fā)生的概率Pc，變異發(fā)生的概率Pm，種群規(guī)模M，終止進(jìn)化的代數(shù)T，種群中個體優(yōu)勝劣汰的臨界值S。

輸出 適應(yīng)度值最大的個體Individual，適應(yīng)度值最大個體的總花費成本Cost。

begin： 初始化Pm、Pc、M、T等參數(shù)；由概率為p的隨機生成個體和掃描法生成概率為1-p的結(jié)構(gòu)化個體形成第一代初始種群Pop；do{ 初始化偏好矩陣； 計算種群Population中每一個體的適應(yīng)度F(i)； 初始化空種群newPopulation；do{if(random(0,1)

if(random(0,1)

{ 從n個合乘小組中選取m個用戶將具有相似偏好值的用戶相互交換； 在n個合乘小組中將每個合乘小組中具有最小偏好值的用戶刪除； 被刪除的用戶采用合乘小組概率值計算方法插入任何一個合乘小組； }

更新并修改偏好矩陣；

if(個體適應(yīng)度值超過S)

{ 將新個體加入種群newPopulation中； }

}until(M個子代被創(chuàng)建)

用newPopulation取代Population；

}until(超過運行時間，或繁殖代數(shù)超過T)

找出種群中適應(yīng)度值最大的個體Individual及相應(yīng)的總花費；

end

圖5 RC-M變異算子

PMGA采用隨機和結(jié)構(gòu)化的編碼方式保證了解的多樣性。在交叉和變異的過程中違反約束條件的用戶在修復(fù)之前就能被移出合乘小組，縮短了取得可行解的時間。編碼方式和采用S-CM、R-CM變異算子的變異操作增強了遺傳算法跳出局部收斂的能力，以便解決調(diào)節(jié)遺傳算法局部最優(yōu)與收斂速度的矛盾;同時，增強了PMGA的健壯性。

3 仿真結(jié)果與分析

本文使用的24個測試實例是在硬時間窗車輛路徑問題(Vehicle Routing Problem, VRP)實例的基礎(chǔ)上修改獲得的。實例中的用戶分別采用三種分布方式：隨機分布、群集分布以及隨機和群集混合分布，分別用S-R、S-C、S-RC來表示。

3.1 測試環(huán)境

軟件環(huán)境 Java虛擬機SUN JDK1.8.0_91。

硬件環(huán)境 Windows 2008系統(tǒng)64 bit，Intel Core2雙核處理器3.2 GHz CPU，4 GB RAM。

3.2 參數(shù)配置

算法相關(guān)參數(shù)設(shè)置和仿真配置如下：種群規(guī)模為100；運行總時間為180 s；初始種群為80%結(jié)構(gòu)化個體，20%隨機生成個體；交叉率和變異率分別為Pc=0.8,Pm=0.1；初始偏好矩陣參數(shù)為α=0.7,β=0.3，M=10 000。對更新后的偏好矩陣，選出具有最高適應(yīng)度的個體的數(shù)量為5，ωij=0.9,θ=n/300(n<300),θ=1(n≥300)，其中n為當(dāng)前種群的代數(shù)；SC-M變異算子選取的用戶數(shù)量m為全部用戶的5%，RC-M變異算子選取的合乘小組數(shù)量n為全部合乘小組的10%，懲罰值為pi=0.5×ci0。

鑒于有限的計算資源和組合的復(fù)雜性，本文首先依據(jù)經(jīng)驗設(shè)定多組參數(shù)值，然后選出多組值中平均輸出結(jié)果最好的一組作為最終實驗參數(shù)。運行總時間代表每個算法允許執(zhí)行的時間，由于不同算法生成新解的方式和每次迭代生成新解的數(shù)量不同，故使用迭代數(shù)或總生成新解數(shù)量作為終止條件無法保證比較的公平性，而以運行時間作為終止條件可以更公平地比較不同算法的求解效率和求解質(zhì)量。

3.3 測試結(jié)果

本文通過對每個合乘小組中不同用戶進(jìn)行排列組合，最終篩選出小組內(nèi)每名成員作為司機時的最短行駛路徑，進(jìn)而獲得每個合乘小組的最短路徑。由于篇幅原因，只列出用于計算機仿真實驗的群集分布的100名用戶的分組結(jié)果(如圖6所示)及其中6個合乘小組行駛路徑。

第1天 19- 37- 10- 20；14- 99- 100- 16；45- 46- 42- 69；98- 73- 70- 61；72- 71- 67- 56；59- 55- 54- 24；

第2天 37- 20- 10- 19；99- 16- 100- 14；42- 46- 45- 69；61- 98- 73- 70；71- 56- 72- 67；54- 24- 55- 59；

第3天 20- 10- 19- 37；100- 99- 14- 16；46- 45- 69- 42；73- 61- 98- 70；56- 67- 72- 71；24- 55- 54- 59；

第4天 10- 37- 20- 19；16- 99- 100- 14；69- 46- 42- 45；70- 73- 61- 98；67- 72- 71- 56；55- 59- 54- 24。

GA、ACO與PMGA在解決LTCPP時所獲得的解的質(zhì)量的比較如表1所示，其中Solutionavg為通過20次運行所獲得的20個最優(yōu)解的平均值，Solutionmax和Solutionmin分別為所獲得解中的最大值和最小值。PMGA與GA、ACO算法相比，解的質(zhì)量更高。

圖6 群集分布種群合乘小組仿真

表1GA、ACO和PMGA成本計算結(jié)果

Tab.1CostcalculationresultsofGA,ACOandPMGA

實例用戶數(shù)量GASolutionavgSolutionmaxSolutionminACOSolutionavgSolutionmaxSolutionminPMGASolutionavgSolutionmaxSolutionmin比GA改進(jìn)比例/%比ACO改進(jìn)比例/%S?C111003872．644234．343534．533647．614012．323534．533638．583764．373534．536．040．25S?R111006164．376729．425432．125585．935834．085432．125521．515738．475432．1210．431．15S?RC111006632．517537．456182．146331．976866．886149．916246．376354．396149．915．821．35S?C212007247．447749．486838．346902．917125．016337．346385．456647．366337．2111．857．50S?R2120012087．8213546．8711421．8710751．3811807．2210355．3610532．5111074．2510311．6512．902．04S?RC2120013898．0414498．3212587．7613684．2414168．9312552．2112623．6813275．4712552．219．177．75S?R4140013384．8115563．5712575．3812997．1213531．7712326．7412318．8812856．6112021．897．965．22S?C4140020583．1121475．4919374．5718865．4819285．4617892．2118063．8418844．4317618．2312．204．25S?RC4140020849．4821465．2718485．5818798．5619646．5617946．2917747．5218472．5217592．2114．905．59

從表1中可以看出，在相同的計算環(huán)境下，對于中等規(guī)模的實例如：S-C11、S-R11、S-RC11，PMGA與自適應(yīng)控制優(yōu)化[6]的計算結(jié)果相近；但是在處理大規(guī)模的實例如：S-C41、S-R41、S-RC41時，PMGA所獲得的解的質(zhì)量有了顯著地提高。同時在表中還可以看到，在任何情況下PMGA所獲得的解的質(zhì)量都優(yōu)于標(biāo)準(zhǔn)的遺傳算法。通過對實驗結(jié)果中平均值的比較，可以得出由PMGA所獲得的實驗結(jié)果與最優(yōu)化算法的運算結(jié)果更接近，同時在用戶數(shù)量小于200時，通過PMGA所獲得的20個解中的最優(yōu)解的值與最優(yōu)化算法相同，而且在處理大規(guī)模的實例時，PMGA可以獲得更高質(zhì)量。

4 結(jié)語

本文提出的PMGA與傳統(tǒng)遺傳算法相比，獲得的解的質(zhì)量有了顯著的提高，尤其是在處理大規(guī)模的實例時，可以通過PMGA獲得更高質(zhì)量的解。所以，通過實驗可以得出，PMGA能夠更加有效地解決LTCPP。未來的研究將會結(jié)合實際來對這一算法作更深入的評估，并進(jìn)一步探索求解長期車輛合乘問題的其他算法。

)

[1]MORRISBT,TRANC,SCORAG,etal.Real-timevideo-basedtrafficmeasurementandvisualizationsystemforenergy/emissions[J].IEEETransactionsonIntelligentTransportationSystems, 2012, 13(4): 1667-1678.

[2]TERROSO-SAENZF,VALDES-VELAM,SOTOMAYOR-MAR-TINEZC,etal.AcooperativeapproachtotrafficcongestiondetectionwithcomplexeventprocessingandVANET[J].IEEETransactionsonIntelligentTransportationSystems,2012,13(2):914-929.

[3] 曹忠于.車輛合乘研究[D].上海：華東師范大學(xué),2006:178-190.(CAOZY.Researchonvehicleride[D].Shanghai:EastChinaNormalUniversity, 2006: 178-190.)

[4]BOUKHATERCM,DAKROUBO,LAHOUDF,etal.AnintelligentandfairGAcarpoolingschedulerasasocialsolutionforgreenertransportation[C]//MELECON2014:Proceedingsofthe17thIEEEMediterraneanElectrotechnicalConference.Piscataway,NJ:IEEE, 2014: 182-186.

[5]YANS,CHENC,LINY.Amodelwithaheuristicalgorithmforsolvingthelong-termmany-to-manycarpoolingproblem[J].IEEETransactionsonIntelligentTransportationSystems, 2011, 12(4): 1362-1373.

[6]MANIEZZOV,CARBONAROA,HILDMANNH.AnANTSheuristicforthelong-termcarpoolingproblem[M]//StudiesinFuzzinessandSoftComputing,Volume141oftheSeriesStudiesinFuzzinessandSoftComputing.Berlin:Springer, 2004: 411-430.

[7]BARREROR,VANMIERLOJ,TACKOENX.Energysavingsinpublictransport[J].IEEEVehicularTechnologyMagazine, 2008, 3(3): 26-36.

[8] 王萬良,黃海鵬,趙燕偉,等.基于車輛共享的軟時間窗動態(tài)需求車輛路徑問題[J].計算機集成制造系統(tǒng),2011,17(5):1056-1063.(WANGWL,HUANGHP,ZHAOYW,etal.DynamiccustomerdemandVRPwithsofttimewindowsbasedonvehiclesharing[J].ComputerIntegratedManufacturingSystems, 2011, 17(5): 1056-1063.)

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

[10] 雷英杰.MATLAB遺傳算法工具箱及應(yīng)用[M].西安:西安電子科技大學(xué)出版社,2014:1-10.(LEIYJ.MATLABGeneticAlgorithmToolboxandApplication[M].Xi’an:XidianUniversityPress, 2014: 1-10.)

[11]HUANGSC,JIAUMK,LINCH.Agenetic-algorithm-basedapproachtosolvecarpoolserviceproblemsincloudcomputing[J].IEEETransactionsonIntelligentTransportationSystems, 2015, 16(1): 352-364.

[12]JIAUMK,HUANGSC.Services-orientedcomputingusingthecompactgeneticalgorithmforsolvingthecarpoolservicesproblem[J].IEEETransactionsonIntelligentTransportationSystems, 2015, 16(5): 2711-2722.

[13]GILLETTB,MILLERL.Aheuristicalgorithmforthevehicledispatchproblem[J].OperationsResearch,1974,22(2):340-349.

ThisworkissupportedbytheNaturalScienceFoundationofLiaoningProvince(2015020095).

GUO Yuhan, born in 1983, Ph.D., associate professor.His research interests include intelligent search algorithm, vehicle scheduling problem, supply chain optimization problem.

ZHANG Meiqi, born in 1991, M.S.candidate.Her research interests include supply chain optimization problem.

ZHOU Nan, born in 1994.Her research interests include vehicle scheduling problem.

Genetic algorithm with preference matrix for solving long-term carpooling problem

GUO Yuhan*, ZHANG Meiqi, ZHOU Nan

(SchoolofSoftware,LiaoningTechnicalUniversity,HuludaoLiaoning125105,China)

A Preference Matrix based Genetic Algorithm (PMGA) was introduced for solving the Long-Term Car Pooling Problem (LTCPP), and a group of users with both vehicle and the same destination was assigned to the co-generation group to minimize the total travel cost.First, the objective function of calculating the cost of all users was set up, and a long-term car pooling model with constraints of user time window and car capacity was designed.Then based on the characteristics of the model and classic Genetic Algorithm (GA), a preference matrix mechanism was adapted into the crossover and mutation operators to memorize and update the preference information among different users, thus improving the quantity and the quality of feasible solutions.The experimental results show that in the same computing environment, the optimal solution value of 20 solutions obtained by PMGA is the same as that of the exact algorithm when the number of users is less than 200.Moreover, PMGA is remarkable in solution quality when dealing with large size of instances.The proposed algorithm can significantly improve the solution quality of the long-term car pooling problem, and play an important role in reducing vehicle emission and traffic congestion.

combinational optimization; vehicle scheduling problem; heuristics algorithm; Genetic Algorithm (GA); Long-Term Car Pooling Problem (LTCPP)

2016- 08- 24;

2016- 09- 17。 基金項目:遼寧省自然科學(xué)基金資助項目(2015020095)。

郭羽含(1983—)，男，黑龍江哈爾濱人，副教授，博士，主要研究方向：智能搜索算法、車輛調(diào)度問題、供應(yīng)鏈優(yōu)化問題； 張美琪(1991—)，女，遼寧阜新人，碩士研究生，主要研究方向：供應(yīng)鏈優(yōu)化問題； 周楠(1992—)，女，遼寧朝陽人，主要研究方向：車輛調(diào)度問題。

1001- 9081(2017)02- 0602- 06

10.11772/j.issn.1001- 9081.2017.02.0602

TP399;TP

A