出租車合乘定價多目標優(yōu)化研究＊

張 薇 何瑞春 肖 強 馬昌喜

（蘭州交通大學交通運輸學院 蘭州 730070）

0 引 言

近年來，我國各大城市開始出現(xiàn)出租車合乘模式，出租車合乘指乘客經(jīng)協(xié)商同意共同乘坐同一輛出租車的行為模式，能夠在一定程度上提高運輸效率［1］.國內(nèi)外許多學者對合乘問題展開了研究，Lin等［2］基于費用的考慮研究了合乘路徑優(yōu)化方法；Yan等［3］基于拉格朗日松弛法建立了合乘路徑規(guī)劃模型；He等［4］基于GPS定位數(shù)據(jù)，采用數(shù)據(jù)挖掘技術(shù)研究了合乘路徑的優(yōu)化問題；Manzini等［5］設(shè)計了輔助合乘匹配的決策支持系統(tǒng)；肖強等［6］基于聚類和模式識別方法研究了合乘系統(tǒng)中的乘客匹配問題.目前的研究主要集中于合乘路徑選擇［7－8］及合乘匹配問題［9－10］，而較少涉及出租車合乘系統(tǒng)定價的優(yōu)化問題，由于合乘系統(tǒng)價格參數(shù)直接關(guān)系到乘客、出租車司機及出租車公司等多方利益，所以合乘系統(tǒng)價格參數(shù)必須均衡考慮多方利益的最大化.文中綜合考慮出租車合乘系統(tǒng)定價問題所涉及到的合乘支付比例、管理費、燃氣補貼等多種價格參數(shù)，構(gòu)建了多目標優(yōu)化模型，設(shè)計了基于粒子群的多目標優(yōu)化算法，通過計算分析了出租車與乘客供需比對優(yōu)化結(jié)果的影響.

1 出租車合乘多目標優(yōu)化模型

按照現(xiàn)行交通管理政策規(guī)定，合乘出租車時，合乘路段乘客只需支付一定比例費用（簡稱支付比例），獨自乘車路段由個人承擔費用.支付比例直接關(guān)系到司機與乘客雙方利益.另外，出租車公司對司機收取的管理費、政府給予的燃氣補貼也在一定程度上對司機的收入產(chǎn)生影響.因此，文中考慮支付比例、管理費及燃氣補貼3個價格參數(shù)，以司機收入最大化、乘客支付最小化、出租車公司利益最大化、政府補貼最小化為目標，建立合乘系統(tǒng)的多目標優(yōu)化模型.

令出租車合乘系統(tǒng)有N輛出租車，M位乘客，出租車的起步價為ps元／（akm），超過akm后，每車公里租價為pr元，行程為s的乘客獨自乘坐出租車時的費用P（s）為

令乘客i的行程為si，yi＝1為乘客i以合乘模式乘坐出租車，yi＝0為乘客i獨自乘坐出租車.若合乘時出現(xiàn)繞行現(xiàn)象，繞行方的費用按照原行程進行合乘優(yōu)惠，不繞行方按照實際行程進行合乘優(yōu)惠，zi＝1為乘客i合乘出租車并且為繞行方，否則zi＝0.dji＝1為車輛j拉載乘客i，dji＝0為車輛j未拉載乘客i，πi為乘客i合乘路段占其行程的比例；α為合乘支付比例.則乘客i的乘車費用為

計算車輛j的收入為

式中：β為每車每日需繳納的管理費用，元／（本·d）；γ為每日的燃氣補貼，元／d；W（lj）為車輛j當日行駛lj公里的燃氣費用，按照每100km，8m3耗氣量計算.

式中：q為每立方米燃氣價格，元／m3；lj為車輛j當日行駛公里數(shù)，km.

出租車每車日均收入最大化為

另外，令出租車公司根據(jù)企業(yè)利潤情況對收取的車輛管理費的下限估算為βmin，司機對管理費的上限要求為βmax，政府根據(jù)財政支出情況對車輛燃氣補貼的上限估算為γmax，考慮對每車實行相同的管理費及補貼，為了保證出租車企業(yè)與政府的利益，車輛需要交納的管理費及獲得的補貼需要在βmin＜β＜βmax，0＜γ＜γmax范圍內(nèi)，滿足maxβ與minγ，將兩者合并考慮為

綜上，合乘系統(tǒng)的價格參數(shù)多目標優(yōu)化模型如下.

2 算法設(shè)計

2.1 多目標適應度函數(shù)

合乘系統(tǒng)的價格參數(shù)包括支付比例α、管理費β、燃氣補貼γ，因此定義粒子編碼為（α，β，γ）.為區(qū)別多目標問題粒子的優(yōu)劣性，粒子的適應度函數(shù)采取權(quán)重加權(quán)法，任意粒子xa的多目標適應度函數(shù)定義如下.

式中：fi，g為單目標fi的當前最優(yōu)值；fi（xa）為粒子xa的單目標值；λi為各單目標的權(quán)重， ＝1.

2.2 非支配解集

多目標的Pareto解是不受其他解所支配的非支配解，建立非支配解集，將粒子中所有非支配解添加至非支配解集中，作為進一步選擇全局最優(yōu)與確定多目標Pareto解的基礎(chǔ).具體方法如下：對一粒子xa，如果不存在xb∈Ω，xb≠xa，使得對所有單目標fi（xb）?fi（xa），i＝1，2，3，那么粒子xa為非支配解.

2.3 基于小生境的全局最優(yōu)選擇策略

根據(jù)小生境思想，隨著進化相似粒子會逐漸聚集，從而形成若干小生境子群.本文以歐式距離表示粒子距離，并設(shè)計以下策略劃分小生境子群：

定義1 粒子空間Ω中的任意2個粒子xa，xb∈Ω之間的距離D（xa，xb）用歐式距離表示為

定義2 Ω為粒子空間，X為Ω中的小生境子群集合，粒子xa∈Ω與小生境子群Xs∈X之間的距離D（xa，Xs）為

式中：（O（Xs））i為小生境子群Xs的中心點的第i個參數(shù)值，O（Xs）為小生境子群Xs的中心點.

定義3 小生境子群Xs的中心點定義為Xs中所有粒子的中心位置，當粒子xa加入小生境子群Xs時，Xs的中心點變換

定義4 若粒子xa∈Ω 滿足：（1）min｛D（xa，Xk）｜Xk?X｝＝D（xa，Xs）；（2）D（xa，Xs）＜ε，則粒子xa與Xs為同一小生境子群；若只滿足條件（1），則粒子xa單獨作為一個小生境子群.其中：ε為所有粒子之間相互的平均距離.

基于以上定義將所有粒子劃分為若干小生境子群，并進行全局最優(yōu)粒子的選擇，方法如下：根據(jù)多目標適應度函數(shù)在各小生境子群中選出最優(yōu)粒子，作為最優(yōu)粒子集，并計算各小生境子群的規(guī)模，即各小生境子群的粒子數(shù)，選出最優(yōu)粒子集中所屬小生境子群規(guī)模最小的粒子作為全局最優(yōu)粒子.結(jié)合多目標適應度函數(shù)與小生境子群獲得最優(yōu)粒子的方法既能挑選出目標優(yōu)化的粒子又能保留粒子的多樣性.

2.4 粒子的更新

根據(jù)選擇的全局最優(yōu)更新粒子，粒子的速度和位置更新如下.

式中：w 為慣性權(quán)重；r1，r2為（0，1）之間均勻分布的 隨 機 數(shù)；c1，c2為 學 習 因 子；分 別 是粒子xa在第t代時的速度和位置為粒子xa的局部最優(yōu)位置為粒子群的全局最優(yōu)位置.

2.5 算法流程

步驟1 隨機生成乘客出行距離si～N（μ，σ2），以概率p1隨機選擇同意合乘的乘客yi＝1，根據(jù)出行距離配對合乘乘客，隨機生成合乘路段比例πi∈ ［0，1］，以概率p2隨機選擇繞行的乘客zi＝1.對單獨乘車的乘客i，若車輛j的當前行駛里程lj＜lmax，則分配dji＝1，對每組合乘乘客，若lj＜lmax，則將該組所有乘客分配給車輛j，至到所有乘客分配完或所有車輛的行駛里程達到最大值為止.

步驟2 初始化群體規(guī)模MP，最大迭代次數(shù)NP，慣性權(quán)重w等粒子更新參數(shù)，隨機生成初始群體.

步驟3 按照非支配粒子選取方法，生成非支配解集.

步驟4 根據(jù)小生境子群劃分方法，將非支配集中的粒子劃分為若干小生境子群，并計算各小生境子群規(guī)模.

步驟5 計算粒子的多目標適應度函數(shù)，保留各小生境子群中適應度函數(shù)最優(yōu)粒子，形成最優(yōu)粒子集.

步驟6 選擇規(guī)模最小的小生境子群中的最優(yōu)粒子作為全局最優(yōu)粒子.

步驟7 根據(jù)全局最優(yōu)粒子更新粒子速度與位置，同時記錄各粒子的個體最優(yōu).

步驟8 若迭代條件滿足，算法結(jié)束，最優(yōu)粒子集即最終Pareto解集，否則，轉(zhuǎn)步驟3.

3 實例分析

假設(shè)出租車起步價10元／（3km），每車公里租價1.4元／車，單車日行駛最大里程200km，燃氣價格3.10元／m3.設(shè)粒子群大小MP＝100，每日管理費βmin＝50元／d，βmax＝200元／d，每日燃氣補貼γmax＝20元／d，出租車數(shù)量N＝100，乘客數(shù)量M＝2 500人，取目標權(quán)重λ1＝λ2＝λ3，慣性權(quán)重w＝0.3，學習因子c1＝c2＝2，乘客的出行距離si～N（8，4），乘客同意合乘的概率p1＝0.6，繞行概率p2＝0.1.基于本文提出的多目標優(yōu)化模型與算法，得到迭代100次的優(yōu)化結(jié)果見圖1，圖中看出，降低乘客支付的同時必然會降低車輛收入，燃氣補貼的增加或者管理費的減少，能夠提高車輛的收入，與實際相符.最優(yōu)解具體見表1，解的分布均勻性較好，編號靠前的解，車輛收入水平較高，燃氣補貼降低，收取的管理費較高；編號靠后的解乘客支付較少，但車輛收入較低；中間的解兼顧了各目標，在各目標之間找到均衡.根據(jù)結(jié)果分析，支付比例是合乘系統(tǒng)中的重要價格參數(shù)，過高或過低的支付比例都會直接造成其他目標變差，并且無法用其他價格參數(shù)彌補，本例的合適取值范圍大約在［0.6，0.75］之間.

圖1 M＝2 500人時的最優(yōu)解集

表1 最優(yōu)解集

為進一步分析最優(yōu)解的價格參數(shù)對目標的影響，給出圖2～3分別是乘客支付與車輛收入的影響關(guān)系圖.圖中顯示乘客支付僅受到支付比例的影響，支付比例越大，乘客支付越多；而車輛收入同時受到支付比例、燃氣補貼、管理費用的影響，當支付比例較高時，車輛收入較高，此時可以提高管理費或者降低燃氣補貼，當支付比例較低時，車輛收入較低，此時需要降低管理費或者提高燃氣補貼，以平衡司機、出租車企業(yè)各方利益.

圖2 乘客支付的影響關(guān)系圖

以上結(jié)果是在車輛數(shù)N＝100，乘客數(shù)M＝2 500人條件下得到的，下面考慮供需比對合乘系統(tǒng)價格參數(shù)最優(yōu)解的影響.增大乘客數(shù)量，取乘客數(shù)M＝4 000，5 500人，得到的最優(yōu)解集分別見圖4～5.圖中顯示，當乘客數(shù)量達到4 000人時的最優(yōu)解集明顯朝著更加優(yōu)化的方向移動，各目標都較乘客數(shù)量為2 500人時得到進一步優(yōu)化.但是，當乘客數(shù)量繼續(xù)增大到為5 500人時，最優(yōu)解集基本上沒有再發(fā)生變化，說明乘客數(shù)量已經(jīng)超過了出租車的供給能力，出現(xiàn)了過剩乘客無法乘車的現(xiàn)象，所以此時各目標已經(jīng)達到最優(yōu)值，乘客數(shù)量的繼續(xù)增加只會加重打車難問題.

圖3 車輛收入的影響關(guān)系圖

圖4 M＝4 000人時的最優(yōu)解集

圖5 M＝5 500人時的最優(yōu)解集

4 結(jié)束語

文中研究了出租車合乘價格參數(shù)的最優(yōu)解問題，得出以下結(jié)論：（1）當支付比例較高時，車輛收入及乘客支付均較高，此時可以提高管理費或者降低補貼，而當支付比例較低時，需要降低管理費或者提高補貼；（2）為了均衡系統(tǒng)各目標，必須選擇合適的支付比例；（3）出租車與乘客的供需比對系統(tǒng)最優(yōu)解有較大影響，隨著乘客量的增加，各目標逐漸優(yōu)化，直到供需比達到飽和時，系統(tǒng)各目標達到最優(yōu)值，若供需比繼續(xù)減小，只會造成更多的剩余乘客無法乘車的現(xiàn)象.文中工作能夠解釋出租車合乘系統(tǒng)的相關(guān)現(xiàn)象，所得結(jié)論對出租車政策的制定有一定的指導意義.

［1］ZHANG D，HE T，LIU Y H，et al.A carpooling recommendation system for taxicab services［J］.IEEE Transactions on Emerging Topics in Computing，2014，2（3）：254－266.

［2］LIN Y，LI W，QIU F，et al.Research on optimization of vehicle routing problem for ride－sharing taxi［J］.Procedia－Social and Behavioral Sciences，2012，43：494－502.

［3］YAN S Y，CHEN C Y，WU C C.Solution methods for the taxi pooling problem［J］.Transportation，2012，39（3）：723－748.

［4］HE W，HWANG K，LI D.Intelligent carpool routing for urban ridesharing by mining GPS trajectories［J］.IEEE Transactions on Intelligent Transportation Systems，2014，15（5）：2286－2296.

［5］ MANZINI A P.A decision－support system for the car pooling problem［J］.Journal of Transportation Technologies，2012，2（2）：85－101.

［6］肖 強，何瑞春，張 薇，等.基于模糊聚類和識別的出租車合乘算法研究［J］.交通運輸系統(tǒng)工程與信息，2014，14（5）：119－125.

［7］CHUNG C L，JENG J Y，LEE Z Y.Study of carpool user behaviors and route characteristics in Taiwan［J］.Sustainable Transportation Systems，2012（5）：356－363.

［8］CHEN Y T，HSU C H.Improve the carpooling applications with using a social community based travel cost reduction mechanism［J］.International Journal of Social Science and Humanity，2013，3（2）：87－91.

［9］KAMMERDIENER T，ZHANG H.Classification of ride－sharing partners based on multiple constraints［J］.Journal of Computing Sciences in Colleges，2011，26（4）：95－101.

［10］GUO Y，GONCALVES G，HSU T.A clustering ant colony algorithm for the long－term car pooling problem［J］.International Journal of Swarm Intelligence Research，2012，3（2）：39－62.