張 藝,蔣 洋

沈陽工業(yè)大學管理學院,遼寧 沈陽 110870

0 引言

隨著我國經(jīng)濟的發(fā)展以及人民生活水平的提高,對汽車的需求量也逐日攀升,汽車保有量增大,導致環(huán)境污染和交通堵塞等問題出現(xiàn)。諾貝爾獎獲得者加里·貝克爾通過測算得出,全球每年因擁堵造成的損失高達GDP的2.5%[1]。共享汽車的出現(xiàn)解決了這個問題,20世紀80年代末期歐洲開始出現(xiàn)“汽車共享”交通模式[2]。當用戶在車站之間自由移動車輛時,可能會發(fā)生不平衡,不平衡是指有的停車場沒有車而有的停車場出現(xiàn)了車輛堆積。運營商選擇在系統(tǒng)運行階段進行優(yōu)化調(diào)整。Silva et al.[3]提供了4種基于時空網(wǎng)絡(luò)流模型的混合整數(shù)線性規(guī)劃公式。崔洪軍 等[4]通過動態(tài)生成需求和車輛的最佳路線。何李凱 等[5]給予帶時間窗的車輛路徑問題加入懲罰成本。只有少數(shù)研究考慮到了員工調(diào)運車輛后自身的重平衡。Betül et al.[6]提出了尋找所有緊急現(xiàn)場案例的調(diào)運方案。Yasuhiro et al.[7]將基于情景的線性控制策略的計算優(yōu)化模型制定為一個線性優(yōu)化問題。王寧 等[8]以調(diào)度成本最小建立調(diào)度需求模型。蔣陽升 等[9]提出了混合車隊及調(diào)度員的優(yōu)化方法。

為了考慮供給和需求之間功能的匹配,應(yīng)該進一步探索用戶對調(diào)運和重平衡的影響。對用戶進行獎勵補貼,使用戶在取還車時選擇更有利于經(jīng)營者的車站,從而改善車輛的不平衡,也是很重要的解決方案。王誠坤 等[10]提出了利用價格折扣和紅包相結(jié)合的方式激勵用戶參與汽車調(diào)運。王寧 等[11]提出了鼓勵顧客異地取還車給予一定獎勵的激勵手段。姚恩建 等[12]通過車輛動態(tài)折扣策略引導用戶改變默認的最近取還車站點。Clemente et al.[13]提出了一種確定最優(yōu)閾值的方法考慮了客戶對價格優(yōu)惠的隨機響應(yīng)。Karoonsoontawong et al.[14]研究了具有軟時間窗和超時約束的時變車輛。

本文在顧客時空柔性的前提下,提出了車輛搬遷和人員再平衡的聯(lián)合優(yōu)化模型。雖然過去有研究考慮到車輛調(diào)度和員工重平衡,但是沒有與顧客在獎勵條件下產(chǎn)生的時空柔性相結(jié)合,這種對顧客的忽略削弱了系統(tǒng)的現(xiàn)實性。本文構(gòu)建了車輛平衡和人員平衡的聯(lián)合優(yōu)化模型,在模型中加入獎勵機制,考慮需求一側(cè)的時空柔性,利用分解算法求解Np-hard問題。

1 問題描述

向單程式共享汽車系統(tǒng)中引入時間柔性的概念,即從時間角度,允許用戶以預(yù)約訂單出發(fā)時間為基礎(chǔ),選擇提前或者延后出發(fā)。用戶的時間柔性可以根據(jù)他們在網(wǎng)上下單時的情況來確定。定義網(wǎng)上預(yù)約訂單集合W,用戶訂單需求i∈W包含如下若干信息:用戶的起點Mi,終點Ni,出發(fā)時間Di,到達時間Ai,最大可接受的提前出發(fā)時間tai,最大可接受的延后出發(fā)時間tdi,用戶成本系數(shù)yi組成,用戶成本系數(shù)主要取決于用戶的用車時間,時間接近早晚高峰時用戶的成本系數(shù)也會隨之上升。集合Ui={Mi,Ni,Di,Ai,tai,tdi,yi}表示用戶i的信息列表。訂單(i,j)和(p,q)表示一系列調(diào)運組合,用集合Q表示,其中i,j,p,q∈W。

考慮員工的再平衡(見圖1)。根據(jù)圖1,員工在j訂單和p執(zhí)行再平衡。這里需要2輛車,并將工作人員的數(shù)量減少到1個人。然而,時間的靈活性可以進一步降低總成本(見圖2)。訂單的出發(fā)時間已被推遲。因此,完成4個訂單和車輛搬遷只需要1輛車和1名工作人員。

圖1 車輛調(diào)度和人員重平衡圖

圖2 含柔性的車輛調(diào)度和人員重平衡圖

本文存在以下4種假設(shè)。①需求:不一定要滿足所有需求。②停車站:假定設(shè)定的停車站有足夠的停車位。③車輛周轉(zhuǎn):僅考慮當天返回的行程。④已知需求:假設(shè)用戶的需求等信息均為已知。

2 模型建立與求解

將該問題劃分為主問題和子問題。在主問題中,主要考慮車輛調(diào)運的過程;在子問題中,只考慮員工的重平衡。主問題的模型如下。

(1)

(2)

(3)

Dj+Tj-t(Ni,Mj)-(Ai+Ti)≥G×(Xij-1) ?i,j∈W

(4)

-tai≤Ti≤tdi?i∈W

(5)

(6)

Xij=0 ?(i,j)∈N

(7)

Xij∈{0,1} ?(i,j)∈Q

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

式(9)是成本函數(shù),包括員工固定成本和重平衡成本;式(10)是對于員工的時間約束;式(11)為流量平衡約束;式(12)用于計算員工的總數(shù);式(13)中的G為一個大數(shù),其確保調(diào)運組合(i,j)當且僅當t(Ni,Mj)≠0時才是重平衡組合{(i,j),(p,q)}的一部分;式(14)、(15)確保了只有當Xij和Xpq均為1時,Yijpq才能為1;式(16)定義了0-1變量。

綜上所述,分解算法迭代步驟如下。

第1步:初始集合N為空集。

第5步:如果kij≤0,那么結(jié)束計算;否則回到第2步。

3 數(shù)值試驗

3.1 案例參數(shù)設(shè)置

估計1輛車的全部成本為9萬元,攤銷到8年時間,日攤銷成本約為30元,即Cfleet為30。以平均月工資3 600元計算,因為該系統(tǒng)考慮的是早晚高峰一共4 h的訂單,故Cstaff為60。在該系統(tǒng)中,車輛速度為42.5 km/h,車輛耗油量為7 L/100 km,油價目前為9.8元/L,故Crel粗略估算為每分鐘0.5元,Cbal與員工4 h工資有關(guān),為β×Cstaff,本案例中,β定為0.75。本案例中懲罰成本為20元,模型中共有20個站點和75個訂單。

隨機生成Mi、Ni、Di、yi、tai、tdi,并設(shè)置Ai=Di+t(Mi,Ni)。訂單起點到終點的駕駛時間是根據(jù)高德地圖的駕駛時間生成的,代表最長時間的路徑。因為汽車與自行車速度的關(guān)系,本文將人重平衡的時間設(shè)為汽車調(diào)運時間的1.7倍。用戶在時間柔性比例上選擇50%,柔性時間選擇為可以提前和延后10 min。時間獎勵系數(shù)α為0.4。表1為該模型在上述參數(shù)設(shè)置下的案例初始優(yōu)化值。

表1 優(yōu)化結(jié)果

3.2 柔性對比分析

3.2.1 有無時間柔性對比分析

本文對無時間柔性和考慮時間柔性進行對比分析,從總成本、車輛數(shù)目、員工數(shù)目、調(diào)運時間、重平衡時間、訂單未滿足個數(shù)這6方面進行對比。如表2所示,通過時間柔性,訂單接受數(shù)量增加,提高顧客的滿意度,員工數(shù)量減少,調(diào)運時間減少,重平衡時間減少。

表2 有無時間柔性對比

3.2.2 柔性比例分析

在柔性比例方面,本文考慮了50%顧客柔性、40%顧客柔性、30%顧客柔性、20%顧客柔性。這4種情況對影響要素的影響如表3所示。柔性比例越大,接受柔性的訂單也就越多,系統(tǒng)接受的訂單也就越多。

表3 不同柔性比例下的影響要素值

4 結(jié)論

本文提出了一種針對時間柔性的車輛調(diào)運和人員再平衡的聯(lián)合優(yōu)化模型。在模型中包含時間柔性的目的是為了更好地衡量單向汽車共享系統(tǒng)中客戶側(cè)的價值。該模型在幾個隨機試驗中實現(xiàn)。分析表明,時間靈活性使總成本降低了15.5%,使請求接受率提高了7%。

附錄 參數(shù)及解釋