考慮最優會面位置的多車型拼車優化調度模型

胡忠愷，袁鵬程,2，高洪振

（1.上海理工大學 管理學院，上海200093；2.上海理工大學超網絡研究中心，上海200093；3.青島市城市規劃設計研究院，山東青島266000)

0 引言

近年來，Uber、Aribnb等一系列共享平臺逐漸出現在人們的視野中，“共享經濟”熱潮不斷襲來。而在此背景下網約車合乘已成為共享經濟發展中一種主流的交通出行方式，雖然一般情況下合乘可以滿足客戶門到門的出行需求，但客戶因司機未在其期望的會面位置進行接送而造成滿意度大打折扣的情況時有發生。因為道路交通安全法對于車輛臨時停車有一定的規定，司機極有可能因為違停面臨交通處罰從而增加不必要的支出。而新冠疫情的爆發加劇了此類現象的發生，疫情期間各地社區紛紛采取科學合理的防控措施，部分社區合并成一個大的社區實施封閉式管理，原則上只保留幾個進出通道。由于司機屬于社區外人員不能直接進入社區接送客戶，所以只能在社區外選擇某一位置與客戶會面，客戶和司機需要在進出口附近尋求一個最佳的地點作為實際的會面點，從而不僅能保證客戶對會面位置的要求也能避免會面位置的不佳選擇導致的司機過多繞路、客戶等待時間過長等問題。

而隨著網約車平臺的不斷發展與完善，越來越多的車型加入到網約車的隊伍中，常見的網約車類型有：緊湊車、中級車、豪華車、SUV等，一般是5~7座的小型載客車輛，而不同類型的車輛所對應的車輛燃油費等都各不相同。因此網約車平臺在派出車輛為客戶提供服務前通常會考慮車輛類型對成本所造成的影響，并在滿足客戶要求的前提下盡量降低成本以達到利益最大化。綜上所述，將最優會面位置和多車型因素結合起來考慮對網約車合乘來說是至關重要的。

1 相關研究

目前，國內外在網約車合乘模型構建方面，眾多研究主要考慮目標函數和約束條件對模型的影響且已經有了一定的成果。而就優化目標而言主要集中于優化運營成本目標和服務質量目標，許多關于合乘模型的目標函數都是優化單個運營成本，也有部分文獻考慮了運營成本和服務質量相結合的多目標系統。在單目標優化模型中，為了確保能滿足客戶所需的最低服務水平服務質量因素通常以約束條件出現。例如在Wolfler Calvo的文章中，以合乘的總出行時間最短建立目標函數，但對未提供服務的請求設置了懲罰函數，在這種情況下，需要較大幅度地擴展合乘的服務范圍以滿足客戶需求。一些研究考慮了以最大化合乘總利潤或者最小化DARP運營總成本為目標建立模型。除此之外，還有不少文獻考慮了一些更具體的問題作為目標，Guerriero等人以所需車輛最少為目標，Atahran等人以車輛排放量最小為目標，Garaix等人以最大化客戶乘坐率為目標構建模型。

綜合以上分析，目前國內外對網約車合乘模型的研究大多數是考慮單一車型下司機和客戶會面位置確定的合乘模式，并在此基礎上考慮時間窗等約束，而在模型研究中還沒有相關文獻將車輛類型和最優會面位置作為約束條件進行綜合考慮。一方面，以往研究中沒有加入對不確定性會面地點因素的考慮；另一方面，單一車型的合乘不能滿足網約車平臺規模的發展需要以及客戶的多元化需求，現實中用于合乘的網約車車輛類型也趨于多樣化，而且不同車型的車輛各特征都不相同，對合乘過程也造成了不容忽視的影響，因此需要構建新的模型。本文以后疫情時代為背景，以DARP模型作為基本模型，以運輸總成本為目標建立基于車型類別考慮最優會面位置的網約車合乘優化模型。

2 問題描述

基于車輛類型考慮最優會面位置的網約車合乘優化問題可描述為：現有網約車平臺派出一定數量不同車型的車輛提供合乘服務，已知有一定數量的客戶發出合乘請求以及每個客戶的需求量和其所能接受的合乘最大車型，各客戶向平臺提供能接受的多個會面位置供司機選擇其中一個地點作為真實會面點。因此每個客戶各自相對應的多個可能的接送位置中只能有一個接送位置被且只被訪問一次，即每一個客戶應由同一輛車為其完成合乘服務。每輛車所訪問的客戶需求總和不能超出車輛的最大負載能力，并要求車輛對每個客戶的服務時間必須在其要求的時間范圍內開始。目標是在所有的約束條件被滿足的情況下，盡可能找到最科學合理的車輛使用方案、車輛行駛路徑以及車輛訪問客戶的先后順序，保證車輛以最小的運輸總成本完成合乘任務。

如MVDARP-M場景圖（見圖1）所示，網約車平臺存在多種類型的車輛提供合乘服務，均從車輛的出發節點駛出，然后為客戶1、2和3提供服務，而客戶1、2和3均存在三個不同的出發節點和目的地節點，圖1中網約車平臺提供了兩種類型的車輛。車型1車輛從起始節點出發為客戶1和2提供服務，并分別在客戶1和客戶2的所有出發節點中選擇其中一個作為客戶實際的上車位置，再將所有客戶送往各自相對應的目的地之后車輛駛入目的地節點；車型2車輛從起始節點出發為客戶3提供接送服務。

圖1 MVDARP-M場景圖

3 模型建立

3.1 模型的假設

通過對本文所研究問題的描述，為建立模型需要作出以下假設：任意兩節點之間的距離為點到點之間的最短運輸距離，所有類型車輛在運輸過程中均勻速行駛，不考慮交通堵塞、交叉口紅綠燈、車輛損壞以及其他特殊情況的影響；所有車型的屬性都是已知的，包括車輛載重量、運輸成本、使用成本等；所有客戶的需求量以及客戶所能接受的最大車型已知；各客戶的所有節點位置以及服務時間要求已知；每輛車可以為多名客戶提供服務，但每名乘客只能由一輛車完成服務，且服務期間不允許出現換乘的情況。

3.2 模型符號說明

（1）集 合

N=S∪D∪｛0,2n+1｝為節點集合，其中0表示車輛的起始節點，2n+1表示車輛的目的節點；

S=｛1,… ,n｝為客戶的上車節點集合；

D=｛n+1,…,2n｝為客戶的下車節點集合；

Z=｛1,… ,m｝為集合N中各節點所對應的可選擇的節點集合；

K=｛1,… ,k｝為車輛類型集合；

G=｛1,… ,g｝為k類型車輛的集合。

（2）參 數

L為客戶的最大乘車時間；

M為k類型車輛產生的單位固定成本；

C為k類型車輛的單位運輸成本；

Q為k類型車輛車型系數，車型越大，車型系數越大；

o節點p的第i個節點的客戶能接受的最大車型系數；

f為車輛提前到達客戶點時產生的單位時間懲罰成本；

f為車輛延遲到達客戶點時產生的單位時間懲罰成本；

Q為k類型車輛的最大載重量；

T為k類型車輛行駛路線的最大總時長；

d為車輛在節點p的第i個節點的服務持續時間，p∈N，i∈Z；

W為車輛在節點p的第i個節點的載重量；

e為節點p所對應的第i個節點的客戶期望最早服務時間；

l為節點p所對應的第i個節點的客戶期望最晚服務時間；

ee為節點p所對應的第i個節點的客戶可接受的最早服務時間；

ll為節點p所對應的第i個節點的客戶可接受的最晚服務時間；

t為節點p的第i個節點到節點q的第j個節點的行駛時間；

D為節點p的第i個節點到節點q的第j個節點的距離。

（3）變 量

3.3 目標函數說明

本文所構建模型的目標函數是在疫情背景下實現網約車合乘的運輸總成本最小，由于本文考慮的問題是多車型合乘研究，因此不同車型車輛都有各自不同的固定使用成本和單位距離運輸成本。而運輸成本包括三部分：第一部分是車輛的固定使用成本，由公式（1）表示；第二部分是車輛的運輸成本，由公式（2）表示；第三部分是車輛的時間懲罰成本，由公式（3）表示。

3.4 模型建立

其中：式（4）為目標函數即總成本最小化。式（5）至式（27）為約束條件。其中式（5）表示每個發出合乘請求的用戶恰好被服務一次；式（6）表示同一輛車訪問客戶的出發節點和其對應的目的節點；式（7）表示不允許車輛先訪問客戶的目的節點，再訪問客戶的出發節點；式（8）至式（10）表示提供合乘服務的車輛從車輛的出發節點開始，到車輛的目的地節點結束；式（11）表示車輛在服務過程中不允許訪問車輛的出發節點；式（12）表示車輛到達車輛的目的地節點后不會再駛出提供服務，即服務車輛最終都會停在車輛的目的地節點；式（13）表示車輛從車輛的出發節點后必須先訪問某客戶的出發節點再訪問該客戶的目的地節點；式（14）表示車輛不允許從客戶的出發節點直接訪問車輛的目的地節點；式（15）表示車輛是否訪問某個節點；式（16）表示任意車型的服務車輛使用數不超過該車型總的車輛數；式（17）表示服務車輛的車型系數要小于或等于所服務客戶點的最大車型系數；式（18）和式（19）分別表示時間的一致性和負載變量的一致性，其中H是一個非常大的常數；式（20）為每個客戶在車輛k上的乘車時間，并且該時間會受到式（23）的約束，而式（23）也被用作優先約束，式（21）限制了每輛車行駛路徑的總時長；式（22）表示車輛需在客戶要求時間窗內提供服務；式（24）為各類型車輛的容量約束；式（25）為懲罰函數的表達式；式（26）和式（27）表示決策變量為0~1變量。

4 算例分析

4.1 算例描述

假設在上海市某一路網中已知存在86個節點位置。其中有兩個節點分別作為所有服務車輛的出發節點和目的地節點，客戶的所有節點共有84個。平臺提供三種類型的車輛供客戶選擇，且每種車型有2輛車可提供服務。在該路網中共有14個客戶發出請求，且每個客戶各自都對應三個不同的節點供選擇。本文用［0,40］×［0,4 0］的矩形區域來表示該路網范圍，車輛和客戶的所有節點位置都隨機且獨立的均勻分布在該區域內。各種車型的單位運輸成本、固定使用成本、車型系數、車輛數以及最大載重量如表1所示，各節點位置坐標以及時間窗要求、車型系數要求、需求量要求等如表2和表3所示。

表1 各車型的車輛參數

表2 各節點位置坐標

表3 各節點特征數據

4.2 算例結果

基于上文表中給出的節點和各車型數據利用Lingo18.0軟件求解本文構建的MVDARP-M模型，將計算結果進行整理得到的最優接送方案和合乘路徑如表4所示。由表4可知，共需六輛車完成合乘服務，即派出三種不同車型的車輛各兩輛，總行駛距離為537.75公里，總運輸費用為875.90元，并形成六條合乘路徑。

表4 最優合乘方案

4.3 方案對比分析

上述算例是在車型不同且車輛數有限的情況下得到的最優合乘方案，并且選擇最優的會面位置提供合乘服務。為了驗證該方案的優化效果，將該優化方案與未考慮最優會面位置的合乘情況進行對比分析，給出未考慮最優會面位置的合乘方案如表5、表6所示。未優化方案是在所有基本數據保持不變的情況下滿足各約束條件，并在每個客戶所有可能的接送位置中分別隨機選擇會面地點而得到的合乘路徑。從表5、表6可以看出未優化方案仍是提供三種車型的情形下得到的合乘方案，且未對會面位置進行最優的選擇。未優化合乘方案1中，平臺派出六輛車提供服務并形成六條路徑。未優化方案1中車輛總運輸成本為1 053.70元，總行駛距離為635.45公里，未優化方案2中車輛總運輸成本為1 247.76元，總行駛距離為711.99公里。具體的合乘路徑以及各類成本等數據如表5、表6所示。

表5 未優化合乘方案1

表6 未優化合乘方案2

相較于未優化的合乘方案，考慮最優會面位置的多車型網約車合乘最優方案的總運輸成本分別節省了177.8元、371.86元，總行駛距離分別減少97.70公里、174.24公里，即成本費用率分別降低20.30%、42.45%，行駛距離分別降低18.17%、32.40%。而且在網約車實際的合乘方案中，因為客戶地點的不確定性容易產生客戶找不到司機或者司機找不到客戶的情況，從而可能造成實際成本和行駛距離的進一步增加。所以優化方案極大可能比現實的合乘方案更有優勢，不僅能在一定程度上減少車輛行駛距離，而且較大幅度地減少了總運輸成本。通過對比分析表明，本文得到的優化方案能夠為平臺產生一定的經濟效益且是合理有效的，進一步說明本文所構建的基于車型類別考慮最優會面位置的網約車合乘優化模型的有效性，能夠為實際的網約車合乘問題提供參考價值。

5 結論

在后疫情時代的大背景下，本文基于DARP問題，提出了所要研究的網約車合乘問題MVDARP-M，并綜合考慮了網約車車輛的運輸成本、固定成本以及時間懲罰成本建立了基于車型類別考慮最優會面位置的網約車合乘優化模型。將多車型的網約車合乘優化方案分別與單一車型且未選擇客戶最優接送位置的三個方案的運輸總成本及運輸總距離進行對比，驗證了模型的適用性和有效性，可為疫情下的合乘車輛路徑優化和網約車平臺調配車輛提供理論依據?；诒疚乃芯康氖嵌嘬囆偷暮铣藘灮覂H考慮燃油車，而新能源汽車的崛起越來越受到人們的關注，而在實際情況中，電動汽車正不斷加入到網約車的隊伍中。因此在車型中加入新能源汽車對合乘的影響可考慮作為下一步的研究方向。