汪 勇，李文凱，艾學(xué)軼，蒲秋梅

（1.武漢科技大學(xué) 恒大管理學(xué)院，武漢 430065；2.中央民族大學(xué) 信息工程學(xué)院，北京 100081）

0 引言

應(yīng)急物資調(diào)度（Emergency Material Scheduling，EMS）的研究主要包括調(diào)度模型和求解方法兩個(gè)方面。Hu 等（2019）[1]指出EMS 調(diào)度模型主要以最短時(shí)間、最短距離、最小成本、最大滿意度、公平性等為目標(biāo)。Liu 等（2021）[2]考慮到受災(zāi)群眾滿意度，建立了具有滿意度約束的調(diào)度模型。L（i2021）[3]建立了考慮運(yùn)輸時(shí)間、成本、資源可用性等影響因素的資源調(diào)度模型。薛星群等（2020）[4]以受災(zāi)點(diǎn)等待救援的平均時(shí)間最短以及應(yīng)急網(wǎng)絡(luò)總費(fèi)用最低為目標(biāo)，構(gòu)建運(yùn)力受限條件下受通行約束的救援物資聯(lián)合運(yùn)輸多目標(biāo)優(yōu)化模型。苑津莎等（2020）[5]在考慮需求點(diǎn)滿意度的同時(shí)，引入需求迫切度概念，進(jìn)一步提高調(diào)度模型的科學(xué)性。Wan等（2021）[6]建立了基于有序到貨原則的多目標(biāo)多約束應(yīng)急物資調(diào)度模型。由于災(zāi)害發(fā)生后，很難估計(jì)應(yīng)急救援物資的需求，劉揚(yáng)等（2019）[7]以三角模糊數(shù)描述物資需求的不確定性，構(gòu)建了考慮需求點(diǎn)匹配度和響應(yīng)時(shí)間的多目標(biāo)調(diào)度模型。Liu 等（2020）[8]提出了一個(gè)具有連續(xù)時(shí)變供需約束的應(yīng)急物資分配多目標(biāo)優(yōu)化模型，使得應(yīng)急救援行動(dòng)的損失和經(jīng)濟(jì)成本最小化。

EMS 因其多目標(biāo)和多約束特性在大多數(shù)情況下為強(qiáng)NP-Hard問(wèn)題，啟發(fā)式算法成為解決這類優(yōu)化問(wèn)題的重要方法。但啟發(fā)式算法幾乎都存在早收斂和優(yōu)化精度不高的問(wèn)題，為此，一些改進(jìn)和融合算法有效地改善了算法的性能。Han等（2021）[9]通過(guò)引入狀態(tài)轉(zhuǎn)移算法的四種狀態(tài)變換算子，解決了模擬退火算法探索初期收斂進(jìn)度慢的問(wèn)題。Joshi 等（2021）[10]提出了一種嵌入鄰域檔案的改進(jìn)引力搜索算法，有助于以更少的時(shí)間復(fù)雜度增加多樣化的搜索。Mohammed 和Rashid（2020）[11]提出鯨魚灰狼優(yōu)化算法，解決了局部搜索能力不足的問(wèn)題。

目前，考慮目標(biāo)偏好的多目標(biāo)應(yīng)急物資調(diào)度研究尚不多見(jiàn)，算法的優(yōu)化精度和搜索性能仍值得進(jìn)一步改善，鑒于此，本文建立一個(gè)具有目標(biāo)偏好的雙目標(biāo)應(yīng)急物資調(diào)度模型，提出一種麥田競(jìng)賽算法（Tournament in Cornfield Algorithm，TCA），以解決EMS方案優(yōu)化問(wèn)題。

1 應(yīng)急物資調(diào)度模型

1.1 假設(shè)條件

受到物資儲(chǔ)備量、道路狀況、運(yùn)輸能力等因素的影響，使得應(yīng)急物資調(diào)度成為一項(xiàng)十分復(fù)雜的優(yōu)化問(wèn)題?？紤]到上述影響因素以及應(yīng)急物資調(diào)度的可行性，對(duì)調(diào)度模型作如下假設(shè)：（1）供應(yīng)點(diǎn)是指第三方商業(yè)性物資儲(chǔ)備庫(kù)。（2）各類物資總儲(chǔ)備量大于總需求量。（3）每個(gè)需求點(diǎn)應(yīng)急物資需求和每個(gè)供應(yīng)點(diǎn)應(yīng)急物資儲(chǔ)備的種類和數(shù)量不完全相同。（4）每個(gè)需求點(diǎn)可以從多個(gè)供應(yīng)點(diǎn)調(diào)度物資，每個(gè)供應(yīng)點(diǎn)可以向多個(gè)需求點(diǎn)供應(yīng)物資。（5）同一供應(yīng)點(diǎn)運(yùn)輸車輛性能相同且數(shù)量有限，每輛車只從一個(gè)供應(yīng)點(diǎn)裝載物資，只為一個(gè)需求點(diǎn)運(yùn)送物資。

1.2 調(diào)度模型構(gòu)建

1.2.1 問(wèn)題描述

設(shè)有n個(gè)需求點(diǎn)，m個(gè)供應(yīng)點(diǎn)，u種應(yīng)急物資，qik表示需求點(diǎn)i需求應(yīng)急物資k的數(shù)量，cjk表示供應(yīng)點(diǎn)j儲(chǔ)備應(yīng)急物資k的數(shù)量。一個(gè)調(diào)度方案x可表示為x={xijk|i=1，2，…，n，j=1，2，…，m，k=1，2，…，u}。為減少災(zāi)害帶來(lái)的損失，在最短時(shí)間內(nèi)將應(yīng)急物資配送到位是調(diào)度者首要考慮的目標(biāo)。此外，由于供應(yīng)點(diǎn)是商業(yè)性物資儲(chǔ)備庫(kù)，因此在保障應(yīng)急物資及時(shí)供給時(shí)，需考慮應(yīng)急物資的采購(gòu)成本。故以時(shí)間和成本為目標(biāo)構(gòu)建應(yīng)急物資調(diào)度模型。f1(x)、f2(x)分別表示調(diào)度時(shí)間和調(diào)度成本，調(diào)度目標(biāo)是使得f1(x)與f2(x)最小，即：

式（2）至式（7）為式（1）的約束條件。式（2）表示應(yīng)急物資調(diào)度數(shù)量整數(shù)約束，即決策變量xijk為正整數(shù)。式（3）表示決策變量xijk非負(fù)且不大于供應(yīng)點(diǎn)j物資k的儲(chǔ)備量。式（4）表示所有需求點(diǎn)從供應(yīng)點(diǎn)j調(diào)度物資k的總量不大于該供應(yīng)點(diǎn)物資k的儲(chǔ)備量。式（5）表示需求點(diǎn)i從所有供應(yīng)點(diǎn)調(diào)度物資k的總量等于該需求點(diǎn)對(duì)物資k的需求量。

式（4）、式（5）是決策變量定義域約束。所有決策變量定義域不相同且存在依賴關(guān)系。由式（4）知，當(dāng)供應(yīng)點(diǎn)j可供調(diào)度的物資k數(shù)量小于需求點(diǎn)i需求物資k的數(shù)量時(shí)，則需求點(diǎn)i從供應(yīng)點(diǎn)j調(diào)度物資k的數(shù)量不超過(guò)該供應(yīng)點(diǎn)剩余物資k的數(shù)量。即

由式（5）知，需求點(diǎn)i從供應(yīng)點(diǎn)j調(diào)度物資k的數(shù)量不超過(guò)該需求點(diǎn)所需剩余物資k的數(shù)量，即xijk≤qik-

式（6）表示供應(yīng)點(diǎn)物資儲(chǔ)備量和需求點(diǎn)物資需求量非負(fù)約束。式（7）表示所有需求點(diǎn)物資k的需求量不超過(guò)所有供應(yīng)點(diǎn)物資k的儲(chǔ)備量。

1.2.2 調(diào)度時(shí)間

在不考慮物資裝載時(shí)間的情形下，調(diào)度時(shí)間即應(yīng)急物資運(yùn)輸時(shí)間。每個(gè)供應(yīng)點(diǎn)按照需求點(diǎn)受災(zāi)程度運(yùn)送應(yīng)急物資，先向受災(zāi)程度最嚴(yán)重的需求點(diǎn)運(yùn)送物資，接著向受災(zāi)程度次嚴(yán)重的需求點(diǎn)運(yùn)送物資，依此類推，直到完成所有需求點(diǎn)的物資運(yùn)送任務(wù)。對(duì)于一個(gè)調(diào)度方案x，設(shè)需求點(diǎn)i從供應(yīng)點(diǎn)j調(diào)度物資總重量為Mij(x)，則：

其中，rjk是供應(yīng)點(diǎn)j物資k的儲(chǔ)備狀態(tài)，cjk=0 時(shí)，rjk=0；cjk＞0 時(shí)，rjk=1。wjk是供應(yīng)點(diǎn)j物資k的單位重量。設(shè)供應(yīng)點(diǎn)j向所有需求點(diǎn)運(yùn)送物資的車次為b(j)，則：

其中，gj是供應(yīng)點(diǎn)j車輛載重量。b(j)≠0 時(shí)，表示需要多臺(tái)車輛運(yùn)送應(yīng)急物資。設(shè)供應(yīng)點(diǎn)j總的運(yùn)輸任務(wù)為Sj(x)，根據(jù)式（8）、式（9），Sj(x)={s1，s2，…，sb(j)}，b(j)為運(yùn)輸任務(wù)數(shù)，即每車次為一個(gè)運(yùn)輸任務(wù)。一個(gè)需求點(diǎn)可能存在多個(gè)運(yùn)輸任務(wù)，供應(yīng)點(diǎn)j到需求點(diǎn)i的運(yùn)輸時(shí)間記為Tij(x)，則：

其中，dij是供應(yīng)點(diǎn)j到需求點(diǎn)i的距離，vj是供應(yīng)點(diǎn)j車輛平均時(shí)速。由式（10）可得各任務(wù)的運(yùn)輸時(shí)間Tj(x)={t1，t2，…，tb(j)}。設(shè)供應(yīng)點(diǎn)j的車輛數(shù)為h(j)。根據(jù)運(yùn)輸任務(wù)及其運(yùn)輸時(shí)間計(jì)算供應(yīng)點(diǎn)j的調(diào)度時(shí)間DTj(x)。0時(shí)刻開(kāi)始執(zhí)行前h(j)個(gè)運(yùn)輸任務(wù)，當(dāng)有運(yùn)輸任務(wù)完成時(shí)，釋放的車輛開(kāi)始執(zhí)行第h(j)+1個(gè)運(yùn)輸任務(wù)，依此類推，直到所有運(yùn)輸任務(wù)完成為止，設(shè)第a(a=1，2，…，b(j)-h(j)+1)批任務(wù)最短運(yùn)輸時(shí)間為STa，則第a+1批任務(wù)的剩余運(yùn)輸時(shí)間RTa+1見(jiàn)式（11）。

顯然，a=1 時(shí)，RT1∈{t1，t2，…，th(j)}。根據(jù)式（11）計(jì)算每一批未完成任務(wù)的剩余運(yùn)輸時(shí)間，從而得到該批任務(wù)的最短運(yùn)輸時(shí)間STa和最后一批任務(wù)的最長(zhǎng)運(yùn)輸時(shí)間LTb(j)-h(j)+1，則所有任務(wù)的調(diào)度時(shí)間見(jiàn)式（12）。

總的調(diào)度時(shí)間f1(x)取決于所有需求點(diǎn)調(diào)度時(shí)間的最大值，即：

其中，μ為懲罰因子。若調(diào)度方案滿足式（3）、式（4）約束，則μ=1，否則，μ=+∞。

1.2.3 調(diào)度成本

調(diào)度成本由采購(gòu)成本和物流成本構(gòu)成。由假設(shè)條件可知，供應(yīng)點(diǎn)為商業(yè)性物資儲(chǔ)備庫(kù)，調(diào)度物資必然產(chǎn)生成本，稱為采購(gòu)成本，記為pc(x)。采購(gòu)成本取決于供應(yīng)點(diǎn)應(yīng)急物資單位價(jià)格和調(diào)度數(shù)量。設(shè)pjk表示供應(yīng)點(diǎn)j應(yīng)急物資k的單位價(jià)格，則所有需求點(diǎn)調(diào)度的應(yīng)急物資采購(gòu)成本為：

其中，xijk=0 表示需求點(diǎn)i沒(méi)有應(yīng)急物資k的需求。

物流成本主要來(lái)自車輛使用費(fèi)，記為lc(x)。設(shè)ρj表示供應(yīng)點(diǎn)j的單位運(yùn)輸費(fèi)用。根據(jù)式（8）得到物流成本為：

由式（14）和式（15）得到調(diào)度方案x的調(diào)度成本為：

1.3 調(diào)度方案編碼

由于直接采用優(yōu)化變量實(shí)值編碼易產(chǎn)生大量無(wú)效解，故設(shè)置一個(gè)新的決策變量ωijk，ωijk∈[0，λ]，λ為所有新的決策變量上界。ωijk表示需求點(diǎn)i從供應(yīng)點(diǎn)j調(diào)度應(yīng)急物資k的份額，ωijk是一個(gè)三維變量，為便于計(jì)算，按照需求點(diǎn)排列為一維結(jié)構(gòu)編碼。新變量與原始變量的映射函數(shù)見(jiàn)式（17）。

2 麥田競(jìng)賽算法

2.1 相關(guān)定義

定義1：選手手中的麥穗稱為標(biāo)準(zhǔn)麥穗，標(biāo)準(zhǔn)麥穗的集合稱為標(biāo)準(zhǔn)群體，記為X，X={xi|i=1，2，…，N}，xi表示第i個(gè)標(biāo)準(zhǔn)麥穗。選手眼中搜尋到的麥穗稱為挑戰(zhàn)麥穗，挑戰(zhàn)麥穗的集合稱為挑戰(zhàn)群體，記為Y，Y={yi|i=1，2，…，N}，yi是xi的挑戰(zhàn)麥穗。N為群體規(guī)模。

定義2：決策變量是一組反映麥穗質(zhì)量的物理指標(biāo)。xij表示標(biāo)準(zhǔn)麥穗xi的第j項(xiàng)物理指標(biāo)，j=1，2，…，L。yij表示挑戰(zhàn)麥穗yi的第j項(xiàng)物理指標(biāo)。L為物理指標(biāo)數(shù)。

定義3：篩選目標(biāo)是判斷標(biāo)準(zhǔn)麥穗和挑戰(zhàn)麥穗質(zhì)量?jī)?yōu)劣的依據(jù)，如顆粒飽滿度、色澤等。篩選目標(biāo)與麥穗物理指標(biāo)間的關(guān)系稱為篩選目標(biāo)函數(shù)，記為fk(xi)，fk(xi)表示標(biāo)準(zhǔn)麥穗xi的第k個(gè)篩選目標(biāo)，k=1，2，…，m，m為目標(biāo)數(shù)。選手關(guān)注程度最高的目標(biāo)稱為偏好目標(biāo)。

定義4：設(shè)xi∈X，yi∈Y，xi與yi具有質(zhì)量?jī)?yōu)劣關(guān)系，若?k∈[1，m]，都有fk(yi)≥fk(xi)成立，則yi優(yōu)于xi，yi為優(yōu)等麥穗，記為yi?xi。反之，xi為優(yōu)等麥穗，記為xi?yi。顯然，麥穗質(zhì)量?jī)?yōu)劣關(guān)系具有傳遞性。若xi，xj，xh∈X，xi?xj，且xj?xh，則xi?xh。

定義5：對(duì)于xi∈X，yi∈Y，若?k，l∈[1，m]，k≠l，使得fk(xi)＞fk(yi)，且f1(xi)＜f1(yi)，則稱xi與yi質(zhì)量不具有優(yōu)劣關(guān)系，即不存在xi?yi，也不存在yi?xi，記作xi??yi。

定義6：反映麥穗xi成熟程度的函數(shù)稱為成熟度函數(shù)，記為F(xi)。設(shè)xi，xj∈X，i，j=1，2，…，N，若xi?xj，則F(xi)=1，F(xiàn)(xj)=-1。反之，F(xiàn)(xi)=-1，F(xiàn)(xj)=1。若xi??xj，則F(xi)=F(xj)=0。

定義7：設(shè)xi∈X，若對(duì)于?xj∈X，k∈[1，m]，都有F(xi)＞F(xj)成立，則稱xi為標(biāo)準(zhǔn)麥穗群體的最優(yōu)麥穗。若對(duì)于?xj∈X，都有Fk(xi)＞Fk(xj)成立(k=1，2，…，m)，則稱xi為偏好目標(biāo)k的最優(yōu)麥穗。

2.2 麥穗搜尋階段

TCA主要包括麥穗搜尋和麥穗篩選兩個(gè)階段，搜尋實(shí)際上是標(biāo)準(zhǔn)麥穗的啟發(fā)式計(jì)算過(guò)程，由此產(chǎn)生挑戰(zhàn)麥穗。搜尋階段從當(dāng)前標(biāo)準(zhǔn)群體出發(fā)，競(jìng)賽選手根據(jù)標(biāo)準(zhǔn)麥穗所在的區(qū)域范圍，搜尋標(biāo)準(zhǔn)麥穗附近的挑戰(zhàn)麥穗，所有選手搜尋到的挑戰(zhàn)麥穗構(gòu)成挑戰(zhàn)群體。

設(shè)xij(t)表示第t輪標(biāo)準(zhǔn)麥穗xi的第j個(gè)物理指標(biāo)，yij(t)表示其挑戰(zhàn)麥穗相應(yīng)的物理指標(biāo)，i=1，2，…，N，j=1，2，…，L。根據(jù)定義2，挑戰(zhàn)麥穗yi(t) 與標(biāo)準(zhǔn)麥穗xij(t)的啟發(fā)式計(jì)算見(jiàn)式（18）。

式（18）中，Dij(t)是t輪標(biāo)準(zhǔn)麥穗xi物理指標(biāo)j的搜尋方向。當(dāng)標(biāo)準(zhǔn)個(gè)體與挑戰(zhàn)個(gè)體的指標(biāo)值（決策變量）與成熟度值變化趨勢(shì)一致時(shí)，Dij(t)=1，相反時(shí)，Dij(t)=-1；當(dāng)指標(biāo)值無(wú)變化時(shí)，Dij(t)保持不變。搜尋方向引導(dǎo)算法朝著最優(yōu)解方向定向搜索，進(jìn)一步提升TCA 的搜索性能。Instij是物理指標(biāo)j的搜尋指令，Instij=0 表示停止搜尋，Instij=1表示開(kāi)始搜尋。vij是物理指標(biāo)j的搜尋速度，vij計(jì)算見(jiàn)式（19）。

式（19）中，r是均值為0、方差為1的正態(tài)分布的隨機(jī)數(shù)。Gj是截止到第t輪搜尋的最優(yōu)麥穗第j個(gè)物理指標(biāo)值。xij(t)越大，對(duì)該項(xiàng)指標(biāo)的搜尋速度越慢，反之越快。

2.3 篩選階段

2.3.1 淘汰賽階段

篩選階段模擬競(jìng)賽過(guò)程，在小規(guī)模范圍內(nèi)搜索可能的最優(yōu)解，包括淘汰賽和錦標(biāo)賽兩種篩選形式。淘汰賽是在挑戰(zhàn)麥穗和標(biāo)準(zhǔn)麥穗之間進(jìn)行，勝者作為下一輪的標(biāo)準(zhǔn)麥穗，所有獲勝者形成新一輪標(biāo)準(zhǔn)群體。根據(jù)定義3和定義4，第t+1輪標(biāo)準(zhǔn)群體X(t+1)按式（20）、式（21）計(jì)算。

式（20）中，σ(x)是選擇函數(shù)，x≥0 表示標(biāo)準(zhǔn)麥穗優(yōu)于挑戰(zhàn)麥穗或二者之間不具有優(yōu)劣關(guān)系，選擇標(biāo)準(zhǔn)麥穗xi作為優(yōu)等麥穗進(jìn)入第t+1輪標(biāo)準(zhǔn)群體。否則，選擇挑戰(zhàn)麥穗yi作為優(yōu)等麥穗進(jìn)入第t+1輪標(biāo)準(zhǔn)群體。

2.3.2 錦標(biāo)賽階段

錦標(biāo)賽是在標(biāo)準(zhǔn)群體中篩選出最優(yōu)麥穗。通過(guò)計(jì)算標(biāo)準(zhǔn)麥穗的成熟度值，選擇成熟度值最大的標(biāo)準(zhǔn)麥穗作為最優(yōu)麥穗，即問(wèn)題的最優(yōu)解。根據(jù)定義6和定義7，考慮標(biāo)準(zhǔn)麥穗的優(yōu)劣關(guān)系及目標(biāo)偏好，設(shè)計(jì)TCA 成熟度函數(shù)F(xi)，見(jiàn)式（22）。

其中，N為標(biāo)準(zhǔn)群體麥穗數(shù)，m為篩選目標(biāo)數(shù)，fk(xi)為第k 個(gè)篩選目標(biāo)函數(shù)，fk(xi)=1/zk(xi)。ψ(k)為偏好目標(biāo)函數(shù)，取值見(jiàn)式（23）。?(x)為篩選目標(biāo)統(tǒng)計(jì)函數(shù)，取值見(jiàn)式（24）。

pf是篩選目標(biāo)序號(hào)，由決策者根據(jù)偏好設(shè)定，pf∈[1，m]。

由式（24）知，任意兩個(gè)標(biāo)準(zhǔn)麥穗的篩選目標(biāo)統(tǒng)計(jì)函數(shù)值之和為0，即∑(φ(x)+φ(-x))=0。因此，∑F(xi)=0。

2.4 算法描述

步驟1：輸入。需求點(diǎn)應(yīng)急物資需求種類與數(shù)量q，供應(yīng)點(diǎn)應(yīng)急物資儲(chǔ)備種類、數(shù)量c、單位重量w和單價(jià)p，供應(yīng)點(diǎn)車輛數(shù)量h、載重量g、平均時(shí)速v 和單位運(yùn)輸費(fèi)用ρ，競(jìng)賽輪數(shù)T，偏好目標(biāo)pf，搜尋方向D（初始值為1），初始標(biāo)準(zhǔn)群體X。

步驟2：按式（8）至式（13）計(jì)算f1(x)，按式（14）至式（16）計(jì)算f2(x)。

步驟3：按式（22）至式（24）計(jì)算標(biāo)準(zhǔn)麥穗的成熟度F，保存最優(yōu)麥穗（最優(yōu)調(diào)度方案）x*及f(x*)。

步驟4：若達(dá)到最大競(jìng)賽輪數(shù)，則終止計(jì)算，轉(zhuǎn)步驟9，否則，轉(zhuǎn)下一步。

步驟5：按式（18）、式（19）搜尋挑戰(zhàn)麥穗，獲得挑戰(zhàn)群體Y。

步驟6：按式（8）至式（16）分別計(jì)算挑戰(zhàn)群體Y中挑戰(zhàn)麥穗的篩選目標(biāo)值f1(x)和f2(x)。

步驟7：按式（20）、式（21）逐一篩選標(biāo)準(zhǔn)麥穗和相應(yīng)的挑戰(zhàn)麥穗，勝者作為優(yōu)等麥穗加入標(biāo)準(zhǔn)群體，產(chǎn)生新一輪標(biāo)準(zhǔn)群體X。

步驟8：更新搜尋方向D，轉(zhuǎn)步驟3。

步驟9：輸出。全局最優(yōu)調(diào)度方案x*及調(diào)度時(shí)間f1(x*)和調(diào)度成本f2(x*)。

3 實(shí)證分析

3.1 數(shù)據(jù)與參數(shù)設(shè)置

2021 年河南特大洪澇災(zāi)害共造成17 個(gè)省轄市、1417.85萬(wàn)人受災(zāi)，直接經(jīng)濟(jì)損失達(dá)1767.03億元。以此為算例背景，選擇11 個(gè)受災(zāi)地區(qū)為應(yīng)急物資需求點(diǎn)，9 個(gè)倉(cāng)儲(chǔ)為應(yīng)急物資供應(yīng)點(diǎn)，以大米、面粉、飲用水等6種物資為主要的應(yīng)急救援物資。根據(jù)受災(zāi)情況設(shè)置各地區(qū)各類應(yīng)急物資需求量。參考河南省應(yīng)急管理廳、統(tǒng)計(jì)局、電商等官網(wǎng)數(shù)據(jù)，整理得到供應(yīng)點(diǎn)物資儲(chǔ)備、價(jià)格等數(shù)據(jù)，存儲(chǔ)于相關(guān)數(shù)據(jù)集。

為驗(yàn)證調(diào)度模型的有效性和提出算法的性能，同時(shí)采用TCA、DE、GWO、GSA、NSGA-II 和PSO 求解最優(yōu)調(diào)度方案。為便于對(duì)比，各算法初始群體相同，群體個(gè)體數(shù)N=20，誤差精度e=[5.0，0.5]，調(diào)度份額上界lambda=15，最大迭代次數(shù)T=5000。

3.2 應(yīng)急物資優(yōu)化調(diào)度算法比較

應(yīng)急救援工作要求在最短時(shí)間內(nèi)將應(yīng)急物資運(yùn)送到受災(zāi)點(diǎn)，采取最近供應(yīng)點(diǎn)調(diào)度的方案見(jiàn)表1。

表1 最近供應(yīng)點(diǎn)調(diào)度方案

由表1 可知，最近供應(yīng)點(diǎn)調(diào)度的總成本為2560.5 萬(wàn)元，調(diào)度時(shí)間是完成所有需求點(diǎn)應(yīng)急物資運(yùn)送任務(wù)的時(shí)間，故總調(diào)度時(shí)間為74.4小時(shí)。

為求解最優(yōu)調(diào)度方案，并檢驗(yàn)提出算法的優(yōu)化效果，分別采用無(wú)目標(biāo)偏好的TCA算法與其他五個(gè)算法進(jìn)行對(duì)比實(shí)驗(yàn)，為避免算法的隨機(jī)性，所有算法均計(jì)算30 次，取其平均值作為全局最優(yōu)目標(biāo)值。各算法求解結(jié)果見(jiàn)表2。

表2 最優(yōu)調(diào)度方案

由表2 可知，無(wú)論是調(diào)度成本還是調(diào)度時(shí)間，無(wú)目標(biāo)偏好的TCA 算法求解結(jié)果都明顯低于其他算法。TCA 的調(diào)度成本遠(yuǎn)低于最近供應(yīng)點(diǎn)調(diào)度方案，調(diào)度時(shí)間將近縮短一倍。各算法全局最優(yōu)調(diào)度曲線變化趨勢(shì)見(jiàn)圖1。

圖1 全局最優(yōu)調(diào)度目標(biāo)曲線

圖1（a）為算法最優(yōu)調(diào)度成本曲線。1000次迭代計(jì)算內(nèi)，DE 收斂速度最快，NSGA-II 收斂速度最慢。此后，除TCA外，其他算法基本趨于收斂，TCA卻繼續(xù)呈下降趨勢(shì)，且遠(yuǎn)離曲線相對(duì)集中的其他算法。圖1（b）為最優(yōu)調(diào)度時(shí)間曲線。TCA曲線持續(xù)保持下降趨勢(shì)，其他曲線均出現(xiàn)早熟收斂?？梢?jiàn)，TCA優(yōu)化能力明顯優(yōu)于相比較的算法。

3.3 考慮目標(biāo)偏好的TCA優(yōu)化調(diào)度

調(diào)度者根據(jù)目標(biāo)要求設(shè)定目標(biāo)偏好，為驗(yàn)證具有目標(biāo)偏好的調(diào)度模型有效性和TCA求解多目標(biāo)問(wèn)題的優(yōu)化能力，分別考慮調(diào)度成本偏好和調(diào)度時(shí)間偏好求解最優(yōu)調(diào)度目標(biāo)值，并與無(wú)偏好情形進(jìn)行對(duì)比。優(yōu)化結(jié)果見(jiàn)表3，算法均計(jì)算30次，取其平均值作為最優(yōu)調(diào)度目標(biāo)值。

表3 考慮目標(biāo)偏好的TCA最優(yōu)調(diào)度方案

由表1至表3知，考慮成本偏好的TCA求解的調(diào)度成本最低，與最近供應(yīng)點(diǎn)調(diào)度相比，節(jié)約調(diào)度成本26.2%，此時(shí)，調(diào)度時(shí)間約為最近供應(yīng)點(diǎn)調(diào)度的一半?？紤]時(shí)間偏好的TCA求解的調(diào)度時(shí)間最短，僅為36.4小時(shí)，與最近供應(yīng)點(diǎn)調(diào)度相比，節(jié)約調(diào)度時(shí)間51.1%，此時(shí)，調(diào)度成本也明顯低于最近供應(yīng)點(diǎn)調(diào)度以及其他算法求解結(jié)果。無(wú)偏好TCA兩個(gè)目標(biāo)值介于成本偏好和時(shí)間偏好之間，是一個(gè)折中方案。由此可見(jiàn)，TCA求解的應(yīng)急物資優(yōu)化調(diào)度方案均優(yōu)于其他算法求解的優(yōu)化調(diào)度方案?？紤]目標(biāo)偏好的TCA最優(yōu)目標(biāo)變化趨勢(shì)見(jiàn)圖2。

圖2 目標(biāo)偏好的TCA全局最優(yōu)調(diào)度目標(biāo)曲線

由圖2 可知，無(wú)論是考慮成本偏好還是考慮時(shí)間偏好，相應(yīng)的目標(biāo)曲線都呈下降趨勢(shì)，且三種情形下降趨勢(shì)基本一致。表明考慮目標(biāo)偏好的TCA 與無(wú)偏好TCA 一樣，其最優(yōu)目標(biāo)是收斂的。

3.4 算法搜索性能比較

盡管包括TCA 在內(nèi)的上述算法求解的最優(yōu)目標(biāo)均是收斂的，但算法的搜索性能不盡相同。每一代群體最優(yōu)目標(biāo)值變化趨勢(shì)反映算法的搜索性能，所有算法的每一代群體最優(yōu)調(diào)度時(shí)間和最優(yōu)調(diào)度成本曲線見(jiàn)圖3，其中TCA為考慮目標(biāo)偏好情形。

圖3 每一輪群體最優(yōu)調(diào)度目標(biāo)曲線

圖3（a）和圖3（b）分別是調(diào)度時(shí)間和調(diào)度成本優(yōu)化曲線，考慮目標(biāo)偏好的TCA兩個(gè)目標(biāo)曲線基本不存在振蕩，每一代群體兩個(gè)最優(yōu)目標(biāo)值持續(xù)降低，直至收斂。其他算法兩個(gè)目標(biāo)曲線存在較大幅度振蕩。由此可見(jiàn)，考慮目標(biāo)偏好的TCA優(yōu)化算法搜索性能明顯優(yōu)于相比較的算法。

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

實(shí)證表明，本文建立的應(yīng)急物資調(diào)度模型能有效地降低調(diào)度成本，大幅縮短調(diào)度時(shí)間，可為應(yīng)急物資優(yōu)化調(diào)度提供決策參考。所提出的TCA 優(yōu)化算法簡(jiǎn)潔高效，適合求解多目標(biāo)優(yōu)化問(wèn)題，其優(yōu)化精度和搜索性能均優(yōu)于相比較的算法，可滿足應(yīng)急物資管理者的多目標(biāo)調(diào)度決策需求。調(diào)度方案實(shí)值映射編碼能夠保持所有算法個(gè)體更新的有效性。當(dāng)需求點(diǎn)和供應(yīng)點(diǎn)數(shù)量較大、需求物資以及考慮目標(biāo)較多時(shí)，調(diào)度方案解空間將顯著增加，TCA 等優(yōu)化算法計(jì)算效率降低，因此，對(duì)于具有更多調(diào)度目標(biāo)和高維度決策變量的應(yīng)急物資調(diào)度模型，提高TCA 算法的計(jì)算效率值得進(jìn)一步研究。