高鐵快運末端配送車輛路徑規(guī)劃研究

郭軍華，宋星雨

(華東交通大學(xué) 交通運輸工程學(xué)院，江西 南昌 330013)

0 引言

由于高速鐵路的特性，高鐵快運的開通滿足了客戶對高時效、高附加值的快運運輸需求。但高鐵快運的末端配送還存在運輸成本高、配送效率低等問題[1]，“最后一公里”瓶頸依然存在。為打破瓶頸，提升高鐵快運在物流市場的競爭力，提出了適用于城市內(nèi)存在多個高鐵站的高鐵貨運專列“去配送中心”配送模式[2]，但此模式還需要根據(jù)高鐵快運現(xiàn)階段的發(fā)展研究，對其進一步優(yōu)化完善，從而提高普適性。

在對高鐵快運現(xiàn)階段研究中發(fā)現(xiàn)，高鐵快運的發(fā)展給傳統(tǒng)的鐵路運輸帶來了轉(zhuǎn)機，加速了鐵路貨運物流的現(xiàn)代化進程[3]。為研究貨運對客運系統(tǒng)的影響，學(xué)者們在旅客列車系統(tǒng)中添加了貨物列車的數(shù)學(xué)模型[4]，并發(fā)現(xiàn)在現(xiàn)有的客運系統(tǒng)中進行客貨混運能提高列車利用率且僅小幅提高邊際運行成本[5]。目前，隨著高鐵快運量的增加與服務(wù)效率標(biāo)準的提升，現(xiàn)有的網(wǎng)點中轉(zhuǎn)再配送方式，增加了貨物的運輸成本，延長了快遞周轉(zhuǎn)時間，無法滿足靈活化的市場需求；國內(nèi)外學(xué)者先后提出提高高鐵快運核心競爭力，關(guān)鍵是完善高鐵快運“最后一公里”的配送服務(wù)[6-7]。車輛路徑規(guī)劃作為“最后一公里”問題的研究熱點，主要以配送總成本和總時間最小為目標(biāo)[8-10]，考慮貨物時間窗、車輛因素構(gòu)建車輛路徑規(guī)劃模型[11-12]。

因此，將高鐵快運客貨協(xié)同運輸和城市末端配送相結(jié)合，并提出了一種“去配送中心”的高鐵快運城市末端配送方式，即配送貨車(以下簡稱“貨車”)將高鐵站的貨物不經(jīng)過貨物配送中心直接配送到城市末端物流收發(fā)點。基于高鐵運行時刻，以配送時間和成本為目標(biāo)，綜合考慮貨物分配、車輛配送路徑和貨物運輸時間等約束，構(gòu)建高鐵快運末端配送模型；設(shè)計改進遺傳算法對模型進行求解，從而獲得最優(yōu)的高鐵快運末端配送方案。

1 問題描述與建模

1.1 問題描述

針對高鐵快運末端配送展開研究，貨物裝載于高鐵始發(fā)站，利用現(xiàn)有高鐵快運客貨協(xié)同的運輸方式，至目標(biāo)高鐵站進行卸貨；根據(jù)高鐵到站時間和到站貨物量，定時派出貨車在高鐵站裝載貨物，不經(jīng)貨物配送中心中轉(zhuǎn)，直接配送至城市末端各物流收發(fā)點以滿足貨物配送時效要求，高鐵快運的城市配送流程如圖1 所示。貨車須在物流收發(fā)點的收貨時間窗內(nèi)進行服務(wù)，否則會產(chǎn)生懲罰成本，完成所有物流收發(fā)點服務(wù)的貨車必須返回高鐵站。

圖1 高鐵快運的城市配送流程Fig.1 Distribution process of high speed rail express in city

1.2 模型假設(shè)

為簡化模型，特做出以下假設(shè)。

（1）高鐵站沒有儲存功能，貨物到站后需要立即分揀并裝入貨車[2]；

（2）所有貨車均采用同一種車型，其荷載能力固定[2]；

（3）不考慮高鐵列車晚點，即高鐵到站時間是固定的，且不考慮貨車在行駛過程中道路環(huán)境的突發(fā)狀況[13]；

（4）高鐵站和各物流收發(fā)點的位置坐標(biāo)已知，物流收發(fā)點的貨物需求和收貨時間窗已知。

模型中的具體符號表示如表1所示。

表1 符號表示Tab.1 Symbolic representation

1.3 模型建立

在車輛路徑規(guī)劃中，在保證配送成本最小的同時也要縮短配送時間，因此模型目標(biāo)函數(shù)在總成本中主要考慮貨車的行駛距離、使用成本和懲罰成本，在總配送時間中考慮貨車在途時間和服務(wù)時間，其計算公式如下。

模型需要滿足貨車載重約束、貨車到達目的地的時間約束，貨車路線的唯一性等約束條件，具體約束條件如下。

（1）配送第n批貨物時使用貨車的總數(shù)量|K|，可表示為

（2）貨車k裝載貨物的容量限制，可表示為

（3）貨車k超載的懲罰成本，可表示為

（4）貨車k對第n批貨物的各物流收發(fā)點i有且僅能到達一次，可表示為

（5）配送第n批貨物時，物流收發(fā)點i完成配送的時間等于貨車k離開的時間，可表示為

（6）為消除貨車路線中出現(xiàn)子回路的情況，將其約束為

（7）配送第n批貨物的貨車k到達物流收發(fā)點i的配送時間約束，可表示為

（8）貨車k在配送第n批貨物時，不在時間窗內(nèi)配送將產(chǎn)生的懲罰成本，可表示為

模型為總運輸成本和時間最小的雙目標(biāo)模型，為了方便求解需將雙目標(biāo)轉(zhuǎn)化為單目標(biāo)問題。通過把運輸總時間進行閾值劃分并給定相應(yīng)的時間成本系數(shù)，將運輸時間轉(zhuǎn)化為運輸成本，利用線性求和的方式完成多目標(biāo)模型轉(zhuǎn)化為單目標(biāo)模型。因此，按照時間等級的成本函數(shù)轉(zhuǎn)化到模型的目標(biāo)函數(shù)，表達式為

其約束公式⑵至公式⑿不變，運輸總時間的等級劃分為60 min 內(nèi)送達、120 min 內(nèi)送達和超過120 min 送達3 種情形，根據(jù)運輸總時間產(chǎn)生的時間成本，可表示為

式中：ε3，ε4，ε5為時間成本系數(shù)，滿足ε3＜ε4＜ε5。

2 算法設(shè)計

高鐵快運末端配送路徑規(guī)劃屬于非確定性多項式困難問題，基于軟時間窗下的多目標(biāo)路徑規(guī)劃問題求解更為復(fù)雜。因此利用改進的遺傳算法進行求解，以提高解的質(zhì)量避免算法陷入局部最優(yōu)，從而得到高鐵快運末端配送路徑優(yōu)化模型的求解算法。

2.1 改進的遺傳算法

首先，通過編碼方案進行編碼生成初始種群，設(shè)路徑規(guī)劃方案為G=(g1，g2，…，gk)，其中g(shù)k表示車輛路徑，而在車輛路徑gk=(0，1，2，…，n，0)中，0 表示高鐵站，物流收發(fā)點為1，2，…，n，車輛數(shù)的編碼為n+1，n+2，…，n+k(k為貨車的最大車輛數(shù))，本文將物流收發(fā)點和車輛作為基因片段。例如有5 個配送點，由2 輛貨車進行配送，因此車輛1 的編碼為6，車輛2 的編碼為7。其中車輛1 的路徑規(guī)劃為g1=(0，5，3，1，0)，車輛2 的路徑規(guī)劃為g2=(0，2，4，0)，其染色體編碼為5316247，最終調(diào)度方案為G=((0，5，3，1，0)，(0，2，4，0))。使用目標(biāo)函數(shù)的倒數(shù)作為個體適應(yīng)度，然后采用輪盤賭算法進行選擇操作，依概率選擇個體使算法保持隨機性。選擇后的個體采用OX 交叉和變異操作產(chǎn)生新的個體，從而在保證優(yōu)良基因保留下來的同時還能保證種群的多樣性。然后調(diào)用大規(guī)模鄰域搜索算法完成“破壞”和“修復(fù)”兩個過程在種群中尋找最優(yōu)個體。循環(huán)上述過程，直至迭代結(jié)束或者找到最優(yōu)解，算法流程如圖2所示。

圖2 改進的遺傳算法基本流程Fig.2 Basic process of improved genetic algorithm

2.2 “破壞”和“修復(fù)”

由于遺傳算法容易陷入局部最優(yōu)解，因此選取大規(guī)模鄰域搜索算法中影響搜索性能的“破壞”和“修復(fù)”2個過程，對當(dāng)前解進行優(yōu)化避免過早收斂。

“破壞”過程，以減少運輸總路程為目標(biāo)，總路程的增加是由于少數(shù)物流收發(fā)點的存在導(dǎo)致車輛路徑的運輸路程增大，所以移動這類物流收發(fā)點到其他位置能夠有效減少運輸總路程。首先從當(dāng)前解的物流收發(fā)點集合中隨機選出一個物流收發(fā)點，然后根據(jù)相關(guān)性再依次移出幾個物流收發(fā)點達到需要的數(shù)量，用I表示所有被移出物流收發(fā)點的集合，用P表示剩下的物流收發(fā)點。

其中相關(guān)性計算公式中，R(i，j)表示相關(guān)性，R(i，j)越大，表示i，j之間的相關(guān)性越大。di，j表示i與j之間的距離，li，j表示i與j是否由同一輛貨車服務(wù)。如果在同一條路徑上時為0，否則為1。R(i，j)計算公式為

式中：d′i，j表示標(biāo)準化后的值，其值在[0，1]之間。

“修復(fù)”過程，根據(jù)最遠插入啟發(fā)式，依次從I中選擇一個物流收發(fā)點重新插回P中。首先算出I中所有的物流收發(fā)點的最小插入距離，從中選出最大的元素，插入相應(yīng)的車輛路徑達到目標(biāo)值減小的目的。

3 算例求解與結(jié)果分析

3.1 算例設(shè)計

以上海站非高峰時段(10：00—11：00)高鐵運營為例，選擇該時間段內(nèi)時間鄰近的高鐵列車，上海站高鐵列車時刻表如表2 所示，圖定列車時刻表來源于2021年9月1日上海站的車站大屏數(shù)據(jù)。

表2 上海站高鐵列車時刻表Tab.2 Shanghai station high speed railway timetable

案例研究的上海各區(qū)域15 個物流收發(fā)點，如圖3 所示。根據(jù)高德地圖實時避免擁堵路線記錄了物流收發(fā)點及高鐵站的旅行時間。以上海市城市總體規(guī)劃中市區(qū)和郊區(qū)為依據(jù)，基于高鐵時刻表和每批貨物的配送時間窗，對各物流收發(fā)點的各批次貨運時間窗進行劃分，共有15 個物流收發(fā)點，其中1—9 位于郊區(qū)，10—15 位于市區(qū)。貨車提前到達物流收發(fā)點的時間懲罰單位成本為20元/min，延后到達的單位成本為30 元/min，時間窗的超限值為20 min。根據(jù)高鐵裝載的貨物量[14]設(shè)置貨車載重量為 1500 件，允許裝載貨物超出載重量的30%，超載的懲罰成本為 1000 元/件。各物流收發(fā)點的所有批次貨物需求量如表3 所示，貨車單位距離的運輸費用為0.5 元[15]。改進遺傳算法的相關(guān)參數(shù)設(shè)計如下，算法種群規(guī)模為100，最大迭代次數(shù)為200，交叉概率為0.9，變異概率為0.05。

表3 各物流收發(fā)點的所有批次貨物需求量件Tab.3 Demand for all batches of goods at each logistics delivery point

圖3 物流收發(fā)點的位置Fig.3 Location of logistics delivery points

3.2 算法有效性分析

基于案例中高鐵貨物的第一批數(shù)據(jù)，分別使用蟻群算法、遺傳算法和改進的遺傳算法求解，其中遺傳算法與改進遺傳算法參數(shù)相同，蟻群算法的參數(shù)如下：蟻群數(shù)量為10，信息素因子為1，啟發(fā)函數(shù)因子為3，信息素揮發(fā)因子為0.5，信息素常量為10，迭代次數(shù)為200 代。匯總3 種算法運行10 次的最優(yōu)值如表4 所示。雖然蟻群算法最優(yōu)運輸時間稍短，但其成本最優(yōu)解遠大于改進遺傳算法和遺傳算法得出的最優(yōu)解，而改進遺傳算法的最優(yōu)值整體稍優(yōu)于遺傳算法。根據(jù)3 種算法成本和時間的平均值可得，蟻群算法成本最優(yōu)解在[-14%，11%]內(nèi)浮動，時間最優(yōu)解在[-6%，6%]內(nèi)浮動，改進遺傳算法成本最優(yōu)解在[-5%，5%]內(nèi)浮動，時間最優(yōu)解在[-1%，1%]內(nèi)浮動，遺傳算法成本最優(yōu)解在[-50%，46%]內(nèi)浮動，時間最優(yōu)解在[-6%，6%]內(nèi)浮動。綜上所述，改進遺傳算法的迭代過程和穩(wěn)定性綜合來看更好，而且能夠得出高質(zhì)量的最優(yōu)解，適合求解本次模型。

表4 3種算法運行10次的最優(yōu)值Tab.4 Optimal value of three algorithms running 10 times

3.3 算例結(jié)果

根據(jù)算法有效性比較，利用改進遺傳算法對算例進行求解，得到最優(yōu)運輸總成本為 4723.4 元，運輸時間為 2086 min。最優(yōu)配送方案如表5 所示，配送1 h 內(nèi)到達的所有高鐵快運貨物共使用15 輛貨車，每輛貨車平均在90 min內(nèi)將貨物配送完畢。此外，共有5 個物流收發(fā)點未在時間窗內(nèi)完成配送，分別是第一批的6，7 號收發(fā)點，第二批的4 號、8號收發(fā)點，第三批的6號收發(fā)點。由于4個收發(fā)點都位于郊區(qū)，根據(jù)配送路徑和配送時間可知，距離較遠的物流收發(fā)點多與其距離最近的市區(qū)物流收發(fā)點共同進行配送，當(dāng)貨車將多個郊區(qū)收發(fā)點共同進行配送時，更容易違反時間窗。但貨車每次違反時間窗的時長均不超過10 min，即高鐵快運的末端配送能夠保證每一批貨物在60 min內(nèi)完成市內(nèi)各物流收發(fā)點配送，在110 min 內(nèi)將郊區(qū)物流收發(fā)點配送完畢。

表5 最優(yōu)配送方案Tab.5 Optimal distribution scheme

3.4 貨車載重量影響分析

為探究貨車的載重量對配送方案的影響，對比了3 種載重量的貨車，得到3 種貨車載重量的配送方案和貨車滿載率如圖4 所示，由于貨車的載重量不同，所以3 批貨物的貨車滿載率會發(fā)生改變。對比圖4a、圖4b和圖4c可知，載重量為 1000件貨車的平均滿載率最高，達到了74.27%。載重量 1500件的貨車平均滿載率為49.51%，高于載重量 1800 件的貨車平均滿載率41.26%，在相同配送方案下，載重量 1800 件的貨車空間沒有得到較好的利用，所以使用載重量 1500 件的貨車優(yōu)于 1800 件的貨車。

圖4 3種貨車載重量的配送方案和貨車滿載率Fig.4 Distribution scheme and full load rate of three kinds of wagon load capacity

此外，3種貨車載重量的運行結(jié)果如表6所示，載重量為 1500 件的貨車運輸時間和總成本最低。 1800 件的貨車只在總成本上高于 1500 件的貨車， 1000件的貨車與 1500件的貨車運行結(jié)果相比，多花費1.2%的運輸時間和38.4%運輸成本，由于載重量為 1000 件的貨車選擇增加違反時間窗個數(shù)，使最大行駛距離增加了5.4%，從而避免違反貨車載重，保證車輛安全?；谏鲜龇治觯d重量為 1500 件的貨車無論是在時間上還是成本上都優(yōu)于其他2 種載重量的貨車，并且滿載率相對較高，所以使用載重量為 1500 件的貨車在本算例中是最佳方案。

表6 3種貨車載重量的運行結(jié)果Tab.6 Running results of three kinds of wagon load capacity

4 結(jié)論

針對高鐵快運“最后一公里”配送問題，考慮即時配送、貨車載重和貨物時間窗，建立了最優(yōu)運輸成本和運輸時間的多目標(biāo)模型，設(shè)計了改進的遺傳算法，以上海站及上海各區(qū)域的物流收發(fā)點為例，將改進的遺傳算法與蟻群算法、遺傳算法進行對比分析，驗證了設(shè)計的算法對本案例的有效性。得出的案例結(jié)果表明，高鐵快運末端“去配送中心”的直接配送模式能夠保證在成本維持不變的情況下，提高配送服務(wù)的質(zhì)量和效率。此外，對不同的貨車載重量進行了分析，得出最佳高鐵快運末端配送方案，為高鐵快運末端配送路徑規(guī)劃提供一定指導(dǎo)和決策支持。