李詩茵 （浙江理工大學 經濟管理學院，浙江 杭州 310018）

0 引 言

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

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

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

1 問題描述

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

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

約束條件：

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

2 繞行決策

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

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

現(xiàn)有研究中，對于繞行限飛區(qū)，往往采用沿原配送路徑飛至限飛區(qū)，而后旋轉繞行該區(qū)域的方式。基于該方式，本文對繞行路徑進行了優(yōu)化，在繞行避過每個限飛區(qū)時，無人機先沿著限飛區(qū)的外切線路徑飛至限飛區(qū)邊緣，隨后可選擇沿限飛區(qū)的左側或右側旋轉飛行以避開無人區(qū)。若無人機經過的限飛區(qū)數量為m，則無人機共有2m種可能繞行路徑。

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

3 算法設計

3.1 混合遺傳算法設計

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

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

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

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

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

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

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

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

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

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

3.2 混合遺傳算法步驟

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

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

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

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

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

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

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

Step 7 更新算子的分數及權重；

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

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

4 算例分析

本文對某生鮮產品公司進行了調研，并對需要用到的相關數據進行收集和整理。

4.1 數據準備

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

表1 相關參數設置

4.2 算例仿真結果

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

圖1 路徑示意圖

算法運行的結果對比如表2所示。

表2 算法結果對比

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

5 結 論

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