疫情封控下的卡車和無人車聯合配送問題研究

姜博涵，劉 翱，鄧旭東，任 亮，彭琨琨，艾學軼

（武漢科技大學 管理學院，武漢 430065）

0 引言

新冠疫情爆發以來，全球經濟都受到了嚴重的影響，后疫情時代的到來使各地的防疫形勢依然嚴峻。作為中國經濟體系的關鍵部分，物流業某些環節的薄弱點和不足也顯露出來。在疫情防控下道路封閉、配送鏈斷裂，導致居民生活和物資需求不能得到保障，傳統的配送方式已不能滿足物流需求。針對上述問題，考慮到城市中部分地區封控的情況下，無接觸式配送能有效降低病毒傳播的風險，卡車和無人車聯合配送能為疫情封控背景下的配送活動提供可行的方案。

無人配送近年來廣受學者關注，主要用到的工具是無人機和無人車。在無人機配送的研究中，Kuo 等［1］研究了考慮時間窗的無人機配送路徑問題；張夢［2］和王新等［3］研究了車輛和無人機聯合配送的優化方法，并設計算法進行求解驗證。但基于無人機技術的發展受到各地政治、經濟水平等因素的限制，在實際場所中無法得到廣泛的應用。相較于無人機，無人車具有更大的優勢，已經開始應用到實踐中。

Taefi 等［4］認為，電動汽車在配送領域有很大的應用空間，可以很大程度減少運輸成本和緩解環境問題；Miguel［5］對比了傳統燃油車和無人車的碳排放和成本也驗證了這一觀點；趙國富［6］分析了無人車在普及過程中遇到的問題，并進行案例分析和規劃設計；王愚勤［7］和Liu 等［8］研究了智聯網下的無人車問題；Sonneberg［9］和趙思雨等［10］在研究無人車在“最后一公里”配送路徑問題中，考慮了無人車電池容量和時間窗等因素；陳志強等［11］提出了一種遺傳禁忌混合算法，求解基于無人車的帶有時間窗車輛路徑問題；施磊［12］研究了無人車和傳統車輛結合的混合車隊問題；鄭李萍等［13］設計了4 種不同規模的無人車輛服務網絡，并仿真分析了車輛配置對于配送網絡的影響；孫珊［14］針對“最后一公里”配送問題，設計了一種卡車攜帶無人車協同配送的模式。

針對疫情封控下的物流配送現實困難，本文提出卡車和無人車聯合選址-配送問題，在封控區設立無人車站點，由站點的無人車進行配送，而未被封控的地區保持原有的配送方式不變，并以此為基礎建立最小化運輸成本目標模型，運用最大最小距離算法（Maximum and Minimum Distance Algorithm，MMD），對需求點進行聚類操作并選出無人配送站點，使用粒子群算法（Particle Swarm Optimization，PSO）求解配送路徑優化問題。

1 卡車和無人車聯合配送優化模型

1.1 問題描述

假定封控區設立的無人車站點可以提供足夠數量的車輛，而無人車站點的位置需要依據封控區需求點的位置去建立，站點的位置一經確定后不發生變化。卡車從配送中心出發，如遇到封控區的貨物需求不能送達，需要將貨物交接到無人車站點，并由站點的無人車進行無接觸配送，卡車繼續執行配送任務。卡車和無人車聯合配送路線如圖1 所示：

圖1 卡車和無人車聯合配送路線圖Fig.1 A schematic diagram of the joint distribution of trucks and driverless cars

1.2 條件假設

本問題為不失一般性，基于以下假設：

（1）卡車從配送中心出發，執行配送后必須返回配送中心；

（2）無人車只能從站點出發，執行配送任務后須返回站點；

（3）需求點的需求量為qi，由于疫情防控貨物只能在固定的時間段［ei，li］內到達，無人車站點的時間窗由需求點的最早和最晚時間點決定；

（4）卡車和無人車有容量和最大行駛里程的約束；

（5）配送任務中，每個需求點和站點只能被訪問一次；

（6）封控區的需求點只能由無人車訪問，而卡車只能訪問無人車站點和未被封控的需求點；

（7）每個無人車站點只對其服務范圍內的需求點展開配送。

1.3 符號說明

本文問題涉及的所有節點（包括配送中心、無人車站點、客戶需求點等）都定義在一張無向圖G ＝（N，E，F）上。

（1）點集合N ＝｛Nk∪Nv｝；

其中，Nk是卡車可到達的點集合，包括配送中心N0、無人車站點集合Ns、未被封控的需求點集合是無人車可到達的點集合，包括無人車站點集合Ns、被封控的需求點集合

（2）卡車行駛的邊集合E ＝｛（i，j）｜i.j∈Nk，i≠j｝；

其中僅包含卡車可到達兩點之間的連線。

（3）無人車行駛的邊集合F ＝｛（i，j）｜i.j∈Nv，i≠j｝。

其中僅包含無人車可到達兩點之間的連線。

設卡車的集合為K，無人車的集合為V。其中卡車的最大行駛里程和載重量分別為Lk和Qk；無人車的最大行駛里程和最大載重量為Lv和Qv。a和b分別代表單輛卡車和無人車的使用成本分別表示單輛卡車和無人車從點i到點j的行駛成本。dij表示節點i到節點j之間的距離；Sv表示第v輛無人車的所屬站點；ti表示節點i所需的服務時間；qi表示第i個點的需求量。

根據所述問題，定義xijk、yijv變量如下：

1.4 模型構建

基于問題描述、條件假設和符號說明可構建以下模型：

其中，式（1）為總成本最低目標函數，包括卡車和無人車的使用成本和路徑成本；式（2）表示每個無人車站點和未封控需求點只被卡車訪問一次；式（3）表示每個封控的需求點只被無人車訪問一次；式（4）表示封控的需求點只能由無人車訪問，而未封控的需求點只能被卡車訪問；式（5）表示只有卡車對無人車站點進行訪問之后，該站點的無人車才能開始執行配送任務；式（6）和式（7）是卡車和無人車最大容量的約束；式（8）和式（9）表示卡車和無人車最大行駛里程約束；式（10）和式（11）表示卡車和無人車完成配送任務后，必須返回配送中心或站點；式（12）表示卡車滿足未封控需求點和無人車站點的時間窗約束；式（13）表示無人車滿足封控需求點的時間窗約束；式（14）表示配送時間滿足時間窗約束。

2 基于MMD 算法的無人車站點選址

2.1 MMD 算法的基本原理

最大最小距離（MMD 算法）是模式識別中一種基于試探的類聚算法，以歐式距離為基礎，取盡可能遠的對象作為聚類中心。其基本思想是對待分類模式樣本集采取以最大距離原則選取新的聚類中心，以最小距離原則進行模式歸類。結合該算法的基本思想，將被封控的需求點進行聚類處理，確定聚類中心，建立無人車站點。

2.2 算法基本步驟

步驟1在被封控的需求點集合中任選一個需求點，作為第一個聚類中心z1；

步驟2選取距離z1最遠的一個需求點為第二個聚類中心z2；

步驟3計算其余需求點到z1與z2之間的距離，并得出最小值：

則選取新的需求點o1作為第三個聚類中心z3，判斷是否存在新的聚類中心，若不存在，則轉到步驟6。其中，θ為比例系數。

步驟5假設存在k個聚類中心，計算各需求點到各個聚類中心的距離xij，并計算：

若假設成立，則確定新的需求點o1為新的聚類中心，繼續判斷有無新的聚類中心存在，若沒有，轉到步驟6；

步驟6當判斷沒有新的聚類中心存在時，將封控區需求點集合按最小距離原則分配到各類中，并計算：

步驟7確定各聚類中心為無人車站點的位置。

3 基于粒子群優化的卡車與無人機聯合配送路徑優化

粒子群算法（PSO）是模仿鳥類覓食時的飛行特征，通過模擬鳥類群體在一片隨機的有邊界的區域內尋找一塊食物并飛行到其所在位置，要制定較好的策略，通過尋找離食物最近的鳥，并對其附近進行搜索。若將該算法應用到優化問題中，則將每一個鳥當作一個粒子，承載了一個目標函數的適應度值。通過制定其飛行速度和方向規則，追尋當前最優粒子，去尋找當前解空間中最優目標的位置。

3.1 粒子編碼

假設顧客數目為L，車輛最大使用數為M，構造粒子位置為2 行L列的矩陣，矩陣由左至右依次為編號1-L對應的列。第一行為顧客對應的車輛編號Xv，第二行為車輛順序編號Xr。

現假設有6 位顧客，2 輛車輛，對應以上定義，一個可能出現的粒子［Xv；Xr］如下：

車輛編號：2 2 1 1 1 2 順序編號：6 4 2 3 5 1

將第1 輛車服務的需求點3、4、5 放在一起，第2 輛車服務的顧客1、2、6 放在一起，然后按照各個需求點的順序編號，按從小到大的順序訪問需求點。對上述粒子進行調整，可得到以下配送方案：

車輛1 0→2→3→5→0 車輛2 0→6→4→1→0

3.2 粒子初始化

在粒子位置的初始化時，［Xv；Xr］中Xv和Xr每個位置的元素分別為區間1-M和1-L的隨機數。對于粒子編碼操作中不能判斷需求點被服務的次序時，按照Xr的大小，對次序進行更新。

粒子的更新公式如式（20），為粒子速度的更新公式如式（21）：

在粒子速度的初始化中，Xv對應速度Vv，Xr對應速度Vr。則Vv中每個位置上的元素都應該為-（M -1）～（M -1）的隨機數，Vr中每個位置上的元素都應該為-（L -1）～（L -1）的隨機數。

3.3 粒子更新取整與越界處理

基于粒子更新后可能會出現向量中元素不為整數的情況（Xv不為整數），則需進行向上取整操作，Xr是順序向量，體現出大小就行，不需取整操作；而后對Xv和Xr中的越界元素進行處理，將越界元素賦值為邊界值。

3.4 局部搜索

為使配送方案滿足約束，增加局部搜索算子提高解的質量。具體操作步驟如下：

步驟1判斷得出配送方案VC 是否滿足終止條件，若滿足條件轉至步驟5，否則轉步驟2；

步驟2計算VC 每條線路上車輛開始服務時間ti與需求點li的差值，即違反約束的值，挑出違反約束最大的需求點，記錄到一個n行2 列的矩陣R中，第一列為n個違反約束的需求點編號，第二列為違反約束值，如未違反約束，則矩陣中的各個值記為0；轉到步驟3；

步驟3若R中存在正值，找出對應的需求點i并移除，得到RVC 轉到步驟4；若R中所有值都為0，則將違反約束的需求點插入到距離該顧客最近的兩個節點中，轉到步驟1；

步驟4將矩陣插回到配送方案RVC 中滿足約束且距離增量最小的位置，得到新的配送方案VC；

步驟5計算目標函數值。

4 算例分析

本文采用solomon 的測試算例c101，使用matlab 編寫MMD 算法和粒子群算法進行求解；運行的計算機參數配置為11th Gen Intel（R）Core（TM）i5-11400 ＠ 2.60 GHz 2.59 GHz、RAM 16 GB、windowsl0 操作系統。

4.1 無人車站點的選址

為了簡化問題和滿足一般性，基于算例，本文假設疫情封控區為圖2 矩形框內的區域（即橫坐標20～60 和縱坐標0～40 的區域）。

圖2 封控區表示圖Fig.2 The control area

將比例系數θ設置為0.5，運行MMD 算法得出可將封控區需求點聚類為3 個區域（如圖3）。其中3 個聚類中心為無人車站點的位置，坐標分別為（50，35）、（35，5）、（25，30）。

圖3 聚類結果及選址點表示Fig.3 Cluster results and site selection points representation

4.2 參數設置

分別計算3 個區域需求點的總需求，以節點最早和最晚的時間點為無人車站的時間窗。其它參數設置如下：

卡車的最大裝載量為200、無人車的最大裝載量為50、卡車的車輛最大使用數為25、無人車的最大使用數為5、卡車的單位路徑成本為10、無人車的單位路徑成本為2、單輛卡車的使用成本為100、單輛無人車的使用成本為20。

4.3 計算結果分析

4.3.1 第一階段求解

在求解第一階段配送時參數設置為：慣性因子ω初始值為1，衰減率為0.98，c1和c2分別為1.5 和2。迭代50 次得到的配送路徑見表1。

表1 卡車配送路徑表Tab.1 Truck delivery path table

算法運行時間為110.65 s，求得全局最優總運輸成本為8 753，卡車的使用數目為10，卡車的總行駛里程為775，其中卡車5、7、10 前往無人車站點執行配送。

4.3.2 第二階段求解

求解第二階段無人車前往封控區需求點的配送方案參數設置：慣性因子初始值為1，衰減率為0.95，c1和c2分別為1.5 和2，迭代20 次得到配送路徑見表2。

算法運行時間為37 s，求得全局最優總運輸成本為485，無人車的使用數目為10，無人車的行駛總里程為193。綜上，可得最終求得的全局最優解的總成本為9 228。

4.4 結果對比

為更好的證明卡車和無人車聯合配送的優勢，通過計算某一卡車司機和需求點顧客出現感染時造成的疫情傳播風險，對兩種情況進行對比，表3 為傳統模式的配送方案。

表3 傳統模式配送路徑表Tab.3 Table of traditional mode distribution paths

假設卡車司機5、需求點57（封控）感染病毒，密接的感染率為4.41%［15］，計算一次配送任務中的總傳播風險值見表4。

表4 傳統和聯合配送模式對比表Tab.4 Comparison table of traditional and joint distribution modes

卡車和無人車的配送成本小于傳統的配送模式，節省了運輸成本。而針對以上一輛卡車只服務無人車站點的情況，恰好符合疫情防控的需求，疫情傳播的風險遠小于傳統模式，有利于疫情防控。

5 結束語

本文研究了在城市局部區域疫情封控的背景下卡車和無人車聯合配送模式，并考慮了部分需求點屬于封控區域情況，在保證完成正常配送任務的同時，設立無人車站，對封控區的需求點進行配送；建立了最小化運輸成本為目標，并用兩階段算法對算例進行求解，結果證明了模型和算法是可行的，為疫情防控背景下的物流配送提供了啟示。