基于不同車型的城市快遞配送車輛路徑優(yōu)化研究

鄧學(xué)平　孫芹　田帥輝

摘要：在城市快遞配送的業(yè)務(wù)中，車型的不同以及配送線路的選擇都會影響企業(yè)的成本、效益。如何能夠在不同車型的情況下，選擇合理的配送線路，保質(zhì)保量的完成快件的配送。在此背景下，本文建立了基于時間窗、多車型城市快遞配送路徑優(yōu)化的成本最小化數(shù)學(xué)模型。使用兩點互異和兩點交叉改進(jìn)的遺傳算法對模型進(jìn)行計算。運(yùn)用Matlab軟件對城市快遞配送算例進(jìn)行仿真，驗證模型的有效性及適用性。

Abstract： In the business of urban express delivery， the different models and the choice of distribution routes will affect the cost and benefit of the enterprises. How to choose a reasonable distribution route in the case of different models， and complete the delivery of express mail with quality and quantity guaranteed？ In this context， this paper establishes a mathematical model of cost minimization based on time window and multi-model city express delivery route optimization. The model is solved by an improved genetic algorithm with two points crossing and two different points. The Matlab software is used to simulate the urban express delivery example to verify the applicability and effectiveness of the model.

關(guān)鍵詞：城市快遞配送;時間窗;多車型;遺傳算法

Key words： urban express delivery;time windows;multi-model;genetic algorithm

中圖分類號：F570.5? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號：1006-4311（2020）12-0275-06

0? 引言

近幾年，隨著知識的進(jìn)步，科技日新月異的發(fā)展，人們迅速步入了信息社會。為了便捷，熱衷于網(wǎng)購的人逐年增多，快遞也漸漸成為網(wǎng)購者日常生活的一部分。據(jù)國家郵政管理局最新統(tǒng)計數(shù)據(jù)顯示：2019年1月至9月全國快遞業(yè)務(wù)量達(dá)439.1億件，同比增長26.4%;業(yè)務(wù)收入為5271億元，同比增長24.1%。其中，同城業(yè)務(wù)量為78.3億件，同比下降1.7%;異地業(yè)務(wù)量為350.7億件，同比增長35%;國際/港澳臺業(yè)務(wù)量為10億件，同比增長27.2%?？爝f公司為了提升自身行業(yè)競爭力，往往在快遞配送過程中把客戶滿意度和配送成本作為首要目標(biāo)，然而目標(biāo)的實現(xiàn)需要在配送路徑上體現(xiàn)。因此如何選擇合適的配送線路，既能在客戶要求的時間內(nèi)將快件準(zhǔn)時無誤送達(dá)，又能為企業(yè)節(jié)約成本顯得尤為重要。

對于車型不同車輛路徑問題方面的相關(guān)研究，葛顯龍[1]等人根據(jù)動態(tài)信息產(chǎn)生的時間點不同，提出時間軸的概念，建立多車型車輛調(diào)度模型。仝凌云[2]等人從低碳環(huán)保角度出發(fā)，建立以油耗費用和固定發(fā)車費用為優(yōu)化目標(biāo)的低油耗多車型的數(shù)學(xué)模型。陳呈頻[3]等人針對解的質(zhì)量差和求解效率低的問題，建立了多車型多車場的整數(shù)規(guī)劃模型。

對于城市快遞配送問題方面的研究，張曉[4]根據(jù)在城市快遞配送過程中存在的許多特點，構(gòu)建雙類別快遞配送模型。楊志清[5]考慮到時間的不確定性以及車型的因素，構(gòu)建了帶時間窗的多目標(biāo)車輛路徑問題模型。

對于VRPTW，國內(nèi)外對此也進(jìn)行了研究，文獻(xiàn)[6]構(gòu)建了基于時間窗的逆向物流車輛路徑模型，采用混合優(yōu)先級嵌套遺傳算法進(jìn)行求解。文獻(xiàn)[7]在設(shè)計局部優(yōu)化框架的基礎(chǔ)上，結(jié)合遺傳算法來解決帶時間窗的車輛路徑問題。文獻(xiàn)[8]構(gòu)建了關(guān)于硬時間窗的隨機(jī)動態(tài)問題模型。

本文主要研究基于車型不同的帶時間窗的城市快遞配送路徑優(yōu)化問題，建立配送成本最小化為目標(biāo)的車輛路徑優(yōu)化模型，并采用改進(jìn)的遺傳算法對其模型進(jìn)行求解。

1? 問題描述及模型

1.1 問題描述

基于不同車型的城市快遞配送車輛路徑優(yōu)化研究可以詳細(xì)描述為：快遞企業(yè)根據(jù)區(qū)域內(nèi)每個站點需要派件的快件數(shù)量，在已知轉(zhuǎn)運(yùn)中心條件下，尋找最佳快遞配送線路，不僅使企業(yè)的快遞配送成本最小而且又能在站點要求的時效內(nèi)將快件送達(dá)。

實際場景：將快遞配送系統(tǒng)中的節(jié)點簡化為轉(zhuǎn)運(yùn)中心、站點。配送網(wǎng)絡(luò)結(jié)構(gòu)圖如圖1所示，不同車型的配送車輛從轉(zhuǎn)運(yùn)中心出發(fā)，按照一定的線路經(jīng)過各個站點為其提供服務(wù)，最后回到轉(zhuǎn)運(yùn)中心，形成一個閉環(huán)環(huán)路。在快遞的實際配送過程當(dāng)中，我們不能把所有的配送車輛都認(rèn)為是同種車型，車型不同，車輛的油耗不盡相同，產(chǎn)生的運(yùn)輸成本也就不同。因此，我們必須考慮不同車型產(chǎn)生的油耗成本即運(yùn)輸成本。本文的目標(biāo)函數(shù)是實現(xiàn)企業(yè)的快遞配送成本最小，包含配送車輛的時間懲罰成本和運(yùn)輸成本。

1.2 模型假設(shè)（表1）

1.3 參數(shù)定義

1.3.1 參數(shù)定義

本文模型中的已知參數(shù)含義如表2。

1.3.2 決策參數(shù)定義

本文模型中的已知參數(shù)含義如表3。

1.4 目標(biāo)函數(shù)定義

目標(biāo)函數(shù)：右邊第一部分表示車型為r的車輛空載時的耗油成本，第二部分表示車型為r的車輛k從站點i行駛到站點j的耗油成本，第三、四部分為時間懲罰成本。

2? 模型求解

為解決不同車型城市快遞配送車輛路徑優(yōu)化問題，使用改進(jìn)的遺傳算法對模型進(jìn)行計算。車輛的配送路線用染色體編碼來轉(zhuǎn)化，基因則代表轉(zhuǎn)運(yùn)中心、配送站點，形成初始種群;對超過配送站點時間限制的車輛進(jìn)行對應(yīng)的懲罰，計算目標(biāo)函數(shù)的最小值，得到個體適應(yīng)度;再對種群進(jìn)行選擇、交叉、變異和多次迭代后，最終形成最優(yōu)路徑。

2.1 染色體編碼

對于城市快遞配送車輛調(diào)度問題而言，遺傳算法主要是解決快遞車輛服務(wù)的客戶群問題，所以序列編碼的方法比較適合文獻(xiàn)[9]。用數(shù)字0表示轉(zhuǎn)運(yùn)中心，1，2，…，n表示n個站點，將2個數(shù)字0分別作為染色體的頭部和尾部，剩余的數(shù)字0嵌插到1，2，…n之間，形成0，1，2，3，4，0，5，6，0，…，n，0這樣的染色體編碼結(jié)構(gòu)，兩個0之間的部分代表染色體的一條子路徑。例如染色體編碼（02560840317090）所代表的實際含義為車輛一從轉(zhuǎn)運(yùn)中心出發(fā)，依次經(jīng)過配送站點2，5，6，最后返回到轉(zhuǎn)運(yùn)中心，是第一條子路徑;車輛二也是從轉(zhuǎn)運(yùn)中心出發(fā)，依次經(jīng)過站點8，4，返回到轉(zhuǎn)運(yùn)中心，是第二條子路徑;車輛三從轉(zhuǎn)運(yùn)中心出發(fā)，依次經(jīng)過站點3，1，7，返回到轉(zhuǎn)運(yùn)中心，是第三條子路徑;車輛四從轉(zhuǎn)運(yùn)中心出發(fā)，經(jīng)過配送站點9返回到轉(zhuǎn)運(yùn)中心，是第四條子路徑。

相對應(yīng)的配送路徑如下所示（0表示轉(zhuǎn)運(yùn)中心）：

第一條路徑：0-2-5-6-0

第二條路徑：0-8-4-0

第三條路徑：0-3-1-7-0

第四條路徑：0-9-0

2.2 初始種群

雖然初始群體的解分布不影響目標(biāo)函數(shù)的最優(yōu)解，但是如果初始群體的解是均勻分布的，則會大大減少算法陷入局部最優(yōu)的可能性，所以本文在保證多樣性的同時，隨機(jī)產(chǎn)生初始群體。

2.3 適應(yīng)度函數(shù)

本文的適應(yīng)度函數(shù)為目標(biāo)函數(shù)的倒數(shù)，其中fi是染色體的適應(yīng)度值，Zi是染色體i的目標(biāo)函數(shù)值[10]。

2.4 選擇算子

本文采用輪盤賭[11]選擇算子的方法來保證種群的多樣性同時避免適應(yīng)度高的個體被后續(xù)的遺傳操作改變。詳細(xì)選擇操作如表4。

2.5 交叉操作

本文交叉操作選用兩點交叉法[12]，具體的操作描述如下：假設(shè)存在兩個父代個體為“5，4，1，6，2，9，7，8，3”和“1，3，7，4，6，8，2，9，5”。首先確定交叉的起始位置，對兩個位置中間的數(shù)據(jù)執(zhí)行交叉操作。其次為沖突檢測。最后形成新的染色體。交叉操作的過程圖如圖2。

2.6 變異操作

本文采取兩點互異[12]的變異操作。變異操作簡單來說就是等位基因的替換，以此來形成新的個體。一個父代染色體的基因為“1，3，7，4，6，8，2，9，5”，變異基因節(jié)點為7和2，變異操作的過程只需要交換節(jié)點7和2的位置，就形成了新的基因。變異操作的示意圖如圖3。

2.7 算法終止條件

運(yùn)用遺傳算法進(jìn)行計算的時候，當(dāng)出現(xiàn)以下幾個規(guī)則時，停止運(yùn)行算法：①算法運(yùn)行到事先設(shè)定的迭代次數(shù)或者達(dá)到實現(xiàn)預(yù)設(shè)的時間值;②連續(xù)進(jìn)行若干次迭代，但都沒有更好的適應(yīng)目標(biāo)值;③根據(jù)設(shè)定的問題邊界，并結(jié)合偏差值來進(jìn)行運(yùn)算，當(dāng)所求結(jié)果的偏差水平處在合理范圍時，則停止運(yùn)行算法并將求解的數(shù)值輸出。

2.8 遺傳算法參數(shù)

①種群規(guī)模：200;②迭代次數(shù)：300;③變異概率：0.01;④交叉概率：0.8。

2.9 算法靈敏度分析

遺傳算法中有許多參數(shù)設(shè)置，參數(shù)不同，出現(xiàn)的最終結(jié)果也不盡相同。參數(shù)設(shè)置包括：種群規(guī)模、迭代次數(shù)、變異概率、交叉概率。以下詳細(xì)闡述不同參數(shù)設(shè)置對算法的影響。

①種群規(guī)模。

分別選取100、150、200、250、300的種群規(guī)模，運(yùn)行5次，取其平均值，其他參數(shù)設(shè)置為：停止迭代次數(shù)200次，變異概率0.01，交叉概率為0.8。詳細(xì)數(shù)據(jù)如表5。

種群規(guī)模為100、150、200、250、300，目標(biāo)函數(shù)收斂圖如圖4、圖5、圖6、圖7、圖8。

從表5可以看出，收斂代數(shù)以及最優(yōu)解都隨著種群規(guī)模的變化而變化，但沒有明顯的變化趨勢。

②迭代次數(shù)。

分別選取300、400、500、600、700的迭代次數(shù)。其他參數(shù)設(shè)置為：種群規(guī)模為200，變異概率0.01，交叉概率為0.8。具體數(shù)據(jù)如表6。

從表6可以看出，收斂代數(shù)以及最優(yōu)解也是隨著迭代次數(shù)的變化而變化，但沒有出現(xiàn)明顯的變化趨勢。

③變異概率。

分別選取0.01、0.04、0.08、0.1、0.12的變異概率。其他參數(shù)設(shè)置為：種群規(guī)模為200，停止迭代次數(shù)300，交叉概率為0.8。具體數(shù)據(jù)如表7。

從表7可以看出，隨著算法變異概率的改變，迭代次數(shù)沒有一個固定的變化趨勢，最優(yōu)解的呈現(xiàn)先減小后增大。

④交叉概率。

對于算法中的交叉概率，分別取0.4、0.5、0.6、0.8、0.9。其他參數(shù)設(shè)置為：迭代次數(shù)為300，變異概率為0.01，種群規(guī)模為200。具體數(shù)據(jù)如表8。

從表8可以看出，隨著算法交叉概率的改變，迭代次數(shù)先增大后減小，最優(yōu)解沒有固定的變化趨勢。

3? 算例驗證

3.1 數(shù)據(jù)生成與處理

以百世快遞重慶分公司為例，整個大重慶市內(nèi)，只有1個轉(zhuǎn)運(yùn)中心，69個下屬站點。假設(shè)轉(zhuǎn)運(yùn)中心有三種不同的車型，載重量分別為3t，5t，8t，載容量分別為2000，3000，5000，不設(shè)定三種配送車型的最大行駛距離，三種車型的費用參數(shù)見表9，轉(zhuǎn)運(yùn)中心數(shù)據(jù)見表10，69個站點的坐標(biāo)和快件量見表10。假設(shè)配送車輛早于站點要求的時間內(nèi)到達(dá)的成本5元/小時，晚于客戶要求時間到達(dá)的成本10元/小時，計算的距離為兩個站點之間的直線距離，該距離可以通過百度APP計算得到。

根據(jù)轉(zhuǎn)運(yùn)中心及各個站點自身的經(jīng)緯度，利用地圖慧App，把每個點在百度地圖上表示出來，如圖9。

3.2 結(jié)果分析

①利用MATLAB軟件對該模型進(jìn)行求解，基于不同車型的城市快遞配送車輛路徑優(yōu)化研究問題的詳細(xì)結(jié)果可以表述表述為：總共需要11輛配送車輛，即3輛車型一的配送車輛，4輛車型二的配送車輛，4輛車型三的配送車輛，最小配送成本為4074元。具體的如表11所示。

最優(yōu)的目標(biāo)函數(shù)收斂圖10。

從圖10可以得出，在最初算法優(yōu)化階段，迭代次數(shù)達(dá)到10時最優(yōu)個體適應(yīng)值急速下降，但隨著迭代次數(shù)的逐漸增加，最優(yōu)個體適應(yīng)值的下降逐漸平緩，并在第196代收斂于最優(yōu)解4074。

4? 結(jié)束語

本文針對不同載重的城市快遞配送車輛，采用以百世快遞為主體，把重慶市內(nèi)每個配送站點的時間要求轉(zhuǎn)化為時間成本加入目標(biāo)函數(shù)中，建立一個不同車型的受時間窗約束的配送車輛路線模型，最終目標(biāo)是求解配送車輛的最小成本。運(yùn)用改進(jìn)的遺傳算法對其模型進(jìn)行求解，同時對遺傳算法進(jìn)行靈敏度分析，并用Matlab軟件對其案例進(jìn)行仿真，得到本文車型不同的城市快遞車輛路徑問題的最優(yōu)路徑。本文提出的觀點為快遞企業(yè)的快遞配送問題提供參考依據(jù)。本文在研究不同車型的城市快遞配送的問題中，沒有考慮速度的變化，文章假定的是相同速度，可在以后的研究中進(jìn)行改進(jìn)。

參考文獻(xiàn)：

[1]葛顯龍，許茂增，王偉鑫.多車型車輛路徑問題的量子遺傳算法研究[J].中國管理科學(xué)，2013（1）：125-133.

[2]仝凌云，王琳.低油耗多車型車輛路徑問題及算法[J].河北工業(yè)大學(xué)學(xué)報，2019，48（02）：94-100.

[3]陳呈頻，韓勝軍，魯建廈，等.多車場與多車型車輛路徑問題的多染色體遺傳算法[J].中國機(jī)械工程，2018，29（02）：96-101.

[4]張曉.城市快遞配送車輛路徑規(guī)劃研究[D].2016.

[5]楊志清.城市快遞配送條件下的多目標(biāo)車輛路徑優(yōu)化研究[D].

[6]Ma Y ， Li Z ， Yan F ， et al. A hybrid priority-based genetic algorithm for simultaneous pickup and delivery problems in reverse logistics with time windows and multiple decision-makers[J]. Soft Computing - A Fusion of Foundations， Methodologies and Applications， 2019.

[7]Ursani Z， Essam D， Cornforth D， et al. Localized genetic algorithm for vehicle routing problem with time windows[J]. Applied Soft Computing Journal， 2011， 11（8）：5375-5390.

[8]Chang T S， Wan Y W， Ooi W T. A stochastic dynamic traveling salesman problem with hard time windows[J]. European Journal of Operational Research， 2009， 198（3）：748-759.

[9]胡乃平，于豐平.基于混合遺傳算法的車輛路徑優(yōu)化問題研究[J].計算機(jī)與數(shù)字工程，2018，46（6）：1123-1129.

[10]陳婷.基于帶時間窗的快遞車輛路線安排問題研究[D].

[11]宋汶軒.城市快遞配送車輛路徑規(guī)劃研究[D].北京郵電大學(xué)，2019.

[12]鄧學(xué)平，周昔敏，田帥輝.B2C電子商務(wù)物流中心選址-路徑綜合優(yōu)化研究[J].重慶郵電大學(xué)學(xué)報（自然科學(xué)版），2016，28（04）：593-600.