疫情封控下的卡車(chē)和無(wú)人車(chē)聯(lián)合配送問(wèn)題研究

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

（武漢科技大學(xué) 管理學(xué)院，武漢 430065）

0 引言

新冠疫情爆發(fā)以來(lái)，全球經(jīng)濟(jì)都受到了嚴(yán)重的影響，后疫情時(shí)代的到來(lái)使各地的防疫形勢(shì)依然嚴(yán)峻。作為中國(guó)經(jīng)濟(jì)體系的關(guān)鍵部分，物流業(yè)某些環(huán)節(jié)的薄弱點(diǎn)和不足也顯露出來(lái)。在疫情防控下道路封閉、配送鏈斷裂，導(dǎo)致居民生活和物資需求不能得到保障，傳統(tǒng)的配送方式已不能滿(mǎn)足物流需求。針對(duì)上述問(wèn)題，考慮到城市中部分地區(qū)封控的情況下，無(wú)接觸式配送能有效降低病毒傳播的風(fēng)險(xiǎn)，卡車(chē)和無(wú)人車(chē)聯(lián)合配送能為疫情封控背景下的配送活動(dòng)提供可行的方案。

無(wú)人配送近年來(lái)廣受學(xué)者關(guān)注，主要用到的工具是無(wú)人機(jī)和無(wú)人車(chē)。在無(wú)人機(jī)配送的研究中，Kuo 等［1］研究了考慮時(shí)間窗的無(wú)人機(jī)配送路徑問(wèn)題；張夢(mèng)［2］和王新等［3］研究了車(chē)輛和無(wú)人機(jī)聯(lián)合配送的優(yōu)化方法，并設(shè)計(jì)算法進(jìn)行求解驗(yàn)證。但基于無(wú)人機(jī)技術(shù)的發(fā)展受到各地政治、經(jīng)濟(jì)水平等因素的限制，在實(shí)際場(chǎng)所中無(wú)法得到廣泛的應(yīng)用。相較于無(wú)人機(jī)，無(wú)人車(chē)具有更大的優(yōu)勢(shì)，已經(jīng)開(kāi)始應(yīng)用到實(shí)踐中。

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

針對(duì)疫情封控下的物流配送現(xiàn)實(shí)困難，本文提出卡車(chē)和無(wú)人車(chē)聯(lián)合選址-配送問(wèn)題，在封控區(qū)設(shè)立無(wú)人車(chē)站點(diǎn)，由站點(diǎn)的無(wú)人車(chē)進(jìn)行配送，而未被封控的地區(qū)保持原有的配送方式不變，并以此為基礎(chǔ)建立最小化運(yùn)輸成本目標(biāo)模型，運(yùn)用最大最小距離算法（Maximum and Minimum Distance Algorithm，MMD），對(duì)需求點(diǎn)進(jìn)行聚類(lèi)操作并選出無(wú)人配送站點(diǎn)，使用粒子群算法（Particle Swarm Optimization，PSO）求解配送路徑優(yōu)化問(wèn)題。

1 卡車(chē)和無(wú)人車(chē)聯(lián)合配送優(yōu)化模型

1.1 問(wèn)題描述

假定封控區(qū)設(shè)立的無(wú)人車(chē)站點(diǎn)可以提供足夠數(shù)量的車(chē)輛，而無(wú)人車(chē)站點(diǎn)的位置需要依據(jù)封控區(qū)需求點(diǎn)的位置去建立，站點(diǎn)的位置一經(jīng)確定后不發(fā)生變化?？ㄜ?chē)從配送中心出發(fā)，如遇到封控區(qū)的貨物需求不能送達(dá)，需要將貨物交接到無(wú)人車(chē)站點(diǎn)，并由站點(diǎn)的無(wú)人車(chē)進(jìn)行無(wú)接觸配送，卡車(chē)?yán)^續(xù)執(zhí)行配送任務(wù)。卡車(chē)和無(wú)人車(chē)聯(lián)合配送路線如圖1 所示：

圖1 卡車(chē)和無(wú)人車(chē)聯(lián)合配送路線圖Fig.1 A schematic diagram of the joint distribution of trucks and driverless cars

1.2 條件假設(shè)

本問(wèn)題為不失一般性，基于以下假設(shè)：

（1）卡車(chē)從配送中心出發(fā)，執(zhí)行配送后必須返回配送中心；

（2）無(wú)人車(chē)只能從站點(diǎn)出發(fā)，執(zhí)行配送任務(wù)后須返回站點(diǎn)；

（3）需求點(diǎn)的需求量為qi，由于疫情防控貨物只能在固定的時(shí)間段［ei，li］內(nèi)到達(dá)，無(wú)人車(chē)站點(diǎn)的時(shí)間窗由需求點(diǎn)的最早和最晚時(shí)間點(diǎn)決定；

（4）卡車(chē)和無(wú)人車(chē)有容量和最大行駛里程的約束；

（5）配送任務(wù)中，每個(gè)需求點(diǎn)和站點(diǎn)只能被訪問(wèn)一次；

（6）封控區(qū)的需求點(diǎn)只能由無(wú)人車(chē)訪問(wèn)，而卡車(chē)只能訪問(wèn)無(wú)人車(chē)站點(diǎn)和未被封控的需求點(diǎn)；

（7）每個(gè)無(wú)人車(chē)站點(diǎn)只對(duì)其服務(wù)范圍內(nèi)的需求點(diǎn)展開(kāi)配送。

1.3 符號(hào)說(shuō)明

本文問(wèn)題涉及的所有節(jié)點(diǎn)（包括配送中心、無(wú)人車(chē)站點(diǎn)、客戶(hù)需求點(diǎn)等）都定義在一張無(wú)向圖G ＝（N，E，F(xiàn)）上。

（1）點(diǎn)集合N ＝｛Nk∪Nv｝；

其中，Nk是卡車(chē)可到達(dá)的點(diǎn)集合，包括配送中心N0、無(wú)人車(chē)站點(diǎn)集合Ns、未被封控的需求點(diǎn)集合是無(wú)人車(chē)可到達(dá)的點(diǎn)集合，包括無(wú)人車(chē)站點(diǎn)集合Ns、被封控的需求點(diǎn)集合

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

其中僅包含卡車(chē)可到達(dá)兩點(diǎn)之間的連線。

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

其中僅包含無(wú)人車(chē)可到達(dá)兩點(diǎn)之間的連線。

設(shè)卡車(chē)的集合為K，無(wú)人車(chē)的集合為V。其中卡車(chē)的最大行駛里程和載重量分別為L(zhǎng)k和Qk；無(wú)人車(chē)的最大行駛里程和最大載重量為L(zhǎng)v和Qv。a和b分別代表單輛卡車(chē)和無(wú)人車(chē)的使用成本分別表示單輛卡車(chē)和無(wú)人車(chē)從點(diǎn)i到點(diǎn)j的行駛成本。dij表示節(jié)點(diǎn)i到節(jié)點(diǎn)j之間的距離；Sv表示第v輛無(wú)人車(chē)的所屬站點(diǎn)；ti表示節(jié)點(diǎn)i所需的服務(wù)時(shí)間；qi表示第i個(gè)點(diǎn)的需求量。

根據(jù)所述問(wèn)題，定義xijk、yijv變量如下：

1.4 模型構(gòu)建

基于問(wèn)題描述、條件假設(shè)和符號(hào)說(shuō)明可構(gòu)建以下模型：

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

2 基于MMD 算法的無(wú)人車(chē)站點(diǎn)選址

2.1 MMD 算法的基本原理

最大最小距離（MMD 算法）是模式識(shí)別中一種基于試探的類(lèi)聚算法，以歐式距離為基礎(chǔ)，取盡可能遠(yuǎn)的對(duì)象作為聚類(lèi)中心。其基本思想是對(duì)待分類(lèi)模式樣本集采取以最大距離原則選取新的聚類(lèi)中心，以最小距離原則進(jìn)行模式歸類(lèi)。結(jié)合該算法的基本思想，將被封控的需求點(diǎn)進(jìn)行聚類(lèi)處理，確定聚類(lèi)中心，建立無(wú)人車(chē)站點(diǎn)。

2.2 算法基本步驟

步驟1在被封控的需求點(diǎn)集合中任選一個(gè)需求點(diǎn)，作為第一個(gè)聚類(lèi)中心z1；

步驟2選取距離z1最遠(yuǎn)的一個(gè)需求點(diǎn)為第二個(gè)聚類(lèi)中心z2；

步驟3計(jì)算其余需求點(diǎn)到z1與z2之間的距離，并得出最小值：

則選取新的需求點(diǎn)o1作為第三個(gè)聚類(lèi)中心z3，判斷是否存在新的聚類(lèi)中心，若不存在，則轉(zhuǎn)到步驟6。其中，θ為比例系數(shù)。

步驟5假設(shè)存在k個(gè)聚類(lèi)中心，計(jì)算各需求點(diǎn)到各個(gè)聚類(lèi)中心的距離xij，并計(jì)算：

若假設(shè)成立，則確定新的需求點(diǎn)o1為新的聚類(lèi)中心，繼續(xù)判斷有無(wú)新的聚類(lèi)中心存在，若沒(méi)有，轉(zhuǎn)到步驟6；

步驟6當(dāng)判斷沒(méi)有新的聚類(lèi)中心存在時(shí)，將封控區(qū)需求點(diǎn)集合按最小距離原則分配到各類(lèi)中，并計(jì)算：

步驟7確定各聚類(lèi)中心為無(wú)人車(chē)站點(diǎn)的位置。

3 基于粒子群優(yōu)化的卡車(chē)與無(wú)人機(jī)聯(lián)合配送路徑優(yōu)化

粒子群算法（PSO）是模仿鳥(niǎo)類(lèi)覓食時(shí)的飛行特征，通過(guò)模擬鳥(niǎo)類(lèi)群體在一片隨機(jī)的有邊界的區(qū)域內(nèi)尋找一塊食物并飛行到其所在位置，要制定較好的策略，通過(guò)尋找離食物最近的鳥(niǎo)，并對(duì)其附近進(jìn)行搜索。若將該算法應(yīng)用到優(yōu)化問(wèn)題中，則將每一個(gè)鳥(niǎo)當(dāng)作一個(gè)粒子，承載了一個(gè)目標(biāo)函數(shù)的適應(yīng)度值。通過(guò)制定其飛行速度和方向規(guī)則，追尋當(dāng)前最優(yōu)粒子，去尋找當(dāng)前解空間中最優(yōu)目標(biāo)的位置。

3.1 粒子編碼

假設(shè)顧客數(shù)目為L(zhǎng)，車(chē)輛最大使用數(shù)為M，構(gòu)造粒子位置為2 行L列的矩陣，矩陣由左至右依次為編號(hào)1-L對(duì)應(yīng)的列。第一行為顧客對(duì)應(yīng)的車(chē)輛編號(hào)Xv，第二行為車(chē)輛順序編號(hào)Xr。

現(xiàn)假設(shè)有6 位顧客，2 輛車(chē)輛，對(duì)應(yīng)以上定義，一個(gè)可能出現(xiàn)的粒子［Xv；Xr］如下：

車(chē)輛編號(hào)：2 2 1 1 1 2 順序編號(hào)：6 4 2 3 5 1

將第1 輛車(chē)服務(wù)的需求點(diǎn)3、4、5 放在一起，第2 輛車(chē)服務(wù)的顧客1、2、6 放在一起，然后按照各個(gè)需求點(diǎn)的順序編號(hào)，按從小到大的順序訪問(wèn)需求點(diǎn)。對(duì)上述粒子進(jìn)行調(diào)整，可得到以下配送方案：

車(chē)輛1 0→2→3→5→0 車(chē)輛2 0→6→4→1→0

3.2 粒子初始化

在粒子位置的初始化時(shí)，［Xv；Xr］中Xv和Xr每個(gè)位置的元素分別為區(qū)間1-M和1-L的隨機(jī)數(shù)。對(duì)于粒子編碼操作中不能判斷需求點(diǎn)被服務(wù)的次序時(shí)，按照Xr的大小，對(duì)次序進(jìn)行更新。

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

在粒子速度的初始化中，Xv對(duì)應(yīng)速度Vv，Xr對(duì)應(yīng)速度Vr。則Vv中每個(gè)位置上的元素都應(yīng)該為-（M -1）～（M -1）的隨機(jī)數(shù)，Vr中每個(gè)位置上的元素都應(yīng)該為-（L -1）～（L -1）的隨機(jī)數(shù)。

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

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

3.4 局部搜索

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

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

步驟2計(jì)算VC 每條線路上車(chē)輛開(kāi)始服務(wù)時(shí)間ti與需求點(diǎn)li的差值，即違反約束的值，挑出違反約束最大的需求點(diǎn)，記錄到一個(gè)n行2 列的矩陣R中，第一列為n個(gè)違反約束的需求點(diǎn)編號(hào)，第二列為違反約束值，如未違反約束，則矩陣中的各個(gè)值記為0；轉(zhuǎn)到步驟3；

步驟3若R中存在正值，找出對(duì)應(yīng)的需求點(diǎn)i并移除，得到RVC 轉(zhuǎn)到步驟4；若R中所有值都為0，則將違反約束的需求點(diǎn)插入到距離該顧客最近的兩個(gè)節(jié)點(diǎn)中，轉(zhuǎn)到步驟1；

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

步驟5計(jì)算目標(biāo)函數(shù)值。

4 算例分析

本文采用solomon 的測(cè)試算例c101，使用matlab 編寫(xiě)MMD 算法和粒子群算法進(jìn)行求解；運(yùn)行的計(jì)算機(jī)參數(shù)配置為11th Gen Intel（R）Core（TM）i5-11400 ＠ 2.60 GHz 2.59 GHz、RAM 16 GB、windowsl0 操作系統(tǒng)。

4.1 無(wú)人車(chē)站點(diǎn)的選址

為了簡(jiǎn)化問(wèn)題和滿(mǎn)足一般性，基于算例，本文假設(shè)疫情封控區(qū)為圖2 矩形框內(nèi)的區(qū)域（即橫坐標(biāo)20～60 和縱坐標(biāo)0～40 的區(qū)域）。

圖2 封控區(qū)表示圖Fig.2 The control area

將比例系數(shù)θ設(shè)置為0.5，運(yùn)行MMD 算法得出可將封控區(qū)需求點(diǎn)聚類(lèi)為3 個(gè)區(qū)域（如圖3）。其中3 個(gè)聚類(lèi)中心為無(wú)人車(chē)站點(diǎn)的位置，坐標(biāo)分別為（50，35）、（35，5）、（25，30）。

圖3 聚類(lèi)結(jié)果及選址點(diǎn)表示Fig.3 Cluster results and site selection points representation

4.2 參數(shù)設(shè)置

分別計(jì)算3 個(gè)區(qū)域需求點(diǎn)的總需求，以節(jié)點(diǎn)最早和最晚的時(shí)間點(diǎn)為無(wú)人車(chē)站的時(shí)間窗。其它參數(shù)設(shè)置如下：

卡車(chē)的最大裝載量為200、無(wú)人車(chē)的最大裝載量為50、卡車(chē)的車(chē)輛最大使用數(shù)為25、無(wú)人車(chē)的最大使用數(shù)為5、卡車(chē)的單位路徑成本為10、無(wú)人車(chē)的單位路徑成本為2、單輛卡車(chē)的使用成本為100、單輛無(wú)人車(chē)的使用成本為20。

4.3 計(jì)算結(jié)果分析

4.3.1 第一階段求解

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

表1 卡車(chē)配送路徑表Tab.1 Truck delivery path table

算法運(yùn)行時(shí)間為110.65 s，求得全局最優(yōu)總運(yùn)輸成本為8 753，卡車(chē)的使用數(shù)目為10，卡車(chē)的總行駛里程為775，其中卡車(chē)5、7、10 前往無(wú)人車(chē)站點(diǎn)執(zhí)行配送。

4.3.2 第二階段求解

求解第二階段無(wú)人車(chē)前往封控區(qū)需求點(diǎn)的配送方案參數(shù)設(shè)置：慣性因子初始值為1，衰減率為0.95，c1和c2分別為1.5 和2，迭代20 次得到配送路徑見(jiàn)表2。

算法運(yùn)行時(shí)間為37 s，求得全局最優(yōu)總運(yùn)輸成本為485，無(wú)人車(chē)的使用數(shù)目為10，無(wú)人車(chē)的行駛總里程為193。綜上，可得最終求得的全局最優(yōu)解的總成本為9 228。

4.4 結(jié)果對(duì)比

為更好的證明卡車(chē)和無(wú)人車(chē)聯(lián)合配送的優(yōu)勢(shì)，通過(guò)計(jì)算某一卡車(chē)司機(jī)和需求點(diǎn)顧客出現(xiàn)感染時(shí)造成的疫情傳播風(fēng)險(xiǎn)，對(duì)兩種情況進(jìn)行對(duì)比，表3 為傳統(tǒng)模式的配送方案。

表3 傳統(tǒng)模式配送路徑表Tab.3 Table of traditional mode distribution paths

假設(shè)卡車(chē)司機(jī)5、需求點(diǎn)57（封控）感染病毒，密接的感染率為4.41%［15］，計(jì)算一次配送任務(wù)中的總傳播風(fēng)險(xiǎn)值見(jiàn)表4。

表4 傳統(tǒng)和聯(lián)合配送模式對(duì)比表Tab.4 Comparison table of traditional and joint distribution modes

卡車(chē)和無(wú)人車(chē)的配送成本小于傳統(tǒng)的配送模式，節(jié)省了運(yùn)輸成本。而針對(duì)以上一輛卡車(chē)只服務(wù)無(wú)人車(chē)站點(diǎn)的情況，恰好符合疫情防控的需求，疫情傳播的風(fēng)險(xiǎn)遠(yuǎn)小于傳統(tǒng)模式，有利于疫情防控。

5 結(jié)束語(yǔ)

本文研究了在城市局部區(qū)域疫情封控的背景下卡車(chē)和無(wú)人車(chē)聯(lián)合配送模式，并考慮了部分需求點(diǎn)屬于封控區(qū)域情況，在保證完成正常配送任務(wù)的同時(shí)，設(shè)立無(wú)人車(chē)站，對(duì)封控區(qū)的需求點(diǎn)進(jìn)行配送；建立了最小化運(yùn)輸成本為目標(biāo)，并用兩階段算法對(duì)算例進(jìn)行求解，結(jié)果證明了模型和算法是可行的，為疫情防控背景下的物流配送提供了啟示。