需求可拆分車輛路徑問題探究綜述

《需求可拆分車輛路徑問題探究綜述》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、需求可拆分車輛路徑問題探究綜述　　摘要：SDVRP允許單一節(jié)點(diǎn)的訂單需求由多個(gè)車輛進(jìn)行配送，與傳統(tǒng)VRP相比可提高車輛利用率并降低車輛使用數(shù)目和運(yùn)輸成本。文中在國內(nèi)外研究的基礎(chǔ)上，重點(diǎn)介紹了SDVRP的主要分支，并與國內(nèi)研究現(xiàn)狀對比，發(fā)現(xiàn)我國在該領(lǐng)域的研究仍處于起步階段。關(guān)鍵詞：需求可拆分車輛路徑問題；分支；國內(nèi)現(xiàn)狀一.引言傳統(tǒng)的VRP一直是網(wǎng)絡(luò)最優(yōu)化問題中最基本的問題之一，由于其應(yīng)用的廣泛性和經(jīng)濟(jì)上的重大價(jià)值，多年以來，受到國內(nèi)外廣泛關(guān)注。傳統(tǒng)的VRP假定每個(gè)客戶端的需求只能由一輛車來完成，即需求不可以被拆分，但實(shí)際應(yīng)用中，有可能會(huì)存在相當(dāng)一部分任務(wù)點(diǎn)的需求量比較大，此時(shí)，如果

2、仍然要求每個(gè)客戶點(diǎn)只能由一輛車來完成服務(wù)，勢必會(huì)造成車輛的空載率提高，浪費(fèi)運(yùn)輸資源。1989年Dror&Trudeau首次提出了SDVRP的概念[1]，并指出SDVRP是一種約束松弛的VRP，即每個(gè)客戶點(diǎn)的需求由傳統(tǒng)VRP中的只能由一輛車滿足，擴(kuò)展為可以由多輛車滿足，這可使得車輛數(shù)量和路線總長得到節(jié)約。二.SDVRP的分類根據(jù)研究重點(diǎn)的不同，SDVRP5有多種分類方式。雖然諸如帶時(shí)間窗、帶集貨和配送的VRP在傳統(tǒng)VRP問題中已經(jīng)被大量研究，但是，在SDVRP情況下，仍然會(huì)得出一些有意義的結(jié)論。根據(jù)對國內(nèi)外文獻(xiàn)進(jìn)行歸納，常見的SDVRP的分支主要有以下幾類：（一）帶時(shí)間窗限制（SD

3、VRPTW）。帶時(shí)間窗限制，意味著訂單必須在顧客規(guī)定的時(shí)間段內(nèi)到達(dá)，帶時(shí)間窗限制的車輛路徑問題（VRPTW）屬于傳統(tǒng)VRP分支。Archettietal.提出了第一個(gè)求解SDVRPTW的精確算法[2]。他們運(yùn)用禁忌搜索算法和新的有效不等式對子問題分別求解，一種新的啟發(fā)式算法則被用于尋找最優(yōu)拆分點(diǎn)。實(shí)驗(yàn)結(jié)果表明，該求解方法對顧客規(guī)模為100的SDVRPTW同樣具有良好的求解效果。目前，基于禁忌搜索求解SDVRPTW的啟發(fā)式算法，是由Ho&Haugland提出的[3]，該算法將SDVRPTW的求解規(guī)模擴(kuò)大至100以上。（二）帶集貨和配送限制（SDVRPPD）。在SDVRPPD中，無時(shí)

4、間窗和最大車輛路線限制，但每一節(jié)點(diǎn)只能被一輛車訪問一次，且每一節(jié)點(diǎn)可能同時(shí)具有收貨和配送兩種需求，任一節(jié)點(diǎn)的需求都可能超過車輛容量。其目標(biāo)函數(shù)是通過最小化車輛使用數(shù)目來最小化總運(yùn)輸成本。這一應(yīng)用在實(shí)際生活中非常常見，如快遞員在送貨的過程中，經(jīng)常也會(huì)收到客戶寄送貨物的需求.Nowaket5al.通過研究證明[3]，在同一地理分布的顧客群下，當(dāng)訂單平均大小為車載容量一半時(shí)，拆分能夠獲得最大的收益。（三）利潤最大化一般情況下，SDVRP的目標(biāo)函數(shù)是最小化車輛行駛路線或運(yùn)輸成本，有時(shí)也對使用成本進(jìn)行優(yōu)化。但是，由于需求可拆分，可能帶來額外收益。Brnmoetal.通過數(shù)學(xué)規(guī)劃模型并整合分

5、區(qū)的方法對此類問題進(jìn)行求解[3]，結(jié)果證明允許拆分可以提高物流企業(yè)利潤率。（四）庫存和生產(chǎn)自從供應(yīng)鏈管理的觀念提出以來，庫存路徑問題已為很多學(xué)者關(guān)注。由于庫存的概念是基于時(shí)間、庫存成本以及庫存容量之上，時(shí)間成為SDVRP中考慮的一個(gè)重要因素。在這些問題中，一個(gè)顧客通常在特定的時(shí)間范圍可以被訪問多次，但是一個(gè)配送日內(nèi)只能訪問一次。同時(shí)，庫存路徑模型還會(huì)考慮生產(chǎn)制造策略。（五）其他除了以上四種主要的SDVRP分支以外，考慮最小損耗率、混合車輛編隊(duì)、隨機(jī)性、需求的離散性以及弧路徑的SDVRP分支也逐漸出現(xiàn)在國內(nèi)外研究中，限于文章篇幅不在此一一贅述。三.國內(nèi)研究現(xiàn)狀5當(dāng)前，國內(nèi)對SDVR

6、P的研究尚不多見。隋露斯，唐加福等用蟻群算法求解SDVRP[4]，給出了基于整數(shù)規(guī)劃的描述方法；通過仿真實(shí)驗(yàn)發(fā)現(xiàn)，該算法對車輛數(shù)目和運(yùn)輸距離的改進(jìn)顯著。魯強(qiáng)等用遺傳算法求解K-SDVRP[5]，數(shù)值試驗(yàn)表明，某些條件下，SDVRP較VRP車輛使用數(shù)和車輛運(yùn)輸距離更少。孟凡超等通過改進(jìn)傳統(tǒng)的數(shù)學(xué)模型[6]，建立SDVRP數(shù)學(xué)模型，利用禁忌搜索算法對SDVRP進(jìn)行求解。算例結(jié)果表明，該模型可以節(jié)省車輛數(shù)目、縮短路線長度、提高車輛裝載率。楊亞璪等等對SDVRPPD進(jìn)行研究[7]，算例結(jié)果表明，所設(shè)計(jì)的算法可以得到合理的車輛路徑，特別當(dāng)集貨需求的總量小于送貨需求的總量時(shí)，優(yōu)化效果更好。無

7、論是使用蟻群算法、禁忌搜索算法還是遺傳算法，隋露斯、魯強(qiáng)、孟凡超以及楊亞璨等人關(guān)于可拆分車輛路徑問題的研究，都是在需求確定的情況下研究SDVRP，并未考慮客戶的時(shí)間窗以及需求的隨機(jī)性。四.結(jié)論在對SDVRP的主要分支以及常用求解方法進(jìn)行總結(jié)的基礎(chǔ)上，我們發(fā)現(xiàn)目前對SDVRP的求解方法主要是通過混合整數(shù)規(guī)劃建模并整合精確或者啟發(fā)式算法對問題進(jìn)行求解，但隨著問題規(guī)模的擴(kuò)大，其求解面臨著維數(shù)災(zāi)難的問題。計(jì)算機(jī)仿真作為一種新的建模方法，隨著計(jì)算機(jī)技術(shù)的發(fā)展，使研究者可以通過搜索海量解空間