鄭建國，李園園

(東華大學旭日工商管理學院，上海200051)

0 引言

有效的出租車合乘模式，可以提高座位利用率，緩解城市交通壓力，降低能源消耗等，可產生社會、環(huán)境、經濟等綜合效益.近些年，一些國內外學者圍繞出租車合乘問題展開了相關研究.

根據乘客需求是否變化，合乘可分為靜態(tài)合乘與動態(tài)合乘.Lin等[1]研究了靜態(tài)有時間窗的出租車合乘路徑優(yōu)化模型；Tao等[2]提出動態(tài)出租車合乘，但主要研究合乘匹配，并未解決路徑問題，而綜合考慮合乘匹配與路徑優(yōu)化可以進一步實現系統(tǒng)成本最優(yōu).

同時，多數研究將乘客上車時間定義為硬時間窗，且所有請求必須滿足，如Cordeau等[3]；部分學者假設在硬時間窗的約束下可以不滿足所有乘客，如 Hosni[4]、Jung[5]等.而實際上，略超出時間窗，客戶也可能接受，硬時間窗則限制了該情形.目前，部分VRP文獻做了相關研究，如：劉家利等[6]在開環(huán)VRP問題研究中以軟時間窗在一定程度上避免嚴格約束，但車輛到達時間可能過早或過晚；而楊翔等[7]綜合利用硬、軟時間窗的特點，使時間窗模糊化.現實中，乘客對出行時間窗的認知也是非嚴格理性的，故模糊時間窗更符合實際.

另外，乘客對繞行、合乘等服務的偏好不盡相同.考慮乘客不希望繞行，Hosni H.等[4]引入行駛時間約束，Jung J.等[5]增加最大繞行約束；而在合乘意愿方面，當前研究存在“乘客均接受合乘”的一般假設，顯然與實際不符，如何對合乘意愿進行量化、區(qū)分描述，還需進一步研究.

綜上，鑒于當前出租車合乘模型與實際偏離的情況，本文定義模糊時間窗，考慮合乘意愿，建立更切實際的問題模型，并設計改進的差分進化算法求解，最后通過算例驗證模型和算法的有效性.

1 基于模糊時間窗的出租車合乘問題描述及建模

1.1 出租車合乘問題描述

本文所研究的出租車合乘為多上車點到多下車點的多對多模式.具體描述為：多輛出租車在某區(qū)域行駛，車上可能有乘客；同時，有多名新的乘客預約，各有其上下車位置與時間要求.調度中心根據當前乘客與出租車的狀態(tài)，在滿足多種約束的條件下確定乘客與出租車的最佳匹配方案及行駛路徑.

數學描述為：給定包含4個子集的點集V，V=V1?V2?V3?V4，其中，V1表示出租車坐標集，V2表示車上乘客的下車點集，V3、V4分別表示預約乘客的上下車點集，乘客p的上下車點分別為s(p)、f(p)；T、O、S分別表示出租車、車上乘客、預約乘客集合，乘客全集P=O?S；乘客具有是否接受合乘2種態(tài)度，將其量化為占用座位數Q(p)，取值為1或q(出租車最大容量)；乘客最早、最遲上車時間分別為表示p的出行時間上限；i、j之間距離為dij、用時為Uij、成本為Cij.決策變量，0-1決策變量表示如果p乘t車從i到j則為1，否則為 0；0-1決策變量表示若t車從i至j則否則為0；0-1決策變量dpt，表示若p乘t車則dpt=1，否則為0；非負決策變量uti表示t車到達i的時間.

1.2 模糊時間窗

根據模糊集理論，定義“及時度”Jp(t)，表征出租車到達上車點的及時程度.若t在原時間窗內，及時度為1；當t超出原時間窗且在之內，導致車輛等待或客戶滿意度下降，及時度降低；當t超出容忍限度時，及時度為0.因此，梯形模糊數更加契合，故用其表征基于模糊時間窗的及時度隸屬函數Jp(t)為

及時度為1時，懲罰費用為0；及時度為0時，出租車因到達過早產生車輛等待成本μ，或過晚而產生客戶懲罰成本?；t超出原時間窗且在之內時，產生相應比例成本.時間懲罰費用函數Lp(t)為

1.3 模型建立

式(3)為目標函數，表示總成本最小化，成本項依次是路徑成本、拒載成本、時間懲罰成本；式(4)為最大容量約束；式(5)表示任1位乘客最多被1輛車服務；式(6)和式(7)為乘客上車時間容忍限度約束；式(8)為繞行約束；式(9)～式(17)為節(jié)點流量及路徑規(guī)則約束，詳見文獻[4]，此不贅述；式(18)表示二進制變量和非負變量約束.

本模型參考文獻[4]建立，主要區(qū)別有3點：①目標函數不同，文獻[4]從出租車單方面考慮，以利潤最大化為目標，而本文考慮乘客服務因素(拒載、服務及時度等)，量化其造成的客戶損失及車輛等待成本等，從乘客與出租車兩個角度考慮系統(tǒng)成本最小化.②時間窗定性不同，文獻[4]為硬時間窗，而本文為模糊時間窗，并考慮因其匹配差異產生的相關成本.③文獻[4]假設“乘客都愿意合乘”，本文對合乘意愿進行區(qū)分描述.

2 基于個體排序的差分進化算法設計

2.1 編碼、解碼及種群初始化

(1)分段編碼與初始化.

乘客分為車上和預約2種，故二進制編碼無法直接應用[8]；而以實數編碼、并用0間隔表示不同車輛[9]，計算復雜度增加，且在DE算法中會產生大量不可行解.因此，本文設計一種分段取值的實數編碼方案.

假設有m個車，s個預約乘客(上車點SO、下車點 SD)，oi個車上乘客(下車點 OD)，將個乘客節(jié)點以{SO，SD，OD}的順序編碼，個體可表示為

其中，SO、SD的xi取值范圍為：1≤xi≤m+1；OD的xi取值范圍為：1≤xi≤mi+1(mi為該乘客所在車輛編號).

按照上述編碼，所有乘客節(jié)點數即為維度D，各維元素在其取值范圍內隨機生成，產生初始種群.

(2)解 碼.

將個體按如下步驟解碼為m行的元胞矩陣P，表示各出租車服務乘客及行駛路徑.

Step 1根據SO的取值范圍1≤xi≤m+1為每個預約乘客分配車輛，如1≤xi≤2，即m=1，該乘客由車1服務.

Step 2根據Step1的分配結果，將各車服務的乘客節(jié)點編號按從小到大的順序排列，構成該車輛的可能路徑R1.應注意，是否有乘客的下車點在其上車點之前，若有，則轉Step3；否則，轉Step4.

Step 3路徑調整，將下車點在上車點之前的乘客互換兩點位置，構成路徑R2，轉step4.

Step 4判斷是否滿足車輛到達時間的最大容忍限度及車的容量約束，若有任一條件不滿足，則將該乘客的上下車節(jié)點從原有路徑中去除，視為拒載；路徑更新為R3.

Step 5按以上4個步驟完成所有車輛的路徑解碼，即構成元胞矩陣P.

2.2 適應度函數設計

本文模型為最小化問題，故將式(3)中Z的倒數作為適應度函數，即f=1/Z=1/(TD+TR+TL)，其中，TD、TR、TL分別為總路徑成本、總拒載成本與總時間懲罰成本，目標函數越小、適應度越大，個體越優(yōu)秀.

2.3 算子設計

(1)基于個體排序的變異策略.

采用DE/rand/1變異策略，公式為

式中：r0,r1,r2∈[1,NP]，為互不相同且與i不等的隨機整數；一般，變異率F∈(0,1).本文利用種群信息，設計基于個體適應度排序的變異率Fi為

式中：Rank(xi)為個體按照適應度從優(yōu)到劣的排序值，則個體從優(yōu)到劣的Fi值從1/NP到1變化，從而精英個體以較小縮放步長實現局部精確尋優(yōu)，而較差個體以較大縮放步長全局尋優(yōu).

(2)基于個體排序的交叉策略.

而Gong等[10]根據當前種群的適應度排序按比例選擇變異算子的基準向量與終點向量，以實現較優(yōu)個體的信息有更大機會被繁殖.受此啟發(fā)，本文設計一種新的基于個體排序的交叉概率CRi為

由式(21)，越優(yōu)秀個體的CRi越小，其攜帶信息越可能被選擇貢獻給試驗個體；其中，CRmin、CRmax為CR的最小、最大值.

(3)混合輪盤賭的半貪婪選擇策略.

具體步驟為：

Step 1對第G代種群XG，執(zhí)行輪盤賭，產生新種群XG1.

Step 2比較XG中個體xi,G與相應試驗個體ui,G的適應度，如果f(ui,G)＜f(xi,G)，則選擇ui,G作為下一代第i個個體；否則，選擇XG1種群中的xi,G1作為新一代個體.

2.4 改進的差分進化算法(ISDE)基本流程

算法步驟為：

Step 1設置參數，包括種群規(guī)模NP、最大進化代數GM及CRmin、CRmax等，生成初始種群，運行代數t=0.

Step 2對第t代xi,G執(zhí)行基于個體排序的變異操作產生vi,G，詳見2.3節(jié)(1)所述.

Step 3對第t代vi,G執(zhí)行基于個體排序的交叉操作產生ui,G，詳見2.3節(jié)(2)所述.

Step 4對原種群進行輪盤賭選擇產生新種群，以半貪婪的選擇方式產生新一代個體，詳見2.3節(jié)(3)所述.

Step 5判斷是否達到代數限制，若是，則停止，輸出最優(yōu)解；否則，t=t+1，轉Step2再次循環(huán)，直到達到終止條件.

算法流程如圖1所示.

圖1 ISDE算法的基本流程Fig.1 The basic flow of the ISDE algorithm

3 實驗結果及分析

3.1 測試算例

參照文獻[4]創(chuàng)建一個20輛出租車，60個預約乘客及20個車上乘客的測試算例：出租車及乘客接送點坐標根據均勻分布在[-10,10]×[-10,10]范圍內隨機產生，假設Uij是i到j的歐氏距離，Cij=Uij，客容量為4；根據U(10,15)隨機生成，模糊時間窗寬度前5組算例數據如表1和表2所示.

表1 出租車信息Table 1 The information of taxies

表2 乘客信息Table 2 The information of passengers

3.2 算法有效性分析

分別獨立運行10次DE、GA及ISDE算法求解本文算例，NP=50、GM=200，其他算法參數設置如表3所示；運行環(huán)境為win7、Intel(R)Pentium(R)CPU、2.13GHZ、matlab2012b.算法對比結果如圖2和表4所示.

表3 算法參數設置Table 3 The parameter settings of the algorithms

圖2 算法收斂曲線Fig.2 The convergence curve of the algorithm

由圖2和表4可知，求解效果由好到差依次為ISDE、DE、GA；與GA相比，DE收斂速度更快，但易陷入局優(yōu)，而ISDE算法收斂較快，同時精度較優(yōu)，說明該算法的優(yōu)越性.

表4 算法求解結果對比Table 4 The comparison of the algorithms solution results

3.3 模型有效性分析

分別獨立運行10次ISDE算法分別求解合乘與非合乘2種模式，結果對比如表5所示，所求最優(yōu)解分別如表6和表7(僅列5組)所示.

表5 合乘與非合乘模式的求解對比Table 5 The comparison of solutions between the shared and non-shared model

表6 合乘模式所求最優(yōu)解Table 6 The best solution solved in the shared model

表7 非合乘模式所求最優(yōu)解Table 7 The best solution solved in the non-shared model

由表6可知，本文模型能保證出租車將車上乘客送至目的地的同時，接送新的預約乘客，且出現合乘；由表7可知，在非合乘模式中，出租車均是先將車上乘客送至目的地，再接送其他預約乘客，不出現合乘；而由表5可知，與非合乘模式相比，合乘模式能服務更多乘客，節(jié)約總成本，充分說明本文模型求解出租車合乘問題的有效性.

3.4 模糊時間窗寬度的影響分析

改變模糊時間窗的寬度W，10次求解結果如表8所示.

表8 不同時間窗寬度下的模型求解對比Table 8 The comparison of solutions among models with various width of time window

由表8可知，模糊時間窗的寬度越大，總成本越小，平均服務乘客越多.因此，在實際運營時，獲取乘客的模糊時間要求，并通過一定措施放松其寬度，具有一定價值.

3.5 合乘意愿的影響分析

改變拒絕合乘的人數N，10次求解結果如表9所示.

表9 拒絕合乘人數不同的模型求解對比Table 9 The comparison results of various number of people rejecting to share a taxi

由表9可知，拒絕合乘的人數越多，總成本越大，平均服務乘客越少，說明接受合乘的人數越多，合乘模式越能節(jié)約成本，此外，考慮合乘意愿能提升乘客滿意度.因此，在實際運營時，了解合乘意愿，并通過一定措施激勵乘客接受合乘，也具有一定價值.

4 結論

為提高出租車的座位利用率，考慮模糊時間窗及合乘意愿，建立更切實際的出租車合乘模型，并設計改進的差分進化算法(ISDE)求解.該算法采用分段實數編碼，設計一種基于個體排序的縮放因子F與交叉概率CR，并提出混合輪盤賭的半貪婪選擇策略，使種群多樣性與收斂速度得到有效平衡.仿真結果表明，所構建的問題模型及改進的差分進化算法均為求解帶時間窗的多對多出租車合乘問題的有效方法，為后續(xù)研究奠定一定基礎.動態(tài)環(huán)境下的仿真、時間窗設置、合乘意愿的影響因素等問題，還需進一步深入研究.

[1]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.

[2]TAO C C.Dynamic taxi-sharing service using intelligent transportation system technologies[C]//International Conference on Wireless Communications,Networking and Mobile Computing.IEEE Xplore,2007:3209-3212.

[3]CORDEAU J-F.A branch-and-cut algorithm for the dial-a-ride problem[J].Operations Research,2006,54(3):573-586.

[4]HOSNI H,NAOUM-SAWAYA J,ARTAIL H.The shared-taxi problem: Formulation and solution methods[J].Transportation Research Part B:Methodological,2014(70):303-318.

[5]JUNG J,JAYAKRISHNAN R,PARK J Y.Dynamic shared-taxi dispatch algorithm with hybrid-simulated annealing[J].Computer-Aided Civil and Infrastructure Engineering,2016,31(4):275-291.

[6]劉家利,馬祖軍.存在車輛租賃及共享且有時間窗的多配送中心開環(huán)VRP[J].系統(tǒng)工程理論與實踐,2013,33(3):666-675.[LIU J L,MA Z J.Multi-depot open vehicle routing problem with time windows based on vehicle leasing and sharing[J].Systems Engineering-Theory&Practice,2013,33(3):666-675.]

[7]楊翔,范厚明,張曉楠,等.基于模糊時間窗的多中心開放式車輛路徑問題[J].計算機集成制造系統(tǒng),2016(7):1768-1778.[YANG X,FAN H M,LI X N.The multi centers and open vehicle routing problem based on fuzzy time window[J].Computer Integrated Manufacturing Systems,2016(7):1768-1778.]

[8]YE Q,MA C,HE R,et al.Multi-objective optimisation for taxi ridesharing route based on non-dominated sorting genetic algorithm[J].International Journal of Wireless&Mobile Computing,2015,8(3):262-270.

[9]程杰,唐智慧,劉杰,等.基于遺傳算法的動態(tài)出租車合乘模型研究[J].武漢理工大學學報(交通科學與工程版),2013(1):187-191.[CHENG J,TANG Z H,LIU J,et al.Research on the dynamic taxi sharing model based genetic algorithm[J].Journal of Wuhan University of Technology(Transportation Science Engineering),2013(1):187-191.]

[10]GONG W,CAI Z.Differential evolution with rankingbased mutation operators[J].IEEE Transactions on Cybernetics,2013,43(6):2066-2081.

[11]DAS S,SUGANTHAN P N.Differential evolution:A survey of the state-of-the-art[J].IEEE Transactions on Evolutionary Computation,2011,15(1):4-31.

[12]王海燕,趙燕偉,張景玲,等.基于混合差分進化的混排Flow-shop分批優(yōu)化調度[J].計算機集成制造系統(tǒng),2013(7):1613-1625.[WANG H Y,ZHAO Y W,ZHANG J L,et al.Batch optimized scheduling of intermingling flow-shop based on hybrid differential evolution algorithm[J].Computer Integrated Manufacturing Systems,2013(7):1613-1725.]