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

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

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

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

0? 引言

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

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

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

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

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

1? 問(wèn)題描述及模型

1.1 問(wèn)題描述

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

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

2? 模型求解

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

2.1 染色體編碼

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

相對(duì)應(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)解，但是如果初始群體的解是均勻分布的，則會(huì)大大減少算法陷入局部最優(yōu)的可能性，所以本文在保證多樣性的同時(shí)，隨機(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 選擇算子

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

2.5 交叉操作

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

2.6 變異操作

本文采取兩點(diǎn)互異[12]的變異操作。變異操作簡(jiǎn)單來(lái)說(shuō)就是等位基因的替換，以此來(lái)形成新的個(gè)體。一個(gè)父代染色體的基因?yàn)椤?，3，7，4，6，8，2，9，5”，變異基因節(jié)點(diǎn)為7和2，變異操作的過(guò)程只需要交換節(jié)點(diǎn)7和2的位置，就形成了新的基因。變異操作的示意圖如圖3。

2.7 算法終止條件

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

①種群規(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ī)模的變化而變化，但沒(méi)有明顯的變化趨勢(shì)。

②迭代次數(shù)。

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

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

③變異概率。

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

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

④交叉概率。

對(duì)于算法中的交叉概率，分別取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)解沒(méi)有固定的變化趨勢(shì)。

3? 算例驗(yàn)證

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

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

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

3.2 結(jié)果分析

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

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

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

4? 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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

[5]楊志清.城市快遞配送條件下的多目標(biāo)車(chē)輛路徑優(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]胡乃平，于豐平.基于混合遺傳算法的車(chē)輛路徑優(yōu)化問(wèn)題研究[J].計(jì)算機(jī)與數(shù)字工程，2018，46（6）：1123-1129.

[10]陳婷.基于帶時(shí)間窗的快遞車(chē)輛路線安排問(wèn)題研究[D].

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

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