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

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

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

【部分圖文】：

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

棖罌殺渙???分，可根據(jù)車輛剩余裝載情況機(jī)動(dòng)地對(duì)客戶需求以任意方式(需求大小)進(jìn)行拆分。如圖1所示，共有3個(gè)客戶點(diǎn)(括號(hào)內(nèi)數(shù)字為需求量)，各弧旁數(shù)字為相鄰點(diǎn)間距離。假設(shè)車輛裝載能力為10，則所需最小車輛數(shù)為2。在相應(yīng)的DSDVＲP中，如圖2所示，各客戶點(diǎn)的總需求量和車輛裝載能力與圖1中的例子相同，但各客戶需求均由2批(訂單)組成(括號(hào)內(nèi)為訂單需求量)。采用動(dòng)態(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個(gè)拆分點(diǎn)，2條路徑中公共點(diǎn)個(gè)數(shù)為3，大于路徑數(shù)2，總路徑長(zhǎng)度為10.83，長(zhǎng)于SDVＲP總路徑長(zhǎng)度(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對(duì)比SDVＲP，DSDVＲP及其最優(yōu)解具有以下特性(cij、di和Q及其相關(guān)限制條件均相同的情況下):1)若Ｒ和Ｒ'分別為SDVＲP和DSDVＲP最優(yōu)解中任意2條路徑間存在的公共點(diǎn)數(shù)，存在Ｒ≤Ｒ'，即DSDVＲP最優(yōu)解中任意兩條路徑間可能存在多個(gè)公共點(diǎn);2)若L和L'分別為SDVＲP和DSDVＲP最優(yōu)解中需求拆分點(diǎn)個(gè)數(shù)，存在L≤L'，即DSDVＲP最優(yōu)解中拆分點(diǎn)個(gè)數(shù)可能多于路徑數(shù);3)若Z和Z'分別為SDVＲP和DSDVＲP的最優(yōu)解對(duì)應(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è)計(jì)2.1解的表達(dá)方式本文在算法設(shè)計(jì)及求解過程的描述中，將各客戶的離散需求看成相互獨(dú)立?

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

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



本文編號(hào)：3570882