鄭建國(guó)，李園園

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

0 引言

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

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

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

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

綜上，鑒于當(dāng)前出租車(chē)合乘模型與實(shí)際偏離的情況，本文定義模糊時(shí)間窗，考慮合乘意愿，建立更切實(shí)際的問(wèn)題模型，并設(shè)計(jì)改進(jìn)的差分進(jìn)化算法求解，最后通過(guò)算例驗(yàn)證模型和算法的有效性.

1 基于模糊時(shí)間窗的出租車(chē)合乘問(wèn)題描述及建模

1.1 出租車(chē)合乘問(wèn)題描述

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

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

1.2 模糊時(shí)間窗

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

及時(shí)度為1時(shí)，懲罰費(fèi)用為0；及時(shí)度為0時(shí)，出租車(chē)因到達(dá)過(guò)早產(chǎn)生車(chē)輛等待成本μ，或過(guò)晚而產(chǎn)生客戶(hù)懲罰成本?；t超出原時(shí)間窗且在之內(nèi)時(shí)，產(chǎn)生相應(yīng)比例成本.時(shí)間懲罰費(fèi)用函數(shù)Lp(t)為

1.3 模型建立

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

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

2 基于個(gè)體排序的差分進(jìn)化算法設(shè)計(jì)

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

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

乘客分為車(chē)上和預(yù)約2種，故二進(jìn)制編碼無(wú)法直接應(yīng)用[8]；而以實(shí)數(shù)編碼、并用0間隔表示不同車(chē)輛[9]，計(jì)算復(fù)雜度增加，且在DE算法中會(huì)產(chǎn)生大量不可行解.因此，本文設(shè)計(jì)一種分段取值的實(shí)數(shù)編碼方案.

假設(shè)有m個(gè)車(chē)，s個(gè)預(yù)約乘客(上車(chē)點(diǎn)SO、下車(chē)點(diǎn) SD)，oi個(gè)車(chē)上乘客(下車(chē)點(diǎn) OD)，將個(gè)乘客節(jié)點(diǎn)以{SO，SD，OD}的順序編碼，個(gè)體可表示為

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

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

(2)解 碼.

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

Step 1根據(jù)SO的取值范圍1≤xi≤m+1為每個(gè)預(yù)約乘客分配車(chē)輛，如1≤xi≤2，即m=1，該乘客由車(chē)1服務(wù).

Step 2根據(jù)Step1的分配結(jié)果，將各車(chē)服務(wù)的乘客節(jié)點(diǎn)編號(hào)按從小到大的順序排列，構(gòu)成該車(chē)輛的可能路徑R1.應(yīng)注意，是否有乘客的下車(chē)點(diǎn)在其上車(chē)點(diǎn)之前，若有，則轉(zhuǎn)Step3；否則，轉(zhuǎn)Step4.

Step 3路徑調(diào)整，將下車(chē)點(diǎn)在上車(chē)點(diǎn)之前的乘客互換兩點(diǎn)位置，構(gòu)成路徑R2，轉(zhuǎn)step4.

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

Step 5按以上4個(gè)步驟完成所有車(chē)輛的路徑解碼，即構(gòu)成元胞矩陣P.

2.2 適應(yīng)度函數(shù)設(shè)計(jì)

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

2.3 算子設(shè)計(jì)

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

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

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

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

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

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

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

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

具體步驟為：

Step 1對(duì)第G代種群XG，執(zhí)行輪盤(pán)賭，產(chǎn)生新種群XG1.

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

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

算法步驟為：

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

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

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

Step 4對(duì)原種群進(jìn)行輪盤(pán)賭選擇產(chǎn)生新種群，以半貪婪的選擇方式產(chǎn)生新一代個(gè)體，詳見(jiàn)2.3節(jié)(3)所述.

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

算法流程如圖1所示.

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

3 實(shí)驗(yàn)結(jié)果及分析

3.1 測(cè)試算例

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

表1 出租車(chē)信息Table 1 The information of taxies

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

3.2 算法有效性分析

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

表3 算法參數(shù)設(shè)置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算法收斂較快，同時(shí)精度較優(yōu)，說(shuō)明該算法的優(yōu)越性.

表4 算法求解結(jié)果對(duì)比Table 4 The comparison of the algorithms solution results

3.3 模型有效性分析

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

表5 合乘與非合乘模式的求解對(duì)比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可知，本文模型能保證出租車(chē)將車(chē)上乘客送至目的地的同時(shí)，接送新的預(yù)約乘客，且出現(xiàn)合乘；由表7可知，在非合乘模式中，出租車(chē)均是先將車(chē)上乘客送至目的地，再接送其他預(yù)約乘客，不出現(xiàn)合乘；而由表5可知，與非合乘模式相比，合乘模式能服務(wù)更多乘客，節(jié)約總成本，充分說(shuō)明本文模型求解出租車(chē)合乘問(wèn)題的有效性.

3.4 模糊時(shí)間窗寬度的影響分析

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

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

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

3.5 合乘意愿的影響分析

改變拒絕合乘的人數(shù)N，10次求解結(jié)果如表9所示.

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

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

4 結(jié)論

為提高出租車(chē)的座位利用率，考慮模糊時(shí)間窗及合乘意愿，建立更切實(shí)際的出租車(chē)合乘模型，并設(shè)計(jì)改進(jìn)的差分進(jìn)化算法(ISDE)求解.該算法采用分段實(shí)數(shù)編碼，設(shè)計(jì)一種基于個(gè)體排序的縮放因子F與交叉概率CR，并提出混合輪盤(pán)賭的半貪婪選擇策略，使種群多樣性與收斂速度得到有效平衡.仿真結(jié)果表明，所構(gòu)建的問(wèn)題模型及改進(jìn)的差分進(jìn)化算法均為求解帶時(shí)間窗的多對(duì)多出租車(chē)合乘問(wèn)題的有效方法，為后續(xù)研究奠定一定基礎(chǔ).動(dòng)態(tài)環(huán)境下的仿真、時(shí)間窗設(shè)置、合乘意愿的影響因素等問(wèn)題，還需進(jì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]劉家利,馬祖軍.存在車(chē)輛租賃及共享且有時(shí)間窗的多配送中心開(kāi)環(huán)VRP[J].系統(tǒng)工程理論與實(shí)踐,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]楊翔,范厚明,張曉楠,等.基于模糊時(shí)間窗的多中心開(kāi)放式車(chē)輛路徑問(wèn)題[J].計(jì)算機(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]程杰,唐智慧,劉杰,等.基于遺傳算法的動(dòng)態(tài)出租車(chē)合乘模型研究[J].武漢理工大學(xué)學(xué)報(bào)(交通科學(xué)與工程版),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]王海燕,趙燕偉,張景玲,等.基于混合差分進(jìn)化的混排Flow-shop分批優(yōu)化調(diào)度[J].計(jì)算機(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.]