郭軍華，宋星雨

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

0 引言

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

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

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

1 問題描述與建模

1.1 問題描述

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

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

1.2 模型假設(shè)

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

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

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

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

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

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

表1 符號表示Tab.1 Symbolic representation

1.3 模型建立

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

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

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

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

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

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

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

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

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

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

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

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

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

2 算法設(shè)計

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

2.1 改進(jìn)的遺傳算法

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

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

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

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

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

其中相關(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)準(zhǔn)化后的值，其值在[0，1]之間。

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

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

3.1 算例設(shè)計

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

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

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

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

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

3.2 算法有效性分析

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

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

3.3 算例結(jié)果

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

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

3.4 貨車載重量影響分析

為探究貨車的載重量對配送方案的影響，對比了3 種載重量的貨車，得到3 種貨車載重量的配送方案和貨車滿載率如圖4 所示，由于貨車的載重量不同，所以3 批貨物的貨車滿載率會發(fā)生改變。對比圖4a、圖4b和圖4c可知，載重量為 1000件貨車的平均滿載率最高，達(dá)到了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種貨車載重量的運(yùn)行結(jié)果如表6所示，載重量為 1500 件的貨車運(yùn)輸時間和總成本最低。 1800 件的貨車只在總成本上高于 1500 件的貨車， 1000件的貨車與 1500件的貨車運(yùn)行結(jié)果相比，多花費(fèi)1.2%的運(yùn)輸時間和38.4%運(yùn)輸成本，由于載重量為 1000 件的貨車選擇增加違反時間窗個數(shù)，使最大行駛距離增加了5.4%，從而避免違反貨車載重，保證車輛安全?；谏鲜龇治?，載重量為 1500 件的貨車無論是在時間上還是成本上都優(yōu)于其他2 種載重量的貨車，并且滿載率相對較高，所以使用載重量為 1500 件的貨車在本算例中是最佳方案。

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

4 結(jié)論

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