摘 "要：電子商務(wù)的發(fā)展勢頭愈發(fā)迅猛，為解決“最后一公里”問題，京東、菜鳥裹裹、毫末智行相繼研發(fā)并推出了“小蠻驢”、“大白”、“小魔駝”等智能無人快遞配送車，希望以人機協(xié)同的新形式更有效地提高物流配送效率，并在校園配送、商超模式、即時配送和無接觸場景配送中得到了廣泛應(yīng)用。文章在對各類智能啟發(fā)式算法的特性進(jìn)行了調(diào)查研究的前提下，在遺傳算法算法的基礎(chǔ)上進(jìn)行改進(jìn)，為無人快遞配送車的路徑規(guī)劃、任務(wù)分配問題給出了一套較為合理的解決方案。

"關(guān)鍵詞：電子商務(wù)；快遞配送；智能啟發(fā)式算法；遺傳算法；路徑規(guī)劃

"中圖分類號：F250 " "文獻(xiàn)標(biāo)志碼：A " "DOI：10.13714/j.cnki.1002-3100.2024.23.002

Abstract： The development momentum of e-commerce is becoming increasingly rapid. In order to solve the \"last mile\" problem， JD， Cainiao Baobao， and Mimo Zhixing have successively developed and launched intelligent unmanned express delivery vehicles such as \"Little Man Donkey\"， \"Big White\"， and \"Little Magic Camel\". They hope to improve logistics and distribution efficiency more effectively through new forms of human-machine collaboration， and have been widely used in campus distribution， supermarket mode， instant delivery， and contactless scene delivery. Based on the investigation and research of the characteristics of various intelligent heuristic algorithms， this article improves the genetic algorithm and provides a relatively reasonable solution for the path planning and task allocation problems of unmanned express delivery vehicles.

Key words： e-commerce; express delivery; intelligent heuristic algorithms; genetic algorithms; path planning

0 "引 "言

近年來，伴隨著互聯(lián)網(wǎng)的快速發(fā)展和移動支付技術(shù)的更廣泛普及，越來越多的人更愿意在PC端和移動端輕松實現(xiàn)線上購物，物流網(wǎng)絡(luò)的趨近完善和邊際效應(yīng)所產(chǎn)生的影響推動了快遞成本的不斷降低，消費主義的盛行又進(jìn)一步加劇了人們對物質(zhì)欲望的渴求，每逢六一八、雙十一等購物節(jié)來臨時，即便工作人員加班加點，交易量的激增也會導(dǎo)致大量快遞包裹堆積在驛站的情況出現(xiàn)[1]。幸運的是，時代在發(fā)展，科技在進(jìn)步，人工智能技術(shù)和物聯(lián)網(wǎng)技術(shù)的不斷突破正在推動著我們的生活由信息化走向智能化，越來越多的無人快遞配送車開始持證上崗為快遞配送提供便利。而合理的路徑規(guī)劃設(shè)計可以提高物流配送效率，滿足日益?zhèn)€性化的配送需求，減輕快遞驛站的存取壓力的同時緩解節(jié)假日期間快遞驛站人流擁堵的現(xiàn)象。

1 "相關(guān)研究現(xiàn)狀

各類智能啟發(fā)式算法借助了自然界的機制或特性構(gòu)造生成，20世紀(jì)80年代以來，其算法迭代機制被廣泛應(yīng)用于車輛路徑和物流選址等運籌學(xué)問題的求解中。在對車輛路徑問題的研究當(dāng)中，主要以汽車和電動汽車的研究較為廣泛，而有關(guān)于無人配送車和配送機器人路徑的相關(guān)研究還較少，且主要集中于混合時間窗領(lǐng)域。無人快遞配送車需要在特定時間段將特定貨物送達(dá)指定收貨人手中，此外，配送車的載重量有限，因此，智能無人快遞配送車的路徑規(guī)劃問題也可參考帶載重量的車輛路徑規(guī)劃問題（CVRP）、帶時間窗的車輛路徑規(guī)劃（VRPTW）問題相關(guān)研究。

"CVRPTW（Capicitated Vehicle Route Problem with Time Window）問題是在VRP（Vehicle Route Problem）問題的基礎(chǔ)上，引入了載重量、時間窗的相關(guān)概念，從而對配送過程加以時間限制的一個衍生變體，其中，時間窗又分為硬時間窗、軟時間窗和混合時間窗，在硬時間窗情形下，晚于客戶規(guī)定的時間窗到達(dá)，則客戶不接受貨物。而在軟時間窗情形下，客戶接收貨物，但是會收到一定懲罰。無論硬時間窗還是軟時間窗，早于規(guī)定時間到達(dá)，都要付出機會成本，此外，軟時間窗情形下，晚于規(guī)定時間抵達(dá)還需要付出懲罰成本。機會成本和懲罰成本的數(shù)值由時間長短和懲罰系數(shù)決定，而混合時間窗則是將軟時間窗和硬時間窗相結(jié)合，軟時間窗的范圍設(shè)定小于硬時間窗，超出硬時間窗則不接受貨物，超出軟時間窗則接受懲罰?；旌蠒r間窗的路徑規(guī)劃在車輛路徑的相關(guān)研究中應(yīng)用最為廣泛。

"在使用智能啟發(fā)式算法求解帶時間窗的車輛路徑問題相關(guān)研究中，高升[2]在汽車配送模型的基礎(chǔ)上，結(jié)合電動車的特性構(gòu)建了以總成本最小為目標(biāo)的數(shù)學(xué)模型，并基于遺傳算法的基本原理設(shè)計了合適的染色體編碼方式和遺傳算子求解模型。周航等[3]基于遺傳算法和禁忌搜索算法的原理特性，提出了一種遺傳禁忌混合搜索算法機制，經(jīng)驗證其算法收斂速度明顯優(yōu)于遺傳算法（GA）和禁忌搜索（TS）任意單一算法，為智能搬運機器人的任務(wù)分配、自動化倉儲的有效實現(xiàn)提供了參考方案。賀琪[4]基于帕累托優(yōu)化概念提出了一種混合鄰域進(jìn)化算法，充分利用了局部搜索算法和進(jìn)化算法的優(yōu)勢，求解了一個帶有硬時間窗的多目標(biāo)車輛配送模型，并得到了帕累托可行解集。

2 "帶硬時間窗的CVRPTW模型構(gòu)建

2.1 "問題描述

"智能快遞車就好比一臺移動的快遞柜，取件人通過app、小程序填寫時間、地點等信息進(jìn)行預(yù)約取件，由快遞員為智能快遞車進(jìn)行人工貨物裝載，而后快遞車開始執(zhí)行配送任務(wù)，在特定的時間段抵達(dá)特定地點，并提前用短信或電話通知收貨人，其用取件碼或掃碼完成取件。有若干車輛為若干取件人進(jìn)行服務(wù)，根據(jù)相關(guān)資料，菜鳥裹裹的“小蠻驢”以及京東的“大白”等無人配送車充電一次能行駛幾十公里，滿足全天需求，因此本文設(shè)定配送車電量充盈，無需充電樁進(jìn)行補給。無人配送車需在規(guī)定時間完成配送任務(wù)，因此本文的研究屬于硬時間窗車輛路徑研究范疇，從無人配送車到達(dá)指定任務(wù)點后開始等待到取件完成后的時間為服務(wù)時間，當(dāng)前任務(wù)點服務(wù)完成后配送車?yán)^續(xù)前往下一任務(wù)點執(zhí)行任務(wù)或任務(wù)完成返回配送中心。模型建立的目標(biāo)為力求使所有配送車輛的總行駛里程最小化，從而降低運輸成本。為了方便對模型進(jìn)行求解，結(jié)合實際配送案例，本文針對智能無人配送快遞車的貨物裝載、配送行進(jìn)做出以下假設(shè)：

"（1）假設(shè)智能無人快遞配送車行進(jìn)速度恒定，且不考慮道路擁堵以及惡劣天氣、車輛故障等不可抗力因素等[2]。

"（2）每臺智能無人快遞配送車的載重量恒定，且需要執(zhí)行無人配送的任務(wù)點所需貨物重量不超過單一配送車的載重量，每個任務(wù)點的貨物配送只由一輛配送車來執(zhí)行。

" （3）已知客戶預(yù)約的配送時間段，地點信息。

" （4）只有一個配送中心，配送車輛的類型單一，所有的車輛均以配送中心為起點，配送完成后返回配送中心。

"（5）貨物流向為單向，只執(zhí)行配送任務(wù)。

"（6）所有任務(wù)點的服務(wù)時間為固定值已知。

"（7）無人配送車完成貨物裝載后開始配送的時刻為0。

2.2 "模型建立

對數(shù)學(xué)模型中的相關(guān)概念使用特定參數(shù)進(jìn)行如下定義[2]：

N：客戶點集合；

O：配送中心，下標(biāo)用o表示；

V：任務(wù)點、配送中心等點的集合，下標(biāo)用v表示，V=NUO；

Q：無人配送車的額定載重量；

d：點i到點j的距離，i，j∈V；

q：客戶點i的需求量，f∈N；

e：客戶點i預(yù)約時間段的起始時間， i∈N；

l：客戶點i預(yù)約時間段的結(jié)束時間，i∈N；

t：無人配送車抵達(dá)任務(wù)點i的時間；

X：二元決策變量，配送車從點i到點j則為1，否則為0；

Y：二元決策變量，客戶點i的任務(wù)由車輛k完成則為1，否則為0。

構(gòu)造的CVRPTW模型如下所示：

式（1）為目標(biāo)函數(shù)，即模型追求在滿足特定時間窗約束的條件下，使得所有配送車的配送路徑里程最小。式（2）為每一輛無人配送車都以配送中心為起點和終點。式（3）為載重量約束條件，保證單一車輛執(zhí)行的所有配送任務(wù)的貨物重量之和不超過車輛載重量。式（4）為時間窗約束條件，即配送車在抵達(dá)并完成服務(wù)后的時間在規(guī)定的時間窗范圍內(nèi)。

3 "算法設(shè)計

遺傳算法（Genetic Algorithm）是模擬生物在自然環(huán)境中的遺傳和進(jìn)化的過程而形成的自適應(yīng)全局優(yōu)化搜索算法。它遵循適者生存、優(yōu)勝劣汰的原則，其基本思想是從一個初始種群開始，通過模擬自然選擇、交叉、變異三種操作，不斷優(yōu)化種群[5]。

"本文的遺傳算法設(shè)計，在充分利用了輪盤賭規(guī)則增加解和種群的多樣性的基礎(chǔ)上，在初始種群的生成中貪婪構(gòu)造一定量的解，并在選擇操作中直接保留一部分適應(yīng)度較高的解，從而加快算法收斂速度，更高效地獲得優(yōu)質(zhì)解。

（1）編碼設(shè)計

"為方便模型求解和算法構(gòu)造，采用自然數(shù)編碼格式，染色體長度為m+n+1，其中m表示客戶點數(shù)量，n為配送車數(shù)量，配送中心的編碼為0。0表示配送中心，1-m表示配送任務(wù)點[2]。編碼方案中每兩個零之間的數(shù)字編碼依次代表不同車輛的配送方案設(shè)計，單一配送車的編碼數(shù)次序則表明此配送車的任務(wù)執(zhí)行順序。假設(shè)有3輛無人配送車為6個任務(wù)點配送貨物，車輛1為任務(wù)點1、2執(zhí)行配送，車輛2為任務(wù)點3、4執(zhí)行配送，車輛3為任務(wù)點5、6執(zhí)行配送，則完整的編碼方案設(shè)計如下所示：

（2）插入算子

為減少程序迭代次數(shù)，縮短程序運行時間，選擇貪婪構(gòu)造一個初始解，即初始解的插入構(gòu)造優(yōu)先按照距離進(jìn)行。在插入任務(wù)點對應(yīng)編碼的過程中，還需要檢測是否超過了配送車的額定載重量，以及按照既定配速，是否能在規(guī)定的時間窗內(nèi)到達(dá)指定地點完成配送任務(wù)。如果超過了額定載重量，則此車輛的配送任務(wù)結(jié)束，添加自然數(shù)序號0表示任務(wù)結(jié)束，配送車返回配送中心。如果不能滿足規(guī)定的時間窗要求，則忽略此任務(wù)點編碼繼續(xù)執(zhí)行插入操作，其余車輛的配送路徑構(gòu)造以此類推。以前文編碼為例，共有1～6個任務(wù)點，距始發(fā)點距離以此增加，首先插入編碼0代表從配送中心出發(fā)，依次按照距離插入編碼1、2，執(zhí)行插入編碼3操作時出現(xiàn)了超載現(xiàn)象，因此在編碼3之前插入編碼0。

（3）初始種群生成

若初始種群的大小設(shè)定為M，首先使用隨機函數(shù)按照編碼方案隨機生成3/4M份符合配送車載重量的編碼解，將貪婪構(gòu)造的初始解復(fù)制1/4M份與隨機生成的編碼進(jìn)行合并共同組成初始種群。

（4）適應(yīng)度計算

根據(jù)前文所建立的硬時間窗車輛配送路徑模型，在考慮實現(xiàn)最短路徑距離這一目標(biāo)的構(gòu)造基礎(chǔ)上，適應(yīng)度函數(shù)還需要加以時間窗約束條件的限制，設(shè)置一個極大的參數(shù)作為乘數(shù)使得不符合時間窗約束條件的路徑適應(yīng)度計算值極大，從而在迭代過程中被淘汰。

"（5）選擇算子

對種群中的染色體按照適應(yīng)度由高到低進(jìn)行排序，選擇適應(yīng)度較高的前1/4部分，對種群中剩余的染色體依照輪盤賭規(guī)則篩選出1/3部分，將兩部分進(jìn)行合并即為所得。

"（6）交叉算子

"將選擇出的染色體一一配對，每一對染色體都隨機選擇一個車輛的路徑片段，使2個染色體片段各自向另一染色體最前端遷移，再按順序遍歷2 條染色體，去掉重復(fù)基因，運用插入算子補足缺少的編碼0，從而獲得經(jīng)過交叉的1條新個體。

"（7）變異算子

"隨機選擇一輛配送車的路徑編碼并隨機選擇兩個位置進(jìn)行交換，如隨機選擇了第一輛車的第1、2個位置的數(shù)字編碼進(jìn)行交換，變異操作流程如下所示：

4 "實驗與分析

4.1 "實驗環(huán)境介紹

本文選用Python編程語言求解算法，并在Pycharm編輯器中運行求解。Pycharm是一種Python IDE（Integrated Development Environment，集成開發(fā)環(huán)境），帶有一整套可以幫助用戶在使用Python語言開發(fā)時提高其效率的工具，比如調(diào)試、語法高亮、項目管理、代碼跳轉(zhuǎn)、智能提示、自動完成、單元測試、版本控制[6]。實驗使用的Pycharm集成開發(fā)環(huán)境，搭載Python3.9.5版本。

4.2 "算例介紹

"某大學(xué)城校園配送中心有3輛無人快遞配送車，共有27個任務(wù)點有配送任務(wù)待執(zhí)行。無人配送車的載重量為5t，各任務(wù)點序號及詳細(xì)坐標(biāo)值、時間窗約束條件如表1所示：

4.3 "實驗結(jié)果分析

兩點之間直線最短，但是正向行進(jìn)更為符合無人配送車的實際行進(jìn)過程，可以采用橫縱坐標(biāo)的差值絕對值之和來替代歐氏距離近似作為不同任務(wù)點之間的距離，配送路徑采用直線端點所構(gòu)造的兩條直角邊近似代替也更為貼切，因此本文給出了以直線行進(jìn)和以折線行進(jìn)的兩種方案。路徑分別為0-13-9-20-3-12-25-5-23-0-11-19-16-27-24-26-4-22-0-7-1-15-2-6-14-10

-21-17-8-18-0、0-20-11-15-14-25-24-22-23-4-0-1-7-3-16-27-6-0-13-19-9-2-12-10-26-21-5-18-8-17-0，配送路徑規(guī)劃圖如圖1、圖2所示：

5 "結(jié) "論

"本文在帶時間窗的車輛配送路徑問題的研究基礎(chǔ)上，結(jié)合了無人配送車相較于一般車輛的配送特性，對遺傳算法的流程進(jìn)行優(yōu)化，給出了一個較為合理的無人配送車路徑規(guī)劃解決方案。但是本文仍存在著一定的局限性，比如只考慮了貨物重量和配送車輛載重量，未考慮貨物體積和實際車輛容積。此外，多配送中心情形，即車輛分別從不同位置集貨出發(fā)執(zhí)行配送任務(wù)更為符合實際情況，有待后續(xù)進(jìn)一步改進(jìn)優(yōu)化[2]。

參考文獻(xiàn)：

[1] 屠佳若，彭泓銘，易璐，等. 基于消費需求視閾下高校眾包物流模式發(fā)展策略研究[J]. 江蘇商論，2020（12）：39-41，51.

[2] 高升. 基于電動汽車的帶時間窗的路徑優(yōu)化問題研究[D]. 大連：大連海事大學(xué)，2015.

[3] 周航，秦實宏，方?jīng)茇? 基于混合遺傳禁忌搜索算法的多機器人任務(wù)分配[J]. 自動化與儀表，2023，38（11）：35-39.

[4] 賀琪. 帶硬時間窗的車輛路徑優(yōu)化算法研究[D]. 重慶：重慶交通大學(xué)，2023.

[5] 唐瓊，李翠，劉石洋. 基于禁忌搜索算法的生鮮農(nóng)產(chǎn)品冷鏈物流配送路徑優(yōu)化研究[J]. 商業(yè)經(jīng)濟，2022（10）：55-56，65.

[6] 三棵小草. Pycharm的基本使用教程 （1）. [EB/OL]. （2022-03-20）[2024-04-10]. https：//huaweicloud.csdn.net/63802ef4dacf622b

8df86285.html.