針對客戶需求常以若干離散訂單（批次）構(gòu)成的問題特性,本文給出需求可離散拆分車輛路徑問題的描述及數(shù)學(xué)模型。對比需求可連續(xù)拆分的問題類型,對該問題性質(zhì)進行了研究,分析提出問題解的特性。本文提出求解該問題的禁忌搜索算法,針對同客戶的不同訂單（批次）需求,設(shè)計兩種特殊操作以避免不必要的路徑成本,加快搜索速度并增強算法搜索性能。計算結(jié)果與現(xiàn)有方法結(jié)果進行了比較,表明所提出的算法可以找到更好的解決方案。 

【文章來源】：哈爾濱工程大學(xué)學(xué)報. 2019,40(03)北大核心EICSCD

【文章頁數(shù)】：9 頁

【部分圖文】：

SDVＲP最優(yōu)路徑方案

棖罌殺渙???分，可根據(jù)車輛剩余裝載情況機動地對客戶需求以任意方式(需求大小)進行拆分。如圖1所示，共有3個客戶點(括號內(nèi)數(shù)字為需求量)，各弧旁數(shù)字為相鄰點間距離。假設(shè)車輛裝載能力為10，則所需最小車輛數(shù)為2。在相應(yīng)的DSDVＲP中，如圖2所示，各客戶點的總需求量和車輛裝載能力與圖1中的例子相同，但各客戶需求均由2批(訂單)組成(括號內(nèi)為訂單需求量)。采用動態(tài)規(guī)劃算法可分別求得SDVＲP及DSDVＲP在使用最小車輛數(shù)且不超載的條件下的最優(yōu)路徑方案。圖1SDVＲP最優(yōu)路徑方案Fig．1OptimalsolutiontotheSDVＲP圖2DSDVＲP最優(yōu)路徑方案Fig．2OptimalsolutiontotheDSDVＲPDSDVＲP的上述路徑方案中，各路徑中各包含有3個拆分點，2條路徑中公共點個數(shù)為3，大于路徑數(shù)2，總路徑長度為10.83，長于SDVＲP總路徑長度(9.48)。路徑10－1(3)－2(7)－0路徑20－1(2)－3(8)－0路徑10－1(1)－2(2)－3(7)－0路徑20－1(4)－2(5)－3(1)－0對比SDVＲP，DSDVＲP及其最優(yōu)解具有以下特性(cij、di和Q及其相關(guān)限制條件均相同的情況下):1)若Ｒ和Ｒ'分別為SDVＲP和DSDVＲP最優(yōu)解中任意2條路徑間存在的公共點數(shù)，存在Ｒ≤Ｒ'，即DSDVＲP最優(yōu)解中任意兩條路徑間可能存在多個公共點;2)若L和L'分別為SDVＲP和DSDVＲP最優(yōu)解中需求拆分點個數(shù)，存在L≤L'，即DSDVＲP最優(yōu)解中拆分點個數(shù)可能多于路徑數(shù);3)若Z和Z'分別為SDVＲP和DSDVＲP的最優(yōu)解對應(yīng)的目標(biāo)函數(shù)值，存在Z≤Z'，即DSDVＲP最優(yōu)解可能劣于SDVＲP最優(yōu)解;4)已知SDVＲP為NP－難問題［1，14］，SDVＲP是DSDVＲP的特殊形式，所以DSDVＲP同為NP-Hard問題。2禁忌搜索算法設(shè)計2.1解的表達方式本文在算法設(shè)計及求解過程的描述中，將各客戶的離散需求看成相互獨立?

哈爾濱工程大學(xué)學(xué)報第40卷新路徑起點，繼續(xù)構(gòu)造新路徑。以此類推，直至所有節(jié)點均被分配至指定路徑為止。2.3同客戶節(jié)點合并操作由于路徑構(gòu)造時將所有離散的客戶訂單視為獨立節(jié)點，故生成的路徑中存在同客戶訂單被分散訪問的情況。如圖3所示，節(jié)點i、j分別表示同客戶的不同訂單，路徑中該客戶點被先后訪問了2次，增大了不必要的路徑成本。為此本文設(shè)計同客戶訂單合并操作，對路徑內(nèi)相同客戶的訂單進行合并，避免不必要的路徑成本，該操作為離散需求拆分的基本路徑優(yōu)化操作，為訂單組合的操作奠定基矗圖3同客戶節(jié)點合并操作Fig．3Combinationofitemsfromthesamecustomers2.4同客戶節(jié)點隨機綁定操作一般鄰域操作中使用的操作對象為單一的客戶節(jié)點，因DSDVＲP中的實際個體為各客戶訂單節(jié)點，若簡單將客戶節(jié)點(該客戶的全部訂單)作為操作對象，則無法體現(xiàn)需求可拆分特性。但若將訂單節(jié)點作為操作對象，因訂單數(shù)量遠(yuǎn)大于客戶數(shù)，將耗費大量的計算時間。故本文提出一種折中方式，設(shè)計同客戶節(jié)點隨機綁定操作，用于鄰域操作中實際操作對象的生成及選擇。具體操作方式為:在當(dāng)前解中隨機挑選可行的操作對象(節(jié)點)，向前向后判斷是否存在同客戶節(jié)點。隨后在同客戶節(jié)點間隨機選擇若干個連續(xù)訂單進行綁定，作為接下來鄰域操作的實際操作對象。如圖4所示，挑選出的操作節(jié)點為i，經(jīng)判斷路徑中t、i、j、k屬于同一客戶，t和k分別為起始同客戶節(jié)點。i、j、k為隨機挑選出的連續(xù)同客戶訂單節(jié)點，則在下一步鄰域操作中將i、j、k綁定視為一個綁定節(jié)點i*進行操作。由此可知，經(jīng)該操作確定的操作對象可能是單一訂單節(jié)點，如圖5;可能是部分訂單，如圖4和6;也可能是客戶點(該客戶的全部訂單)，如圖7，由此增大了操作對象的隨機多樣性。在?

【參考文獻】：
期刊論文
[1]求解需求可拆分車輛路徑問題的人工蜂群算法[J]. 姜婷.  四川理工學(xué)院學(xué)報(自然科學(xué)版). 2017(03)
[2]帶軟時間窗的需求依訂單拆分車輛路徑問題及其禁忌搜索算法[J]. 符卓,劉文,邱萌.  中國管理科學(xué). 2017(05)
[3]求解需求可拆分車輛路徑問題的聚類算法[J]. 向婷,潘大志.  計算機應(yīng)用. 2016(11)



本文編號：3570882