求解應(yīng)急物資配送問題的層次樽海鞘群算法

段曉紅

（北方工業(yè)大學(xué)經(jīng)濟(jì)管理學(xué)院，北京 100144）

在應(yīng)急救援中，多車型應(yīng)急車輛的使用能夠有效地縮短物資配送時(shí)間，同時(shí)有助于控制救援成本，對(duì)多車型問題的討論是十分必要的。田曉光[1]將多車型因素引入應(yīng)急物資調(diào)度中，考慮運(yùn)力、裝載能力、限制期等約束，構(gòu)建以災(zāi)害損失最小為目標(biāo)的物資調(diào)度模型。但兵兵等人以總配送時(shí)間最短、安全性最高和成本最低為目標(biāo)，構(gòu)建應(yīng)急物資調(diào)度模型。

對(duì)于災(zāi)害事件下的多車型應(yīng)急物資調(diào)度，學(xué)者多假設(shè)需求點(diǎn)僅能被單車保障。然而，災(zāi)害事件后的應(yīng)急物資需求大，單車保障顯然不符合實(shí)際需求?；诖?，本文針對(duì)多車型的應(yīng)急物資配送問題構(gòu)建模型，并設(shè)計(jì)一種層次樽海鞘群算法實(shí)現(xiàn)模型的求解。

一、問題描述與建模

本文研究的應(yīng)急物資配送問題包括應(yīng)急車輛分配和車輛路徑規(guī)劃兩個(gè)方面。數(shù)學(xué)描述為：一種應(yīng)急物資的體積為s，供給點(diǎn)r的可用物資量為w。K種車型構(gòu)成集合G，第k種車型gk∈G的載重量為lk，容積為Vk。供給點(diǎn)可用的gk型車輛構(gòu)成集合Ck，其中ck,o,o=1,2,…,Ok表示第o輛gk型車輛，Ok為gk型車輛的總數(shù)。I個(gè)受災(zāi)點(diǎn)構(gòu)成集合A，第i個(gè)受災(zāi)點(diǎn)ai∈A的物資需求為qi，時(shí)間窗上限為Tiu。供給點(diǎn)到受災(zāi)點(diǎn)ai的行程時(shí)間為，受災(zāi)點(diǎn)aα∈A到aβ∈A，α≠β的行程時(shí)間為Tα,βa。單位應(yīng)急物資的裝載時(shí)間為tl，卸載時(shí)間為td。

（一）決策變量

模型存在兩種決策變量：一是由ck,o運(yùn)往ai的應(yīng)急物資重量，二是ck,o對(duì)于其所服務(wù)受災(zāi)點(diǎn)的運(yùn)送順序

（二）目標(biāo)函數(shù)

模型的救援滿意度目標(biāo)如式(1)，使不滿足時(shí)間窗約束的應(yīng)急物資總量最小。

其中，為模型的中間變量。當(dāng)ck,o向其服務(wù)的受災(zāi)點(diǎn)umk,o配送物資所需的時(shí)間超過時(shí)，=1，否則=0。

由應(yīng)急物資的裝載時(shí)間、運(yùn)輸時(shí)間和卸載時(shí)間三部分組成，如式(2)所示。

（三）約束條件

規(guī)定ck,o對(duì)同一個(gè)受災(zāi)點(diǎn)最多服務(wù)一次，如式(3)所示。

如式(4)所示，配送至受災(zāi)點(diǎn)ai的物資總量應(yīng)等于需求qi。

如式(5)所示，ck,o的載重量應(yīng)不超過lk。

如式(6)所示，由ck,o運(yùn)輸?shù)奈镔Y總體積應(yīng)不超過Vk。

如式(7)所示，供給點(diǎn)派出的gk型應(yīng)急車輛總數(shù)應(yīng)不超過Ok。

其中，χk,o為調(diào)度模型的中間變量。當(dāng)ck,o被派出時(shí)χk,o=1，否則χk,o=0。

二、基于層次樽海鞘群算法的模型求解

樽海鞘群算法由Mirjalili于2017年提出[3]，是一種模擬樽海鞘群體覓食行為的新型群體優(yōu)化技術(shù)，數(shù)學(xué)模型見文獻(xiàn)[4]。參數(shù)定義為：樽海鞘總數(shù)為N，搜索空間的上下界為ub和lb，最大迭代次數(shù)為Φ。

（一）求解應(yīng)急車輛分配方案的樽海鞘群算法

采用真值編碼，將決策變量編碼為向量

適應(yīng)度函數(shù)決定于約束條件(4)-(6)，適應(yīng)度函數(shù)為

（二）求解應(yīng)急車輛路徑規(guī)劃的樽海鞘群算法

ck,o的運(yùn)輸路徑為其所服務(wù)的M個(gè)受災(zāi)點(diǎn)組成的序列，采用整數(shù)編碼，將其編碼為：

適應(yīng)度函數(shù)決定于目標(biāo)函數(shù)(1)和約束條件(3)，適應(yīng)度函數(shù)為

（三）層次樽海鞘群算法基本流程

分別將2.1和2.2節(jié)所述算法定義為上、下層算法，則層次樽海鞘群算法求解步驟為：

步驟1.上層算法初始化應(yīng)急車輛分配種群。分別以u(píng)b和lb為搜索空間的上下界，隨機(jī)生成N個(gè)樽海鞘個(gè)體構(gòu)成種群P，每一個(gè)個(gè)體En,n=1,2,…,N代表一種應(yīng)急車輛分配方案。

步驟2.將En輸入下層算法，并計(jì)算最優(yōu)運(yùn)輸路徑。對(duì)于每一個(gè)En執(zhí)行以下步驟：

步驟2.1.分別以u(píng)b’和lb’為搜索空間的上下界，隨機(jī)生成N1個(gè)樽海鞘個(gè)體構(gòu)成種群P1，每一個(gè)個(gè)體Un,z,z=1,2,…,N1代表一種應(yīng)急物資運(yùn)輸路徑。

步驟2.2.根據(jù)式（10）和（11）所示的編碼方案和適應(yīng)度函數(shù)，采用樽海鞘群算法獲得最優(yōu)運(yùn)輸路徑Un。

步驟3.將Un及其適應(yīng)度值傳遞給上層算法，計(jì)算各方案{En,Un}的適應(yīng)度值B=B1+B2，根據(jù)適應(yīng)度B從優(yōu)到劣的順序?qū)ΨN群排序。

步驟4.上層算法種群位置更新。根據(jù)樽海鞘群算法步驟更新上層算法中個(gè)體位置En。

步驟5.重復(fù)步驟2-4直至完成最大迭代次數(shù)Φ，輸出最優(yōu)配送方案{Enb,Unb}。

三、算例分析

應(yīng)急物資的體積為6m3/T。應(yīng)急車輛車型參數(shù)如表1；供給點(diǎn)的g1、g2和g3型車輛數(shù)分別為3、4和2；受災(zāi)點(diǎn)a1、a2和a3的應(yīng)急物資需求分別為6T、3T和7T，救援時(shí)間窗分別為3600s、5400s和5400s。應(yīng)急物資的裝載和卸載時(shí)間均為300s/T。供給點(diǎn)到各受災(zāi)點(diǎn)的最短行程時(shí)間如表2。

表1 應(yīng)急車輛車型參數(shù)

表2 行程時(shí)間

運(yùn)行層次樽海鞘群算法獲得最優(yōu)配送方案如表3-4。

表3 應(yīng)急車輛最優(yōu)分配方案

表4 最優(yōu)運(yùn)輸路徑

分析表3和4可知，應(yīng)急車輛分配方案滿足受災(zāi)點(diǎn)需求和應(yīng)急車輛載重約束，最優(yōu)路徑符合同一受災(zāi)點(diǎn)最多服務(wù)一次的要求。

四、結(jié)束語

本文構(gòu)建了多車型多受災(zāi)點(diǎn)應(yīng)急物資配送模型，設(shè)計(jì)一種層次樽海鞘群算法，通過上下層變量傳遞實(shí)現(xiàn)模型求解。算例驗(yàn)證結(jié)果表明層次樽海鞘群算法能夠獲得滿足車輛載重、物資需求等約束且救援滿意度最大的物資配送方案。