基于遺傳算法的動(dòng)態(tài)出租車(chē)合乘模型研究

程 杰 唐智慧 劉 杰 鐘 流

（西南交通大學(xué)交通運(yùn)輸與物流學(xué)院1） 成都 610031） （重慶公共運(yùn)輸職業(yè)學(xué)院軌道交通工程系2） 重慶 402247）

0 引 言

隨著我國(guó)國(guó)民經(jīng)濟(jì)的高速發(fā)展和城市化進(jìn)程的加快，機(jī)動(dòng)車(chē)保有量持續(xù)增加，交通需求迅猛增長(zhǎng)，交通擁堵日益嚴(yán)重.出租車(chē)作為城市交通的有機(jī)組成部分，由于價(jià)格偏高等原因，在非高峰時(shí)期經(jīng)常處于空載狀態(tài)；在高峰期又常因?yàn)榇罅砍鲎廛?chē)只載一位乘客而出現(xiàn)打車(chē)難的問(wèn)題，因此推廣有效的出租車(chē)合乘模式，可以提高出租車(chē)的運(yùn)輸效率，降低出租車(chē)空載率，協(xié)助城市公交緩解城市交通壓力.

出租車(chē)合乘問(wèn)題與DARP問(wèn)題同屬于乘客交通工具配對(duì)問(wèn)題，在以往的DARP問(wèn)題中，Teodorovic等［1－2］對(duì)動(dòng)態(tài) DARP問(wèn)題和靜態(tài) DARP問(wèn)題進(jìn)行了區(qū)分，他們指出動(dòng)態(tài)DARP問(wèn)題是出現(xiàn)在路網(wǎng)中每個(gè)結(jié)點(diǎn)上的需求的時(shí)間和位置是隨時(shí)間動(dòng)態(tài)變化的，而靜態(tài)DARP問(wèn)題的需求是固定不變的.Coslovich 等［3－5］求 解 了 帶 時(shí) 間窗的動(dòng)態(tài)DARP問(wèn)題.出租車(chē)合乘問(wèn)題作為一個(gè)NP問(wèn)題吸引了大量國(guó)內(nèi)外學(xué)者的研究，Tao Chichung等［6］用貪婪算法對(duì)出租車(chē)合乘一對(duì)多模式和多對(duì)一模式進(jìn)行了求解.Yan Shangyao等［7］將具有相同需求的乘客視作一個(gè)乘客組，然后出于安全與舒適的考慮，把出租車(chē)合乘問(wèn)題中的乘客和出租車(chē)進(jìn)行了分類(lèi)，并借助時(shí)空網(wǎng)絡(luò)圖對(duì)問(wèn)題予以描述.覃運(yùn)梅等［8］采用固定費(fèi)率對(duì)靜態(tài)出租車(chē)合乘問(wèn)題進(jìn)行了求解.

本文重點(diǎn)研究不同類(lèi)型出租車(chē)和不同類(lèi)型乘客組的多對(duì)多模式的動(dòng)態(tài)出租車(chē)合乘問(wèn)題.綜合考慮出行者與駕駛員的利益，對(duì)時(shí)間窗約束引入?yún)f(xié)調(diào)機(jī)制，建立了動(dòng)態(tài)出租車(chē)合乘模型，并且針對(duì)模型特點(diǎn)采用了遺傳算法進(jìn)行求解.

1 問(wèn)題描述

出租車(chē)動(dòng)態(tài)合乘問(wèn)題是乘客和出租車(chē)的匹配問(wèn)題.在一固定時(shí)間（一般指系統(tǒng)刷新時(shí)間間隔）內(nèi)，新的乘客組出現(xiàn)在不同的乘車(chē)點(diǎn)的情況是隨機(jī)的且出租車(chē)的位置是隨時(shí)間動(dòng)態(tài)變化的.每一個(gè)乘客組屬性包括：乘客組數(shù)量、起始點(diǎn)位置、出發(fā)和旅行時(shí)間窗約束以及乘客組類(lèi)別.根據(jù)這些屬性對(duì)該區(qū)域網(wǎng)絡(luò)內(nèi)一定數(shù)量出租車(chē)合理指派，組織乘客組間的合乘，利用優(yōu)化模型確定每輛出租車(chē)合乘路徑及所載各乘客組的乘車(chē)費(fèi)率.動(dòng)態(tài)出租車(chē)合乘問(wèn)題的關(guān)鍵在于根據(jù)當(dāng)前區(qū)域網(wǎng)絡(luò)中乘客組和出租車(chē)狀態(tài)，實(shí)時(shí)優(yōu)化安排合乘方案.整個(gè)合乘過(guò)程用時(shí)空網(wǎng)絡(luò)圖描述見(jiàn)圖1.

圖1 動(dòng)態(tài)出租車(chē)合乘的時(shí)空網(wǎng)絡(luò)圖

2 模型的建立

2.1 模型假設(shè)

在確定最優(yōu)合乘方案時(shí)，當(dāng)前網(wǎng)絡(luò)的擁堵?tīng)顩r會(huì)對(duì)合乘方案產(chǎn)生影響，但這會(huì)使問(wèn)題研究的復(fù)雜度增加，因此本文對(duì)問(wèn)題給出如下前提假設(shè)：（1）所有乘客組時(shí)間窗約束均為軟約束；（2）由于乘客組起訖點(diǎn)位置的隨機(jī)性，允許車(chē)輛的逆向行駛；（3）不考慮網(wǎng)絡(luò)的路徑阻抗影響，每輛出租車(chē)的行駛相互獨(dú)立；（4）所有乘客組的乘車(chē)需求都必須全部滿(mǎn)足；（5）乘客組在合乘過(guò)程中不允許換乘；（6）不考慮出租車(chē)的燃料成本.

2.2 變量說(shuō)明

K為所有車(chē)輛集合；H為網(wǎng)絡(luò)節(jié)點(diǎn)集合；T為刷新時(shí)間；Pm為第m次刷新時(shí)刻所有車(chē)輛位置集合為第m次刷新時(shí)刻已經(jīng)上車(chē)的乘客組集合為第m次刷新時(shí)刻沒(méi)有上車(chē)的乘客組集合；Gm為第m次刷新時(shí)刻所有需求點(diǎn)乘客組狀態(tài)集合為第K輛車(chē)經(jīng)過(guò)的路徑；為第g組乘客非合乘狀態(tài)下從u到v所需的費(fèi)用；FSm為在m次刷新時(shí)間所有車(chē)輛種類(lèi)集合fsm∈FSm；PSm為在m次刷新時(shí)間所有乘客組種類(lèi)集合psm∈PSm為車(chē)輛從i到j(luò)的運(yùn)行時(shí)間；qg為第g組乘客的數(shù)量為uv之間最短距離為第g組乘客希望從u點(diǎn)出發(fā)的時(shí)間為第g組乘客希望到達(dá)v的時(shí)間為第k輛車(chē)抵達(dá)u的時(shí)間為第k輛車(chē)從u到v實(shí)際運(yùn)行時(shí)間為u點(diǎn)上車(chē)v點(diǎn)下車(chē)的第g組乘客的合乘費(fèi)率；r0出租車(chē)單位距離價(jià)格；C0為出租車(chē)起步價(jià)；L0為出租車(chē)起步距離為第k輛車(chē)從u出發(fā)時(shí)的載客量；C為出租車(chē)的最大容量；為u點(diǎn)上下車(chē)的乘客人數(shù)凈差.

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

2.4 決策變量

路徑變量.設(shè)為路徑變量，為1時(shí)，表示第k輛車(chē)經(jīng)過(guò)邊（i－j）；為0時(shí)，表示不經(jīng)過(guò).費(fèi)用變量.設(shè)為費(fèi)用決策變量，表示u點(diǎn)上車(chē)v點(diǎn)下車(chē)第g組乘客的合成費(fèi)率.

2.5 目標(biāo)函數(shù)和約束條件

目標(biāo)函數(shù)第一部分為出行成本，第二部分為乘客費(fèi)用.約束條件約束條件（2），（3），（7），（8）分別為司機(jī)收益、費(fèi)率、出租車(chē)容量和決策變量約束，文獻(xiàn)［9］已經(jīng)對(duì)目標(biāo)函數(shù)（1）和約束條件（2），（3），（7），（8）做了詳細(xì)說(shuō)明，本文不重復(fù)介紹.在動(dòng)態(tài)合乘的過(guò)程中，乘客組分為兩類(lèi)集合：一類(lèi)是已經(jīng)上車(chē)的乘客組；另一類(lèi)則是沒(méi)有上車(chē)的乘客組.在刷新時(shí)間間隔內(nèi)，車(chē)輛按照前一次的合乘方案路徑行駛，在此期間有的乘客組已經(jīng)上車(chē)處于前往目的地的途中，有的乘客組還未上車(chē)，同時(shí)也有新的乘客組需求產(chǎn)生.約束（4），（5）分別表示車(chē)輛外乘客組的運(yùn)行和出發(fā)時(shí)間窗約束.因?yàn)樵谲?chē)內(nèi)但未到達(dá)目的地的乘客組會(huì)對(duì)模型下次刷新時(shí)間點(diǎn)上求解的車(chē)輛路徑結(jié)果產(chǎn)生影響，如果不考慮車(chē)輛內(nèi)乘客組的限制，則可能導(dǎo)致車(chē)輛內(nèi)乘客組無(wú)法在運(yùn)行時(shí)間窗內(nèi)到達(dá)目的地，所以隨著車(chē)輛的運(yùn)動(dòng)，約束條件（6）表示車(chē)輛內(nèi)乘客組運(yùn)行時(shí)間窗約束的變化.約束（9）表示出租車(chē)和乘客組種類(lèi)匹配，本文將出租車(chē)分為：1，一般型；2，只搭乘女性乘客型.乘客組按其人員構(gòu)成分為4類(lèi)：（1）全為男性；（2）全為女性但無(wú)性別要求；（3）全為女性但有性別要求；（4）男女混合.出租車(chē)種類(lèi)為1時(shí)，只能與乘客組種類(lèi)中1，2，4匹配，不能和種類(lèi)3匹配.出租車(chē)種類(lèi)為2時(shí)，只能與乘客組種類(lèi)中2，3匹配，不能和種類(lèi)1，4匹配.

3 模型求解算法

由于出租車(chē)合乘問(wèn)題是一個(gè)NP問(wèn)題，采用啟發(fā)式算法容易編程求解.本文采用遺傳算法求解該模型.本文所有乘客組時(shí)間窗約束均為軟約束，即在無(wú)法滿(mǎn)足該時(shí)間窗約束導(dǎo)致模型沒(méi)有可行解時(shí)，乘客組接受協(xié)調(diào)機(jī)制，將其出發(fā)或達(dá)到時(shí)間窗約束適當(dāng)增大［10］.除此之外，種類(lèi)約束也接受協(xié)調(diào)機(jī)制.

3.1 變量編碼

染色體采用實(shí)數(shù)編碼的方式，染色體分為3部分，第一部分表示路徑變量，第二部分為乘客組變量，第三部分為費(fèi)率變量.除了第三部分外，其余都會(huì)用0將不同車(chē)輛的路徑和乘客組隔開(kāi)且乘客組的排列是按其搭乘車(chē)輛的順序進(jìn)行排序的.這樣就可以直接從染色體中看出乘客組搭乘、費(fèi)率及車(chē)輛合乘路徑情況.例如染色體0 1 2 3 0 6 7 8 9 0 1 4 5 0 7 0 0.2 0.5 0.3 0.1表示第一輛車(chē)載有編號(hào)分別為1，4，5的乘客組，其合乘行駛路徑為1―2―3，乘客組費(fèi)率分別為0.2，0.5，0.3.第二輛車(chē)載有編號(hào)為7的乘客組，其行駛路徑為6―7―8―9，乘客組7的費(fèi)率為0.1.

3.2 適應(yīng)度函數(shù)和選擇算子

因?yàn)槟Ｐ湍繕?biāo)函數(shù)是求最小值，因此將染色體目標(biāo)函數(shù)的倒數(shù)作為其適應(yīng)度函數(shù).模型帶有約束條件，本文采用懲罰函數(shù)法對(duì)模型約束條件進(jìn)行處理，將懲罰函數(shù)加在適應(yīng)度函數(shù)上，如果某一染色體解滿(mǎn)足約束條件，則它解碼適應(yīng)度函數(shù)會(huì)很小，從而在選擇時(shí)被選中概率會(huì)小，遺傳到下一代可能性變小.將種群中適應(yīng)度值排名前1／4的染色體復(fù)制1次，中間2／4的染色體復(fù)制一次，拋棄最后1／4的染色體作為選擇操作.

3.3 交叉算子

由于乘客組與費(fèi)率問(wèn)題的條件約束，如果仍使用簡(jiǎn)單交叉算子，將有可能產(chǎn)生大量的不可行解.因此本文對(duì)乘客組和費(fèi)率分別進(jìn)行交叉操作.采用文獻(xiàn)［11］的交叉算子對(duì)乘客組部分進(jìn)行交叉操作.對(duì)費(fèi)率部分采用算術(shù)交叉.

3.4 變異算子

本文變異的策略是隨機(jī)交換乘客組部分中2個(gè)等位基因，其乘客組對(duì)應(yīng)的費(fèi)率也相應(yīng)的進(jìn)行交換，根據(jù)文獻(xiàn)［11］對(duì)變異后染色存在連續(xù)0的情況進(jìn)行處理.整個(gè)動(dòng)態(tài)出租車(chē)合乘流程圖見(jiàn)圖2.

圖2 動(dòng)態(tài)出租車(chē)合乘流程圖

4 算例分析

算例路網(wǎng)如圖3所示.設(shè)定現(xiàn)在網(wǎng)絡(luò)中存在著30個(gè)出行需求點(diǎn)對(duì)，節(jié)點(diǎn)代表出租搭乘點(diǎn)，邊的權(quán)值表示行駛距離，單位：km.路網(wǎng)中有5輛出租車(chē)，初始位置分別為節(jié)點(diǎn)7，2，25，10，30.根據(jù)成都市當(dāng)前出租車(chē)的價(jià)格，本文規(guī)定出租車(chē)的起步價(jià)為8元，起步距離為2km，起步距離之后是1.9元／km，出租車(chē)運(yùn)行速度為40km／h，每輛出租車(chē)最多載4位乘客.設(shè)置初始交叉概率為0.8，變異概率為0.1.

圖3 算例網(wǎng)絡(luò)

由于篇幅原因，本文只進(jìn)行兩次刷新計(jì)算，刷新時(shí)間間隔為1 000s，即調(diào)用模型2次.2次刷新時(shí)刻的乘客組信息分別見(jiàn)表1、表2.

表1 第1次刷新時(shí)刻乘客組信息

表2 第2次刷新時(shí)刻乘客組信息

利用Matlab編程計(jì)算，模型收斂性見(jiàn)圖4.因?yàn)槌跏汲丝徒M信息是隨機(jī)給定，因此可能導(dǎo)致無(wú)可行解，本文引入?yún)f(xié)調(diào)機(jī)制，使得協(xié)調(diào)各乘客組的乘客組屬性后，適應(yīng)度函數(shù)值會(huì)增大，但這樣可以得模型的可行解，最終得到較滿(mǎn)意解.計(jì)算得到每輛出租車(chē)的行駛路徑如下：出租車(chē)1：7─13─12─11─10─9─1；出租車(chē)2：19─11─12─14─22─24─17；出租車(chē)3：25─19─11─12─9─13─7─6─8─4─5；出租車(chē)4：10─2─1─6─7─14─21─22─30─29；出租車(chē)5：30─28─24─16─8─4.

圖4 算法的收斂性

每個(gè)乘客組合乘與非合乘所交納的費(fèi)用見(jiàn)表3.從表中不難看出，合乘費(fèi)用比非合乘費(fèi)用少.另一方面，司機(jī)的收益也是本文研究的重點(diǎn)，在行駛同樣距離的情況下，合乘時(shí)的司機(jī)收益比非合乘時(shí)大，5輛出租車(chē)在2次刷新時(shí)間的平均空載率分別為0.14，0.41，0.18，0.36，0，其中只有一輛出租車(chē)的空載率大于國(guó)內(nèi)出租車(chē)平均空載率0.40即該輛出租車(chē)?yán)眯瘦^低［12］.

表3 合乘前后費(fèi)用與距離對(duì)比

表4 合乘前后司機(jī)收益與平均空載率

5 結(jié) 論

研究了動(dòng)態(tài)出租車(chē)合乘問(wèn)題，考慮了在乘客組、出租車(chē)分類(lèi)型情況下，引入?yún)f(xié)調(diào)機(jī)制，建立了多對(duì)多模式的動(dòng)態(tài)出租車(chē)合乘模型，并且在一個(gè)小型網(wǎng)絡(luò)上進(jìn)行了仿真測(cè)試，結(jié)果表明：出租車(chē)合乘減少了乘客費(fèi)用，增加了司機(jī)的收益，同時(shí)空載率下降.尚未考慮出租車(chē)在合乘狀態(tài)下的燃油成本和其他成本，這些還有待進(jìn)一步研究.

［1］TEODOROVIC D，RADIVOJEVIC G.Fuzzy logic approach to dynamic dial－a－ride problem［J］.Fuzzy Sets and Systems，2000，116（2）：23－33.

［2］COLORNI A，RIGHINI G.Modeling and optimizing dynamic dial－a－ride problems ［J］.International Transactions in Operational Research，2001，8（3）：155－166.

［3］COSLOVICH L，PESENTI R，UKOVICH W.A twophase insertion technique of unexpected customers for a dynamic dial－a－ride problem ［J］.European Journal of Operational Research，2006，175（2）：1605－1615.

［4］DIANA M，DESSOUKY M.A new regret insertion heuristic for solving large－scale dial－a－ride problems with time windows［J］.Transportation Research Part B，2004，38（4）：539－557.

［5］FU L.Scheduling dial－a－ride paratransit under timevarying stochastic congestion［J］.Transportation Research PartB，2002 36（2）：485－506.

［6］TAO Chichung，CHEN Chunying.Dynamic rideshare matching algorithms for the taxipooling service based on intelligent transportation system technologies［C］／／2007International Conference on Management Science and Engineering，Harbin，China，2007：399－404.

［7］YAN Shangyao，CHEN Chunying，WU Chuanche.Solution methods for the taxi pooling problem［J］.Transportation，2011，39（3）：723－748.

［8］覃運(yùn)梅，石 琴.出租車(chē)合乘模式的探討［J］.合肥工業(yè)大學(xué)學(xué)報(bào)，2006，29（1）：77－79.

［9］周和平，鐘璧檣.出租車(chē)合乘路徑選擇與費(fèi)率優(yōu)化模型［J］.長(zhǎng)沙理工大學(xué)學(xué)報(bào)，2011，8（1）：20－25.

［10］JORGENSEN R M，LARSEN J，BERGVINSDOTTIR K B.Solving the dial－a－ride problem using genetic algorithms［J］.Journal of the Operational Research Society，2007，58（4）：1321－1331.

［11］唐 坤.車(chē)輛路徑問(wèn)題中的遺傳算法設(shè)計(jì)［J］.東華大學(xué)學(xué)報(bào)，2002，28（1）：66－70.

［12］劉鴻婷.出租車(chē)運(yùn)力規(guī)模評(píng)價(jià)與優(yōu)化研究［D］.大連：大連海事大學(xué)，2011.