摘要： 針對網(wǎng)約車合乘中忽視乘客繞行容忍度而導(dǎo)致合乘體驗(yàn)和意愿下降的問題，本文引入模糊繞行窗的概念，并將其與模糊時(shí)間窗相結(jié)合來量化乘客的個(gè)性化需求，構(gòu)建了一種能夠同時(shí)滿足乘客的上車時(shí)間偏好和繞行容忍度的網(wǎng)約車合乘模型. 該模型以最小化行駛距離、乘客費(fèi)用和懲罰函數(shù)為優(yōu)化目標(biāo)，綜合考慮乘客的繞行窗、時(shí)間窗以及車輛額定載客量等約束條件. 基于乘客公平性原則提出了一種費(fèi)率分?jǐn)偡椒ǎ瑢Τ丝偷馁M(fèi)用和駕駛員的收益進(jìn)行約束，實(shí)現(xiàn)司乘雙贏. 結(jié)合模型特點(diǎn)，設(shè)計(jì)了改進(jìn)的遺傳算法對優(yōu)化模型進(jìn)行求解. 實(shí)驗(yàn)結(jié)果表明，所得最優(yōu)合乘方案相較于單乘模式，承載的乘客數(shù)量提高了33. 3%，乘客的出行費(fèi)用降低了24. 3%，同時(shí)滿足了乘客的個(gè)性化需求.

關(guān)鍵詞： 合乘；遺傳算法；多目標(biāo)優(yōu)化；個(gè)性化需求

中圖分類號：TP301. 6 文獻(xiàn)標(biāo)志碼： A DOI：10. 19907/j. 0490-6756. 240227

1引言

為了緩解交通供需失衡及由此引起的交通擁堵，網(wǎng)約車合乘出行模式應(yīng)運(yùn)而生，滴滴、高德和美團(tuán)等網(wǎng)約車平臺(tái)都推出了拼車選項(xiàng). 網(wǎng)約車合乘有利于發(fā)揮網(wǎng)約車的平臺(tái)優(yōu)勢，有效整合車輛資源，既不失傳統(tǒng)出租車舒適便捷的優(yōu)勢，又能緩解交通壓力、降低出行成本，還能減少能源消耗、保護(hù)環(huán)境［1］. 然而網(wǎng)約車合乘模式也帶來了諸多挑戰(zhàn)，包括如何滿足乘客的個(gè)性化需求，如何分?jǐn)偤铣速M(fèi)用，如何優(yōu)化合乘路線等，這些挑戰(zhàn)使得網(wǎng)約車合乘模式的普及存在困難. 在這種前提下，有必要研究基于個(gè)性化需求的網(wǎng)約車合乘模型，并設(shè)計(jì)公平的費(fèi)用分?jǐn)偛呗?，以期更好地滿足乘客品質(zhì)化的出行需求，從而提高社會(huì)公眾的合乘意愿，有效推廣綠色共享出行模式.

網(wǎng)約車合乘問題，是傳統(tǒng)車輛路徑問題（VRP， Vehicle Routing Problem）的擴(kuò)展，涉及到較復(fù)雜的組合優(yōu)化，被證明屬于NP-Hard 問題［2］.針對該問題的優(yōu)化算法的研究一直保持較高的熱度，啟發(fā)式算法被廣泛用于車輛合乘模型的求解.如Beed 等［3］提出了一種混合的GA-A*算法，在遺傳算法的基礎(chǔ)上，利用啟發(fā)式搜索A*算法計(jì)算最短路徑，進(jìn)一步優(yōu)化最佳路徑選擇；Tamannaei等［4］提出了一種基于分枝定界算法和啟發(fā)式集束搜索算法的精確求解方法，最大限度地減少了行駛時(shí)間、車輛使用和車輛延誤的成本. 這些研究解決了合乘過程中的路徑規(guī)劃問題，但主要側(cè)重于提升算法的效率和性能，而未能在系統(tǒng)建模中考慮乘客的個(gè)性化偏好，從而影響到算法的實(shí)際應(yīng)用.

為提升用戶的乘車體驗(yàn)和服務(wù)質(zhì)量，近年來國內(nèi)外學(xué)者在網(wǎng)約車合乘問題的研究中考慮了用戶的出行偏好. Zhang 等［5］根據(jù)乘客的偏好需求構(gòu)建偏好列表，使用穩(wěn)定匹配算法選擇共乘對象. 劉文彬等［6］針對用戶之間的出行軌跡相似度和興趣偏好的相似性，篩選出滿足用戶偏好需求的車輛，并采用貪婪算法實(shí)現(xiàn)用戶與車輛的匹配. Thaithatkul等［7］研究了基于用戶偏好的一對一的乘客匹配策略，采用改進(jìn)的穩(wěn)定室友問題算法實(shí)現(xiàn)乘客之間的匹配. ?ak 等［8］將合乘問題表述為包含乘客各種偏好需求的多準(zhǔn)則數(shù)學(xué)規(guī)劃問題，并采用多目標(biāo)啟發(fā)式算法生成帕累托近似最優(yōu)解. 鄭建國等［9］考慮乘客的時(shí)間窗和合乘意愿，利用改進(jìn)的差分進(jìn)化算法實(shí)現(xiàn)乘客與車輛的匹配.

合乘往往需要繞路，導(dǎo)致行程時(shí)間延長，降低合乘服務(wù)對潛在乘客的吸引力［10］. 在研究合乘問題時(shí)，少數(shù)學(xué)者考慮了繞路的因素. Daganzo 等［11］建立了用戶需求的保證水平與匹配率、車輛行駛距離和用戶行駛路程的關(guān)系的分析模型，探討了繞行邊界對合乘服務(wù)性能的影響. 薛守強(qiáng)等［12］引入最大繞行時(shí)間約束，曹弋等［13］規(guī)定繞行里程不超過最短路徑的1. 6 倍. 這兩篇文獻(xiàn)對繞行進(jìn)行了統(tǒng)一的約束，不能滿足乘客對繞路的個(gè)性化需求. 崔洪軍等［14］根據(jù)乘客的共乘意愿和繞行偏差容忍度，查找滿足匹配要求的車輛，并利用插入算法獲得最優(yōu)共乘路徑. 該算法對繞行偏差容忍度進(jìn)行了簡單的約束，但沒有體現(xiàn)乘客個(gè)體對繞行偏差認(rèn)知的主觀性. 為了彌補(bǔ)現(xiàn)有研究的不足，本文首次在網(wǎng)約車合乘路徑優(yōu)化問題的研究中引入模糊繞行窗的概念，對乘客的繞行偏好進(jìn)行量化和區(qū)分，并結(jié)合模糊時(shí)間窗［15］來共同表述乘客的出行偏好，從而構(gòu)建個(gè)性化需求約束下的網(wǎng)約車合乘模型，實(shí)現(xiàn)在滿足乘客個(gè)性化偏好的前提下優(yōu)化車輛行駛里程，降低乘客的出行成本.

2問題描述與假設(shè)條件

2. 1問題描述

本文研究的網(wǎng)約車合乘問題為多對多的組織模式，即多個(gè)上車點(diǎn)對多個(gè)下車點(diǎn)，具體描述如下：某區(qū)域中有數(shù)名乘客，分別對應(yīng)一對上下車點(diǎn). 現(xiàn)有若干輛初始位置已知的網(wǎng)約車提供合乘服務(wù). 要求：①網(wǎng)約車到達(dá)乘客的時(shí)間具有模糊時(shí)間窗限制；② 網(wǎng)約車承載某乘客組的繞行距離具有模糊繞行窗限制；③網(wǎng)約車在提供服務(wù)過程中，載客人數(shù)不能超過該車的額定載客量. 在以上前提下，尋找合理的乘客與網(wǎng)約車匹配方案及網(wǎng)約車的行駛路線，將所有乘客從上車點(diǎn)送到下車點(diǎn)，同時(shí)實(shí)現(xiàn)網(wǎng)約車行駛距離最短，乘客的上車時(shí)間和繞路比滿意度最高，乘客的分?jǐn)傎M(fèi)用最低等目標(biāo).

2. 2假設(shè)條件

（1）每個(gè)乘客組的人數(shù)不大于網(wǎng)約車的額定載客量；

（2）每個(gè)乘客組被視為整體被一輛車服務(wù)一次，中間不能換乘、改變或取消行程；

（3）為簡化問題，假定每輛網(wǎng)約車均以固定的已知速度行駛，不存在影響行駛的情況發(fā)生；

（4）網(wǎng)約車不得故意繞行；

（5）忽略乘客的上車時(shí)間；

（6）所有乘客的接送位置、時(shí)間窗、繞行窗等條件已知且固定，所有網(wǎng)約車的初始位置已知.

2. 3參數(shù)和變量說明

模型中涉及到的集合、參數(shù)和變量等標(biāo)識(shí)符的定義如表1 所示：

3網(wǎng)約車合乘優(yōu)化模型

基于乘客出行偏好的網(wǎng)約車合乘模型總體研究框架如圖1 所示，分為乘客個(gè)性化偏好處理、模型構(gòu)建和算法設(shè)計(jì)三個(gè)部分. 乘客的個(gè)性化偏好包括上車時(shí)間偏好和繞行距離偏好，首先將這兩個(gè)指標(biāo)模糊化并進(jìn)行滿意度量化，以貼合乘客的主觀認(rèn)知，在此基礎(chǔ)上構(gòu)建多目標(biāo)優(yōu)化的網(wǎng)約車合乘優(yōu)化模型. 然后設(shè)計(jì)改進(jìn)的遺傳算法求解，從而獲得滿足乘客個(gè)性化需求的車輛與乘客的最優(yōu)匹配方案.

4. 1算法有效性評估

本文的運(yùn)行環(huán)境為 Inte（l R） Core（TM） i7-6700 CPU @ 3. 40GHz，Windows 7 操作系統(tǒng)，MatlabR2021a. 分別運(yùn)用雙種群遺傳算法和傳統(tǒng)的單種群遺傳算法進(jìn)行獨(dú)立實(shí)驗(yàn)，求解合乘和單乘模式下的最優(yōu)解. 雙種群算法的參數(shù)設(shè)置如表3 所示，傳統(tǒng)算法采用種群1 的參數(shù)設(shè)置. 由圖3 顯示的適應(yīng)度變化曲線可知，四種情況下的適應(yīng)度值都隨著迭代次數(shù)的增加而不斷下降，適應(yīng)度值越低，則目標(biāo)函數(shù)公式（26）的值越小. 相較于合乘模式，單乘模式由于沒有繞行懲罰費(fèi)用，收斂階段的適應(yīng)度值總體較低，同時(shí)由于約束條件相對較少，單乘模式下算法能更快地收斂到最優(yōu)值. 從求解效果來看，在合乘和單乘兩種模式下，雙種群算法都比單種群算法收斂更快，搜索最優(yōu)解的能力更強(qiáng)，說明了該算法的有效性和優(yōu)越性. 在后面的實(shí)驗(yàn)中，均采用雙種群算法求解.

4. 2 模型有效性評估

為了說明模型的有效性，針對以下3 種乘車模式分別使用雙種群算法編程求解：合乘A——兼顧乘客的繞行窗和時(shí)間窗約束；合乘B——僅考慮乘客的時(shí)間窗約束；單乘—— 每個(gè)乘客組獨(dú)享網(wǎng)約車，此時(shí)僅需考慮時(shí)間窗約束. 不同乘車模式的對比結(jié)果如表4～表8 所示.

4. 2. 1三種乘車模式的求解結(jié)果對比 3 種乘車模式下的最優(yōu)組合路徑如表4 所示，同時(shí)對3 種乘車模式下的最優(yōu)解進(jìn)行了對比，如表5 所示. 由以上兩表可知，合乘A 模式下，6 輛車可以為12 組乘客提供品質(zhì)較高的服務(wù)，平均繞行滿意度和平均時(shí)間滿意度都很高；合乘B 模式下，由于不考慮繞行窗的約束，僅5 輛車就可以為12 組乘客提供服務(wù)，但乘客的平均繞行滿意度僅為64%；而單乘模式下，6 輛車僅能為9 個(gè)乘客提供服務(wù)，平均繞行滿意度和平均時(shí)間滿意度均達(dá)到了100%. 可見，合乘A 模式能夠同時(shí)保證合乘乘客的繞行滿意度和時(shí)間滿意度. 與單乘模式相比，合乘A 模式下服務(wù)的乘客數(shù)量提高了33. 3%.

4. 2. 2不同合乘模式下乘客滿意度對比 表6 和表7 對合乘A 和合乘B 的每組乘客的時(shí)間滿意度和繞行滿意度進(jìn)行了對比. 表6 的數(shù)據(jù)顯示，兩種合乘模式下每組乘客的時(shí)間滿意度均超過了乘客期望的滿意度值. 由表7 的數(shù)據(jù)可知，合乘A 模式下每組乘客獲得了100% 的繞行滿意度，而合乘B模式下，4 個(gè)乘客組的繞行滿意度低于或等于10%，其中兩個(gè)乘客的滿意度為零. 可見，合乘B方案僅考慮乘客的時(shí)間偏好，不能滿足每個(gè)乘客的繞行容忍度需求，而本文提出的合乘A 方案能夠兼顧每個(gè)乘客個(gè)體的時(shí)間偏好和繞行偏好，較好地滿足乘客的個(gè)性化出行需求.

4. 2. 3不同乘車模式下乘客費(fèi)用與駕駛員收益對比 表8對比了不同乘車模式下駕駛員的收益與乘客的費(fèi)用. 可以看出合乘A 模式下每輛車的駕駛員收益均大于或等于單乘*模式下的收益，而小于或等于車輛單獨(dú)運(yùn)送每位乘客的費(fèi)用之和，即驗(yàn)證了公式（11）和（12）對駕駛員收益約束的有效性. 與單乘*模式相比，合乘A 模式下駕駛員的總收益增加了16. 9%. 在乘客的費(fèi)用方面，表8 的數(shù)據(jù)顯示合乘A 模式下每位乘客需支付的乘車費(fèi)用均小于或等于傳統(tǒng)單乘模式下的費(fèi)用，乘客的總費(fèi)用相較于單乘模式降低了24. 3%. 以上分析表明，本文提出的合乘方案能夠有效提高車輛資源的利用率，同時(shí)降低乘客的費(fèi)用，保障駕駛員的收益，從而實(shí)現(xiàn)乘客與駕駛員的雙贏，激發(fā)雙方參與合乘出行模式的積極性.

5結(jié)語

乘客的出行偏好具有個(gè)性化、多樣化的特點(diǎn)，本文對基于乘客個(gè)性化的網(wǎng)約車合乘問題展開研究，主要研究工作如下：首先引入繞行窗的概念描述乘客的繞行偏好，并兼顧乘客的時(shí)間偏好，采用模糊化的方法多角度刻畫乘客的出行需求，在此基礎(chǔ)上構(gòu)建四目標(biāo)優(yōu)化的網(wǎng)約車合乘模型；提出一種兼顧乘客成本與駕駛員收益的費(fèi)用分?jǐn)偛呗裕估@路多的乘客得到較高的費(fèi)用補(bǔ)償；基于遺傳算法，根據(jù)網(wǎng)約車合乘問題的特點(diǎn)設(shè)計(jì)改進(jìn)的遺傳算子，采用雙種群算法對優(yōu)化模型進(jìn)行求解.仿真結(jié)果表明所提模型和算法可以較快地搜索到近似最優(yōu)解，所得的乘車方案能夠在滿足乘客個(gè)性化需求的基礎(chǔ)上減少乘客的出行費(fèi)用，提高駕駛員的收益.

由于本文研究的個(gè)性化合乘問題涉及多約束條件下的多目標(biāo)尋優(yōu)，所提模型和算法較適用于小規(guī)模的合乘問題，如大學(xué)校園、大型社區(qū)、城市區(qū)域、農(nóng)村地區(qū)等環(huán)境下的網(wǎng)約車合乘. 研究成果對探索提供個(gè)性化的合乘服務(wù)，推廣共享出行模式具有理論意義和實(shí)用價(jià)值.