考慮最優(yōu)會(huì)面位置的多車型拼車優(yōu)化調(diào)度模型

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

（1.上海理工大學(xué) 管理學(xué)院，上海200093；2.上海理工大學(xué)超網(wǎng)絡(luò)研究中心，上海200093；3.青島市城市規(guī)劃設(shè)計(jì)研究院，山東青島266000)

0 引言

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

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

1 相關(guān)研究

目前，國(guó)內(nèi)外在網(wǎng)約車合乘模型構(gòu)建方面，眾多研究主要考慮目標(biāo)函數(shù)和約束條件對(duì)模型的影響且已經(jīng)有了一定的成果。而就優(yōu)化目標(biāo)而言主要集中于優(yōu)化運(yùn)營(yíng)成本目標(biāo)和服務(wù)質(zhì)量目標(biāo)，許多關(guān)于合乘模型的目標(biāo)函數(shù)都是優(yōu)化單個(gè)運(yùn)營(yíng)成本，也有部分文獻(xiàn)考慮了運(yùn)營(yíng)成本和服務(wù)質(zhì)量相結(jié)合的多目標(biāo)系統(tǒng)。在單目標(biāo)優(yōu)化模型中，為了確保能滿足客戶所需的最低服務(wù)水平服務(wù)質(zhì)量因素通常以約束條件出現(xiàn)。例如在Wolfler Calvo的文章中，以合乘的總出行時(shí)間最短建立目標(biāo)函數(shù)，但對(duì)未提供服務(wù)的請(qǐng)求設(shè)置了懲罰函數(shù)，在這種情況下，需要較大幅度地?cái)U(kuò)展合乘的服務(wù)范圍以滿足客戶需求。一些研究考慮了以最大化合乘總利潤(rùn)或者最小化DARP運(yùn)營(yíng)總成本為目標(biāo)建立模型。除此之外，還有不少文獻(xiàn)考慮了一些更具體的問(wèn)題作為目標(biāo)，Guerriero等人以所需車輛最少為目標(biāo)，Atahran等人以車輛排放量最小為目標(biāo)，Garaix等人以最大化客戶乘坐率為目標(biāo)構(gòu)建模型。

綜合以上分析，目前國(guó)內(nèi)外對(duì)網(wǎng)約車合乘模型的研究大多數(shù)是考慮單一車型下司機(jī)和客戶會(huì)面位置確定的合乘模式，并在此基礎(chǔ)上考慮時(shí)間窗等約束，而在模型研究中還沒(méi)有相關(guān)文獻(xiàn)將車輛類型和最優(yōu)會(huì)面位置作為約束條件進(jìn)行綜合考慮。一方面，以往研究中沒(méi)有加入對(duì)不確定性會(huì)面地點(diǎn)因素的考慮；另一方面，單一車型的合乘不能滿足網(wǎng)約車平臺(tái)規(guī)模的發(fā)展需要以及客戶的多元化需求，現(xiàn)實(shí)中用于合乘的網(wǎng)約車車輛類型也趨于多樣化，而且不同車型的車輛各特征都不相同，對(duì)合乘過(guò)程也造成了不容忽視的影響，因此需要構(gòu)建新的模型。本文以后疫情時(shí)代為背景，以DARP模型作為基本模型，以運(yùn)輸總成本為目標(biāo)建立基于車型類別考慮最優(yōu)會(huì)面位置的網(wǎng)約車合乘優(yōu)化模型。

2 問(wèn)題描述

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

如MVDARP-M場(chǎng)景圖（見圖1）所示，網(wǎng)約車平臺(tái)存在多種類型的車輛提供合乘服務(wù)，均從車輛的出發(fā)節(jié)點(diǎn)駛出，然后為客戶1、2和3提供服務(wù)，而客戶1、2和3均存在三個(gè)不同的出發(fā)節(jié)點(diǎn)和目的地節(jié)點(diǎn)，圖1中網(wǎng)約車平臺(tái)提供了兩種類型的車輛。車型1車輛從起始節(jié)點(diǎn)出發(fā)為客戶1和2提供服務(wù)，并分別在客戶1和客戶2的所有出發(fā)節(jié)點(diǎn)中選擇其中一個(gè)作為客戶實(shí)際的上車位置，再將所有客戶送往各自相對(duì)應(yīng)的目的地之后車輛駛?cè)肽康牡毓?jié)點(diǎn)；車型2車輛從起始節(jié)點(diǎn)出發(fā)為客戶3提供接送服務(wù)。

圖1 MVDARP-M場(chǎng)景圖

3 模型建立

3.1 模型的假設(shè)

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

3.2 模型符號(hào)說(shuō)明

（1）集 合

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

S=｛1,… ,n｝為客戶的上車節(jié)點(diǎn)集合；

D=｛n+1,…,2n｝為客戶的下車節(jié)點(diǎn)集合；

Z=｛1,… ,m｝為集合N中各節(jié)點(diǎn)所對(duì)應(yīng)的可選擇的節(jié)點(diǎn)集合；

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

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

（2）參 數(shù)

L為客戶的最大乘車時(shí)間；

M為k類型車輛產(chǎn)生的單位固定成本；

C為k類型車輛的單位運(yùn)輸成本；

Q為k類型車輛車型系數(shù)，車型越大，車型系數(shù)越大；

o節(jié)點(diǎn)p的第i個(gè)節(jié)點(diǎn)的客戶能接受的最大車型系數(shù)；

f為車輛提前到達(dá)客戶點(diǎn)時(shí)產(chǎn)生的單位時(shí)間懲罰成本；

f為車輛延遲到達(dá)客戶點(diǎn)時(shí)產(chǎn)生的單位時(shí)間懲罰成本；

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

T為k類型車輛行駛路線的最大總時(shí)長(zhǎng)；

d為車輛在節(jié)點(diǎn)p的第i個(gè)節(jié)點(diǎn)的服務(wù)持續(xù)時(shí)間，p∈N，i∈Z；

W為車輛在節(jié)點(diǎn)p的第i個(gè)節(jié)點(diǎn)的載重量；

e為節(jié)點(diǎn)p所對(duì)應(yīng)的第i個(gè)節(jié)點(diǎn)的客戶期望最早服務(wù)時(shí)間；

l為節(jié)點(diǎn)p所對(duì)應(yīng)的第i個(gè)節(jié)點(diǎn)的客戶期望最晚服務(wù)時(shí)間；

ee為節(jié)點(diǎn)p所對(duì)應(yīng)的第i個(gè)節(jié)點(diǎn)的客戶可接受的最早服務(wù)時(shí)間；

ll為節(jié)點(diǎn)p所對(duì)應(yīng)的第i個(gè)節(jié)點(diǎn)的客戶可接受的最晚服務(wù)時(shí)間；

t為節(jié)點(diǎn)p的第i個(gè)節(jié)點(diǎn)到節(jié)點(diǎn)q的第j個(gè)節(jié)點(diǎn)的行駛時(shí)間；

D為節(jié)點(diǎn)p的第i個(gè)節(jié)點(diǎn)到節(jié)點(diǎn)q的第j個(gè)節(jié)點(diǎn)的距離。

（3）變 量

3.3 目標(biāo)函數(shù)說(shuō)明

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

3.4 模型建立

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

4 算例分析

4.1 算例描述

假設(shè)在上海市某一路網(wǎng)中已知存在86個(gè)節(jié)點(diǎn)位置。其中有兩個(gè)節(jié)點(diǎn)分別作為所有服務(wù)車輛的出發(fā)節(jié)點(diǎn)和目的地節(jié)點(diǎn)，客戶的所有節(jié)點(diǎn)共有84個(gè)。平臺(tái)提供三種類型的車輛供客戶選擇，且每種車型有2輛車可提供服務(wù)。在該路網(wǎng)中共有14個(gè)客戶發(fā)出請(qǐng)求，且每個(gè)客戶各自都對(duì)應(yīng)三個(gè)不同的節(jié)點(diǎn)供選擇。本文用［0,40］×［0,4 0］的矩形區(qū)域來(lái)表示該路網(wǎng)范圍，車輛和客戶的所有節(jié)點(diǎn)位置都隨機(jī)且獨(dú)立的均勻分布在該區(qū)域內(nèi)。各種車型的單位運(yùn)輸成本、固定使用成本、車型系數(shù)、車輛數(shù)以及最大載重量如表1所示，各節(jié)點(diǎn)位置坐標(biāo)以及時(shí)間窗要求、車型系數(shù)要求、需求量要求等如表2和表3所示。

表1 各車型的車輛參數(shù)

表2 各節(jié)點(diǎn)位置坐標(biāo)

表3 各節(jié)點(diǎn)特征數(shù)據(jù)

4.2 算例結(jié)果

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

表4 最優(yōu)合乘方案

4.3 方案對(duì)比分析

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

表5 未優(yōu)化合乘方案1

表6 未優(yōu)化合乘方案2

相較于未優(yōu)化的合乘方案，考慮最優(yōu)會(huì)面位置的多車型網(wǎng)約車合乘最優(yōu)方案的總運(yùn)輸成本分別節(jié)省了177.8元、371.86元，總行駛距離分別減少97.70公里、174.24公里，即成本費(fèi)用率分別降低20.30%、42.45%，行駛距離分別降低18.17%、32.40%。而且在網(wǎng)約車實(shí)際的合乘方案中，因?yàn)榭蛻舻攸c(diǎn)的不確定性容易產(chǎn)生客戶找不到司機(jī)或者司機(jī)找不到客戶的情況，從而可能造成實(shí)際成本和行駛距離的進(jìn)一步增加。所以優(yōu)化方案極大可能比現(xiàn)實(shí)的合乘方案更有優(yōu)勢(shì)，不僅能在一定程度上減少車輛行駛距離，而且較大幅度地減少了總運(yùn)輸成本。通過(guò)對(duì)比分析表明，本文得到的優(yōu)化方案能夠?yàn)槠脚_(tái)產(chǎn)生一定的經(jīng)濟(jì)效益且是合理有效的，進(jìn)一步說(shuō)明本文所構(gòu)建的基于車型類別考慮最優(yōu)會(huì)面位置的網(wǎng)約車合乘優(yōu)化模型的有效性，能夠?yàn)閷?shí)際的網(wǎng)約車合乘問(wèn)題提供參考價(jià)值。

5 結(jié)論

在后疫情時(shí)代的大背景下，本文基于DARP問(wèn)題，提出了所要研究的網(wǎng)約車合乘問(wèn)題MVDARP-M，并綜合考慮了網(wǎng)約車車輛的運(yùn)輸成本、固定成本以及時(shí)間懲罰成本建立了基于車型類別考慮最優(yōu)會(huì)面位置的網(wǎng)約車合乘優(yōu)化模型。將多車型的網(wǎng)約車合乘優(yōu)化方案分別與單一車型且未選擇客戶最優(yōu)接送位置的三個(gè)方案的運(yùn)輸總成本及運(yùn)輸總距離進(jìn)行對(duì)比，驗(yàn)證了模型的適用性和有效性，可為疫情下的合乘車輛路徑優(yōu)化和網(wǎng)約車平臺(tái)調(diào)配車輛提供理論依據(jù)。基于本文所研究的是多車型的合乘優(yōu)化且僅考慮燃油車，而新能源汽車的崛起越來(lái)越受到人們的關(guān)注，而在實(shí)際情況中，電動(dòng)汽車正不斷加入到網(wǎng)約車的隊(duì)伍中。因此在車型中加入新能源汽車對(duì)合乘的影響可考慮作為下一步的研究方向。