多隔間車輛路徑問題研究綜述

彭麗文 沈吟東

摘? 要：隨著不能混裝貨物需要同時進行配送要求的出現(xiàn)，以及現(xiàn)代物流中待運產(chǎn)品多樣性特征的產(chǎn)生，多隔間車輛路徑問題（MCVRP）于近年來逐漸受到關(guān)注。文章首先歸納了多隔間車輛路徑問題的應(yīng)用場景，并闡述了每種場景下使用多隔間車輛運輸不相容貨物的優(yōu)點。然后，根據(jù)問題特征，對多隔間車輛路徑問題研究進行歸納分類并就每類研究問題分別予以綜述。最后，針對多隔間車輛路徑問題在當前形勢下面臨的新挑戰(zhàn)進行展望，并提出五個新的研究方向。

關(guān)鍵詞：多隔間車輛路徑問題;問題特征;應(yīng)用場景;文獻綜述

中圖分類號：U116.2? ? ? 文獻標識碼：A

Abstract： With the emergence of requirements for simultaneous delivery of products that cannot be mixed and the diversity of products to be shipped in modern logistics， the multi-compartment vehicle routing problem（MCVRP）has attracted more and more attention in recent years. This paper first summarizes the application scenarios of the MCVRP， and then expounds the advantages of using multi-compartment vehicles to distribute incompatible products in each scenario. Furthermore， according to the characteristics of the problem， the research on the MCVRP is grouped into seven types， for each of which an overview is provided respectively. Finally， the new challenges to the MCVRP are prospected， whilst five new research directions are suggested.

Key words： multi-compartment vehicle routing problem; problem characteristics; application scenarios; research overviews

0? 引? 言

隨著科技的進步和電子商務(wù)的飛速發(fā)展，物流業(yè)作為連接生產(chǎn)者與消費者的橋梁，發(fā)揮著越來越重要的作用。特別是疫情當下，在減少出行以及區(qū)域封鎖的情況下，物流配送則變得尤為重要，而如何在防護狀態(tài)下進行及時且合理的配送以滿足各戶生活所需，這對于物流業(yè)來說不僅是一份責任和發(fā)展契機，同樣也是一個新的挑戰(zhàn)。

與此同時，物流配送需求的普遍存在也使得作為運輸組織優(yōu)化中的核心問題即車輛路徑問題[1]（Vehicle Routing Problem，VRP）受到廣泛關(guān)注，已有很多學者對其進行研究并取得了豐碩的成果[2]。其中，大部分研究假設(shè)所有貨物都相容且混裝在單車廂中進行同時運輸。而隨著多樣性、個性化消費經(jīng)濟的迅猛發(fā)展，現(xiàn)代物流配送系統(tǒng)出現(xiàn)了待運產(chǎn)品種類紛繁多樣和配送網(wǎng)絡(luò)日趨復(fù)雜這兩個新的特征，配送的部分甚至所有產(chǎn)品之間很可能存在著不相容關(guān)系。此時，若仍然混裝在同一車廂中則將導(dǎo)致產(chǎn)品變質(zhì)甚至直接報廢。例如，冷鏈物流[3]中常溫和冷凍食品混裝會導(dǎo)致食品發(fā)生變質(zhì)，成品油配送[4]中不同類型石油混裝會影響油品的使用性能且易發(fā)生安全事故，垃圾回收[5]中將多個分類盒倒出后混裝會增加工作負擔甚至導(dǎo)致此次回收任務(wù)失敗。另外，將所有不相容產(chǎn)品都分別采用單隔間車輛單獨配送則會大幅度增加成本[6]，繼續(xù)使用傳統(tǒng)的單隔間車輛運輸已經(jīng)不能更好地滿足現(xiàn)代物流的運輸需求了。因此，在面臨不同類型產(chǎn)品不相容的這種特殊物流運輸問題時，為了提高運輸效率和節(jié)約成本，需要將單隔間分割成多隔間以使得車輛能同時運輸多種不相容產(chǎn)品，由此衍生出了一類新的VRP問題：多隔間車輛路徑問題（Multi-Compartment VRP，MCVRP）。

本文將首先給出MCVRP與傳統(tǒng)VRP的不同之處，并歸納出多隔間車輛路徑問題的應(yīng)用場景;然后根據(jù)問題特征，對多隔間車輛路徑問題研究進行歸納分類并就每類研究分別予以綜述;最后，針對多隔間車輛路徑問題在當前形勢下面臨的新挑戰(zhàn)進行展望并提出五個新的研究方向。

1? MCVRP的特征及應(yīng)用場景

MCVRP最早由Brown和Graves[7]提出，經(jīng)典的MCVRP可描述為：有一個起點和若干個有多種產(chǎn)品需求的客戶點，以及若干帶有多個隔間的車輛且不同種類的產(chǎn)品需放在不同隔間進行配送，已知各點的地理位置和各客戶對各種產(chǎn)品的需求，在滿足各隔間容量約束以及其他約束條件下，如何規(guī)劃一條最優(yōu)的路徑，使其能服務(wù)到每個客戶點并最終返回起點?？梢园l(fā)現(xiàn)，與傳統(tǒng)VRP在問題上的區(qū)別在于，除了使用能實現(xiàn)同時運輸多種不相容產(chǎn)品的多隔間車輛外，還將傳統(tǒng)VRP中的單隔間容量限制替換成了每種產(chǎn)品所對應(yīng)的隔間容量限制。另外，與傳統(tǒng)VRP的發(fā)展歷程也不同，MCVRP早期時并沒有引起廣泛關(guān)注，而是隨著其在某些特殊領(lǐng)域應(yīng)用的必要性以及現(xiàn)代物流中待運產(chǎn)品多樣性特征的出現(xiàn)，直到近年才逐漸成為學者們研究的一個熱點課題。

目前，隨著研究的深入，MCVRP的應(yīng)用場景也在逐步增多，其中關(guān)于冷鏈物流、成品油配送以及生活垃圾回收的MCVRP研究則相對較多。例如，陶榮[8]（2014）構(gòu)建了冷鏈產(chǎn)品多溫共配的數(shù)學模型并利用蟻群算法對其求解;Chen等[9]（2019）在研究冷鏈配送時考慮時間窗和燃油消耗等因素，提出了一種比基于經(jīng)驗的人工方法更加有效的自適應(yīng)大鄰域搜索算法對該MCVRP進行求解;Coelho等[10]（2015）針對石油運輸中的MCVRP，采用分支定界法進行求解;張源凱等[11]（2017）針對成品油配送中多車型、多車艙的車輛優(yōu)化調(diào)度問題，以派車成本與油耗成本之和的總成本最小為目標，構(gòu)建了綜合考慮多車型車輛指派、多隔間車輛裝載及路徑規(guī)劃等決策的MCVRP模型;Reed等[12]（2014）針對來自家庭垃圾廢舊品回收中的MCVRP，提出了一種改進的蟻群算法對其進行求解，針對顧客點分散在不同集群的回收網(wǎng)絡(luò)，使用K-means聚類算法來提高蟻群算法的求解效率;Henke等[13]（2015）討論了不同顏色玻璃回收的MCVRP，并提出了一種分支—切割算法（Branch-and-Cut Algorithm）有效地進行了求解。表1歸納了目前文獻中關(guān)于MCVRP的大部分應(yīng)用場景，并且除了“使用多隔間運輸相較于單隔間效率更高成本更低”的優(yōu)點外，MCVRP應(yīng)用在每種場景的其他優(yōu)點以及其對應(yīng)運載的不相容產(chǎn)品也在表中列出。

由于要滿足實際生活需求，應(yīng)用到現(xiàn)實場景中，MCVRP問題也變得復(fù)雜了，一些MCVRP的擴展問題也逐漸被學者們研究，如多車型MCVRP，帶有時間窗的MCVRP以及需求可拆分的MCVRP等。本文旨在對近年來國內(nèi)外文獻關(guān)于MCVRP所研究的具體問題進行較為全面的綜述，并在最后指出研究的發(fā)展趨勢，希望能給予讀者啟示。

2? MCVRP問題分類及研究現(xiàn)狀

隨著MCVRP其應(yīng)用場景的逐漸增加，關(guān)于它的研究成果也日益豐富。根據(jù)MCVRP問題的不同特征，MCVRP問題研究可以大致歸納為如下7類：（1）多車場MCVRP;（2）多車型MCVRP;（3）帶時間窗的MCVRP;（4）需求可拆分的MCVRP;（5）動態(tài)MCVRP;（6）取送貨MCVRP;（7）多目標MCVRP。本節(jié)將對每類的研究現(xiàn)狀分別予以綜述。

2.1? 多車場MCVRP

多車場MCVRP是基本MCVRP問題的一種擴展，指的是有數(shù)個車場同時對多個帶有多種產(chǎn)品需求的客戶進行服務(wù)，要求對各車場的多隔間車輛和行駛路線進行適當?shù)陌才牛诒ＷC滿足各客戶需求的前提下，使總運輸成本最小。相比較于單車場MCVRP，除了需要安排每輛車的路徑外，它還涉及到場站的選擇，所以其求解相對較難。

目前，大部分MCVRP研究都是考慮單車場，而少數(shù)涉及多車場[30-32]。如戴錫等[31]（2009）在油品配送車輛路徑問題中考慮多油庫和多成品油，以兩階段啟發(fā)式算法為基礎(chǔ)，給出了求解該問題的人機交互求解方法。Alinaghian和Shokouhi[32]（2018）提出了一種以車輛數(shù)和運輸成本最小化為目標的多車場多隔間車輛路徑問題數(shù)學模型并采用混合自適應(yīng)大鄰域搜索算法對其進行求解。

2.2? 多車型MCVRP

根據(jù)車輛的型號是否相同，MCVRP又可分為單車型和多車型MCVRP。需要注意的是，與傳統(tǒng)VRP相比，MCVRP采用的是多隔間車輛，所以其車輛類型劃分除了需要考慮車輛容量外，還需要進一步考慮隔間比例。以往研究大多數(shù)假設(shè)配送過程中所使用的都是具有相同容量和相同隔間比例的單車型車輛，而隨著物流業(yè)的發(fā)展，為了更好地滿足實際運輸需要，已有一些學者在MCVRP研究中考慮使用多車型多間隔車輛對多種不相容產(chǎn)品進行運輸，其中主要出現(xiàn)的若干種多車型情形歸納于圖1。

可以發(fā)現(xiàn)，根據(jù)在選擇多隔間車輛前每輛車的隔間尺寸/隔板位置是否固定，多車型MCVRP又可繼續(xù)分為帶固定隔間多車型MCVRP和柔性隔間多車型MCVRP。而對于帶固定隔間多車型MCVRP，根據(jù)車容量和隔間比例的不同，其又對應(yīng)三種多車型情況，即：（1）同車容量但不同隔間比例;（2）不同車容量但同隔間比例;（3）不同車容量且不同隔間比例。例如張源凱等[11]（2017）針對多隔間成品油MCVRP，使用具有不同車容量且不同隔間比例的多輛多隔間車進行運輸，并提出了一種利用Relocate和Exchange算子進行并行鄰域搜索改進的算法用于求解，結(jié)果顯示與單車型車輛獨立運營相比，多車型車輛混合運營能夠綜合運用大車型遠距離配送油耗成本小，小車型近距離配送派車成本小的優(yōu)點，使得總運營成本更小。另外，需要注意的是，在帶固定隔間多車型MCVRP中，即使每輛車的隔間尺寸固定，但是這并不意味著將產(chǎn)品分配到某隔間也是固定的，此處分為產(chǎn)品固定到隔間和產(chǎn)品再分配到隔間。前者研究起來簡單方便且每次使用完多隔間車輛后不用立刻清洗，而后者則增加了產(chǎn)品如何分配到隔間該決策變量，其應(yīng)用靈活但每次使用完后多隔間車輛后往往需要立刻清洗，比如在多種類型的成品油運輸中以及裝備了可自由切換的車載溫控系統(tǒng)的冷鏈物流中等。例如陳久梅等[29]（2018）在研究生鮮農(nóng)產(chǎn)品多隔間冷鏈配送問題時，假定車輛隔室與產(chǎn)品一一對應(yīng)并建立了該問題的數(shù)學模型。而王旭坪等[14]（2019）則在考慮碳排放和時空距離的冷鏈配送路徑優(yōu)化研究中，使用帶有可自由切換溫度的冷凍艙和冷藏艙的車輛進行運輸，在建立優(yōu)化模型后設(shè)計了K-means算法與改進模擬退火算法相結(jié)合的兩階段啟發(fā)式算法用于求解。

而對于柔性隔間多車型MCVRP，該問題中每輛多隔間車的總?cè)萘侩m然相同，但是其隔間尺寸并不是提前固定的，而是可根據(jù)運輸需要進行變化即可變隔間尺寸，這種機制使得每輛多隔間車都可能是一種新車型。進一步地，根據(jù)隔間尺寸的變化形式，柔性隔間MCVRP又可分為具有離散可變隔間尺寸的MCVRP和具有連續(xù)可變隔間尺寸的MCVRP，前者其隔間尺寸只能從一組潛在尺寸選項中選擇得到，而后者其隔間尺寸則可以從一個連續(xù)區(qū)間中任意取值。在求解柔性隔間MCVRP時，相較于固定隔間多車型MCVRP，其求解任務(wù)除了需要（1）確定車輛行程外，還需要同時確認（2）每輛車的車容量應(yīng)劃分為多少個車廂、（3）每個車廂的尺寸應(yīng)該為多少以及（4）應(yīng)為每個車廂分配哪種產(chǎn)品類型，所以該類多車型MCVRP求解難度較大，其相關(guān)文獻也較少。目前，Derigs等[33]（2011）構(gòu)建了一種使用離散可變尺寸隔間來分配食物和燃料的MCVRP模型，其隔間尺寸是在滿足車容量限制條件下從一組隔間集合中選擇得到的。而Henke等[13]（2015）針對玻璃廢料搜索難題也提出了一種考慮離散可變隔間尺寸的MCVRP，但其隔間尺寸是在給定的區(qū)間內(nèi)可按等步長離散變化，即設(shè)置每個車廂是基本車廂單元的整數(shù)倍，之后構(gòu)建了數(shù)學模型并使用可變鄰域搜索算法對其進行了求解。緊接著，Henke等[34]（2016）又考慮到一輛車中可使用的最大隔間數(shù)可能小于或等于產(chǎn)品類型的數(shù)量，在此基礎(chǔ)上構(gòu)建了具有連續(xù)可變隔間尺寸的MCVRP模型并使用遺傳算法求解。

除了以上多車型MCVRP外，一些特殊的車型組合也在或?qū)⒈恢饾u考慮使用。比如Ostermeier和Huebner[19]（2018）在研究雜貨配送車輛路徑問題時，考慮傳統(tǒng)單隔間車輛和多隔間車輛的混合車隊，并且通過實驗發(fā)現(xiàn)使用混合車隊運輸與使用單一的單車型或者多車型車隊相比能減少30%的成本。另外，隨著國家節(jié)能減排要求的提出，一些如電動汽車、既能燃油也能用電的動力混合型汽車等新能源汽車的使用將會逐漸興起和流行，這使得在運輸任務(wù)中使用的車輛類型將更加多樣化，混合配送車隊的情形將會更加普遍。所以，將新能源車引入到MCVRP中甚至與傳統(tǒng)燃油車組成混合配送車隊，將會是未來的一種發(fā)展趨勢。

2.3? 帶時間窗的MCVRP

在實際物流配送過程中，當每個顧客要求配送車輛在特定時間段內(nèi)交付多種產(chǎn)品時，若由于產(chǎn)品特性這些產(chǎn)品不能同時存放在車廂中進行運輸而使用傳統(tǒng)的單車廂運輸，這不僅會造成配送車輛的增加，也存在著顧客在短時間段內(nèi)頻繁取貨的缺點，所以采用多隔間車輛來滿足客戶對多種產(chǎn)品的需求以及滿足客戶的時間窗要求是很有必要的，對應(yīng)的帶有時間窗的多隔間車輛路徑問題（MCVRP with Time Windows，MCVRPTW）也被逐漸研究。

根據(jù)顧客點是否嚴格按照時間窗接受服務(wù)，MCVRPTW可進一步分為帶有硬時間窗的MCVRP[35-37]（MCVRP with Hard Time Windows，MCVRPHTW）和帶有軟時間窗的MCVRP[4，15，20]（MCVRP with Soft Time Windows，MCVRPSTW）。其中，在MCVRPHTW中，車輛必須在規(guī)定的時間段內(nèi)到達顧客點并服務(wù)，如果早到則需要等待至最早服務(wù)時刻才能開始服務(wù);而如果車輛晚于顧客規(guī)定的最晚服務(wù)時刻到達，則其無法對該顧客點提供服務(wù)。在MCVRPSTW中，允許車輛在規(guī)定的時間段外對顧客進行服務(wù)，但是需要承擔一定的時間窗懲罰成本。例如Chen等[37]（2019）研究了城市范圍內(nèi)的MCVRPHTW問題，在建立該優(yōu)化問題的數(shù)學模型的基礎(chǔ)上，提出了一種結(jié)合模擬退火的混合粒子群優(yōu)化算法進行了有效的求解;詹紅鑫等[15]（2019）針對成品油配送中多車型、多隔間的優(yōu)化調(diào)度難題，以配送成本最小、配送風險最小和軟時間窗懲罰成本最小這三個目標建立了成品油配送多目標路徑優(yōu)化模型，并基于鄰域搜索的思想提出了求解該多目標問題的多目標變鄰域搜索框架。

2.4? 需求可拆分的MCVRP

目前，大多數(shù)關(guān)于MCVRP的研究都是假設(shè)每個客戶的需求只由一輛車來完成，即考慮需求不可拆分，該類問題求解簡單并且對于客戶來說不用一次需求多次取貨。然而，在實際應(yīng)用中，相當一部分客戶點的需求量可能較大，此時若仍要求每個客戶點只由一輛車來提供服務(wù)，則勢必造成車輛空載率上升，浪費運輸資源。此外，還可能出現(xiàn)某客戶總需求直接超過了車輛總?cè)萘炕蚰晨蛻裟钞a(chǎn)品需求直接超過了對應(yīng)隔間容量的情況，此時則必須對需求進行拆分才能完成對該客戶點的運輸任務(wù)。因此，在客戶接受多次取貨時或者使用“客戶點的所有需求都已由多輛車運輸至臨時發(fā)放點后再通知顧客取貨”的方法，采用需求拆分的運輸方式能充分利用車輛裝載能力和降低車輛行駛成本?；谝陨蟽?yōu)點，需求可拆分的MCVRP（Split Delivery MCVRP，SDMCVRP）近年來也逐漸被學者們研究?？梢园l(fā)現(xiàn)，根據(jù)客戶是否要求每種產(chǎn)品需一次送達，SDMCVRP又細分為“客戶總需求可拆分但每種產(chǎn)品只能由一輛車配送[32，36，38-39]”和“客戶總需求可拆分且每種產(chǎn)品可由多輛車配送[11]”，后者在拆分上較前者更加完全、純粹。例如王茜等[38]（2016）在研究多車型MCVRP問題中還假設(shè)客戶需求可拆分但每種產(chǎn)品只能由一輛車運輸，在此基礎(chǔ)上構(gòu)建了該問題的數(shù)學模型，并通過將反應(yīng)機制與導(dǎo)引機制有機結(jié)合，提出了一種混合導(dǎo)引反應(yīng)式禁忌搜索算法予以求解。而張源凱等[11]（2017）針對成品油配送中的多車型MCVRP，進一步放寬需求拆分限制，允許多輛車對每個加油站點的單個油品進行運輸，在建立該問題的優(yōu)化調(diào)度模型后，提出了基于C-W節(jié)約算法的“需求拆分→合并裝載”的車輛裝載策略，并綜合利用Relocate和Exchange算子進行并行鄰域搜索改進的算法用于求解。

2.5? 動態(tài)MCVRP

在傳統(tǒng)MCVRP模型中的信息是靜態(tài)不變的，而實際物流配送中其實存在著較多不確定因素，比如客戶需求變化、交通狀況或天氣導(dǎo)致的行駛時間波動以及人員或車輛自身等導(dǎo)致的不確定性。為了使得模型更加準確地反應(yīng)和解決實際問題，有必要建立新的動態(tài)MCVRP模型和設(shè)計相應(yīng)的算法對其求解。查閱文獻發(fā)現(xiàn)，現(xiàn)有的動態(tài)MCVRP主要包括具有隨機需求的MCVRP（MCVRP with Stochastic Demands，MCVRPSD）和具有隨機行駛時間的MCVRP（MCVRP with Stochastic Travel Time，MCVRPSTT）。

對于隨機需求，按照需求點的產(chǎn)生和需求量的變化可分為：（1）到達客戶點處才能確定需求量的“已知點的隨機需求”;（2）配送途中接收某處客戶新訂單的“隨機產(chǎn)生點的固定需求”;（3）最為復(fù)雜的“隨機產(chǎn)生點的隨機需求”。需要注意的是，在MCVRP中考慮隨機需求因素時不同于傳統(tǒng)VRP，它需要進一步考慮每種產(chǎn)品的隨機需求，問題復(fù)雜且求解也較難?，F(xiàn)有關(guān)于隨機需求下的MCVRP主要研究第一種隨機需求情形，其相對于其他兩種較簡單一些。例如Mendoza等[40]（2010）將MCVRPSD視為一個有追索權(quán)的隨機規(guī)劃問題并采用文化基因算法求解;之后，Mendoza等[41]（2011）又將該類問題描述為兩階段隨機規(guī)劃模型并開發(fā)了三種啟發(fā)式算法進行了求解;Goodson[42]（2015）則針對MCVRPSD設(shè)計了計算在先驗路徑上到達特定客戶的初始到達期望時間的方法，并提出了基于循環(huán)順序的模擬退火算法進行了有效求解;王淑云等[3]（2018）在MCVRPSD中還考慮了碳排放，并采用事前估計策略求解隨機需求所帶來的回程補貨問題，并根據(jù)概率分布構(gòu)造了多維冷鏈品剩余量分布圖用以決策可能的前行/回程方案。而對于具有隨機行駛時間的MCVRP即MCVRPSTT，其于近年來逐漸被研究，且主要集中應(yīng)用在冷鏈物流的多溫共配場景中。例如Huang和Lu[43]（2017）在研究冷鏈產(chǎn)品的多溫共配問題時不僅考慮貨損率還假設(shè)車輛行駛時間服從已知的正態(tài)分布，在此基礎(chǔ)上建立隨機優(yōu)化模型并使用節(jié)約算法（Saving Algorithm）進行了求解;Lu和Wang[44]（2018）針對模糊環(huán)境下的多溫共配問題，使用三角模糊數(shù)來表示行駛時間并建立該問題的模糊優(yōu)化模型，然后設(shè)計了兩種離散螢火蟲算法進行了有效的求解;徐梅和陳淮莉[45]（2019）針對交通擁堵情況下的多溫共配車輛路徑問題，使用兩客戶點之間路段的交通量與該路段的通行能力之比作為判斷路段擁堵的決策變量，并進而使用該決策變量計算出通過路段的實際耗時，在建立基于交通擁堵的多溫共配優(yōu)化模型后采用隨機自適應(yīng)遺傳算法進行了求解;張濟風和楊中華[46]（2020）則針對時變路網(wǎng)環(huán)境下的多溫區(qū)產(chǎn)品配送車輛路徑問題，考慮車廂容量限制以及時間窗約束，建立以運輸成本、貨損成本及制冷成本構(gòu)成的總配送成本最小為目標的數(shù)學優(yōu)化模型，并設(shè)計了模擬退火算法用以求解。

2.6? 取送貨MCVRP

根據(jù)任務(wù)特性，MCVRP問題可分為送貨MCVRP、取貨MCVRP以及取送貨MCVRP。其中，送貨MCVRP的研究最多且其主要應(yīng)用于正向物流中，比如表1中的冷鏈物流運送不同保溫要求的肉類到超市[3]、成品油運輸中將不同油品配送到加油站[4]以及便利店雜貨運輸中將不同貨物配送到商店[19]等。其次，取貨MCVRP則主要應(yīng)用于逆向物流[47]中，比如生活垃圾回收行業(yè)[48]中使用多隔間車輛前往多個回收點收集不同類別廢棄物、家畜收集行業(yè)[25]中使用多隔間車輛前往農(nóng)場收集不同種類動物以及動物奶收集行業(yè)[26]中使用多隔間車輛前往各產(chǎn)奶點收集不同動物奶等。而對于取送貨MCVRP，它是正向物流和逆向物流相結(jié)合，根據(jù)客戶是否要求同時取送貨，其又可分為同時取送貨的MCVRP和分別取送貨的MCVRP。其中，同時取送貨的MCVRP研究的較少，雖然其應(yīng)用場景在實際物流中存在但不多見，比如便利店雜貨運輸中可能需要在對某產(chǎn)品進貨的同時讓廠家把該類已回收或過期的產(chǎn)品也取走（回收的壞產(chǎn)品需要做標記）。目前，只有胡衛(wèi)等[49]（2016）在研究多溫共配問題時結(jié)合同時送取貨，構(gòu)建了基于同時送取貨的機械式冷凍區(qū)隔間多溫共配模型，并利用遺傳算法進行求解，結(jié)果表明與傳統(tǒng)冷鏈專車配送模式相比，多溫層冷鏈配送模式能有效降低成本。而對于分別取送貨的MCVRP，它使用取貨和送貨兩種車隊來分別對客戶進行服務(wù)。如Huang等[30]（2015）提出并解決了一個帶有隨機需求和容量限制的選址路徑模型，模型中將車隊劃分為取貨和送貨兩個車隊以形成兩套不同的配送路線，之后使用禁忌搜索算法對其進行了求解。

2.7? 多目標MCVRP

經(jīng)典MCVRP僅存一個目標，往往是車輛總行駛距離最短或車輛數(shù)最少。而隨著現(xiàn)實情況的愈加復(fù)雜，需要考慮更多相關(guān)因素，這不僅使得MCVRP模型中約束條件增多，其目標函數(shù)也變得復(fù)雜了。就單目標MCVRP而言，除了考慮最短路徑[50]或最少車輛[11]外，還可能進一步與其他甚至多個目標加權(quán)組成單目標，比如在帶軟時間窗的MCVRP模型中考慮違背時間窗的懲罰成本[4]、選址路徑問題模型中考慮新建車場費用[30]、冷鏈物流多溫共配問題模型中考慮制冷成本和貨損成本[46]甚至碳排放成

本[14]等。需要注意的是，多個目標之間其實往往存在著矛盾或沖突，若只通過單目標加權(quán)中調(diào)節(jié)權(quán)值大小的方法來權(quán)衡這些目標則較難，并且單目標加權(quán)求和只能逼近凸的帕累托面。而要求多個目標在給定區(qū)域內(nèi)同時盡可能最佳的多目標優(yōu)化問題則直接求解而不存在確定權(quán)值的問題，而且其帕累托解集能包含更多有效信息。因此，多目標MCVRP也逐漸被學者們研究，且前期主要考慮的是雙目標MCVRP，后期則開始逐漸考慮三目標的MCVRP。例如Sun[51]（2015）建立了多溫共配問題的雙目標二進制整數(shù)規(guī)劃模型，其目標函數(shù)是同時將物流成本以及影響環(huán)境的碳排放成本最小化;孫麗君等[16]（2018）分別以總配送成本和車輛間工作量差距為目標，構(gòu)建了考慮司機工作量均衡的成品油配送的多目標優(yōu)化模型，并提出了一種新型的Split_Assign算法對第二代非支配快速排序遺傳算法（Nondominated Sorting Genetic Algorithm II，NSGA-II）進行改進以用于求解;而詹紅鑫等[15]（2019）則針對成品油配送中的多車型MCVRP，以配送成本最小、配送風險最小以及油品準時送達這三個目標建立了成品油配送多目標路徑優(yōu)化模型，并基于鄰域搜索的思想提出了求解該多目標問題的多目標變鄰域搜索框架。Tsang等[52]（2020）針對冷鏈物流中的多溫共配問題，建立了同時優(yōu)化行駛時間最小、使用車輛數(shù)最少以及客戶滿意度最大這三個目標的數(shù)學模型，并提出一種兩階段多目標遺傳算法優(yōu)化器用于求解。

3? 結(jié)束語與展望

多隔間車輛路徑問題（MCVRP）是一個涉及隔間容量約束、時間窗口、多車型可選、信息動態(tài)等的復(fù)雜路徑規(guī)劃問題。本文主要是根據(jù)其問題特征，把MCVRP問題歸納為7類，并從問題的角度分別進行了綜述。鑒于篇幅有限，關(guān)于MCVRP求解方法的綜述將另文闡述。

隨著現(xiàn)代物流中待運產(chǎn)品多樣性特征的出現(xiàn)，MCVRP的應(yīng)用場景也在逐漸增加，與此同時，一些新的運輸需求也將被提出，相應(yīng)的MCVRP新擴展問題需要被研究以滿足相應(yīng)的需求。本文建議未來的研究與發(fā)展可著重以下五個方面：（1）使用新型交通工具，比如電動車、可替代燃料車，甚至無人駕駛車等;（2）軟硬時間窗共存，即部分客戶是硬時間窗要求而其他客戶是軟時間窗要求;（3）需求點隨機產(chǎn)生，即在配送過程中突然隨機產(chǎn)生需求點，是就近優(yōu)先配送還是原計劃配送后回程取貨;（4）客戶服務(wù)優(yōu)先級，即如何對不僅有多種產(chǎn)品需求且不同客戶間可能存在不同優(yōu)先級的客戶群體進行合理配送;（5）更多目標函數(shù)，即當模型中出現(xiàn)四個甚至更多個目標的MCVRP時，如何求解該類高維多目標優(yōu)化問題以及如何對其得到的目標前沿進行可視化。

參考文獻：

[1] Dantzig G B， Ramser J H. The truck dispatching problem[J]. Management Science， 1959，6（1）：80-91.

[2] 畢國通. 車輛路徑問題及其優(yōu)化算法研究綜述[J]. 物流科技，2016，39（6）：95-97.

[3] 王淑云，孫虹，牟進進. 隨機需求下蓄冷式多溫共配優(yōu)化模型[J]. 系統(tǒng)管理學報，2018，27（4）：712-721.

[4] 王旭坪，詹紅鑫，李麗麗. 考慮時空距離的成品油多艙配送路徑優(yōu)化研究[J]. 管理工程學報，2018，32（4）：126-132.

[5]? Mofid-Nakhaee E， Barzinpour F. A multi-compartment capacitated arc routing problem with intermediate facilities for solid waste collection using hybrid adaptive large neighborhood search and whale algorithm[J]. Waste Management & Research， 2019，37（1）：38-47.

[6]? Abdulkader M M S， Gajpal Y， Elmekkawy T Y. Hybridized ant colony algorithm for the Multi Compartment Vehicle Routing Problem[J]. Applied Soft Computing， 2015，37：196-203.

[7]? Brown G G， Graves G W. Real-time dispatch of petroleum tank trucks[J]. Management Science， 1981，27（1）：19-32.

[8] 陶榮. 基于蟻群算法的多溫共配冷鏈物流配送問題研究[J]. 物流技術(shù)，2014，33（9）：302-304，307.

[9]? Chen L， Liu Y， Langevin A. A multi-compartment vehicle routing problem in cold-chain distribution[J]. Computers & Operations Research， 2019，111：58-66.

[10]? Coelho L C， Laporte G. Classification， models and exact algorithms for multi-compartment delivery problems[J]. European Journal of Operational Research， 2015，242（3）：854-864.

[11] 張源凱，孫麗君，胡祥培. 成品油配送多車艙車輛指派及路徑優(yōu)化問題研究[J]. 運籌與管理，2017，26（7）：1-9.

[12]? Reed M， Yiannakou A， Evering R. An ant colony algorithm for the multi-compartment vehicle routing problem[J]. Applied Soft Computing， 2014，15：169-176.

[13]? Henke T， Speranza M G， Waescher G. A branch-and-cut algorithm for the multi-compartment vehicle routing problem with flexible compartment sizes[J]. Annals of Operations Research， 2015，275（2）：321-338.

[14] 王旭坪，董杰，韓濤，等. 考慮碳排放與時空距離的冷鏈配送路徑優(yōu)化研究[J]. 系統(tǒng)工程學報，2019，34（4）：555-565.

[15] 詹紅鑫，王旭坪，孫自來，等. 基于鄰域搜索的成品油多艙多目標配送路徑優(yōu)化算法研究[J]. 系統(tǒng)工程理論與實踐，2019，39（10）：2660-2675.

[16] 孫麗君，石海洋，胡祥培. 考慮司機工作量均衡的成品油配送優(yōu)化[J]. 系統(tǒng)工程理論與實踐，2018，38（3）：677-686.

[17]? Zbib H， Wohlk S. A comparison of the transport requirements of different curbside waste collection systems in Denmark[J]. Waste Management， 2019，87：21-32.

[18]? Elbek M， Wohlk S. A variable neighborhood search for the multi-period collection of recyclable materials[J]. European Journal of Operational Research， 2016，249（2）：540-550.

[19]? Ostermeier M， Huebner A. Vehicle selection for a multi-compartment vehicle routing problem[J]. European Journal of Operational Research， 2018，269（2）：682-694.

[20]? Martins S， Ostermeier M， Amorim P， et al. Product-oriented time window assignment for a multi-compartment vehicle routing problem[J]. European Journal of Operational Research， 2019，276（3）：893-909.

[21]? Huebner A， Ostermeier M. A Multi-Compartment Vehicle Routing Problem with Loading and Unloading Costs[J]. Transportation Science， 2019，53（1）：282-300.

[22]? Gocmen E， Erol R. Location and Multi-Compartment Capacitated Vehicle Routing Problem for Blood Banking System[J]. International Journal of Engineering Technologies， 2018，4（1）：1-12.

[23]? Kandiller L， Eliiyi D T， Tasar B. A Multi-compartment Vehicle Routing Problem for Livestock Feed Distribution[C] // Operations Research Proceedings 2015，2017：149-155.

[24]? El Fallahi A， Prins C， Calvo R W. A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem[J]. Computers & Operations Research， 2008，35（5）：1725-1741.

[25]? Oppen J， Lokketangen A. A tabu search approach for the livestock collection problem[J]. Computers & Operations Research， 2008，35（10）：3213-3229.

[26]? Paredes-Belmar G， Marianov V， Bronfman A， et al. A milk collection problem with blending[J]. Transportation Research Part E Logs and Transportation Review， 2016，94：26-43.

[27]? Caramia M， Guerriero F. A Milk Collection Problem with Incompatibility Constraints[J]. Interfaces， 2010，40（2）：130-143.

[28]? Lahyani R， Coelho L C， Khemakhem M， et al. A multi-compartment vehicle routing problem arising in the collection of olive oil in Tunisia[J]. Omega-International Journal of Management Science， 2015，51：1-10.

[29] 陳久梅，周楠，王勇. 生鮮農(nóng)產(chǎn)品多隔室冷鏈配送車輛路徑優(yōu)化[J]. 系統(tǒng)工程，2018，36（8）：106-113.

[30]? Huang S H. Solving the multi-compartment capacitated location routing problem with pickup-delivery routes and stochastic demands[J]. Computers & Industrial Engineering， 2015，87：104-113.

[31] 戴錫，葉耀華，吳勤旻，等. 油品配送車輛路徑問題的交互式求解方法[J]. 系統(tǒng)工程學報，2009，24（6）：749-753.

[32]? Alinaghian M， Shokouhi N. Multi-depot multi-compartment vehicle routing problem， solved by a hybrid adaptive large neighborhood search[J]. Omega-International Journal of Management Science， 2018，76：85-99.

[33]? Derigs U， Gottlieb J， Kalkoff J， et al. Vehicle routing with compartments： applications， modelling and heuristics[J]. Or Spectrum， 2011，33（4）：885-914.

[34]? Koch H， Henke T， Wascher G. A genetic algoritm for the multi-compartment vehicle routing problem with flexible compartment sizes. Working Paper No. 04/2016， Otto-von-Guericke University Magdeburg： Faculty of Economics and Management[EB/OL]. （2018）[2020-11-30]. https：//doi.org/10.24352/UB.OVGU-2018-552.

[35]? Melechovsky J. Evolutionary Local Search Algorithm to Solve the Multi-Compartment Vehicle Routing Problem with Time Windows[C] // 30th International Conference on Mathematical Methods in Economics， 2012：564-568.

[36]? Kaabi H. Hybrid Metaheuristic to Solve the Selective Multi-compartment Vehicle Routing Problem with Time Windows[C]

// Proceedings of the Second International Afro-European Conference for Industrial Advancement， 2016：185-194.

[37]? Chen J， Shi J. A multi-compartment vehicle routing problem with time windows for urban distribution-A comparison study on particle swarm optimization algorithms[J]. Computers & Industrial Engineering， 2019，133：95-106.

[38] 王茜，吉清凱，胡祥培. 多車型多車槽VRP的混合導(dǎo)引反應(yīng)式禁忌搜索算法[J]. 管理工程學報，2016，30（3）：179-187.

[39]? Silvestrin P V， Ritt M. An iterated tabu search for the multi-compartment vehicle routing problem[J]. Computers & Operations Research， 2017，81：192-202.

[40]? Mendoza J E， Castanier B， Gueret C， et al. A memetic algorithm for the multi-compartment vehicle routing problem with stochastic demands[J]. Computers & Research， 2010，37（11）：1886-1898.

[41]? Mendoza J E. Solving real-world vehicle routing problems in uncertain environments[J]. 4OR-A Quarterly Journal of Operations Research， 2011，9（3）：321-324.

[42]? Goodson J C. A priori policy evaluation and cyclic-order-based simulated annealing for the multi-compartment vehicle routing problem with stochastic demands[J]. European Journal of Operational Research， 2015，241（2）：361-369.

[43]? Huang G， Lu R. The Route Optimization of Multi-temperature Joint Distribution for Cold-Chain Products under the Condition of Random Driving Time[C] // International Conference on Education， 2017：163-166.

[44]? Lu S， Wang X. Discrete Firefly Algorithm for Clustered Multi-Temperature Joint Distribution with Fuzzy Travel Times[J]. International Journal of Computational Intelligence Systems， 2018，11（1）：195-205.

[45] 徐梅，陳淮莉. 交通擁堵情況下的多溫共配車輛路徑優(yōu)化[J]. 江蘇大學學報（自然科學版），2019，40（2）：152-158.

[46] 張濟風，楊中華. 時變路網(wǎng)環(huán)境下多溫冷鏈配送路徑優(yōu)化研究[J]. 重慶師范大學學報（自然科學版），2020，37（1）：119-126.

[47] 楊冬英，潘文軍. 逆向物流網(wǎng)絡(luò)設(shè)計分類研究綜述[J]. 物流科技，2020，43（5）：68-72.

[48]? Zbib H， Laporte G. The commodity-split multi-compartment capacitated arc routing problem[EB/OL]. （2020）[2020-11-30]. https：//www.sciencedirect.com/science/articie/abs/pii/s0305054820301118.

[49] 胡衛(wèi)，梁承姬，樊陸彬. 基于同時取送貨的多溫共配冷鏈車輛路徑優(yōu)化[J]. 廣西大學學報（自然科學版），2016，41（5）：1576

-1584.

[50] 王成亮，李守偉. 一種基于復(fù)雜網(wǎng)絡(luò)的多廂車輛配送路徑優(yōu)化算法[J]. 系統(tǒng)管理學報，2019，28（4）：708-716.

[51]? Sun H. A Model for Vehicle Routing Problem for Multi-Temperature Joint Distribution System with Carbon Emission Constraints[C] // International Conference on Logistics Engineering， 2015：1022-1026.

[52]? Tsang Y P， Wu C H， Lam H Y， et al. Integrating internet of things and multi-temperature delivery planning for perishable food e-commerce logistics： a model and application[EB/OL]. （2020）[2020-11-30]. https：//doi.org/10.1080/00207543.2020.1841315.