薛守強(qiáng)，宋瑞，安久煜，王攸妙

(北京交通大學(xué)，綜合交通運(yùn)輸大數(shù)據(jù)應(yīng)用技術(shù)交通運(yùn)輸行業(yè)重點(diǎn)實(shí)驗(yàn)室，北京100044)

0 引言

合乘問題(ride-sharing)，也稱共乘，即將原本空閑的車上座位利用起來，不僅合理利用路面車輛閑置運(yùn)力資源，還可有效減少私家車出行，緩解城市交通壓力，消減出行成本。

國內(nèi)外專家學(xué)者都熱衷于研究合乘問題。Hosni H.[1]提出一種混合整數(shù)規(guī)劃模型并用拉格朗日分解展開求解；Alonso-Mora[2]等提出成對共享圖理論及對應(yīng)算法；之后Simonetto[3]等在文獻(xiàn)[2]基礎(chǔ)上通過改進(jìn)策略，保證解結(jié)果的次優(yōu)，使計算時間縮短為原先的1/4。但這類研究均假設(shè)乘客具有完全理性的出行行為，側(cè)重于優(yōu)化系統(tǒng)出行效率，忽視乘客在實(shí)際出行中具有有限理性行為的特征。

在挖掘乘客出行心理特征方面，Wang[4]等從感知價值和感知風(fēng)險探討非用戶使用拼車服務(wù)的驅(qū)動因素；Nguyen-Phuoc[5]研究網(wǎng)約車乘客滿意度和忠誠度的相關(guān)關(guān)系；張薇[6]從行程時間、費(fèi)用、舒適度的角度判斷乘客合乘決策。這類研究未能將乘客對服務(wù)的感知體驗(yàn)應(yīng)用于微觀匹配調(diào)度機(jī)制。

鑒于此，本文綜合考慮乘客具有有限理性行為特征優(yōu)化系統(tǒng)出行效率，通過多個方面動態(tài)感知乘客得失心理，并將其融入到合乘問題的匹配調(diào)度機(jī)制中。本文改進(jìn)了文獻(xiàn)[2-3]中的算法框架，令其不僅能夠解決動態(tài)合乘——NP 難問題，而且通過捕捉乘客心理和實(shí)際車輛匹配情況制定匹配調(diào)度方案，從而真實(shí)地遵從乘客主觀意愿，為乘客提供更為滿意的出行體驗(yàn)。

1 問題描述

本文研究單對多的出租車動態(tài)合乘問題：即存在一組出租車隊(duì)，乘客可隨時向共乘系統(tǒng)提出出行需求。系統(tǒng)采用滾動更新機(jī)制，每隔周期時長t0收集乘客請求和當(dāng)前車輛具體信息。在滿足各約束下，系統(tǒng)以優(yōu)化出行效率和提升感知價值為目的，為乘客匹配合適車輛，制定最優(yōu)出行路線。未被分配到的乘客將進(jìn)入下一周期重新優(yōu)化，若至其最大等待時間仍未被安排車輛服務(wù)，將取消該訂單。此外，一名乘客只能由一輛車服務(wù)，一個周期內(nèi)一輛車最多接受一名乘客請求的要求。

數(shù)學(xué)定義在一個完全有向的G={ }V,A路網(wǎng)中，其中，V為所有站點(diǎn)集合，i,j為路網(wǎng)頂點(diǎn)，A表示(i,j)點(diǎn)間的路段集合，A={(i,j)|i,j∈V,i≠j} ，ti,j表示車輛在路段(i,j)間消耗的時間。請求集合R包含各乘客出行請求信息r={(pr,dr,rt,δ,η,d*r,wr)|r∈R} ，其中，包括乘客r的上車位置pr、下車位置dr、發(fā)出請求的時間rt、最大等待時間δ、最大繞行時間η、到達(dá)目的地最短用時，以及乘客r對時間、費(fèi)用和共乘人數(shù)的權(quán)重大小wr=[w1,w2,w3] (詳細(xì)見2.3 節(jié))。C為車輛集合，同時每輛車c∈C的承載能力為Lc。

2 算法框架構(gòu)建

定義可行出行對(c,r)：車輛c在滿足各約束下能夠服務(wù)乘客r，則構(gòu)成一個可行出行對(c,r)。每個(c,r)包含3 項(xiàng)信息{t,Ttime,t,Pvalue,t} ，其中，t為行程，指車輛c服務(wù)乘客r實(shí)際路徑方案，Ttime,t,Pvalue,t分別為行程t中所有乘客的總損耗時間和總感知價值。

為解決一段時間內(nèi)的出租車動態(tài)合乘問題，系統(tǒng)將該段時間按照t0分為 |M|個周期，從第1 個周期開始，進(jìn)行滾動更新優(yōu)化，具體流程如圖1所示，虛線框內(nèi)為第2節(jié)算法框架主要內(nèi)容。

圖1 算法流程圖Fig.1 Algorithm flowchart

2.1 可行出行對

為獲取?c∈C與?r∈R間所有可行匹配，采用貪婪法中插入法快速判斷車輛c是否可服務(wù)乘客r。下面簡要說明判斷過程：若車輛1 當(dāng)前服務(wù)路線是(d1,d3,d2)，即乘客按照乘客1→乘客3→乘客2的順序先后下車，則新乘客4的上、下車點(diǎn)p4,d4從開始位置依次嘗試插入；若(p4,d4,d1,d3,d2)滿足各約束要求，則貪婪法終止，表明車輛1 可服務(wù)乘客4，構(gòu)成可行出行對，但車輛1 服務(wù)乘客4 的最優(yōu)路線將由2.2 節(jié)模型求解；如不滿足則依次改變插入位置如(p4,d1,d4,d3,d2)繼續(xù)判斷，若最后仍找不到滿足約束的插入位置，則說明車輛1不能服務(wù)乘客4，貪婪法終止。

2.2 最優(yōu)出行路徑

經(jīng)典撥號問題(Dial a Ride Problem，DARP)假設(shè)乘客均未上車，其上、下站點(diǎn)對稱分布。但因滾動更新機(jī)制，部分乘客已在車中，故本節(jié)改進(jìn)文獻(xiàn)[7]中的3指標(biāo)模型，確定(c,r)中車輛c的最優(yōu)路徑為，并令其為(c,r)的行程t，Ttime,t即為目標(biāo)函數(shù)值。

點(diǎn) 集V′={(0,2m+n+1),P,D|V′?V}，其 中，(0,2m+n+1)為車輛c的當(dāng)前位置和虛擬終點(diǎn)，任一點(diǎn)到虛擬終點(diǎn)的距離均為0。共計m名車外乘客，即未上車乘客，包括已被安排車輛服務(wù)但當(dāng)前時刻還未上車的乘客Q*c和新乘客r，對應(yīng)上車點(diǎn)P={1,…,m} 和下車點(diǎn)D1={m+1,…,2m} ，各點(diǎn)上車人數(shù)qi ＞0，對應(yīng)下車人數(shù)-qm+i ＜0；n名車內(nèi)乘客對應(yīng)下車點(diǎn)D2={2m+1,…,2m+n} ，下車人數(shù)-q2m+i ＜0 ，其中，q0=q2m+n+1=0 ，下車點(diǎn)集合D=D1?D2。此外，記上(下)車點(diǎn)為i或j點(diǎn)所對應(yīng)乘客r的繞行時間Ri，等待時間Wj(或Wi)，車內(nèi)乘客已在車時間t*c,i，到達(dá)目的地最短時間d*i，車輛到達(dá)點(diǎn)i的時刻和已載人數(shù)Lc,i，懲罰值M。

目標(biāo)函數(shù)式(1)保證乘客總等待和繞行時間最少。約束條件：式(2)～式(4)保證流量平衡，式(5)和式(6)保證車輛到達(dá)各點(diǎn)的時間和車載能力約束，式(7)和式(8)分別表示車內(nèi)、車外乘客的繞行時間，式(9)表示車外乘客上車時的等待時間，式(10)～式(12)是對等待、繞行時間，承載能力的約束，式(13)定義決策變量xi,j，當(dāng)車輛c從點(diǎn)i到點(diǎn)j時取1，反之取0。

不同于文獻(xiàn)[3]提出的啟發(fā)示插入法求解出行路線，本節(jié)構(gòu)建模型并用商業(yè)軟件GUROBI 計算，不僅能保證找出車輛c的最優(yōu)路線，還可解決文獻(xiàn)[2]和文獻(xiàn)[3]中是否考慮排隊(duì)的兩種不同策略，更具普適性。當(dāng)集合Q*c={}時，即為不排隊(duì)策略，已安排服務(wù)但當(dāng)前還沒上車的乘客將進(jìn)入下一周期重新優(yōu)化；排隊(duì)策略表示上述乘客將按照當(dāng)前出行方案排隊(duì)等待服務(wù)。

2.3 感知體系

在2.2 節(jié)確定(c,r)具體路線方案f*(c,r)(即行程t)后，分別求解行程t中車內(nèi)乘客感知價值pin,t和車外乘客感知價值pout,t，以及該趟行程中總感知價值Pvalue,t=∑pin,t+∑pout,t。

(1)乘客心理特征

已有研究表明，感知價值與乘客滿意度呈顯著正相關(guān)，感知風(fēng)險與乘客滿意度呈負(fù)相關(guān)。時間和費(fèi)用對應(yīng)感知價值中的功利價值成分，而乘客由于性別及出行目的等不同，對共乘人數(shù)常持有積極或消極態(tài)度。積極態(tài)度包括感知價值中的享樂主義和社會價值，如結(jié)交朋友擴(kuò)大交際圈，減少私家車使用獲得社會認(rèn)同感[4-5]；消極態(tài)度如侵犯隱私等感知風(fēng)險[4]。此外，文獻(xiàn)[6]考慮時間、費(fèi)用、共乘人數(shù)3 項(xiàng)指標(biāo)作為乘客合乘決策主要因素。因此，本文選取這3項(xiàng)內(nèi)容作為量化指標(biāo)感知乘客心理，并以感知價值(%)表示乘客滿意度。

(2)價值函數(shù)

在動態(tài)合乘問題中，出租車和乘客的出行方案是時刻變化的，具有不確定性。為捕捉不確定下的主觀價值，選取前景理論中的價值函數(shù)感知量化上述3項(xiàng)指標(biāo)。具體價值函數(shù)為

式中：x為某情境下的具體取值；Δx為相對于參照點(diǎn)k的某種收益；α和β為風(fēng)險態(tài)度系數(shù)；λ為損失規(guī)避系數(shù)。根據(jù)文獻(xiàn)[8]，α=0.89，β=0.92，λ=2.25最符合決策者心理特征。

具體對應(yīng)三要素包括：

① 感知時間價值函數(shù)Etime，參照點(diǎn)，ktime為乘客r在當(dāng)前出行方案中的總時間成本，Δt=k*time-ktime為時間收益。

②感知費(fèi)用價值函數(shù)Ecost，參照點(diǎn)k*cost為原價，kcost為乘客r根據(jù)當(dāng)前出行方案所需支付的費(fèi)用，Δc=k*cost-kcost為支付優(yōu)惠，與一人共乘8 折，兩人共乘7折，以此類推，最低5折。

③感知共乘人數(shù)價值函數(shù)Enump，對共乘人數(shù)持有積極態(tài)度時，參照點(diǎn)為乘客r已與nˉ人共乘；持有消極態(tài)度時，乘客最滿意的情況是無人合乘，因此乘客在共乘人數(shù)一項(xiàng)中只存在最滿意和損失心理兩種狀態(tài)?？紤]與積極態(tài)度保持大小一致以及權(quán)重中正負(fù)數(shù)值關(guān)系，令，當(dāng)無人共乘時Enump=-λ；有人共乘時，

消減不同量綱的計算影響，將各感知價值做規(guī)范化處理，構(gòu)建各因素權(quán)重w1,w2,w3(w1+w2+w3=1)的多元線性函數(shù)，最終乘客r感知價值pr(區(qū)間在(-w3,1])的函數(shù)形式為

2.4 匹配優(yōu)化

最終構(gòu)成Ttrip={(c,r)={t,Ttime,t,Pvalue,t}|c∈C,r∈R} 。由于一個(c,r)對應(yīng)一個行程t，因此，車輛c完成行程t，即表示車輛c服務(wù)乘客r。同時在Ttrip中設(shè)立車輛c、乘客r分別與行程t的對應(yīng)關(guān)系：車輛c服務(wù)的行程集合Ttrip,c，乘客r所在行程集合Ttrip,r，總行程集合T*trip，服務(wù)行程t的車輛c集合Tcar,t。

決策變量εt,c=1 表示行程t由車輛c完成，否則為0；yr=1 表示乘客r未被安排車輛服務(wù)，否則為0。

目標(biāo)函數(shù)：式(20)保證總出行時間成本最小化，以避免部分乘客因折扣等原因逗留在車內(nèi)從而占用道路資源，未被服務(wù)的乘客施以懲罰成本M；式(21)保證乘客滿意度最大化。約束條件：式(22)保證車輛在一次匹配中最多被分配一位乘客，式(23)保證乘客在一次匹配中最多被一輛車服務(wù)。

2.5 求解多目標(biāo)規(guī)劃問題

為快速獲得2.4 節(jié)多目標(biāo)規(guī)劃問題的優(yōu)質(zhì)解，選擇文獻(xiàn)[9]提出的EMOABC 算法，其與同類型先進(jìn)算法相比，具有可實(shí)現(xiàn)程度高、控制參數(shù)少，快速返回優(yōu)質(zhì)解等特點(diǎn)。

EMOABC 采用Pareto 概念，創(chuàng)建外部檔案庫(External Archive)。每次搜索過程中，為保持種群多樣性，避免算法過早收斂。選擇檔案庫中擁擠度最大的精英樣本對雇傭蜂、偵查蜂與跟蹤蜂改進(jìn)以產(chǎn)生新食物源，同時檔案庫根據(jù)擁擠度大小存儲更新搜索時發(fā)現(xiàn)的非支配解。具體可參考文獻(xiàn)[9]。

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)獲取海口市經(jīng)度110.27°E～110.39°E，緯度19.98°N～20.09°N 內(nèi)的道路網(wǎng)空間數(shù)據(jù)，并篩除車輛無法通行的道路。以道路網(wǎng)交叉口為節(jié)點(diǎn)，交叉口間路段為弧制成路網(wǎng)，共生成1043 處節(jié)點(diǎn)和1974條有向路段。

實(shí)驗(yàn)采集?？谑胁糠值貐^(qū)出租車訂單數(shù)據(jù)中某日0:00-1:00 這1 h 內(nèi)的100%和2 倍100%的乘客訂單數(shù)據(jù)，并采用Floyd 法提前求解各點(diǎn)間的最短距離。車輛初始位置隨機(jī)設(shè)置在各節(jié)點(diǎn)，并以10 m·s-1勻速行駛，δ=300 s，η=300 s，Lc=4，M=1000，周期t0=30 s。表1～表4均為1 h后的最終優(yōu)化結(jié)果。

重要度權(quán)重設(shè)為[0.45, 0.35, 0.2]，理論上隨機(jī)排布共有12 種重要度順序(包含6 種w3為負(fù)的消極態(tài)度)，但考慮到持消極態(tài)度的乘客，其不能過于在乎價格等情況，最終w1,w2,w3排序?yàn)椋篬0.45,0.35,0.2]，[0.45, 0.2, 0.35]，[0.35, 0.45, 0.2]，[0.2, 0.45,0.35]，[0.45, 0.35,-0.2]，[0.45, 0.2,-0.35]。實(shí)驗(yàn)中乘客隨機(jī)獲得其中一種重要度偏好。

3.2 不同策略機(jī)制分析

設(shè)置2組不同乘客和車輛數(shù)的實(shí)驗(yàn)案例，交叉組合兩類策略，共計4 種，計算各自在動態(tài)合乘下服務(wù)率、平均滿意度等方面數(shù)值，如表1所示。

表1 4 種策略優(yōu)化結(jié)果對比Table 1 Comparison of results of four strategy models

表1中，Re 為不排隊(duì)策略，Qu 為排隊(duì)策略；Pt表示考慮出行效率的同時，感知乘客出行心理，Tn表示僅考慮出行效率而不感知乘客心理。其中，Re+Tn、Qu+Tn分別代表文獻(xiàn)[2]和文獻(xiàn)[3]中的方法策略。同時對表中服務(wù)率等定義為

式中：、和分別為服務(wù)率、平均滿意度和人均耗時；N1為截止到1:00收到的乘客總訂單請求；N2為截止到1:00 已服務(wù)乘客總數(shù)量；N3為截止到1:00服務(wù)完成且下車的乘客總?cè)藬?shù)；S1為截止到1:00服務(wù)完成且下車的乘客滿意度之和；S2為截止到1:00服務(wù)完成且下車的乘客所耗時間成本之和。

同類策略間比較(如表1中實(shí)驗(yàn)1 和2 比較Re和Qu、1 和3 比較Pt 和Tn 等)可以發(fā)現(xiàn)：相比于Qu策略，Re策略使乘客在上車前，更有可能被分配到更適合的車輛中，因此Re+Tn 比Qu+Tn 人均耗時少，但服務(wù)率偏低，而Re+Pt在服務(wù)率、滿意度等方面均優(yōu)于Qu+Pt；相比于Tn 策略，加入感知機(jī)制的Pt策略通過微觀調(diào)整匹配方案，可明顯提升乘客出行滿意度。

因此，綜合考慮乘客心理和全局出行效率的Re+Pt策略，能夠安排更合理、綜合性更強(qiáng)的匹配方案，使其在各組實(shí)驗(yàn)中均產(chǎn)生最優(yōu)乘客滿意度，較Tn類策略平均相對提升12%，同時在最終服務(wù)率、平均損耗時間方面也保證具有最優(yōu)或次優(yōu)表現(xiàn)。而在計算時間上，Pt類策略較Tn類策略，增加了求解感知機(jī)制及多目標(biāo)問題的計算時間；而相較于Qu策略，Re策略使得部分訂單不斷重新優(yōu)化，增加了一定計算時間，但均在可接受范圍內(nèi)。

3.3 算法對比分析

為驗(yàn)證EMOABC 求解多目標(biāo)問題的有效性，與非支配排序遺傳算法(Non Dominated Sorting Genetic Algorithm-II，NSGA-II)[10]、Pareto 準(zhǔn)則和經(jīng)典人工蜂群算法[11]結(jié)合的多目標(biāo)人工蜂群算法(Multi-Objective Artificial Bee Colony，MOABC)進(jìn)行比較。設(shè)置2組實(shí)驗(yàn)，分別采用3種算法求解，各測算5次，數(shù)據(jù)取5次最終服務(wù)結(jié)果的平均值，結(jié)果如表2所示。設(shè)置控制參數(shù)，種群數(shù)60，最大迭代數(shù)200，外部檔案庫規(guī)模為5。

表2 算法性能比較Table 2 Algorithm performance comparison

由表2可知，NSGA-II算法求解時間過長，且平均滿意度均劣于EMOABC；MOABC 算法求解時間最短，但其過早收斂，獲得較差解；EMOABC在2組實(shí)驗(yàn)的求解質(zhì)量上均達(dá)到最優(yōu)，平均滿意度較MOABC 相對優(yōu)化4.4%，較NSGA-II 優(yōu)化1.7%，計算時間為次優(yōu)，綜合表現(xiàn)更佳。

3.4 車輛數(shù)靈敏度分析

為分析車隊(duì)數(shù)量對優(yōu)化結(jié)果的影響，在其他條件不變的情況下，改變車輛數(shù)進(jìn)行求解，結(jié)果如表3所示。

由表3可知：對于Pt 類策略，車輛數(shù)增加為匹配機(jī)制提供更多兼顧滿意度和出行效率的可行方案，故企業(yè)在實(shí)際應(yīng)用中可通過適當(dāng)增加車輛數(shù)的方式，有效提升滿意度、服務(wù)率，降低人均耗時；對于Tn 類策略，以出行效率為導(dǎo)向的匹配機(jī)制優(yōu)先實(shí)現(xiàn)出行效率最高(出行成本最小)的匹配方案，故服務(wù)率得到提升，人均耗時下降，但滿意度降低。

表3 不同車輛數(shù)優(yōu)化結(jié)果Table 3 Optimization results under different number of taxis

3.5 周期靈敏度分析

其他條件不變的情況下，改變周期時長t0，以分析其對優(yōu)化結(jié)果的影響，結(jié)果如表4所示。

表4 不同周期優(yōu)化結(jié)果Table 4 Optimization results under different period

由表4可知，周期越短，服務(wù)率越高，滿意度越低。這主要是因?yàn)橥瑯訒r間內(nèi)，周期越短，1名乘客可被重新優(yōu)化的次數(shù)就越多，即增加了其與車輛匹配的可能性，故服務(wù)率提升；因式(20)中M對可被服務(wù)的乘客具有一定強(qiáng)制性，故部分乘客以較低的滿意度完成出行服務(wù)，從而造成滿意度降低。

4 結(jié)論

乘客出于個人原因?qū)铣藳Q策中價格、時間，共乘人數(shù)有不同喜好，本文通過感知模塊捕捉乘客心理，并運(yùn)用到合乘問題中的匹配規(guī)劃模塊。所提出的算法框架，能夠巧妙處理動態(tài)合乘問題所涉及的匹配、調(diào)度和感知間的復(fù)雜關(guān)系，并保證在有限時間內(nèi)得到優(yōu)質(zhì)解，這是單個算法或模型難以解決的。多次實(shí)驗(yàn)表明，本文提出的Re+Pt優(yōu)化策略綜合表現(xiàn)最優(yōu)，不僅能夠較大改善乘客合乘中的出行體驗(yàn)，同時服務(wù)率也能保持次優(yōu)及以上水平，盡管人均耗時較最優(yōu)解有所差距，但對乘客來說，這也是其更愿意接受的情形。本文研究內(nèi)容為應(yīng)用于實(shí)際場景，改善企業(yè)服務(wù)水平，提供基本策略和理論方法指導(dǎo)。