A公司快遞配送車輛路徑優化研究

王劍澤 廖儀佳 郭婷婷

A公司快遞配送車輛路徑優化研究

王劍澤，廖儀佳，郭婷婷

（西南石油大學，四川 成都? 610500）

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

關鍵詞：物流配送；快遞配送；遺傳算法；路徑優化

中圖分類號：TP18? ? 文獻標識碼：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? 引? 言

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

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

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

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

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

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

2? 模型構建

2.1? 假設條件及參數定義

在對A公司順義區快遞配送路徑優化問題建模的過程中，為保證模型構建的準確性，做相關假設如表2所示。模型參數的定義如表3所示。

2.2? 目標函數模型建立

（1）

s.t：

（2）

（3）

（4）

（5）

（6）

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

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

3.1? 遺傳算法編碼與解碼

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

3.2? 遺傳算子設計

具體內容是：

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

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

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

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

3.3? 問題求解及結果分析

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

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

4? 結? 論

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

參考文獻：

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

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

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

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

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

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

收稿日期：2022-08-29