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

郭羽含，張美琪，周 楠

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

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

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

郭羽含*，張美琪，周 楠

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

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

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

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

0 引言

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

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

1 問題的定義和描述

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

圖1 長(zhǎng)期車輛合乘示意圖

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

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

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

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

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

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

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

(1)

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

(2)

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

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

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

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

2.1 偏好矩陣遺傳算法

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

2.2 染色體編碼

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

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

2.3 生成初始種群

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

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

2.4 選擇

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

(25)

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

2.5 偏好矩陣

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

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

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

(26)

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

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

(27)

2.6 偏好交叉算子

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

(28)

其中:wik是偏好矩陣中用戶i對(duì)用戶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)是隨機(jī)選取n個(gè)合乘小組并在其中隨機(jī)選擇m個(gè)用戶，根據(jù)用戶的偏好信息搜索相似的用戶，然后嘗試將其交換。即當(dāng)合乘小組h中的用戶i被選中時(shí)，其他合乘小組的用戶按照與合乘小組h的偏好值由大到小的順序排列，算子將選擇與i的偏好信息差異最小的用戶來與i進(jìn)行交換。

圖4 SC-M變異算子

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

2.8 PMGA算法描述和分析

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

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

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

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

if(random(0,1)

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

更新并修改偏好矩陣；

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

{ 將新個(gè)體加入種群newPopulation中； }

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

用newPopulation取代Population；

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

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

end

圖5 RC-M變異算子

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

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

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

3.1 測(cè)試環(huán)境

軟件環(huán)境 Java虛擬機(jī)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；運(yùn)行總時(shí)間為180 s；初始種群為80%結(jié)構(gòu)化個(gè)體，20%隨機(jī)生成個(gè)體；交叉率和變異率分別為Pc=0.8,Pm=0.1；初始偏好矩陣參數(shù)為α=0.7,β=0.3，M=10 000。對(duì)更新后的偏好矩陣，選出具有最高適應(yīng)度的個(gè)體的數(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。

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

3.3 測(cè)試結(jié)果

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

第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時(shí)所獲得的解的質(zhì)量的比較如表1所示，其中Solutionavg為通過20次運(yùn)行所獲得的20個(gè)最優(yōu)解的平均值，Solutionmax和Solutionmin分別為所獲得解中的最大值和最小值。PMGA與GA、ACO算法相比，解的質(zhì)量更高。

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

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

Tab.1CostcalculationresultsofGA,ACOandPMGA

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

4 結(jié)語

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

)

[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] 王萬良,黃海鵬,趙燕偉,等.基于車輛共享的軟時(shí)間窗動(dòng)態(tài)需求車輛路徑問題[J].計(jì)算機(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。 基金項(xiàng)目:遼寧省自然科學(xué)基金資助項(xiàng)目(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