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

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

0 引 言

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

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

1 模型說(shuō)明

1.1 參數(shù)說(shuō)明

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

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

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

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

(1)

(2)

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

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

1.3 約束條件

模型基本約束為

≤Ci

(3)

(4)

toik+τ+tkg+tgdi≤Ti

(5)

(6)

(7)

(8)

(9)

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

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

,?z∈Z,Jz∈zm,

?z∈Z,Jz∈z

(10)

(11)

(12)

(13)

(14)

(15)

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

(16)

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

(17)

(18)

,?i∈D

(19)

(20)

(21)

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

2 求解算法

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

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

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

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

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

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

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

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

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

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

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

(22)

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

3 算例分析

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

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

表1 部分乘客出行信息

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

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

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

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

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

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

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

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

1) 模型輸出數(shù)據(jù)中機(jī)動(dòng)車(chē)行駛距離優(yōu)化值σ與合乘人數(shù)υ成正相關(guān).乘客男性比例變化時(shí)，圖4～6中行駛距離優(yōu)化值和合乘參與人數(shù)的變化趨勢(shì)相同.因?yàn)楹铣藚⑴c人數(shù)變多，說(shuō)明參與的乘客增多.行駛距離優(yōu)化值σz=doidi-(doik+dkg+dgdi)+∑j∈J(dojdj-(dojk+dgdj))，其中越多乘客參與通勤合乘，∑j∈J(dojdj-(dojk+dgdj))值會(huì)相應(yīng)增大，σz值也相應(yīng)增大.因?yàn)槊课怀丝蛶?lái)的優(yōu)化值不同，所以行駛距離優(yōu)化值σ與合乘人數(shù)υ呈現(xiàn)正相關(guān)趨勢(shì)，并不是嚴(yán)格正比例關(guān)系.

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

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

4 結(jié) 束 語(yǔ)

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