李詩茵 （浙江理工大學 經(jīng)濟管理學院，浙江 杭州 310018）

0 引 言

近年來，隨著冷鏈物流的發(fā)展和客戶黏性的降低，消費者對生鮮產(chǎn)品配送的及時性提出了更高要求。如何在降低生鮮產(chǎn)品運輸成本的基礎上增加顧客的滿意度，是生鮮產(chǎn)品運輸亟待解決的問題。為此，本文展開了對冷鏈物流路徑優(yōu)化的研究。

車輛路徑問題(VRP)由Dantzig和Ramser于1959年首次提出。近年來，國內(nèi)外眾多學者對冷鏈物流VRP問題進行了廣泛研究。季琳琳等提出以成本與滿意度為雙目標的冷鏈水果運輸模型[1]；李倩等考慮客戶滿意度，以貨損成本、懲罰成本等綜合配送成本最低為目標函數(shù)，構(gòu)建了一個多目標配送路徑優(yōu)化模型[2]；任騰等以車輛載重、客戶時間窗和冷鏈產(chǎn)品變質(zhì)率為約束，構(gòu)建在客戶服務時間范圍內(nèi)以碳排放量最小為優(yōu)化目標的冷鏈車輛路徑優(yōu)化模型[3]?？紤]到生鮮產(chǎn)品的易腐性及生鮮配送的時效性，本文引入模糊梯形函數(shù)來刻畫軟時間窗下的客戶滿意度并構(gòu)建相應的懲罰函數(shù)。

在道路資源日益緊缺的社會背景下，國內(nèi)外對城市交通管制給車輛配送的影響已有一定研究[4-6]。而在考慮飛行限制的無人機配送研究中，Jeong考慮了包裹重量對無人機能耗的影響和受限飛行區(qū)域，并提出了一種兩階段構(gòu)造和搜索啟發(fā)式算法。目前，有關限飛區(qū)等飛行限制對無人機路徑影響的相關研究仍處于起步階段，但是隨著無人機物流逐步走進人們的日常生產(chǎn)生活，考慮飛行限制對無人機配送的影響而對配送路徑進行優(yōu)化，對于提高無人機物流配送效率及客戶滿意度有著重要意義。因此，本文考慮了臨時限飛區(qū)及永久限飛區(qū)對物流路徑規(guī)劃的影響，并綜合考慮客戶滿意度，以無人機載荷限制和飛行距離限制等為約束，構(gòu)建成本最小化及客戶滿意度最大化的雙目標數(shù)學模型并探尋求解算法。

1 問題描述

本文旨在探討在生鮮配送中心利用多架無人機向多個客戶點進行直接配送的情況下，如何在保證配送總成本最小和客戶滿意度最大為雙目標的前提下，建立成本函數(shù)模型。由生鮮產(chǎn)品的新鮮度及每個客戶點的服務時間窗共同決定了客戶的滿意度。由于在任意兩個客戶點之間都可能存在因城市管制或極端惡劣天氣導致的限飛區(qū)，因此無人機應在前往下一個客戶點進行配送服務前，根據(jù)模型決策選擇是否需要繞飛或等待，若需要繞飛，則應重新進行路徑規(guī)劃。

本文在滿足客戶點需求、客戶時間窗、無人機飛行限制約束等條件下，設計出使總成本最小及客戶滿意度最大的混合整數(shù)規(guī)劃模型，模型如下：

約束條件：

式（1）、式（2）表示模型的雙目標函數(shù)；式（3）表示無人機的飛行距離限制；式（4）表示無人機的載荷重量限制；式（5）、式（6）表示每個客戶點均得到配送服務且僅僅被服務一次；式（7）表示從生鮮配送中心出發(fā)前往客戶點的無人機數(shù)量即為派遣的無人機數(shù)量；式（8）表示無人機的耗費時間；式（9）表示配送過程是連續(xù)的，且不考慮無人機在客戶點的服務時間；式（10）表示無人機在限飛區(qū)的等待時間。

2 繞行決策

對于永久限飛區(qū)及長達數(shù)小時的臨時限飛區(qū)，無人機有時無法按照原定的直線配送路徑飛行?？紤]到在實際配送中，由于無人機繞行會產(chǎn)生額外的飛行成本，并且繞行增加的飛行時間有時會大于等待時間，導致客戶滿意度懲罰成本的增加，因此，本文考慮無人機在限飛區(qū)內(nèi)的飛行時間與限飛區(qū)的限飛時間重疊的情況下，無人機可根據(jù)配送成本來選擇等待或繞道飛行限飛區(qū)。

為了更好地規(guī)劃無人機的繞行路徑，首先，對客戶點之間的限飛區(qū)進行統(tǒng)計；然后對限飛區(qū)域按照永久限飛區(qū)及臨時限飛區(qū)進行劃分。對于永久限飛區(qū)，無人機只能選擇繞行；而對于臨時限飛區(qū)，無人機需要進一步根據(jù)限飛時段及成本耗費確定等待或繞行決策。

現(xiàn)有研究中，對于繞行限飛區(qū)，往往采用沿原配送路徑飛至限飛區(qū)，而后旋轉(zhuǎn)繞行該區(qū)域的方式?；谠摲绞剑疚膶@行路徑進行了優(yōu)化，在繞行避過每個限飛區(qū)時，無人機先沿著限飛區(qū)的外切線路徑飛至限飛區(qū)邊緣，隨后可選擇沿限飛區(qū)的左側(cè)或右側(cè)旋轉(zhuǎn)飛行以避開無人區(qū)。若無人機經(jīng)過的限飛區(qū)數(shù)量為m，則無人機共有2m種可能繞行路徑。

若無人機按直線路徑到達限飛區(qū)的時間晚于限飛區(qū)的結(jié)束時間，或無人機離開限飛區(qū)的時間早于限飛區(qū)的開始時間，無人機可按原擬定路徑飛行，無需繞行或等待；對于其他情景，無人機對等待及繞行情況的成本進行比較，從而做出等待或繞行決策。式（11）、式（12）用來判別限飛區(qū)是否需要做出繞行或等待的決策。

3 算法設計

3.1 混合遺傳算法設計

由于遺傳算法直接對結(jié)構(gòu)對象進行操作，不存在求導和連續(xù)性限制，并且具有較好的穩(wěn)定性和全局尋優(yōu)能力，因此被廣泛應用于VRP問題的求解中，但是存在局部搜索能力差和早熟收斂等問題。大型鄰域搜索算法通過在當前解的多個鄰域中尋找更滿意的解，能夠極大地擴大算法在解空間的搜索范圍，但是時間成本較高。模擬退火算法能有效避免優(yōu)化過程中陷入局部最優(yōu)解，但是算法的運行效率不高、進化速度較慢。將遺傳算法與自適應大鄰域搜索算法、模擬退火算法相結(jié)合，使用隨機序列生成方法來構(gòu)造初始解，通過算子間的相互競爭生成當前解的鄰域結(jié)構(gòu)，同時采用Metropolis準則接受差解，對染色體進行進化，可以大幅提升種群的多樣性。同時，基于算法的精英保留策略，每次只會選擇部分染色體參與進化，算法的求解時間不會過度增加。因此，本文設計的混合遺傳算法可以有效地跳出局部最優(yōu)解，以更大的概率獲得全局最優(yōu)解。

首先，對未被服務過的客戶點進行隨機排列，如果能夠滿足如下條件就將其按順序依次放入可訪問列表里面:

該客戶點的貨物重量不超過當前無人機的最大載荷重量；

無人機從配送中心出發(fā)訪問完當前所有客戶點并返回配送中心的距離不超過無人機的最大飛行距離限制。

得到的訪問列表為空，表明當前路線已經(jīng)構(gòu)造完成，無人機就執(zhí)行返回配送中心的操作。重復這一步驟，直至所有客戶點均被服務過。

在計算開始時，每個算子都設置相同的權(quán)重和分值。在每次搜索過程中，破壞和修復算子的選擇都基于輪盤賭規(guī)則，以此增加算子選擇的多樣性。根據(jù)算子的不同表現(xiàn)情況給予得分，得分越高表明算子的表現(xiàn)越好。算法所使用的破壞算子與修復算子如下：

破壞算子1，隨機移除。隨機選擇該路徑上的一個點進行移除，同時更新路徑；

破壞算子2，距離最長移除。隨機選擇一條路徑，移除對路徑長度影響最大的點，以此縮短整條路徑的長度；

修復算子1，隨機插入。將隨機移除的一個點隨機插入一條路徑內(nèi)；

修復算子2，最優(yōu)貪婪插入。隨機選擇一個點，判斷該點插入某位置后該條路徑的總成本增加值，選擇成本增加值最小所對應的位置進行插入。

3.2 混合遺傳算法步驟

混合遺傳算法的具體步驟如下：

Step 1 初始化模型、算法的各項參數(shù)，如初始溫度、初始算子權(quán)重、總循環(huán)次數(shù)、種群數(shù)目等，生成初始編碼；

Step 2 采用隨機序列生成初始解及編碼；

Step 3 計算種群適應度，即總成本目標函數(shù)的倒數(shù)；

Step 4 根據(jù)精英主義選擇前1/3的種群，采用自適應大鄰域搜索算法，根據(jù)算子權(quán)重選擇破壞算子與修復算子，破壞當前編碼、修復被破壞的編碼并生成新編碼；

Step 5 根據(jù)模擬退火算法Metropolis準則以概率接受優(yōu)解和差解進行當前解的更新；

Step 6 若新解優(yōu)于最優(yōu)解，則將當前解替換最優(yōu)解；

Step 7 更新算子的分數(shù)及權(quán)重；

Step 8 更新種群并進行排序；

Step 9 判斷是否達到迭代終止條件（總循環(huán)次數(shù)k達到K），若是，則算法停止計算，輸出最優(yōu)結(jié)果，若否，則跳轉(zhuǎn)至Step3 。

4 算例分析

本文對某生鮮產(chǎn)品公司進行了調(diào)研，并對需要用到的相關數(shù)據(jù)進行收集和整理。

4.1 數(shù)據(jù)準備

本文對客戶點相互之間及生鮮配送中心和客戶點之間的距離均采用直線距離，該距離可根據(jù)客戶和配送中心的坐標計算得到；然后再依次對單日內(nèi)的100個客戶進行編號，統(tǒng)計客戶的需求量、客服期望的時間窗以及7個永久限飛區(qū)和33個臨時限飛區(qū)的禁飛時段。本文將配送中心開始進行配送的時間6:00用0表示，在此基礎上將日常的時鐘時間轉(zhuǎn)化成數(shù)字，比如8:30用150進行簡化處理。最后，設置配送無人機的屬性及貨物的相關參數(shù)，如表1所示。

表1 相關參數(shù)設置

4.2 算例仿真結(jié)果

本文分別采用了模擬退火算法、自適應大鄰域搜索算法及混合遺傳算法進行實驗運算。在參數(shù)相同的情況下，本文在Windows 10系統(tǒng)、16GB內(nèi)存、AMD Ryzen 5 5600H with Radeon Graphics的處理器上采用PYTHON進行無人機配送路徑的仿真實驗?；旌线z傳算法的路徑示意圖如圖1所示。其中，紅色圓形區(qū)域代表繞行或等待的限飛區(qū)，綠色圓點代表客戶點的位置。

圖1 路徑示意圖

算法運行的結(jié)果對比如表2所示。

表2 算法結(jié)果對比

從表2可以看出，與自適應大鄰域搜索算法及模擬退火算法相比，混合遺傳算法的總客戶滿意度數(shù)值分別提高了5.39%及5.65%，總成本下降了28.96元及0.2元。因此，本文所采用的混合遺傳算法與傳統(tǒng)算法相比，可以在耗費較低配送成本的同時取得較高的客戶滿意度。

5 結(jié) 論

本文討論了無人機在兩個客戶點之間至多存在兩個限飛區(qū)的飛行限制情況下，綜合考慮客戶滿意度及配送成本的生鮮產(chǎn)品配送路徑優(yōu)化問題。本研究考慮無人機在限飛區(qū)內(nèi)的飛行時間與限飛區(qū)本身的限飛時間重疊的情況下，無人機可根據(jù)配送成本選擇等待或繞道飛行限飛區(qū)，并對現(xiàn)有研究中的繞行路徑進行了優(yōu)化。本文將自適應大鄰域搜索算法與模擬退火算法及遺傳算法相結(jié)合，大幅提升了編碼的多樣性，擴大了算法在解空間的搜索范圍，進一步提高算法找到更優(yōu)解的概率。最后PYTHON仿真實驗表明，本文所設計的混合遺傳算法有效提高了全局搜索能力，取得了較傳統(tǒng)算法更優(yōu)的解，且迭代次數(shù)較少。此外，研究僅僅考慮了限飛區(qū)對于無人機產(chǎn)生的飛行限制，未來可進一步考慮更多飛行限制情況對無人機物流配送的影響等。