基于乘客出行偏好的網(wǎng)約車合乘模型研究

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

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

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

1引言

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

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

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

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

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

2. 1問題描述

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

2. 2假設(shè)條件

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

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

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

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

（5）忽略乘客的上車時間；

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

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

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

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

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

4. 1算法有效性評估

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

4. 2 模型有效性評估

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

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

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

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

5結(jié)語

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

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