發(fā)布時(shí)間：2020-04-11所屬分類：農(nóng)業(yè)論文瀏覽：1次
摘 要： 摘要:以最小化總的旅行時(shí)間為優(yōu)化目標(biāo)，以單車
摘要:以最小化總的旅行時(shí)間為優(yōu)化目標(biāo)，以單車場(chǎng)、單車型、裝載能力和需求依背包拆分等為約束條件，將以往客戶需求不可拆分的條件松弛為依背包來(lái)離散拆分,建立了帶裝載能力的需求依背包拆分VRP(CVRPSDB)的單目標(biāo)數(shù)學(xué)模型。設(shè)計(jì)了一個(gè)自適應(yīng)禁忌搜索算法(ATSA)對(duì)模型進(jìn)行求解。該算法采用了自適應(yīng)懲罰機(jī)制，構(gòu)建了一個(gè)多鄰域結(jié)構(gòu)體，并針對(duì)客戶點(diǎn)與背包都設(shè)計(jì)了相應(yīng)的鄰域操作算子，較好地適應(yīng)了客戶需求量的離散拆分程度。經(jīng)算例測(cè)試與文獻(xiàn)對(duì)比，驗(yàn)證了所設(shè)計(jì)模型與算法的有效性。
關(guān)鍵詞:車輛路徑問(wèn)題;拆分;依背包拆分;禁忌搜索算法;物流
車輛路徑問(wèn)題(vehicleroutingproblem,VRP)自Dantzig[1]于1959年提出后，便引起了運(yùn)籌學(xué)界和管理科學(xué)界的廣泛關(guān)注。相比于傳統(tǒng)手工排班計(jì)劃，采用現(xiàn)代優(yōu)化算法[2]來(lái)優(yōu)化行車路線，可降低車輛的行駛成本，有助于減少相應(yīng)的碳排放量，降低對(duì)環(huán)境造成的影響。
根據(jù)客戶需求是否允許拆分配送，VRP可分為需求可拆分VRP[3](vehicleroutingproblemwithsplitdeliveries,VRPSD)和需求不可拆分VRP[1]。結(jié)合拆分方式是否是離散化的，VRPSD又可以分為需求離散拆分VRP[2](VRPwithdiscretesplitdeliveries,VRPDSD)與需求連續(xù)拆分的經(jīng)典VRPSD[4]，而在實(shí)踐離散拆分配送的VRPDSD中也有多種拆分方式，如依背包拆分、依貨物特性拆分等。本文將重點(diǎn)針對(duì)帶裝載能力的需求依背包拆分VRP(capacitatedVRPwithsplitdeliveriesbybackpack,CVRPSDB)進(jìn)行研究，并設(shè)計(jì)相應(yīng)的禁忌搜索算法(tabusearchalgorithm,TSA)進(jìn)行求解。
相關(guān)期刊推薦：《工業(yè)工程》(雙月刊)創(chuàng)刊于1998年，是由廣東工業(yè)大學(xué)主辦，中國(guó)機(jī)械工程學(xué)會(huì)協(xié)辦的期刊，國(guó)內(nèi)外公開發(fā)行。本刊理論與應(yīng)用結(jié)合，內(nèi)容涵蓋經(jīng)營(yíng)戰(zhàn)略、決策研究、制造系統(tǒng)、物流系統(tǒng)、設(shè)施規(guī)劃、工作研究、成本分析、工程經(jīng)濟(jì)、質(zhì)量保障、診斷評(píng)價(jià)、信息管理、人機(jī)工程、生產(chǎn)組織、人力資源、組織重構(gòu)等。讀者對(duì)象主要是從事工業(yè)工程理論與應(yīng)用研究的科技人員、各級(jí)政府工業(yè)和經(jīng)濟(jì)管理部門的決策人員、各類企業(yè)管理人員，高校師生及其他有關(guān)人員。
目前，在車輛路徑問(wèn)題研究中，多約定客戶需求只能由一輛車一次完成，屬于需求不可拆分VRP。Dror等[3]于1989年首次提出了VRPSD的一種最基本類型，即純送貨的需求可拆分VRP(vehicleroutingproblemwithsplitdeliveries,VRPSD)，并給出了VRPSD的定義，指出對(duì)客戶需求進(jìn)行合理地拆分配送有利于降低配送成本，其隨后于1994年證明了VRPSD屬于NP-hard問(wèn)題[4]，并給出了VRPSD的子回路消去約束。這些研究吸引了一批學(xué)者進(jìn)入可拆分VRP領(lǐng)域，如Archetti等[5-6]在Dror的基礎(chǔ)上，進(jìn)一步簡(jiǎn)化降低了VRPSD的研究難度，通過(guò)將車輛裝載能力和客戶需求予以整數(shù)單元化，假設(shè)客戶需求可按照計(jì)量單位來(lái)任意連續(xù)拆分，車輛裝載能力不小于客戶需求，構(gòu)建了經(jīng)典VRPSD的整數(shù)規(guī)劃模型(K-VRPSD模型)。
VRPSD拆分裝配具有理論上的成本節(jié)約性，不過(guò)在有些情況下，任意連續(xù)拆分VRPSD方式也會(huì)給物資裝配帶來(lái)實(shí)踐操作上的困難[7-8]，如將同一種物資拆分進(jìn)入不同的車輛線路，這必然會(huì)給裝貨和收貨帶來(lái)不必要的麻煩。在物流配貨中，客戶的需求常可視為由一定項(xiàng)數(shù)的物資離散組合而成，當(dāng)每項(xiàng)物資的特性差異很大時(shí)，配送企業(yè)可將每項(xiàng)物資視為一個(gè)獨(dú)立的“背包”打包用于裝配，同一個(gè)“背包”內(nèi)的物資一般不適合再進(jìn)行拆分組裝。如在電商物流配送、連鎖超市配送、快遞收發(fā)中由于各客戶的需求物品種類、體積大小、質(zhì)量規(guī)則等都不同，其需求若拆分則適合按照“背包”來(lái)離散進(jìn)行，不能按照物資重量來(lái)連續(xù)拆分。因此，研究需求依背包拆分VRP(VRPwithsplitdeliveriesbybackpack,VRPSDB)具有較強(qiáng)的實(shí)踐價(jià)值。另外，在VRPSD相關(guān)文獻(xiàn)中，除Gulczynski等[2]、Xiong等[9]、Wang等[10]、Salani等[7]、Xia等[8]的研究涉及離散拆分思想外，其余多數(shù)沿用Archetti等[5-6]構(gòu)造K-VRPSD模型時(shí)采用的需求連續(xù)拆分思想。可見(jiàn)，對(duì)需求依背包來(lái)離散拆分的VRP進(jìn)行研究具有較強(qiáng)的理論價(jià)值。
需求可拆分VRP(VRPSD)屬于NP-hard問(wèn)題。借用Archetti等[5-6]的需求連續(xù)拆分K-VRPSD模型，謝毅[11]、劉旺盛[12]都對(duì)經(jīng)典VRPSD的求解算法進(jìn)行了研究。VRPSD求解難度比傳統(tǒng)VRP更大，而精確算法如分支定界法[4]、割平面法[13]、動(dòng)態(tài)規(guī)劃法[14]、聚類−路徑兩階段法[15]、列生成及切面法[16]、分支−切平面法[17]等都只能有效求解中小規(guī)模問(wèn)題，因此設(shè)計(jì)能夠解決大規(guī)模問(wèn)題的智能啟發(fā)式算法(智能算法)是求解的關(guān)鍵。已有文獻(xiàn)在求解VRPSD及其衍生類型時(shí)主要結(jié)合了禁忌搜索算法[10-11,18-20]、遺傳算法[21]、蟻群算法[22]、蜂群算法[23]等智能優(yōu)化算法。禁忌搜索算法[24-25](tabusearchalgorithm,TSA)具有簡(jiǎn)單性、適應(yīng)性、易操作性等優(yōu)點(diǎn)，是一種求解需求可拆分VRP較為高效的智能優(yōu)化算法。因此，本文也采用禁忌搜索算法來(lái)進(jìn)行求解。
在以往的需求可拆分VRP文獻(xiàn)[5]中，對(duì)帶裝載能力的VRPSD(capacitatedVRP,CVRP)研究較多。因此，本文也對(duì)帶裝載能力的需求依背包拆分VRP(capacitatedVRPwithsplitdeliveriesbybackpack,CVRPSDB)進(jìn)行研究。由于本文的CVRPDSD是依“背包”來(lái)對(duì)客戶點(diǎn)的需求量進(jìn)行離散拆分操作，因此，CVRPSDB既是需求可拆分VRP(VRPSD)中存在的一種按“背包”離散拆分情形，也是以往傳統(tǒng)VRP的一種拓展。本文將以物流配送中單車場(chǎng)、單車型的純送貨為背景來(lái)對(duì)CVRPSDB進(jìn)行建模，并設(shè)計(jì)一個(gè)自適應(yīng)TSA(adaptiveTSA,ATSA)求解。
1問(wèn)題描述與建模
本文的CVRPSDB可描述為：確定一系列同車型的車輛在客戶點(diǎn)之間的行駛順序，使其從車場(chǎng)出發(fā)，有序地對(duì)各客戶點(diǎn)進(jìn)行送貨服務(wù)，最后返回原出發(fā)點(diǎn)，并在滿足車輛裝載能力的條件下最小化總的旅行時(shí)間。而且，各客戶點(diǎn)的需求量可拆分由多輛車來(lái)共同完成，但若拆分則只能按照“背包”來(lái)離散進(jìn)行，其中“背包”在本文的含義為不可進(jìn)一步拆分的客戶需求的最小集合。結(jié)合一般CVRP，本文的CVRPSDB有如下假設(shè)。
1)車場(chǎng)：車場(chǎng)為單車場(chǎng)，位置已知，且車輛數(shù)充足。
2)車輛：車輛為單車型，即全部車輛擁有相同裝載能力，約定車輛不可超載，車輛的行駛速度相同，且每條線路有截止期限限制，行駛線路為閉合式[38]，即必須返回原出發(fā)點(diǎn)。
3)客戶：全部客戶的地理位置、需求量已知，每個(gè)客戶需求可由多輛車依背包拆分送達(dá)，客戶點(diǎn)間的旅行時(shí)間符合三角不等式約束。
4)道路：忽略道路交通帶來(lái)的影響，車場(chǎng)到客戶點(diǎn)、客戶點(diǎn)與客戶點(diǎn)之間都可直達(dá)。5)目標(biāo)：最小化總的旅行時(shí)間。
2自適應(yīng)TSA設(shè)計(jì)
禁忌搜索算法(TSA)是一種求解VRP效果較好的智能算法。Fu等[26]對(duì)帶裝載能力約束的不拆分開放式VRP進(jìn)行了求解，其研究表明，在求解算法中接受部分不可行解，能夠增強(qiáng)算法鄰域搜索的柔性，有利于從不可行解過(guò)渡到更好的可行解，可增強(qiáng)算法的全局尋優(yōu)能力。本文設(shè)計(jì)一種雙優(yōu)化解機(jī)制，每次迭代后保存相應(yīng)的“最好解”和“當(dāng)前解”，約定“最好解”必須可行，而“當(dāng)前解”則可接受違反裝載能力約束的鄰域解。因此，本文在TSA搜索進(jìn)程中有限的接受部分不可行解，并增設(shè)一種自適應(yīng)懲罰機(jī)制，使得算法能夠在迭代過(guò)程中自適應(yīng)地調(diào)整搜索方向，增強(qiáng)自適應(yīng)尋優(yōu)能力，從而形成一個(gè)自適應(yīng)TSA。
2.1解的表達(dá)方式與初始解構(gòu)造
本文采用隨機(jī)方式[26]生成初始可行解，先隨機(jī)生成客戶點(diǎn)的一個(gè)排列，然后在滿足車輛裝載能力的情況下，按照此排列順序?qū)⒖蛻酎c(diǎn)所對(duì)應(yīng)的背包依次加入車輛線路中，當(dāng)違背車輛裝載能力限制時(shí)就開啟一條新的車輛線路。其中，在構(gòu)造初始可行解時(shí)，不考慮拆分，即同一客戶的背包全部放入一條線路中。
2.2多鄰域結(jié)構(gòu)體設(shè)計(jì)
在大規(guī)模配送CVRPSDB中，組合情況特別復(fù)雜，其解空間非常龐大。設(shè)計(jì)多鄰域結(jié)構(gòu)體，對(duì)解空間進(jìn)行鄰域劃分，采用不同的局部極值來(lái)逐步逼近全局最優(yōu)解是一種很好的迭代尋優(yōu)方式。隨機(jī)鄰域挑選策略能夠有助于算法在各鄰域之間自由變換，加速算法尋優(yōu)。X0X0=50+N
因此，ATSA設(shè)計(jì)一個(gè)多鄰域結(jié)構(gòu)體，設(shè)計(jì)4種鄰域操作算子，并采用隨機(jī)鄰域變換策略，每次隨機(jī)選出一種鄰域算子對(duì)當(dāng)前解變換。約定每次生成鄰域解的數(shù)目為，取。每次生成鄰域解時(shí)，采用隨機(jī)方式挑選出2條相異的線路R1與R2，然后采用隨機(jī)挑選方式，在兩線路內(nèi)各挑選出一個(gè)非0的客戶點(diǎn)或“背包”來(lái)進(jìn)行操作。每次鄰域操作后，逢多個(gè)0相鄰則只保留最前面的一個(gè)，將同一線路內(nèi)的同一客戶點(diǎn)的“背包”按照前后順序排列在一起(即同一線路內(nèi)背包合并)，并對(duì)相關(guān)約束進(jìn)行檢驗(yàn)，判斷生成的新鄰域解是否可行。
在本文的CVRPSDB中，結(jié)合各“背包”與其相應(yīng)客戶點(diǎn)的對(duì)應(yīng)關(guān)系，對(duì)客戶點(diǎn)與“背包”進(jìn)行統(tǒng)一操作，針對(duì)“客戶點(diǎn)”和“背包”都設(shè)計(jì)相應(yīng)的鄰域操作算子，盡可能地降低了由于訂單規(guī)模增大引發(fā)的求解難度。其中的“客戶點(diǎn)”鄰域操作算子相當(dāng)于對(duì)同一客戶點(diǎn)的“背包”實(shí)施了綁定策略，而“背包”鄰域操作算子則相當(dāng)于對(duì)同一客戶點(diǎn)的需求量施行了離散拆分策略。本文針對(duì)“客戶點(diǎn)”和“背包”都設(shè)計(jì)了相應(yīng)的鄰域操作算子，能夠較好地適應(yīng)CVRPSDB的鄰域變換。
2.4禁忌表設(shè)計(jì)與迭代終止條件
禁忌表的結(jié)構(gòu)與禁忌對(duì)象選取是TSA設(shè)計(jì)的重點(diǎn)。TSA中禁忌長(zhǎng)度的類型與大小對(duì)算法性能影響很大，為防止算法前期的循環(huán)搜索和增強(qiáng)算法中后期的隨機(jī)多樣性，本文ATSA把固定值的禁忌長(zhǎng)度和隨機(jī)值的禁忌長(zhǎng)度相結(jié)合，設(shè)計(jì)一個(gè)混合禁忌長(zhǎng)度：在算法迭代尋優(yōu)的前2000步內(nèi)，為定值16，在2000步以后，每次迭代都在[5,16]內(nèi)隨機(jī)取。N×Nςςς≤0
ATSA設(shè)置一個(gè)階的方陣式禁忌表，選取鄰域變換中的點(diǎn)對(duì)(i，j)作為禁忌對(duì)象，表內(nèi)的矩陣元素(i，j)用于存儲(chǔ)禁忌對(duì)象的禁忌長(zhǎng)度值。當(dāng)點(diǎn)i與j或其對(duì)應(yīng)的“背包”被挑選用于鄰域變換，且其對(duì)應(yīng)的候選解將成為下次迭代的“當(dāng)前解”時(shí)，便在其對(duì)應(yīng)的矩陣元素(i，j)中填入對(duì)應(yīng)的值。本文約定在每次鄰域變換后減1，直到方可解除對(duì)相應(yīng)解的禁忌。若存在某個(gè)可行“候選解”優(yōu)于當(dāng)前取到的“最好解”，則把其設(shè)置為新的“當(dāng)前解”與“最好解”，否則將非禁忌的最佳候選解置換為新的當(dāng)前解;若全部“候選解”都被禁忌了，則釋放最佳“候選解”，并將其設(shè)為新的當(dāng)前解。為了增強(qiáng)算法全局尋優(yōu)能力，防止因禁忌過(guò)度而漏搜了有關(guān)解集區(qū)域，本文增設(shè)一個(gè)“禁忌表重新初始化”策略，約定在迭代2000步以后，每隔m次迭代就將禁忌表重新初始化為全0矩陣，m=50。X1X1=5000+100N終止迭代的條件為：總迭代次數(shù)達(dá)到預(yù)設(shè)的上限值，本文取。
2.5算法描述依據(jù)禁忌搜索算法的基本框架，ATSA的基本流程如下。
Step1 初始化;
Step2 讀入相關(guān)數(shù)據(jù)及參數(shù)值;
Step3 隨機(jī)生成初始解，并把此解取為“最好解”與“當(dāng)前解”;
Step4While未滿足總迭代次數(shù)do;
Step5While候選解數(shù)目未達(dá)到預(yù)設(shè)值do;
Step6 在預(yù)設(shè)的4種鄰域操作算子之間隨機(jī)挑選出一種用于鄰域變換;
Step7 按規(guī)則對(duì)“當(dāng)前解”進(jìn)行鄰域變換，并構(gòu)建候選解集;
Step8End;
Step9 挑選出新的“最好解”與“當(dāng)前解”;
Step10 更新禁忌表;
Step11End;
Step12 輸出結(jié)果。
3算法測(cè)試
3.1算例構(gòu)造
需求依背包拆分VRP(VRPSDB)目前尚未有標(biāo)準(zhǔn)測(cè)試算例。文獻(xiàn)[12]、[22]、[23]在研究經(jīng)典CVRPSD時(shí)，都采用一個(gè)含1個(gè)配送中心、15個(gè)客戶點(diǎn)、客戶需求總和為4881、車輛載重為500的CVRP算例進(jìn)行了算法測(cè)試。因此，本文在該算例基礎(chǔ)上構(gòu)造CVRPSDB算例，并將其標(biāo)記為CVRPSDB-15。將算例中各客戶點(diǎn)的需求拆分為1~4個(gè)背包，這樣便構(gòu)造出了CVRPSDB的算例CVRPSDB-15，其客戶需求數(shù)據(jù)如表1所示。
3.2求解結(jié)果
本文使用的編程軟件為Matlab2014a，并且在Lenovo3000，CPU為2.40GHz，內(nèi)存為4GB的AMD筆記本上測(cè)試ATSA。運(yùn)行20次，取最好的結(jié)果。
求解結(jié)果顯示，CVRPSDB-15的總行駛距離為1720.8，有2個(gè)客戶點(diǎn)的需求量被依背包離散拆分配送，具體求解結(jié)果如表2所示。其中，客戶點(diǎn)5的需求量被依背包拆分進(jìn)入線路4與線路10中，對(duì)應(yīng)的離散拆分量分別為(71)與(64+90);而客戶點(diǎn)14的需求量被依背包拆分進(jìn)入線路1與線路6中，對(duì)應(yīng)的離散拆分量分別為(136)與(22+143+161)。
3.3文獻(xiàn)對(duì)比分析
ATSA與文獻(xiàn)算法的對(duì)比結(jié)果見(jiàn)表3。表3中給出的聚類求解算法、改進(jìn)蟻群算法與蜂群優(yōu)化算法都是用來(lái)求解經(jīng)典K-VRPSD類型的，文獻(xiàn)[23]給出的傳統(tǒng)VRP算法是用來(lái)求解需求不拆分VRP類型的。從求得的結(jié)果來(lái)看，本文算法求解的結(jié)果比4種對(duì)比算法求得的結(jié)果都要優(yōu)，ATSA相對(duì)于聚類求解算法、改進(jìn)蟻群算法、蜂群優(yōu)化算法和傳統(tǒng)VRP算法分別改進(jìn)了2.53%、3.38%、2.43%和15.64%，這說(shuō)明ATSA在降低車輛旅行時(shí)間方面具有優(yōu)勢(shì)。
4結(jié)論
帶裝載能力的需求依背包拆分VRP是一種新類型的VRP。從本文研究可知，對(duì)客戶需求依背包進(jìn)行離散拆分配送，既方便了拆分配貨，又有助于縮短旅行時(shí)間，降低行駛成本。本文結(jié)合相關(guān)約束給出了對(duì)應(yīng)的數(shù)學(xué)模型，并設(shè)計(jì)了一種自適應(yīng)禁忌搜索算法(ATSA)進(jìn)行求解。從測(cè)試結(jié)果來(lái)看，所設(shè)計(jì)的ATSA在降低行駛成本方面具有較強(qiáng)的能力。另外，在算法中嵌入自適應(yīng)懲罰機(jī)制，設(shè)計(jì)多鄰域結(jié)構(gòu)體，采用隨機(jī)鄰域挑選方式，使用混合禁忌長(zhǎng)度，增設(shè)禁忌表重新初始化策略等能夠提升算法的爬山能力，增強(qiáng)尋優(yōu)能力。不過(guò)，本文主要對(duì)純送貨類型的CVRPSDB及其自適應(yīng)禁忌搜索算法進(jìn)行了研究，而逆向物流VRP在實(shí)踐中也是急需解決的難題。因此，后續(xù)將會(huì)對(duì)同時(shí)取送貨類型的CVRPSDB進(jìn)行研究，并設(shè)計(jì)出更為高效的求解算法。
