基于遺傳算法的無(wú)人配送車(chē)路徑研究

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

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

"中圖分類(lèi)號(hào)：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 "引 "言

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

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

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

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

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

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

2.1 "問(wèn)題描述

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

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

"（2）每臺(tái)智能無(wú)人快遞配送車(chē)的載重量恒定，且需要執(zhí)行無(wú)人配送的任務(wù)點(diǎn)所需貨物重量不超過(guò)單一配送車(chē)的載重量，每個(gè)任務(wù)點(diǎn)的貨物配送只由一輛配送車(chē)來(lái)執(zhí)行。

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

" （4）只有一個(gè)配送中心，配送車(chē)輛的類(lèi)型單一，所有的車(chē)輛均以配送中心為起點(diǎn)，配送完成后返回配送中心。

"（5）貨物流向?yàn)閱蜗颍粓?zhí)行配送任務(wù)。

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

"（7）無(wú)人配送車(chē)完成貨物裝載后開(kāi)始配送的時(shí)刻為0。

2.2 "模型建立

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

N：客戶點(diǎn)集合；

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

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

Q：無(wú)人配送車(chē)的額定載重量；

d：點(diǎn)i到點(diǎn)j的距離，i，j∈V；

q：客戶點(diǎn)i的需求量，f∈N；

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

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

t：無(wú)人配送車(chē)抵達(dá)任務(wù)點(diǎn)i的時(shí)間；

X：二元決策變量，配送車(chē)從點(diǎn)i到點(diǎn)j則為1，否則為0；

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

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

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

3 "算法設(shè)計(jì)

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

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

（1）編碼設(shè)計(jì)

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

（2）插入算子

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

（3）初始種群生成

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

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

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

"（5）選擇算子

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

"（6）交叉算子

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

"（7）變異算子

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

4 "實(shí)驗(yàn)與分析

4.1 "實(shí)驗(yàn)環(huán)境介紹

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

4.2 "算例介紹

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

4.3 "實(shí)驗(yàn)結(jié)果分析

兩點(diǎn)之間直線最短，但是正向行進(jìn)更為符合無(wú)人配送車(chē)的實(shí)際行進(jìn)過(guò)程，可以采用橫縱坐標(biāo)的差值絕對(duì)值之和來(lái)替代歐氏距離近似作為不同任務(wù)點(diǎn)之間的距離，配送路徑采用直線端點(diǎn)所構(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é) "論

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

參考文獻(xiàn)：

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

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

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

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

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

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

8df86285.html.