前幾期的推送已經(jīng)講解了圖與網(wǎng)絡(luò)分析的基本知識、數(shù)學(xué)模型和相關(guān)算法，相信大家對圖與網(wǎng)絡(luò)分析已經(jīng)有了充分的了解，這期小編將帶大家一起來讀一篇關(guān)于雙目標(biāo)島嶼旅行商問題的文章。

1.文章信息

題目：The bi-objective insular traveling salesman problem with maritime and ground transportation costs

作者：Pablo A. Miranda，Carola A. Blazquez，Carlos Obreque，Javier Maturana-Ross，Gabriel Gutierrez-Jarpa

來源：European Journal of Operational Research

出版信息：Volume 271，Issue 3，27 June 2018，Pages 1014-1036

網(wǎng)址：https://doi.org/10.1016/j.ejor.2018.05.009

2.文章導(dǎo)讀

本研究的動機(jī)是為位于智利南部的一組農(nóng)村島嶼設(shè)計家庭垃圾收集系統(tǒng)。每個島嶼都有一些小港口或碼頭，應(yīng)選擇這些港口或碼頭來收集垃圾。同時為島嶼配備車輛或駁船，以收集家庭垃圾。自然，島嶼上到訪碼頭的數(shù)量和位置會對駁船訪問島嶼所產(chǎn)生的海上運(yùn)輸成本（Maritime Transportation Costs，MTC）產(chǎn)生相關(guān)影響。此外，還嚴(yán)重影響著將生活垃圾或貨物從島嶼內(nèi)運(yùn)至選定碼頭的運(yùn)輸成本，以下簡稱地面運(yùn)輸成本（Ground Transportation Costs,GTC）。因此，本文研究了一個雙目標(biāo)問題，即優(yōu)化一組島嶼的單一無容量限制的訪問序列，并為每個島嶼選擇碼頭，稱為雙目標(biāo)島嶼旅行推銷員問題（Bi-Objective Insular Traveling Salesman Problem，BO-InTSP）。所研究的問題需要在MTC和GTC之間進(jìn)行權(quán)衡。直覺上，如果MTC的重要性很高，那么解決方案傾向于訪問每個島嶼的單個碼頭；如果MTC的重要性較低，那么解決方案可能會訪問每個島嶼上的所有碼頭。

3.摘要

本文介紹并研究了雙目標(biāo)島嶼旅行商問題，用一艘駁船為一組島嶼確定單一選擇路線，每個島嶼都有一定數(shù)量的碼頭，必須至少從中選擇一個碼頭進(jìn)行訪問。本文研究了一種新的BO-InTSP模型，旨在最小化海上運(yùn)輸成本和地面運(yùn)輸成本，其中島嶼產(chǎn)生的地面運(yùn)輸成本與將貨物運(yùn)輸至島嶼內(nèi)選定碼頭的策略密切相關(guān)，這是所研究問題的一個顯著特征。此外，過去文獻(xiàn)研究孤島旅行商問題較少，且島嶼產(chǎn)生的需求一般直接位于碼頭，而不是陸地內(nèi)部，其未考慮到GTC問題。本項研究是首次在島嶼VRP或TSP內(nèi)建模和研究GTC，并將其作為所選碼頭的函數(shù)，以雙目標(biāo)的觀點(diǎn)納入問題中，這是該文章最為新穎之處。最后，本文針對智利的一組實(shí)際實(shí)例，使用加權(quán)和方法求解了所提出的混合整數(shù)規(guī)劃模型，表明了問題的雙目標(biāo)性質(zhì)，強(qiáng)調(diào)了所提方法在島嶼地區(qū)貨運(yùn)收集或配送決策中的適用性。

4.主要內(nèi)容

本文討論了雙目標(biāo)島嶼旅行商問題，即用一艘駁船為一組島嶼確定單一選擇路線，使訪問選定碼頭的駁船總MTC及島嶼居民將貨物運(yùn)送到選定碼頭所產(chǎn)生的總GTC降至最低。其中，島嶼內(nèi)的GTC由居民承擔(dān)，而MTC由公共當(dāng)局負(fù)責(zé)為島嶼服務(wù)，這些費(fèi)用由不同的代理人或利益相關(guān)者承擔(dān)。因此，必須采用雙目標(biāo)建模方法對BO-InTSP進(jìn)行優(yōu)化。如圖1所示，每個島嶼都有一個或多個碼頭可被用作收集地點(diǎn)，收集地點(diǎn)選擇和碼頭選擇也將影響到GTC和MTC。模型應(yīng)優(yōu)化收集地點(diǎn)選擇和所選碼頭的訪問順序，確保每個島嶼都至少有一個碼頭被訪問。

為確定每個島嶼的GTC，建立了如下假設(shè)。首先假設(shè)每個島嶼被分割成若干區(qū)域，每個區(qū)域都與最近的碼頭相關(guān)聯(lián)，并由該碼頭收集每個區(qū)域中產(chǎn)生的貨運(yùn)。此外，每個區(qū)域由一個虛擬質(zhì)心表示，該質(zhì)心集中了該區(qū)域內(nèi)產(chǎn)生的總運(yùn)費(fèi)。圖2顯示了具有三個和四個潛在收集點(diǎn)和貨運(yùn)中心的兩個島嶼示例。

另一個假設(shè)用于拆分質(zhì)心的貨運(yùn)：假設(shè)采用線性建模結(jié)構(gòu)，在這種結(jié)構(gòu)中，位于中心的貨物（未選擇碼頭）在所選碼頭之間均勻分配。僅當(dāng)未選擇與此質(zhì)心相關(guān)的碼頭，且其貨物應(yīng)通過其他選定的碼頭收取時，此假設(shè)才起作用。否則，如前所述，集中在這個質(zhì)心上的貨物將完全通過這個選定的碼頭收集。圖3顯示了一個四碼頭的示例：在圖3-ii中，選擇了三個碼頭，與未選擇碼頭相關(guān)的質(zhì)心的總運(yùn)費(fèi)Q/4分為三部分（Q/4×1/3）。

同時，由于本研究的雙目標(biāo)特性，如果僅將GTC最小化，問題的解決方案為S1（見圖4-i），即訪問所有碼頭，每個質(zhì)心的貨物由最近的碼頭提取。相反，如果僅將MTC最小化，則問題的解決方案為S2，即每個島嶼只訪問一個碼頭（見圖4-ii）。隨著MTC的相對重要性增加，解決方案將從S1轉(zhuǎn)變?yōu)?/span>S2，從而減少所選碼頭的數(shù)量，并相應(yīng)地修改訪問順序。

根據(jù)研究問題的復(fù)雜性和雙目標(biāo)性，本文構(gòu)建了BO-InTSP模型。首先根據(jù)前文所述的假設(shè)給出了近似GTC的線性公式。

每個島h包含一組碼頭，其總貨運(yùn)量均勻分布于若干質(zhì)心，每個質(zhì)心需收集/貨運(yùn)量。假設(shè)單位運(yùn)輸成本用于將貨物從質(zhì)心移動到其關(guān)聯(lián)節(jié)點(diǎn)i，表示從與節(jié)點(diǎn)i相關(guān)聯(lián)的質(zhì)心到另一節(jié)點(diǎn)j的單位運(yùn)輸成本，該成本僅在未選擇節(jié)點(diǎn)i且選擇節(jié)點(diǎn)j時發(fā)生。上述表達(dá)式右側(cè)第一項表示i相關(guān)聯(lián)質(zhì)心到節(jié)點(diǎn)i的GTC，當(dāng)且僅當(dāng)選擇節(jié)點(diǎn)i并且使用k個節(jié)點(diǎn)訪問其島h時（=1），此成本激活。第二項表示從所有質(zhì)心計算到節(jié)點(diǎn)i的GTC。

根據(jù)之前的問題描述和近似GTC的線性公式表達(dá)，本文將BO-InTSP公式化為雙目標(biāo)混合整數(shù)線性規(guī)劃模型。

在該模型中，表達(dá)式（2）是問題的雙目標(biāo)函數(shù)，其目標(biāo)旨在最小化海上運(yùn)輸成本（MTC）和地面運(yùn)輸成本（GTC）；約束條件（3）則確保在每個島h處至少選擇一個碼頭來收集貨運(yùn)；等式（4）用來確定每個島h上訪問的收集點(diǎn)k的數(shù)量；約束（5）將基于變量的每個島h所選采集點(diǎn)的數(shù)量與基于節(jié)點(diǎn)選擇變量選擇要服務(wù)的島上站數(shù)量相關(guān)聯(lián)；當(dāng)且僅當(dāng)選擇節(jié)點(diǎn)i并且使用k個節(jié)點(diǎn)訪問其島h時（=1），表達(dá)式（6）則表示，如果選擇節(jié)點(diǎn)i（=1），則必須為k值激活一個變量；限制（7）表示變量和之間的邏輯關(guān)系；限制（8）和（9）確保如果選擇了節(jié)點(diǎn)，則駁船必須分別到達(dá)和離開該節(jié)點(diǎn)；等式（10）則是上文所提近似GTC的線性公式表達(dá)式，也是本文的重要亮點(diǎn)，其允許計算每個節(jié)點(diǎn)i的每個k值的GTC；表達(dá)式（11）是標(biāo)準(zhǔn)且眾所周知的Miller–Tucker–Zemlin子巡視消除約束；表達(dá)式（12）和（13）是模型的決策變量的域約束。

本文擬議的BO-InTSP針對智利南部的一個真實(shí)案例進(jìn)行了求解，該案例由21個島嶼組成，其中有33個碼頭和一個名為Dalcahue的倉庫。在解決案例問題時采用了基于歸一化加權(quán)和的方法，設(shè)定特定的權(quán)重值α，將問題轉(zhuǎn)變?yōu)閱文繕?biāo)問題，其中α與MTC相關(guān)，（1-α）與GTC相關(guān)。正如預(yù)期那樣，訪問的碼頭數(shù)量隨著α的增加而減少，MTC隨著α的增大而減少，GTC隨著α增加而增加。例如，當(dāng)α值為0.0、0.1和0.2時，解決方案包括訪問33個碼頭和倉庫，而當(dāng)α值分別為0.8、0.9和1.0時，訪問22個碼頭和倉庫。

5.結(jié)論

本文研究了一種新的BO-InTSP模型，旨在最小化海上運(yùn)輸成本（MTC）和地面運(yùn)輸成本（GTC）。MTC由駁船訪問島嶼收取貨物時產(chǎn)生，GTC由島嶼居民運(yùn)輸貨物至到訪碼頭產(chǎn)生。在這個問題中，每個島嶼都是通過一組特定的碼頭來訪問，這些碼頭必須與優(yōu)化訪問順序同時選擇。為了解決BO-InTSP問題，提出了一種雙目標(biāo)混合整數(shù)規(guī)劃模型，并采用加權(quán)歸一化方法，對真實(shí)世界島嶼的一組中小型實(shí)例進(jìn)行了優(yōu)化求解，并分析了解決方案結(jié)構(gòu)以及權(quán)衡MTC和GTC后的結(jié)果。正如預(yù)期的那樣，結(jié)果表明，如果每個島嶼上訪問的碼頭數(shù)量增加，則GTC減少，MTC增加。因此，當(dāng)GTC在目標(biāo)功能中的相對重要性或權(quán)重增加時（與MTC相比），解決方案往往會訪問所有碼頭。然而，當(dāng)GTC的相對重要性降低時，獲得的路線往往會訪問每個島嶼的單個碼頭。

6.貢獻(xiàn)

1、本文研究成果除了可以應(yīng)用于農(nóng)村群島廢物收集，其提議的建模結(jié)構(gòu)可以進(jìn)行調(diào)整和實(shí)施應(yīng)用于其他問題，例如為隔離的農(nóng)村大陸地區(qū)或住宅公寓收集或分配貨物等。

2、本文中島嶼產(chǎn)生的需求并不位于待服務(wù)的網(wǎng)絡(luò)節(jié)點(diǎn)或碼頭，而是位于島內(nèi)，本文將對從島內(nèi)到到訪節(jié)點(diǎn)或碼頭的貨運(yùn)過程GTC建模，這是首次在島嶼VRP或TSP內(nèi)建模和研究GTC。

3、本文研究了一種新BO-InTSP模型，旨在最小化海上運(yùn)輸成本（MTC）和地面運(yùn)輸成本（GTC）。

7.展望

未來的研究可以考慮多階段情景，包括訪問時間和頻率選擇，以及整合收集地點(diǎn)或運(yùn)輸過程中廢物或危險品的環(huán)境影響。同時可以考慮VRP的典型特征，如多車輛、多倉庫、時間窗口問題以及同時提取和交付，對現(xiàn)有模型進(jìn)行擴(kuò)展。此外，解決這些類型的問題需要有效的啟發(fā)式方法，如拉格朗日松弛法、Benders分解法、列生成算法等，未來可專注于啟發(fā)式算法的研究以適應(yīng)計算工作較大的情況。