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

鄧學平　孫芹　田帥輝

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

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.

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

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

中圖分類號：F570.5? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標識碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號：1006-4311（2020）12-0275-06

0? 引言

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

對于車型不同車輛路徑問題方面的相關研究，葛顯龍[1]等人根據動態信息產生的時間點不同，提出時間軸的概念，建立多車型車輛調度模型。仝凌云[2]等人從低碳環保角度出發，建立以油耗費用和固定發車費用為優化目標的低油耗多車型的數學模型。陳呈頻[3]等人針對解的質量差和求解效率低的問題，建立了多車型多車場的整數規劃模型。

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

對于VRPTW，國內外對此也進行了研究，文獻[6]構建了基于時間窗的逆向物流車輛路徑模型，采用混合優先級嵌套遺傳算法進行求解。文獻[7]在設計局部優化框架的基礎上，結合遺傳算法來解決帶時間窗的車輛路徑問題。文獻[8]構建了關于硬時間窗的隨機動態問題模型。

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

1? 問題描述及模型

1.1 問題描述

基于不同車型的城市快遞配送車輛路徑優化研究可以詳細描述為：快遞企業根據區域內每個站點需要派件的快件數量，在已知轉運中心條件下，尋找最佳快遞配送線路，不僅使企業的快遞配送成本最小而且又能在站點要求的時效內將快件送達。

實際場景：將快遞配送系統中的節點簡化為轉運中心、站點。配送網絡結構圖如圖1所示，不同車型的配送車輛從轉運中心出發，按照一定的線路經過各個站點為其提供服務，最后回到轉運中心，形成一個閉環環路。在快遞的實際配送過程當中，我們不能把所有的配送車輛都認為是同種車型，車型不同，車輛的油耗不盡相同，產生的運輸成本也就不同。因此，我們必須考慮不同車型產生的油耗成本即運輸成本。本文的目標函數是實現企業的快遞配送成本最小，包含配送車輛的時間懲罰成本和運輸成本。

1.2 模型假設（表1）

1.3 參數定義

1.3.1 參數定義

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

1.3.2 決策參數定義

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

1.4 目標函數定義

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

2? 模型求解

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

2.1 染色體編碼

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

相對應的配送路徑如下所示（0表示轉運中心）：

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

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

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

第四條路徑：0-9-0

2.2 初始種群

雖然初始群體的解分布不影響目標函數的最優解，但是如果初始群體的解是均勻分布的，則會大大減少算法陷入局部最優的可能性，所以本文在保證多樣性的同時，隨機產生初始群體。

2.3 適應度函數

本文的適應度函數為目標函數的倒數，其中fi是染色體的適應度值，Zi是染色體i的目標函數值[10]。

2.4 選擇算子

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

2.5 交叉操作

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

2.6 變異操作

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

2.7 算法終止條件

運用遺傳算法進行計算的時候，當出現以下幾個規則時，停止運行算法：①算法運行到事先設定的迭代次數或者達到實現預設的時間值;②連續進行若干次迭代，但都沒有更好的適應目標值;③根據設定的問題邊界，并結合偏差值來進行運算，當所求結果的偏差水平處在合理范圍時，則停止運行算法并將求解的數值輸出。

2.8 遺傳算法參數

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

2.9 算法靈敏度分析

遺傳算法中有許多參數設置，參數不同，出現的最終結果也不盡相同。參數設置包括：種群規模、迭代次數、變異概率、交叉概率。以下詳細闡述不同參數設置對算法的影響。

①種群規模。

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

種群規模為100、150、200、250、300，目標函數收斂圖如圖4、圖5、圖6、圖7、圖8。

從表5可以看出，收斂代數以及最優解都隨著種群規模的變化而變化，但沒有明顯的變化趨勢。

②迭代次數。

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

從表6可以看出，收斂代數以及最優解也是隨著迭代次數的變化而變化，但沒有出現明顯的變化趨勢。

③變異概率。

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

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

④交叉概率。

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

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

3? 算例驗證

3.1 數據生成與處理

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

根據轉運中心及各個站點自身的經緯度，利用地圖慧App，把每個點在百度地圖上表示出來，如圖9。

3.2 結果分析

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

最優的目標函數收斂圖10。

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

4? 結束語

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

參考文獻：

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

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

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

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

[5]楊志清.城市快遞配送條件下的多目標車輛路徑優化研究[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]胡乃平，于豐平.基于混合遺傳算法的車輛路徑優化問題研究[J].計算機與數字工程，2018，46（6）：1123-1129.

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

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

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