王劍澤 廖儀佳 郭婷婷

A公司快遞配送車輛路徑優(yōu)化研究

王劍澤，廖儀佳，郭婷婷

（西南石油大學(xué)，四川 成都? 610500）

摘? 要：經(jīng)濟(jì)的增長及電商行業(yè)的興盛，促進(jìn)了我國快遞行業(yè)的高速發(fā)展。為解決日益增長的快遞配送需求和效益低下的傳統(tǒng)快遞配送之間的矛盾，文章以A公司北京市順義區(qū)的快遞配送為例，綜合考慮車輛配送成本和一般路徑約束等條件，構(gòu)建了以配送成本最小為目標(biāo)的車輛路徑問題的數(shù)學(xué)模型，并運用遺傳算法對模型進(jìn)行了求解，最終有效地降低了A公司配送成本，優(yōu)化了配送車輛調(diào)度，證實了算法的可行性。

關(guān)鍵詞：物流配送；快遞配送；遺傳算法；路徑優(yōu)化

中圖分類號：TP18? ? 文獻(xiàn)標(biāo)識碼：A? 文章編號：2096-4706（2023）02-0141-04

Research on Path Optimization of Express Delivery Vehicles of Company A

WANG Jianze， LIAO Yijia， GUO Tingting

（Southwest Petroleum University， Chengdu? 610500， China）

Abstract： The economic growth and the prosperity of the E-Commerce industry have promoted the rapid development of our country's express delivery industry. In order to solve the contradiction between the growing demand for express delivery and the traditional express delivery with low efficiency， this paper takes the express delivery of company A in Shunyi District， Beijing as an example， and comprehensively considers the conditions of vehicle delivery cost and general path constraints， and constructs a mathematical model of the vehicle path problem with the minimum cost for delivery as the goal， and the genetic algorithm is used to solve the model， which finally effectively reduces the delivery cost of company A. It optimizes the delivery vehicle scheduling， and proves the feasibility of the algorithm.

Keywords： logistics delivery; express delivery; genetic algorithm; path optimization

0? 引? 言

作為電子商務(wù)的重要構(gòu)成，快遞行業(yè)的發(fā)展同樣遇到了許多問題，面臨著挑戰(zhàn)。尤其是配送的“末端”“最后一公里”等問題需要去探索和研究?？爝f配送不同于一般意義上的傳統(tǒng)物流配送。相比傳統(tǒng)物流，快遞配送最重要的也是最突出的特點是快遞件數(shù)非常多，且快遞的體積較小，重量更輕。

快遞配送路徑優(yōu)化的核心問題是VRP（Vehicle Routing Problem）問題。國內(nèi)外學(xué)者采用多種智能算法對此類問題進(jìn)行了求解，大部分算法的求解效率都比較高。宋娟在解決同城快遞配送問題上，對遺傳算法進(jìn)行改進(jìn)，加入了模擬退火機制改善了尋優(yōu)過程[1]。麻存瑞通過加入快件數(shù)量、快遞員配送時間等考慮因素對快遞配送路徑進(jìn)行了優(yōu)化[2]。楊粟涵基于遺傳算法，對合肥市蜀山區(qū)的知名快遞企業(yè)進(jìn)行了配送路徑優(yōu)化研究并降低了成本[3]。都雪靜考慮車型和自提點因素對小件快遞配送路徑進(jìn)行研究，并應(yīng)用于某企業(yè)驗證了可行性[4]。李玲玉結(jié)合地圖軟件通過C-W節(jié)約算法對快遞配送地點間的真實路徑進(jìn)行了距離優(yōu)化，降低了配送成本[5]。目前，快遞配送的路徑優(yōu)化研究涉及的問題和研究很多，但是針對企業(yè)真實運營狀況做出分析后的快遞配送路徑優(yōu)化的實例論證存在不足，本文將針對A公司快遞企業(yè)的配送情況進(jìn)行分析后，運用遺傳算法進(jìn)行路徑優(yōu)化研究，提高配送效率，降低配送成本。

1? A公司快遞配送情況簡介

該公司在北京市順義區(qū)設(shè)有一個配送中心及30個網(wǎng)點，主營的業(yè)務(wù)范圍為來自各個平臺消費者網(wǎng)購的各種快遞包裹，主要以小件包裹為主，依據(jù)區(qū)域內(nèi)客戶訂單的物品種類、規(guī)格、地點等信息需求進(jìn)行掃描、分類，裝卸和調(diào)度等，最終將物品送往各網(wǎng)點。30個網(wǎng)點的店面規(guī)模大小不同，所處位置不同，也因位置周圍情況不同，各個網(wǎng)點快遞配送的需求量也有著較大差距。所有網(wǎng)點的位置經(jīng)緯度信息和快遞配送需求量如表1所示。

該公司為滿足配送需求，在配送中心配備了多輛配送汽車和駕駛員。一輛配送汽車給多個配送網(wǎng)點送貨，配送汽車根據(jù)配送需求進(jìn)行快遞配送。出發(fā)從配送中心，執(zhí)行完配送目標(biāo)點后回到配送中心。配送車輛的配送固定成本為50元，單位配送成本為每千米5元。如圖1所示，按以往經(jīng)營情況，A公司的平均配送成本3 200 元～3 500 元，配送車輛通常要調(diào)用7～8輛。

由于快遞體積小和重量輕，結(jié)合實際情況，配送車輛的配送限制為載貨量件數(shù)，為200件。如圖2所示，八月初的每日載貨量與圖1對應(yīng)的配送車輛數(shù)的載貨量上限總和相比，相差較大，超出200件，說明配送車輛的調(diào)度不夠合理，載貨率較低。由此可以看出，A公司采用傳統(tǒng)的物流配送方式，物流配送沒路徑規(guī)劃，極大地影響了配送效率，造成配送成本偏高，因此需要對快遞配送路徑進(jìn)行規(guī)劃以降低配送成本，合理調(diào)度車輛。

2? 模型構(gòu)建

2.1? 假設(shè)條件及參數(shù)定義

在對A公司順義區(qū)快遞配送路徑優(yōu)化問題建模的過程中，為保證模型構(gòu)建的準(zhǔn)確性，做相關(guān)假設(shè)如表2所示。模型參數(shù)的定義如表3所示。

2.2? 目標(biāo)函數(shù)模型建立

（1）

s.t：

（2）

（3）

（4）

（5）

（6）

式（1）表示目標(biāo)函數(shù)由兩部分組成，車輛固定成本和運輸成本。式（2）表示如果配送車輛n從網(wǎng)點i駛向網(wǎng)點j，則Xijn等于1，否則等于0；式（3）表示如果配送車輛n為網(wǎng)點i提供服務(wù)，則Yin等于1，否則等于0；式（4）表示配送車輛會給所有網(wǎng)點配送貨物且只由一輛車配送；式（5）表示所有配送車輛都會從配送中心出發(fā)，且完成配送后返回配送中心；式（6）表示每條路徑上的配送貨物件數(shù)不能超過配送車輛的載貨量件數(shù)限制。

3? A公司快遞配送問題求解

3.1? 遺傳算法編碼與解碼

遺傳算法的編碼方式非常多，根據(jù)要解決的問題和模型的構(gòu)建來進(jìn)行選擇。該公司快遞配送屬于典型的VRP問題，故采用序列編碼。配送中心通過數(shù)字0來表示起點和終點，用1、2、3等數(shù)字來表示表格里對應(yīng)標(biāo)號的配送網(wǎng)點。從配送中心出發(fā)的車輛，根據(jù)配送需求前往對應(yīng)標(biāo)號的網(wǎng)點后返回配送中心，數(shù)字編碼的順序就是配送車輛先后前往網(wǎng)點的順序。例如一串編碼為0-5-7-2-4-0，就表示一輛配送車輛從配送中心出發(fā)，先前往網(wǎng)點5進(jìn)行配送，然后依次前往網(wǎng)點7、網(wǎng)點2、網(wǎng)點4進(jìn)行配送，最終回到配送中心。同時編碼所得到的染色體還要進(jìn)行解碼，從配送中心0開始，按照配送車輛的快件數(shù)量約束放入染色體基因序列中。若到某一配送網(wǎng)點時發(fā)現(xiàn)不滿足約束時，就需要取消當(dāng)前車輛在此網(wǎng)點的編碼并返回配送中心，由下一輛配送汽車為該網(wǎng)點提供服務(wù)。若解碼后滿足所有約束條件，所得到的基因序列便是符合要求的配送路徑。

3.2? 遺傳算子設(shè)計

具體內(nèi)容是：

（1）交叉算子，編碼序列進(jìn)行部分位置的交叉完成交叉操作。

選擇兩個染色體的編碼序列的對應(yīng)部分作為交叉的區(qū)域，如A=02|53618|740，B=03|17586|420；將選擇好的交叉區(qū)域分別加入都彼此的染色體編碼中，且加入位置要相同。A′=0|17586|253618740，B′=0|53618|317586420；分別在A′和B′的原染色體編碼部分依次刪除與交叉區(qū)域重復(fù)的編碼信息，得到A″和B″。A″=0175862340，B″=0536187420。

（2）變異算子，通過對染色體中的基因逆序排列完成變異操作。

（3）選擇算子，采用輪盤賭的選擇策略.在選擇完成后采用精英法則，強行將上一代的最優(yōu)個體直接進(jìn)入下一代。

3.3? 問題求解及結(jié)果分析

該公司配送中心周圍有30個網(wǎng)點，同時配備了足夠的快遞員和配送車輛，配送車輛載貨量的限制為200件。由上面的表1可知配送網(wǎng)點的經(jīng)緯度坐標(biāo)和貨物需求量，為算法求解更加直觀和快捷，對數(shù)據(jù)進(jìn)行了處理。形成如表4和表5所示的形式，內(nèi)容更加直觀，但表4和表5因內(nèi)容過多，只列出10個網(wǎng)點的內(nèi)容作為示例。采用遺傳算法對處理過的數(shù)據(jù)進(jìn)行求解，利用MATLAB進(jìn)行實現(xiàn)，設(shè)置種群規(guī)模N為80，最大迭代次數(shù)為200，交叉概率Pc=0.9，變異概率Pm=0.09。

通過仿真計算結(jié)果得到如圖3所示的配送路徑圖。同時根據(jù)仿真結(jié)果的數(shù)據(jù)得到如表6所示的配送計劃，最優(yōu)解的序列就是配送車輛前往配送網(wǎng)點的排列。根據(jù)配送網(wǎng)點的件數(shù)累計和可知，共需要6輛車來進(jìn)行快遞配送，配送距離的總和為471。計算可得配送總成本6×50+471×5=2 805。同時也可以看到每條配送路徑上的配送車載貨量均超過150件，載貨率超75%，且5輛車超過180件，達(dá)到90%。相比于A公司往日配送成本和配送車輛的數(shù)量使用均有明顯降低，且從車輛調(diào)度來看，配送車輛的載貨量也飽和。證明了路徑規(guī)劃合理，算法可行。

4? 結(jié)? 論

針對具體企業(yè)的快遞配送路徑優(yōu)化，本文以快遞企業(yè)A公司北京市順義區(qū)的網(wǎng)點快遞配送問題作為研究對象，在分析了A公司的網(wǎng)點快遞配送情況后，構(gòu)建了以配送成本最小為目標(biāo)的配送路徑模型并運用遺傳算法進(jìn)行了優(yōu)化，通過MATLAB仿真得到A公司快遞配送的最優(yōu)路徑。通過結(jié)果分析可知，優(yōu)化后的路徑有效降低了A公司的快遞配送成本，車輛調(diào)度更加合理，車輛載貨率整體飽和。本文提出的觀點可以為快遞企業(yè)的快遞配送問題提供參考依據(jù)。但在研究過程中也發(fā)現(xiàn)了不足，此模型相對簡單，沒有考慮配送時間、車輛速度等其他次要因素，可以在后續(xù)的研究中進(jìn)行改進(jìn)。

參考文獻(xiàn)：

[1] 宋娟，崔艷.基于改進(jìn)遺傳算法的同城快遞配送模型 [J].電子技術(shù)應(yīng)用，2014，40（12）：136-139.

[2] 麻存瑞，柏赟，趙欣苗，等.快遞配送車輛路徑優(yōu)化研究 [J].交通運輸系統(tǒng)工程與信息，2017，17（4）：182-187.

[3] 楊粟涵，于蕾.基于遺傳算法的快遞配送路徑優(yōu)化問題研究 [J].現(xiàn)代信息科技，2020，4（9）：99-100+103.

[4] 都雪靜，孫菲菲，王云浩.小件快遞配送路徑優(yōu)化研究 [J].物流技術(shù)，2018，37（4）：29-35+40.

[5] 李玲玉，張昆.快遞配送路徑的優(yōu)化研究與軟件設(shè)計 [J].計算機工程與科學(xué)，2019，41（8）：1406-1412.

作者簡介：王劍澤（1997.04—），男，漢族，河北廊坊人，碩士研究生在讀，研究方向：物流系統(tǒng)規(guī)劃與設(shè)計。

收稿日期：2022-08-29