柏海艦，汪 俊，鐘劍鋒，衛(wèi)立陽

(合肥工業(yè)大學 汽車與交通工程學院，安徽 合肥 230009)

0 引 言

將客運需求與貨運需求進行聯(lián)合運輸能在減少資源使用的同時提高運行效益。針對不同的運輸環(huán)境，客貨聯(lián)運模式已衍生出多種類型。

A. TRENTINI等[2]構建了一個共享旅客和貨物流之間的運輸資源運輸模型，將客運和貨運流量整合到現(xiàn)有城市交通系統(tǒng)中，并對此種重疊進行表征，即將兩種流量進行量化。為了解決兩層交通問題，R. MASSON等[2]創(chuàng)建了一個數(shù)學模型及一個自適應大鄰域搜索算法。在第一層，貨物在城市公交車中從配送中心運輸?shù)揭唤M公交車站，主要思想是利用公交車的剩余容量將貨物運送到市中心；在第二層中，最終貨物由接近零排放的城市貨運船隊分配。E. FATNASSI等[3]為了研究在城市地區(qū)整合共享商品和按需乘客快速運輸系統(tǒng)的潛力，基于個人快速運輸和貨運快速運輸?shù)墓餐攸c，提出了一種快速有效的運輸解決方案，來提高城市物流的可持續(xù)性。賀韻竹等[4]以最優(yōu)的快遞運輸總成本為目標，構建了一種自營貨車與公交車協(xié)同配送的優(yōu)化模型。為解決帶有時間窗和計劃線路的接送問題，V. GHILAS等[5]提出了一種自適應大鄰域搜索啟發(fā)式算法(ALNS)。該算法有效地考慮了固定線路的時間表、同步與時間窗口約束等復雜方面。大量計算實驗的結果表明，ALNS在生成的PDPTW-SL(帶有時間窗和預定線路的取貨和交貨問題)實例上找到高質量的解決方案非常有效，該實例具有多達100個合理代表現(xiàn)實生活情況的貨運請求。貨物運輸對于城市和地區(qū)的經濟增長至關重要,A.MUOZ-VILLAMIZAR等[6]提出了一種使用OEE(總體設備有效性)度量標準來評估城市貨運系統(tǒng)有效性的新方法，OEE度量標準是精益制造框架中使用的眾所周知的比率。該方法使用具有幾個目標函數(shù)的數(shù)學模型來探索經濟發(fā)展、質量、績效和可利用性(OEE的部分利率)之間的關系和權衡，最終目標是優(yōu)化OEE指標和運輸系統(tǒng)的盈利能力。

在乘車需求分布廣且需求密度低的弱客流地區(qū)，客運車輛的載客率往往較低，若在弱客流地區(qū)進行客貨聯(lián)運，將能提高車輛的使用效率，減少車輛使用數(shù)。

筆者提出的運輸模型對弱客流地區(qū)出現(xiàn)的客貨運輸需求進行車輛安排與線路規(guī)劃。筆者首先為場景建模，對不同類型的運輸需求建立線路生成規(guī)則，然后通過算例來證明系統(tǒng)的可行性并比較在相同運輸需求與運行環(huán)境下，采用混合運輸與不采用混合運輸這兩類模式所需的車輛數(shù)以及線路情況。

1 系統(tǒng)搭建

1.1 場景描述與運行流程

運輸系統(tǒng)在發(fā)車前會根據(jù)提前收到的乘車需求對該班次的車輛數(shù)與線路進行規(guī)劃，使得運輸需求在規(guī)定的時間窗內完成，同時應滿足一些優(yōu)化目標，如系統(tǒng)總體運行時間最小或運行成本最低等。系統(tǒng)總體運行結構如圖1。

圖1 系統(tǒng)總體運行流程Fig. 1 Overall system operation process

車輛與線路初始化完成后，系統(tǒng)開始運行，若運行時出現(xiàn)動態(tài)運輸需求，在使車輛原運輸需求的時間窗依舊滿足及車輛容量允許的條件下，可將動態(tài)需求插入到車輛運輸線路中去。

該系統(tǒng)運行前需要知曉各站點之間的連通性及各站點之間的最短路徑和距離。

在筆者的客貨共享的運輸模式中，車輛按班次發(fā)車，乘客與貨物的運輸需求分為動態(tài)需求與靜態(tài)需求。車輛在運行時出現(xiàn)的乘車需求定為動態(tài)需求，車輛發(fā)車前收集到的乘車需求為本班次的靜態(tài)需求，該班次無法滿足的動態(tài)需求會劃歸到下一班次的靜態(tài)需求中。

運行時，車輛從起始點出發(fā)，途徑各個需求起始點，最終到達終點站。車輛能容納的最大客貨量分別為Q與Qh。發(fā)車前根據(jù)收集到的靜態(tài)需求生初始線路，并在車輛運行時，根據(jù)動態(tài)需求的信息在考慮初始乘客和動態(tài)需求的時間窗約束下，進行路線動態(tài)規(guī)劃。

1.2 初始路線生成

將上一班次運行時出現(xiàn)的、未被滿足的動態(tài)運輸需求以及上一班次結束后出現(xiàn)的運輸需求定為下一班次的靜態(tài)運輸需求。在筆者構建的運行模型下，乘客與貨物需提前向系統(tǒng)提交自己的運輸需求，需求信息應包含需求的起始站點，客貨各自期待被接送的時間窗(e,l)與(eh,lh)，需求的大小qh與qkh以及各自能夠接受的最遲送達時刻lj與ljh。當車輛在期望送達時間窗前到達需求站點時，車輛需要進行等待,總等待時間記為TW，直至到達時刻e或eh。

以系統(tǒng)中靜態(tài)需求規(guī)劃生成的車輛線路應當滿足約束：①minαTH+βKT；②maxTA。其中：TA為線路余度，反映的是線路的可插入度；TH,TK為系統(tǒng)中一個班次車輛總的貨運時間與總的客運時間；α,β為車輛貨運總時間與客運總時間各自所占的權重，可人為調節(jié)。其中：

(1)

s.t.

(2)

(3)

ti≤li

(4)

tih≤lih

(5)

tij≤lij

(6)

tijh≤lijh

(7)

(8)

(9)

在時間窗之前到站的車輛需要進行等待，直至時間窗起點時刻。

約束條件可分為4大類：式(2)、式(3)為車輛容量約束，即在車輛運行的各個時刻，在線客運需求與貨運需求均不可超過車輛的客容量與貨容量上限；式(4)～式(7)為時間窗約束，即車輛需要在需求提交的時間窗前或時間窗內完成需求的接送任務；式(8)為車輛數(shù)約束，即出發(fā)車輛數(shù)與最終到站車輛數(shù)目應相同，一個班次內從始發(fā)點出發(fā)的車輛數(shù)與到達終點站的車輛數(shù)相同；式(9)為防止運輸線路出現(xiàn)子回路的約束。

當所有僅在站點連通度上可行的線路生成后，再使用約束條件進行挑選，生成滿足約束的線路，最后選出線路余度最大的線路作為最終的車輛行駛線路。線路生成應以最小化客貨運的等待時間為首要目標，在等待時間相同的情況下，盡可能提高線路余度TA。

靜態(tài)需求的線路規(guī)劃以最小化乘客與貨物的運行時間為目標，通常貨物對于運輸時間的耐受度要強于乘客，所以可以適當調高α值。

1.3 路線的動態(tài)規(guī)劃

車輛在運行過程中，會有新的運輸需求出現(xiàn)。同樣，新的運輸需求需要提交的信息包含起始站點、客貨各自期待被接送的時間窗(e,l)與(eh,lh)、需求大小以及各自能夠接受的最遲送達時刻lj與ljh。系統(tǒng)會對這些需求進行判斷，符合插入條件的運輸需求會插入正在運行的車輛線路中；對于不符合插入條件的運輸需求，將其歸納到下一班次的靜態(tài)需求中進行規(guī)劃。

新需求在插入時應考慮原有已規(guī)劃好需求，在滿足原有需求的時間窗約束與車輛的容量約束的條件下，插入需求后生成的新線路盡可能提高系統(tǒng)的服務水平以原有乘車需求的滿意度。

插入動態(tài)需求時的目標函數(shù)以約束條件與靜態(tài)需求相同，插入動態(tài)需求的新線路仍要對線路的余度進行比較，以提高后續(xù)出現(xiàn)的動態(tài)需求的可插入性。

線路的余度大小反應了線路的可調整性。當在系統(tǒng)運行時會出現(xiàn)動態(tài)的運輸需求，當車輛響應這些需求的時候，需要對原始的線路進行調整。線路的余度越大，留給動態(tài)需求的調整空間就越大，動態(tài)需求也就越有可能被接受。

當車輛的線路確定后，站點的到達順序亦隨之確定。由于每個需求均包含期望接到的時間窗以及最遲被送達時刻，所以兩相鄰站點之間存在一定的松弛時間，松弛時間的大小代表了站點間對于新需求的接收程度。站點間的松弛時間計算如式(10)、式(11)：

(10)

(11)

式中：L代表兩站點間的最短路徑距離；V代表車輛速度；e與l分別代表后一站點的期望最遲送達時間與前一站點的期望最早到達時間；l′為當前一站點為需求起點時前一站點的期望最遲送達時間。采用TS1計算站點間的松弛時間。當前一站點為需求終點時，采用TS2計算站點間的松弛時間。

由于松弛時間具有后向傳播性，即在線路中靠前的站點插入動態(tài)需求所產生的延遲時間會對后續(xù)的站點產生影響。

產生影響的只有后向站點，不會對前向站點產生影響，如圖2。所以對于各個站點而言，最大余度為其前所有站點中最短的站點松弛時間。對應整體線路而言，線路的最大余度為所有站點松弛時間的最小值。即：

圖2 需求插入后的延遲傳播Fig. 2 Delayed propagation after demand insertion

TA=min(TS1,TS2,…,TSi) (i=N)

(12)

2 算法設計

系統(tǒng)準備發(fā)車前，依據(jù)靜態(tài)運輸需求，開始初始車輛數(shù)以及各個車輛的線路確定，具體流程如圖3。

圖3 初始路線生成流程Fig. 3 Initial route generation flowchart

Step 1將需求集合中最早出現(xiàn)的需求放入車輛中，并通過將車上所有需求依次設為終點，采用深度優(yōu)先加回溯的方法生成線路。

Step 2判斷是否存有可行線路。若有可行線路，選擇線路余度最大的作為最優(yōu)解，同時將該需求從需求集合中去除，再次進行Step 1操作；若無可行線路，選擇需求集合中后一需求進行插入操作，若無可行線路繼續(xù)進行該步驟，直至所有需求全部被選擇過。

Step 3判斷需求集合中是否還有存有需求。若有，則增添一輛新車，繼續(xù)從Step 1開始產生線路;若無需求，則線路生成與車輛的數(shù)目確定就此結束。

Step 1中采用深度優(yōu)先加回溯的方法[7]，生成不考慮約束條件下的所有可行線路。該算法在圖論中可用于搜索兩點之間的所有可行線路，筆者采用該算法計算出依次以所有站點為終點的所有可行線路，此可行性僅為站點連通性方面的可行性。

M. BARKAOUI等[8]使用遺傳算法的自適應進化方法，解決在帶時間窗的動態(tài)車輛路徑與遺傳算法收斂過程的策略選擇和運算符的組合問題；M. DIANA等[9]提出了一種并行后悔插入啟發(fā)式方法，以解決帶有時間窗的需求插入問題并實施了新的路線初始化過程，該過程同時考慮了問題的空間和時間方面，然后執(zhí)行后悔插入以服務其余的請求；LUO Ying 等[10]針對靜態(tài)多車輛“搭便車”問題提出了一種新的啟發(fā)式方法，稱之為拒絕重新插入啟發(fā)式方法，其主要目標是在服務質量約束下，盡量減少用于滿足所有需求的車輛數(shù)量。

筆者采用2-opt的方法對線路進行擾動以產生新線路。當動態(tài)需求出現(xiàn)后，依據(jù)流程(圖4)進行需求的可插入性判斷以及新線路的生成。其中，線路的擾動采用2-opt的方法，其最早由文獻[11]提出。該方法屬于局部搜索算法，可用于解決TSP問題，其基本思想是隨機取兩個節(jié)點，對線路進行交換優(yōu)化，一直到無法優(yōu)化為止。

圖4 路線的動態(tài)規(guī)劃流程Fig. 4 Dynamic planning flow chart of route

Step 1動態(tài)需求產生后首先將其起終點就近插入到車輛的運行線路中，如圖5。在將站點插入之后對線路進行擾動以產生新的線路，再對新的線路進行判定是否可行，若可行，記錄并存儲。

圖5 動態(tài)需求就近插入Fig. 5 Dynamic demand insertion nearby

Step 2將需求點插入線路中次近的位置中，繼續(xù)進行線路的擾動，存儲可行線路，直至線路中所有的位置都被插入過。

Step 3換一輛車繼續(xù)進行Step 1和Step 2的評估。

Step 4將所有可行線路進行比較，選擇最優(yōu)的線路作為最終的線路。

Step 5若所有情況下均無可行線路，則將該需求歸納為下一班次的靜態(tài)需求。

文獻[12]提出了一種可快速生成可行線路的2-opt 方法，采用該方法會產生與原始線路上下需求站點順序不同的線路，如圖6。

圖6 2-opt產生新線路Fig. 6 New lines generated by 2-opt

圖6中，圓圈內數(shù)字及字母為站點號，0號站點代表車輛的起始點，+1、+2等代表第幾號運輸需求上車，-1、-2等代表第幾號運輸需求下車。S—1—2—3—4—5—6—7—8—9—10—E為車輛初始線路。在選擇了3—4和5—6兩對站點作為交換起終點后，車輛行駛線路變?yōu)镾—1—2—3—5—4—6—7—8—9—10—E。由于線路存在約束，在線路中進行2-opt的時候，會產生不可行的線路，因此每當新線路生成后，需要對其可行性進行檢驗。

一條原始線路在插入新的運輸需求后會有多種擾動產生的新線路，依次檢驗可行性會耗費大量時間。文獻[11]提出了一種通過縮小可行線路范圍而減少驗證時間的方法。通過該方法可找到潛在可行的線路交換起始點，具體如表1。

表1 站點i與FD(i)值Table 1 Station i and FD (i) values

表1中：i為原始線路中的站點號；FD(i)為從第i號及其以后站點上車需求的第1個下客站點號，如FD(3)=5代表了從原線路第3號及其以后站點上車需求的最先下客點為5號站點。

可將第i個站點設為擾動出點，F(xiàn)D(i)為擾動線路的入點，第i+1號站點為第2段的出點，F(xiàn)D(i)+1為第2段的入點。例如以第5號站點為擾動出點，F(xiàn)D(5)=7，第7號站點為擾動線路的入點，第6號站點為第2段的出點，F(xiàn)D(5)+1=8，第8號站點為第2段的入點，如圖7。

圖7 新的可行路Fig. 7 New feasible road

新線路為S—1—2—3—4—5—7—6—8—9—10—E，在運輸需求起終點順序上可行，下一步即可開始約束條件的檢驗。

通過該擾動方法并不一定能完全能生成滿足運輸需求起終點順序的新線路，但可縮減新可行線路的生成時間。

3 算例分析

3.1 可行性檢驗

為驗證筆者提出的客貨混運模型的可行性，筆者進行算例計算。隨機生成運輸路網，結構如圖8。

圖8 算例路網Fig. 8 Example road network

在運行系統(tǒng)中，生成各個直連站點間的距離。假設車輛行駛速度恒定，根據(jù)路網站點間的連通性，用直連站點間的行駛時間表示距離。

表2中，S為車輛發(fā)車起點，E為車輛到達終點。在此算例中，設定初始靜態(tài)運輸需求為 6 個，動態(tài)運輸需求數(shù)為 4 個，設車輛的可載客運需求量為 3，可載貨運需求量為 2。記系統(tǒng)中，該班次發(fā)車時刻為 0 時。運輸靜態(tài)需求如表3。

表2 直連站點的時間距Table 2 Time interval of directly connected stations min

表3 靜態(tài)運輸需求Table 3 Static transportation requirements

運輸動態(tài)需求如表4。

表4 動態(tài)運輸需求Table 4 Dynamic transportation requirements

按靜態(tài)需求的車輛線路生成流程圖，對表3的靜態(tài)需求進行線路生成，結果如表5。

表5 初始運行線路Table 5 Initial operation route

由表5可知，車輛無法滿足1號動態(tài)運輸需求，歸納到下一班次的靜態(tài)需求中去。車輛行駛軌跡如圖9。

圖9 初始線路車輛線路Fig. 9 Vehicle route of the initial line

按動態(tài)需求的車輛線路生成流程，對表4的動態(tài)需求進行線路生成，結果如表6。

表6 插入動態(tài)續(xù)需求后的新線路Table 6 New lines after inserting dynamic renewal requirements

由表6可知，車輛無法滿足1號動態(tài)運輸需求，歸納到下一班次的靜態(tài)需求中去。車輛行駛軌跡如圖10。

圖10 再規(guī)劃后車輛路線Fig. 10 Vehicle route after re-planning

以此，算例證明了該模型的可行性。

3.2 對比分析

為對比混合運輸模型與非混合運輸模型之間的差異，將兩類模型進行對比實驗。表7、表8生成了非混合運輸時的靜態(tài)需求車輛路徑與動態(tài)需求產生后的車輛路徑。

表7 非混合運輸模型的靜態(tài)需求路徑Table 7 Static demand path of non-mixed transportation model

表8 非混合運輸模型的動態(tài)需求路徑Table 8 Dynamic demand path of non-mixed transportation model

由表8可知，動態(tài)需求3、4因為時間窗約束無法被滿足，劃歸到下一班次的靜態(tài)需求中去?，F(xiàn)將兩種運輸模型的車輛運行時間以及車輛空駛時間進行比較，如圖11～12。

圖11 不同模式下車輛線路參數(shù)Fig. 11 Vehicle line parameters in different modes

圖12 兩種運輸模式總體比較Fig. 12 Overall comparison of two transportation modes

由圖11～12可知，在相同的運輸需求條件下，混合運輸模型所需的車輛數(shù)、總空載時間即總空載里程數(shù)要小于非混合運輸模型情況下的相應值，混合運輸模型下車輛的空載率要小于非混合運輸模型情況下的空載率。

4 總結與展望

1)筆者構建了一種弱客流環(huán)境下的客貨混合運輸模型，該模型能實時響應系統(tǒng)中出現(xiàn)的動態(tài)需求?；谒憷炞C了該模型的可行性。在相同運輸需求下，對比了混合運輸模式與非混合運輸?shù)倪\行情況，發(fā)現(xiàn)在混合運輸時所需的運行車輛數(shù)較少，并對動態(tài)運輸需求的滿足率較高，同時車輛的空載率小于非混合運輸時的車輛空載率。混合運輸可降低整體的運輸成本。

2)筆者將發(fā)車班次間隔設為定值，但為貼切現(xiàn)實應根據(jù)靜態(tài)需求的情況進行調整。同時在驗證可行性時，將車輛速度設為定值，為貼切現(xiàn)實車輛的運行情況，應當將速度設為與運行時間、路段擁堵情況等相關的動值，故而還需進行深入研究。