何勝學(xué) 程 龍 陳經(jīng)緯 杭佳宇

(上海理工大學(xué)管理學(xué)院 上海 200093)

0 引 言

車輛合乘一般將現(xiàn)實中司乘匹配時所考慮的時間、起訖點、費(fèi)用限制等作為約束，以消耗最小出行成本滿足最多的出行需求為目標(biāo)建立模型[1].車輛合乘模型廣泛應(yīng)用于殘疾人和老年人的門對門接送[2]或是校車路線規(guī)劃[3].現(xiàn)在隨著“共享”理念推廣及移動智能終端的普及，車輛合乘進(jìn)一步發(fā)展為出租車合乘[4]與通勤車輛合乘[5].通過對比合乘和公交的效用差值，畢笑天等[6]對市民出行方式選擇進(jìn)行研究，確定了合乘出行和公交出行的選擇依據(jù).在假設(shè)司機(jī)在新模式下可以以一定代價“購買”其他司機(jī)的乘客條件下，Roger等[7]對司乘匹配FCFS(first-come, first-served)模式進(jìn)行了改進(jìn)，發(fā)現(xiàn)加入乘客交換機(jī)制后，整個合乘系統(tǒng)的服務(wù)水平得到顯著提高.聶昌成等[8]以寧波市為例提出了基于電召平臺的出租車合乘模式，并對此合乘模式中的乘客運(yùn)送以及計費(fèi)和收益進(jìn)行了初步分析.

國內(nèi)外學(xué)者對車輛合乘路徑規(guī)劃、費(fèi)率、車輛調(diào)度以及模型算法等領(lǐng)域[9-12]研究較多，較少涉及乘客的合乘偏好等行為決策研究.現(xiàn)實中乘客出于安全等因素的考慮會對合乘者性別進(jìn)行選擇，進(jìn)而考慮選擇是否進(jìn)行合乘.Yan等[13]在使用時空網(wǎng)絡(luò)處理出租車的路徑規(guī)劃問題時，將出租車分為普通出租車和只接受女乘客出租車，更加貼近現(xiàn)實中乘客對出租車安全性的需求.程杰等[14]以出租車合乘為背景建立動態(tài)車輛合乘模型，并在模型中將出租車和乘客進(jìn)行了劃分，以性別作為車輛和乘客匹配的依據(jù).但上述文獻(xiàn)僅考慮固定的乘客組劃分，沒有考慮現(xiàn)實合乘中存在不同的性別合乘需求以及乘客性別占比變化對合乘匹配效果的影響.針對上述問題，文章對通勤車輛合乘匹配中乘客性別因素的影響進(jìn)行深入研究.

1 模型說明

1.1 參數(shù)說明

z(i,J,(k,g))為司機(jī)i與乘客組J可行匹配，通勤乘客上車點和下車點為(k,g)；z0為司機(jī)不進(jìn)行合乘；Z為所有匹配集合.當(dāng)司機(jī)i與乘客組J滿足匹配約束時，即z(i,J,(k,g))匹配成功時會產(chǎn)生一組數(shù)據(jù)(υz,σz)；υz為此次合乘匹配中參與的司機(jī)與乘客總?cè)藬?shù)；σz為合乘給通勤走廊中帶來的機(jī)動車行駛距離優(yōu)化值，σz=doidi-(doik+dkg+dgdi)+∑j∈J(dojdj-(dojk+dgdj)).式中：doidi-(dk+dkg+dgdi)為司機(jī)i在合乘過程中產(chǎn)生的繞行距離；dojdj-(dojk+dgdj)為乘客j參與合乘后走廊中機(jī)動車行駛距離優(yōu)化值.如果σz>0，則表示進(jìn)行z(i,J,(k,g))匹配時合乘使得通勤走廊中機(jī)動車行駛距離優(yōu)化值為正，此次合乘是有意義的.

1.2 目標(biāo)函數(shù)

一般可考慮如下通勤合乘匹配的優(yōu)化目標(biāo)：①方便通勤者在通勤時段出行，即使得通勤時間段內(nèi)走廊中最多的司機(jī)和乘客(υ值)參與到合乘中來;②最大程度的緩解通勤走廊中交通壓力，即使通勤走廊中機(jī)動車行駛距離優(yōu)化值(σ值)最大.

對應(yīng)上述目標(biāo)建立的兩個目標(biāo)函數(shù)為

(1)

(2)

式中：xiz和xjz為司機(jī)與乘客匹配的0-1決策變量.當(dāng)司機(jī)i進(jìn)行z(i,J,(k,g))匹配時，xiz取1；反之xiz取0.當(dāng)乘客j∈J進(jìn)行z(i,J,(k,g))匹配時，xjz取1；反之xjz取0；Jz為z匹配中所有參與乘客的集合；υz為此次z合乘參與的人數(shù)，包括司機(jī)與所有乘客.

式(1)和(2)分別為模型的目標(biāo)是通勤合乘參與者數(shù)值最大和通勤走廊中機(jī)動車行駛距離優(yōu)化值最大.

1.3 約束條件

模型基本約束為

≤Ci

(3)

(4)

toik+τ+tkg+tgdi≤Ti

(5)

(6)

(7)

(8)

(9)

現(xiàn)實中乘客在與其他合乘者合乘時，會出于自身安全等原因考慮對其他合乘者的性別進(jìn)行選擇.為了全面的描述合乘性別模式，下面針對不同模式下乘客的性別合乘偏好給出相應(yīng)的模型約束條件.

第一種合乘模式為偏好同性乘客之間進(jìn)行合乘.假設(shè)在這種合乘模式下通勤乘客只偏好和同性的乘客進(jìn)行合乘.上述偏好同性合乘的模式可表示為

,?z∈Z,Jz∈zm,

?z∈Z,Jz∈z

(10)

(11)

(12)

(13)

(14)

(15)

當(dāng)乘客組J中僅有一位乘客時，此乘客不受性別合乘模式的約束，此時βJ取值為1，對應(yīng)約束如下式.

(16)

當(dāng)對乘客組內(nèi)乘客性別是否滿足合乘模式進(jìn)行判斷后，模型需要對滿足匹配要求的乘客組和通勤司機(jī)進(jìn)行決策變量賦值.即當(dāng)乘客組滿足性別合乘模式要求或乘客組內(nèi)容忍系數(shù)不小于控制系數(shù)時，對應(yīng)參數(shù)xiz和xjz賦值為1；否則賦值為0.約束如下式.

(17)

(18)

,?i∈D

(19)

(20)

(21)

式(19)為模型中任意司機(jī)只能參與到一個合乘匹配中，包括z0.式(20)為模型中任意乘客j只能參與一個匹配中即∑z∈Zxjz=1或不參與匹配即∑z∈Zxjz=0.式(21)為對于?z∈Z，只有匹配z中所有的乘客參與者都參與到z匹配中時，匹配z才是有效的.其中xiz和xiz分別為0-1決策變量.

2 求解算法

司乘匹配約束中有非線性約束條件，因此所建通勤匹配模型為非線性整數(shù)規(guī)劃模型.以通勤中合乘匹配的具體實現(xiàn)過程為基礎(chǔ)，本文設(shè)計一種求解上述模型的啟發(fā)式求解算法.新算法首先確定可行匹配集，然后計算各匹配相關(guān)特征量，最后利用分層法確定最佳合乘匹配.新算法不僅可以有效處理模型的非線性約束，而且實現(xiàn)的復(fù)雜度較低.

新算法首先將整個路網(wǎng)中所有司機(jī)和乘客進(jìn)行匹配，進(jìn)行時間、距離和性別約束處理后統(tǒng)計所有可行匹配Z并計算Z中υZ值和σZ值.根據(jù)可行匹配z賦值對應(yīng)控制變量(xjz和xiz)并進(jìn)行最終模型計算，司機(jī)與乘客在無約束下匹配結(jié)果見圖1.圖中有兩位司機(jī)d1和d2，兩位乘客p1和p2.z0為司機(jī)沒有搭載乘客.兩位司機(jī)可以選擇單獨搭載乘客p1，即圖中z1和z4的匹配結(jié)果；選擇單獨搭載乘客p2，即圖中z2和z5的匹配結(jié)果；或是一同搭載乘客p1和p2，即圖中z3和z6的匹配結(jié)果.

圖1 司機(jī)乘客匹配結(jié)果圖

圖2為司機(jī)乘客匹配結(jié)果優(yōu)化圖，由圖2可知，有些通勤司機(jī)乘客的匹配已經(jīng)因為不符合約束而不存在，例如司機(jī)d2不能一同搭載乘客p1和p2.圖中數(shù)字為每組通勤司機(jī)乘客匹配所產(chǎn)生的兩個數(shù)據(jù)，在模型中用(υz,σz)表示.其中：υz為此次合乘匹配中參與的司機(jī)與乘客總?cè)藬?shù)；σz為此次合乘匹配通勤走廊中產(chǎn)生的行駛距離優(yōu)化值.當(dāng)司機(jī)d1和d2不參與合乘時就不會產(chǎn)生對應(yīng)的(υ,σ)，即d1和d2到z0之間數(shù)據(jù)都為0.

圖2 司機(jī)乘客匹配結(jié)果優(yōu)化圖

針對上文提出的合乘匹配模型，本文設(shè)計了三步驟求解算法,如下所示.

步驟2計算可行匹配z對應(yīng)的(υz,σz).可行匹配z(i,J,(k,g))∈Z中信息包括司機(jī)i與乘客組J和合乘的上車點下車點(k,g).由式σz=doidi-(doik+dkg+dgdi)+∑j∈J(dojdj-(dojk+dgdj))計算出對應(yīng)走廊中機(jī)動車行駛距離優(yōu)化值σ以及匹配人數(shù)υ.

步驟3使用分層求解的方法確定最佳合乘匹配.

步驟4考慮到通勤合乘匹配模型首先要方便最多的通勤者出行，以式(1)作為第一目標(biāo)函數(shù).對于任意匹配z(i,J,(k,g))∈Z，將乘客組J內(nèi)乘客z(i,J,(k,g))依據(jù)合乘模式做匹配.如在同性合乘模式下，依據(jù)式(10)～(11)，式(16)～(18)對J內(nèi)乘客進(jìn)行if-then約束，判斷乘客組J內(nèi)乘客是否滿足同性合乘模式.

當(dāng)乘客組J滿足性別合乘模式時，對乘客j∈J，將乘客j和可行匹配z(i,J,(k,g))對應(yīng)的控制變量xjz賦值為1，即xjz=1.將司機(jī)i和可行匹配對應(yīng)的控制變量xiz賦值為1，即xiz=1.其他的控制變量賦值為0.將所有控制變量(xjz和xiz)賦值之后，以式(3)～(9)、式(19)～(21)為約束條件，以式(1)為模型的目標(biāo)函數(shù)對合乘匹配模型進(jìn)行求解.模型求解后會得到模型中最多的通勤合乘參與人數(shù).

步驟5為了使模型在限制最少合乘參與人數(shù)條件下實現(xiàn)合乘行駛距離最小化，利用步驟4結(jié)果構(gòu)造如下新約束條件：

(22)

此時求解的模型目標(biāo)函數(shù)為式(2)，約束條件增加式(22).在限制最少合乘參與人數(shù)條件下，求解新模型可得到整個通勤走廊中最大的機(jī)動車行駛距離優(yōu)化值.

3 算例分析

算例路網(wǎng)見圖3.通勤走廊路網(wǎng)中共有22個節(jié)點.其中1～16節(jié)點為普通節(jié)點，17～22節(jié)點為合乘點.實線上數(shù)字表示兩點間的距離(單位km)，且路網(wǎng)節(jié)點之間可以相互直達(dá).設(shè)定機(jī)動車行駛速度40 km/h，乘客步行速度為5 km/h.司機(jī)能接受的最大行程時間T直接設(shè)置為司機(jī)通勤最晚到達(dá)時間與最早出發(fā)時間的差值.時間消耗τ值為0.1 h.乘客的容忍系數(shù)?由MATLAB軟件rand函數(shù)隨機(jī)產(chǎn)生.機(jī)動車最大載客量統(tǒng)一設(shè)定為4人.

圖3 單通道合乘通勤走廊示意圖

表1 部分乘客出行信息

表2 部分司機(jī)出行信息

首先考慮第一種合乘模式，即模型約束在性別匹配約束時選擇式(10)～(11)加入模型計算.模型的運(yùn)算部分使用軟件MATLAB進(jìn)行編程運(yùn)算.模型最終計算結(jié)果見圖4.

圖4 同性合乘模式結(jié)果統(tǒng)計圖

下面考慮第二種合乘模式，即模型約束在性別匹配約束時選擇式(12)～(13)加入模型計算.模型運(yùn)算結(jié)果見圖5.

圖5 異性合乘模式結(jié)果統(tǒng)計圖

考慮第三種合乘模式中男性乘客和女性乘客皆偏好和女性乘客進(jìn)行合乘組成通勤乘客組.即模型約束在性別匹配約束時選擇式(14)～(15)加入模型計算.模型運(yùn)算結(jié)果見圖6.

圖6 特別組合合乘模式結(jié)果統(tǒng)計圖

從上面對三種性別合乘模式的運(yùn)算結(jié)果可以得出如下結(jié)論.

1) 模型輸出數(shù)據(jù)中機(jī)動車行駛距離優(yōu)化值σ與合乘人數(shù)υ成正相關(guān).乘客男性比例變化時，圖4～6中行駛距離優(yōu)化值和合乘參與人數(shù)的變化趨勢相同.因為合乘參與人數(shù)變多，說明參與的乘客增多.行駛距離優(yōu)化值σz=doidi-(doik+dkg+dgdi)+∑j∈J(dojdj-(dojk+dgdj))，其中越多乘客參與通勤合乘，∑j∈J(dojdj-(dojk+dgdj))值會相應(yīng)增大，σz值也相應(yīng)增大.因為每位乘客帶來的優(yōu)化值不同，所以行駛距離優(yōu)化值σ與合乘人數(shù)υ呈現(xiàn)正相關(guān)趨勢，并不是嚴(yán)格正比例關(guān)系.

2) 模型輸出結(jié)果與預(yù)期結(jié)果相符，印證了包含性別屬性匹配模型的有效性.其中在同性合乘模式下，男性乘客或女性乘客占總乘客數(shù)比值越高，合乘匹配效果越好；在異性合乘模式下，某一性比乘客數(shù)占比越高，越不利于合乘匹配的進(jìn)行；而在特別組合性別合乘模式下，被偏好性別乘客數(shù)越高，匹配效果越好.

圖7 控制系數(shù)分析統(tǒng)計圖

4 結(jié) 束 語

針對城市交通中的通勤合乘安全問題，本文提出了一種考慮乘客性別影響的通勤車輛司乘匹配模型.模型中涵蓋同性合乘、異性合乘和組合合乘模式，并使用不同約束條件體現(xiàn)性別合乘模式對通勤乘客匹配的影響.算例分析在證實通勤車輛合乘匹配模型有效性的同時，還為現(xiàn)實處理合乘問題中提供以下的指導(dǎo)意見.通勤乘客對合乘同伴性別的偏好會對匹配產(chǎn)生一定影響，為了將負(fù)面影響效果降至最小，現(xiàn)實中可以將具有類似合乘偏好的乘客進(jìn)行分組處理.例如將具有同性合乘偏好的乘客按照性別進(jìn)行分組，以提高組內(nèi)乘客某一性別占比；同樣對異性合乘偏好乘客進(jìn)行分組，以均衡組內(nèi)乘客性別占比，其中男女乘客比值為1∶1時司乘匹配效果為最佳.