程 杰 唐智慧 劉 杰 鐘 流

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

0 引 言

隨著我國國民經濟的高速發(fā)展和城市化進程的加快，機動車保有量持續(xù)增加，交通需求迅猛增長，交通擁堵日益嚴重.出租車作為城市交通的有機組成部分，由于價格偏高等原因，在非高峰時期經常處于空載狀態(tài)；在高峰期又常因為大量出租車只載一位乘客而出現打車難的問題，因此推廣有效的出租車合乘模式，可以提高出租車的運輸效率，降低出租車空載率，協助城市公交緩解城市交通壓力.

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

本文重點研究不同類型出租車和不同類型乘客組的多對多模式的動態(tài)出租車合乘問題.綜合考慮出行者與駕駛員的利益，對時間窗約束引入協調機制，建立了動態(tài)出租車合乘模型，并且針對模型特點采用了遺傳算法進行求解.

1 問題描述

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

圖1 動態(tài)出租車合乘的時空網絡圖

2 模型的建立

2.1 模型假設

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

2.2 變量說明

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

2.3 數學模型

2.4 決策變量

路徑變量.設為路徑變量，為1時，表示第k輛車經過邊（i－j）；為0時，表示不經過.費用變量.設為費用決策變量，表示u點上車v點下車第g組乘客的合成費率.

2.5 目標函數和約束條件

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

3 模型求解算法

由于出租車合乘問題是一個NP問題，采用啟發(fā)式算法容易編程求解.本文采用遺傳算法求解該模型.本文所有乘客組時間窗約束均為軟約束，即在無法滿足該時間窗約束導致模型沒有可行解時，乘客組接受協調機制，將其出發(fā)或達到時間窗約束適當增大［10］.除此之外，種類約束也接受協調機制.

3.1 變量編碼

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

3.2 適應度函數和選擇算子

因為模型目標函數是求最小值，因此將染色體目標函數的倒數作為其適應度函數.模型帶有約束條件，本文采用懲罰函數法對模型約束條件進行處理，將懲罰函數加在適應度函數上，如果某一染色體解滿足約束條件，則它解碼適應度函數會很小，從而在選擇時被選中概率會小，遺傳到下一代可能性變小.將種群中適應度值排名前1／4的染色體復制1次，中間2／4的染色體復制一次，拋棄最后1／4的染色體作為選擇操作.

3.3 交叉算子

由于乘客組與費率問題的條件約束，如果仍使用簡單交叉算子，將有可能產生大量的不可行解.因此本文對乘客組和費率分別進行交叉操作.采用文獻［11］的交叉算子對乘客組部分進行交叉操作.對費率部分采用算術交叉.

3.4 變異算子

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

圖2 動態(tài)出租車合乘流程圖

4 算例分析

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

圖3 算例網絡

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

表1 第1次刷新時刻乘客組信息

表2 第2次刷新時刻乘客組信息

利用Matlab編程計算，模型收斂性見圖4.因為初始乘客組信息是隨機給定，因此可能導致無可行解，本文引入協調機制，使得協調各乘客組的乘客組屬性后，適應度函數值會增大，但這樣可以得模型的可行解，最終得到較滿意解.計算得到每輛出租車的行駛路徑如下：出租車1：7─13─12─11─10─9─1；出租車2：19─11─12─14─22─24─17；出租車3：25─19─11─12─9─13─7─6─8─4─5；出租車4：10─2─1─6─7─14─21─22─30─29；出租車5：30─28─24─16─8─4.

圖4 算法的收斂性

每個乘客組合乘與非合乘所交納的費用見表3.從表中不難看出，合乘費用比非合乘費用少.另一方面，司機的收益也是本文研究的重點，在行駛同樣距離的情況下，合乘時的司機收益比非合乘時大，5輛出租車在2次刷新時間的平均空載率分別為0.14，0.41，0.18，0.36，0，其中只有一輛出租車的空載率大于國內出租車平均空載率0.40即該輛出租車利用效率較低［12］.

表3 合乘前后費用與距離對比

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

5 結 論

研究了動態(tài)出租車合乘問題，考慮了在乘客組、出租車分類型情況下，引入協調機制，建立了多對多模式的動態(tài)出租車合乘模型，并且在一個小型網絡上進行了仿真測試，結果表明：出租車合乘減少了乘客費用，增加了司機的收益，同時空載率下降.尚未考慮出租車在合乘狀態(tài)下的燃油成本和其他成本，這些還有待進一步研究.

［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］覃運梅，石 琴.出租車合乘模式的探討［J］.合肥工業(yè)大學學報，2006，29（1）：77－79.

［9］周和平，鐘璧檣.出租車合乘路徑選擇與費率優(yōu)化模型［J］.長沙理工大學學報，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］唐 坤.車輛路徑問題中的遺傳算法設計［J］.東華大學學報，2002，28（1）：66－70.

［12］劉鴻婷.出租車運力規(guī)模評價與優(yōu)化研究［D］.大連：大連海事大學，2011.