王劍澤 廖儀佳 郭婷婷

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

王劍澤，廖儀佳，郭婷婷

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

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

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

中圖分類號(hào)：TP18? ? 文獻(xiàn)標(biāo)識(shí)碼：A? 文章編號(hào)：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)。尤其是配送的“末端”“最后一公里”等問題需要去探索和研究。快遞配送不同于一般意義上的傳統(tǒng)物流配送。相比傳統(tǒng)物流，快遞配送最重要的也是最突出的特點(diǎn)是快遞件數(shù)非常多，且快遞的體積較小，重量更輕。

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

1? A公司快遞配送情況簡(jiǎn)介

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

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

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

2? 模型構(gòu)建

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

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

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

3.1? 遺傳算法編碼與解碼

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

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

具體內(nèi)容是：

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

選擇兩個(gè)染色體的編碼序列的對(duì)應(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）變異算子，通過對(duì)染色體中的基因逆序排列完成變異操作。

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

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

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

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

4? 結(jié)? 論

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

參考文獻(xiàn)：

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

[2] 麻存瑞，柏赟，趙欣苗，等.快遞配送車輛路徑優(yōu)化研究 [J].交通運(yùn)輸系統(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ì) [J].計(jì)算機(jī)工程與科學(xué)，2019，41（8）：1406-1412.

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

收稿日期：2022-08-29