考慮三維裝箱約束的多車(chē)場(chǎng)車(chē)輛路徑問(wèn)題

考慮三維裝箱約束的多車(chē)場(chǎng)車(chē)輛路徑問(wèn)題顏瑞;張群;胡睿【摘要】針對(duì)實(shí)際物流配送問(wèn)題的特點(diǎn),研究三維裝箱約束車(chē)輛路徑問(wèn)題,首次建立考慮多車(chē)場(chǎng)的三維裝箱約束車(chē)輛路徑問(wèn)題模型,并提出求解該問(wèn)題的混合算法.混合算法采用遺傳算法求解車(chē)輛路徑問(wèn)題,采用引導(dǎo)式局部搜索算法求解三維裝箱問(wèn)題.通過(guò)計(jì)算標(biāo)準(zhǔn)算例檢驗(yàn)算法性能,試驗(yàn)結(jié)果表明混合算法能夠在較短時(shí)間內(nèi)得到質(zhì)量較高的近似最優(yōu)解.通過(guò)數(shù)值仿真檢驗(yàn)?zāi)Ｐ偷目山庑?期刊名稱】《管理工程學(xué)報(bào)》年(卷),期】2016(030)001【總頁(yè)數(shù)】9頁(yè)(P108-116)【關(guān)鍵詞】車(chē)輛路徑問(wèn)題;多車(chē)場(chǎng);三維裝箱;遺傳算法【作者】顏瑞;張群;胡?！咀髡邌挝弧勘本┬畔⒖萍即髮W(xué)經(jīng)濟(jì)管理學(xué)院,北京100192;北京科技大學(xué)東凌經(jīng)濟(jì)管理學(xué)院,北京100083;北京科技大學(xué)東凌經(jīng)濟(jì)管理學(xué)院,北京100083【正文語(yǔ)種】中文【中圖分類】O224車(chē)輛路徑問(wèn)題(VehicleRoutingProblem,VRP)和裝箱問(wèn)題(BinPackingProblem，BPP)都是經(jīng)典的組合優(yōu)化問(wèn)題，且都屬于NP-Hard問(wèn)題。在過(guò)去的幾十年里，對(duì)VRP和BPP的研究都取得了非常豐碩的成果，但是關(guān)于這兩個(gè)問(wèn)題的研究是獨(dú)立進(jìn)行的。然而，現(xiàn)實(shí)的物流配送中有很多情況是需要同時(shí)考慮“裝箱和“運(yùn)輸”這兩個(gè)問(wèn)題的，比如家電、家具的送貨上門(mén)服務(wù)。這類配送問(wèn)題通常具有相似的特征，比如運(yùn)輸工具是帶長(zhǎng)方體封閉式車(chē)廂的貨車(chē)，貨物通常裝在長(zhǎng)方體的包裝箱內(nèi)，車(chē)輛需要拼裝運(yùn)送不同體積、不同重量的貨物。對(duì)于這類問(wèn)題，“裝箱”和“運(yùn)輸”這兩方面是不可分割、相互制約的，只有同時(shí)考慮這兩點(diǎn)才能即保證選擇的配送路線成本最低，又保證貨物可以全部合理地裝入車(chē)輛。近幾年，這類問(wèn)題開(kāi)始吸引國(guó)內(nèi)外學(xué)者的關(guān)注，并且已經(jīng)取得了一些成果。Iori于2005年提出了二維裝箱約束限制容量車(chē)輛路徑問(wèn)題(Two-DimensionalLoadingCapacitatedVehicleRoutingProblem，2L-CVRP)的模型，并提出啟發(fā)式算法和精確算法結(jié)合的方法進(jìn)行求解，通過(guò)大量的仿真計(jì)算檢驗(yàn)了問(wèn)題的可解性和算法的可靠性［1］。2L-CVRP模型提出以后，學(xué)者們相繼提出了不同的算法對(duì)該模型進(jìn)行求解，改善了Iori最初的求解結(jié)果，這其中有分支切割法［2］、禁忌搜索算法［3］、文化基因算法［4］、模擬退火算法［5］以及改進(jìn)的禁忌搜索算法［6］。在2006年，Iori與Gendreau、Laporte等人合作提出了三維裝箱約束限制容量車(chē)輛路徑問(wèn)題(Three-DimensionalLoadingCapacitatedVehicleRoutingProblem，3L-CVRP)的模型，并提出禁忌搜索算法進(jìn)行求解，根據(jù)實(shí)際案例設(shè)計(jì)了幾種不同約束下的模型并分別進(jìn)行求解［刀。隨后，Moura和Oliveira針對(duì)BPP和CVRP分別設(shè)計(jì)算法，采用層次方法求解BPP、采用貫序方法引導(dǎo)局部搜索的啟發(fā)式策略求解CVRP［8］。Fuellerer和Doerner等人采用蟻群算法求解3L-CVRP模型，并根據(jù)路徑和裝箱分別設(shè)計(jì)了信息素更新策略［9］。2010年，Iori和Martello對(duì)CVRP和BPP的研究進(jìn)行了系統(tǒng)的總結(jié)，明確了一些基本概念和基本問(wèn)題，包括2L-CVRP、3L-CVRP及帶裝箱約束的裝卸一體旅行商問(wèn)題(TravelingSalesmanProblemswithPickup&DeliveryandLoadingConstraints，TSPPDL)等［10］。3L-CVRP考慮三維空間中的貨物和車(chē)廂，充分體現(xiàn)了實(shí)際物流配送情形，因此本文針對(duì)3L-CVRP進(jìn)行研究。國(guó)內(nèi)關(guān)于CVRP和BPP聯(lián)合問(wèn)題的研究成果相對(duì)較少。馬珊靜和陳峰等人研究了一維裝箱和車(chē)輛路徑的聯(lián)合問(wèn)題，以最小化倉(cāng)儲(chǔ)成本、運(yùn)輸成本和車(chē)輛運(yùn)營(yíng)成本總和為目標(biāo)，提出了三種不同策略的兩階段啟發(fā)式算法進(jìn)行求解［11］。寧愛(ài)兵和熊小華等人研究了物流配送中的三維裝箱問(wèn)題，考慮到三維裝箱和車(chē)輛路徑相結(jié)合的一些基本問(wèn)題，并提出了一種求解三維裝箱問(wèn)題的算法，但是文獻(xiàn)并沒(méi)有把兩個(gè)問(wèn)題聯(lián)合起來(lái)進(jìn)行建模和求解［12］。王征和胡祥培等人針對(duì)易損、易碎物品的運(yùn)輸問(wèn)題進(jìn)行研究，建立了較為完整的2L-CVRP數(shù)學(xué)模型，并提出了求解該模型的一個(gè)Memetic算法，算法中設(shè)計(jì)了一種基于深度優(yōu)先的裝箱問(wèn)題求解策略，文獻(xiàn)采用Iori提出的標(biāo)準(zhǔn)算例進(jìn)行計(jì)算，全面分析了Memetic算法的求解效率、求解性能和魯棒性，試驗(yàn)取得了較為理想的結(jié)果［13］。目前，對(duì)于3L-CVRP的研究均以經(jīng)典VRP模型為基礎(chǔ)，模型中只考慮一個(gè)配送中心的情況，這在理論上和實(shí)踐上存在很多不足。在經(jīng)典VRP模型的基礎(chǔ)之上，已經(jīng)發(fā)展出包括多車(chē)場(chǎng)、帶時(shí)間窗及不確定顧客需求量等諸多因素的VRP模型，而到目前為止3L-CVRP模型尚未建立考慮這些因素的模型，在理論上具有較大的研究空間。現(xiàn)代商業(yè)模式對(duì)物流業(yè)的發(fā)展提出很高要求，最根本的要求是快速將貨物送達(dá)顧客，這需要物流企業(yè)具有較強(qiáng)的快速反應(yīng)能力和系統(tǒng)協(xié)調(diào)能力，而在一個(gè)城市或地區(qū)建立多個(gè)配送中心是實(shí)現(xiàn)這個(gè)目標(biāo)的途徑之一。在現(xiàn)代城市物流配送模式(比如電子商務(wù)網(wǎng)站的配送模式)中，銷(xiāo)售商通常在一個(gè)城市中擁有幾個(gè)配送中心，根據(jù)總配送距離最短的原則從不同的配送中心同時(shí)發(fā)貨，在較短的時(shí)間內(nèi)把貨物送給客戶，從整體上提高配送效率。因此，本文在研究三維裝箱約束車(chē)輛路徑問(wèn)題的基礎(chǔ)之上，考慮多配送中心的情況，建立考慮三維裝箱約束多配送中心車(chē)輛路徑問(wèn)題(Three-DimensionalLoadingMulti-DepotsCapacitatedVehicleRoutingProblem，3L-MDCVRP)的混合數(shù)學(xué)模型。由于3L-MDCVRP模型是兩個(gè)NP-Hard問(wèn)題的結(jié)合問(wèn)題，因此為了在有效時(shí)間內(nèi)得到問(wèn)題的最優(yōu)解，本文提出遺傳算法和引導(dǎo)式局部搜索算法相結(jié)合的混合算法進(jìn)行求解。問(wèn)題描述3L-CVRP可以描述為圖論問(wèn)題。令為一個(gè)無(wú)向完全圖，其中表示頂點(diǎn)集合，表示弧集。集合中共有個(gè)頂點(diǎn)，其中頂點(diǎn)0表示配送中心節(jié)點(diǎn)，頂點(diǎn)（）表示顧客節(jié)點(diǎn)。弧集中的邊表示節(jié)點(diǎn)和節(jié)點(diǎn)之間的線路，每條線路都有一個(gè)非負(fù)的行駛距離（）。配送中心有輛相同型號(hào)的箱式貨車(chē)，每輛貨車(chē)的最大載重量為、最大容積為貨車(chē)車(chē)廂可抽象成為一個(gè)三維長(zhǎng)方體，其中長(zhǎng)為、寬為、高為，則有，即為貨物的可裝載空間。顧客（）需要個(gè)貨物（），貨物都分別裝在長(zhǎng)方體的貨箱內(nèi)，不同的貨物裝入的貨箱規(guī)格也不一樣，設(shè)定包裝貨物的貨箱長(zhǎng)為、寬為、高為。設(shè)貨物的重量為，則個(gè)貨物的總重量為，總體積為。假設(shè)所有貨物的密度是均勻分布的，且不妨設(shè)車(chē)廂和貨物的長(zhǎng)、寬、高在整數(shù)范圍內(nèi)取值。求解3L-CVRP時(shí)需要將模型分為VRP和BBP兩個(gè)子問(wèn)題。圖1給出3L-CVRP模型的一個(gè)示意圖。3L-CVRP模型假設(shè)：1） 確定最多條回路作為車(chē)輛行駛路線，所有回路均從配送中心出發(fā)并返回配送中心，每個(gè)顧客只能在一條回路上，每條回路上的顧客僅由一輛車(chē)服務(wù)；2） 每條線路上顧客的貨物總重量不能超過(guò)車(chē)輛最大載重，貨物總體積不能超過(guò)車(chē)廂最大容積，每輛車(chē)行駛距離不受限制；3） 每條回路上顧客需求的貨物必須全部裝入車(chē)廂，且滿足全部給定的裝箱約束；4） 貨物從車(chē)廂尾部的車(chē)門(mén)進(jìn)出，裝貨過(guò)程從車(chē)廂內(nèi)側(cè)左下角開(kāi)始，假設(shè)裝貨工具可以把貨物擺放到車(chē)廂內(nèi)任意位置；5） 以所有車(chē)輛的行駛路程之和最小為目標(biāo)。在模型假設(shè)中，有一個(gè)很重要的概念——裝箱約束。貨物裝箱除了要滿足車(chē)輛限重和車(chē)廂限容這兩個(gè)基本約束條件之外，還應(yīng)滿足符合實(shí)際操作的一些約束條件，比如貨物不能懸空放置、不能重疊放置以及交通法規(guī)限定的其他要求等。裝箱約束主要包括：1）基本約束：貨物不能懸空放置、不能重疊放置，貨物總重和總裝載空間不能超過(guò)車(chē)輛載重和車(chē)廂容積。2）方向性約束：貨物邊緣必須與相應(yīng)的車(chē)廂邊緣平行，每個(gè)貨物都是頂部朝上放置，且只能在水平面上做90°的旋轉(zhuǎn)，不能以其它角度或者在垂直面上旋轉(zhuǎn)，可參考圖2。3）貨物穩(wěn)定性約束：當(dāng)貨物被放置在其他貨物之上時(shí)，它與底部貨物之間不能出現(xiàn)空隙，且兩個(gè)貨物直接接觸面積不能小于貨物底面積的（為給定常量，）倍。例如，在圖2.b中，貨物放置在貨物之上，則和的接觸面積應(yīng)該滿足，這樣才能保證穩(wěn)定地放置于之上。顯然，當(dāng)直接放在車(chē)廂底面上的時(shí)候，最小接觸面積的約束始終是滿足的。4） LIFO（Last-in-First-out）約束：為了縮短裝卸貨時(shí)間，貨物擺放位置需要滿足連續(xù)裝卸貨的要求，即先進(jìn)的貨物后出，先出的貨物后進(jìn)。具體描述為，當(dāng)車(chē)輛服務(wù)顧客的時(shí)候，可以從車(chē)尾門(mén)方向連續(xù)的卸載顧客的所有貨物（），且不用挪動(dòng)其他顧客的貨物。根據(jù)圖1的配送線路，線路1先經(jīng)過(guò)顧客1再經(jīng)過(guò)顧客2，那么在圖2.a的裝箱圖中，就不能出現(xiàn)（）放置于（）上方或者前方的情況。5） 易碎品約束：貨物可以分為易碎品和非易碎品。易碎品可以放置在易碎品和非易碎品之上，而非易碎品只能放置在非易碎品之上，即不能出現(xiàn)非易碎品放置在易碎品之上的情況。如圖2.a所示，易碎品可以放在易碎品之上。本文建立的3L-MDCVRP在模型假設(shè)上有如下調(diào)整：一、有多個(gè)配送中心，每個(gè)配送中心均存儲(chǔ)和供應(yīng)足夠多的產(chǎn)品；二、每個(gè)配送中心均有相同數(shù)量相同型號(hào)的車(chē)輛，車(chē)輛從配送中心出發(fā)完成任務(wù)之后返回原配送中心。其他假設(shè)和裝箱約束均與3L-CVRP—致。數(shù)學(xué)模型本文建立的3L-MDCVRP模型分為車(chē)輛路徑模型和三維裝箱模型兩個(gè)部分。在建立模型之前，先給出模型中各個(gè)變量的符號(hào)和意義，如表1所示。其中車(chē)廂容積可表示為，貨物體積可表示為。顧客需求貨物的總重量為，貨物總體積為。模型中的決策變量為：其中，車(chē)輛表示配送中心的第輛車(chē)。建立多配送中心車(chē)輛路徑模型如下：模型解釋如下：目標(biāo)函數(shù)（1）表示最小化車(chē)輛行駛路程；式（2）表示所有顧客只被訪問(wèn)一次；式（3）和式（4）表示車(chē)輛從某個(gè)配送中心出發(fā)，服務(wù)完所有顧客之后返回原配送中心；式（5）表示車(chē)輛進(jìn)入某節(jié)點(diǎn)，也必須從該節(jié)點(diǎn)離開(kāi)；式（6）表示每輛車(chē)裝載貨物的重量之和不超過(guò)車(chē)輛限制載重；式（7）表示每輛車(chē)裝載貨物的體積之和不超過(guò)車(chē)輛限制容積；式（8）綁定了三維裝箱變量和車(chē)輛路徑變量；式（9）為支路消除約束，保證任何路線中只包含一個(gè)配送中心。在建立三維裝箱模型之前，先建立一個(gè)笛卡爾坐標(biāo)系。坐標(biāo)系的坐標(biāo)軸分別對(duì)應(yīng)于車(chē)廂的長(zhǎng)、寬和高，坐標(biāo)系的原點(diǎn)位于車(chē)廂內(nèi)側(cè)左下角，如圖3所示。貨物底部左后方的位置（離原點(diǎn)O最近的頂點(diǎn)）用坐標(biāo)表示，則有：由于貨物大小不同，因此即使貨物總體積小于車(chē)廂容積，也有可能無(wú)法將所有貨物都裝入車(chē)廂?？紤]到這一點(diǎn)，本文以最大化裝入車(chē)廂內(nèi)貨物數(shù)為目標(biāo)建立三維裝箱模型，則可行解的目標(biāo)函數(shù)值等于總貨物數(shù)。三維裝箱模型如下：其中，表示配送中心的車(chē)輛裝載的貨物數(shù)，表示上方貨物底部左后方的可能位置坐標(biāo)，表示貨物頂部任意一點(diǎn)所能承受的最大壓強(qiáng)。VRP模型中表示顧客，3LP模型中表示貨物。式（10）為目標(biāo)函數(shù)，最大化裝入車(chē)輛的總貨物數(shù)；式（11）保證了所有貨物都必須有支撐區(qū)域（不可懸空放置），且貨物不能堆疊；式（12）用以區(qū)分易碎品和非易碎品，取值為0表示貨物為易碎品，取值為1表示非易碎品，非易碎品不可放在易碎品之上；式（13）給出了決策變量；式（14）和式（15）計(jì)算貨物的長(zhǎng)和寬；式（16）給出每輛車(chē)裝載貨物總數(shù)。模型中的變量和標(biāo)識(shí)參考文獻(xiàn)［14］和文獻(xiàn)［15］。對(duì)于3L-MDCVRP這樣的NP-Hard問(wèn)題，如何在較短的時(shí)間內(nèi)給出有效的解是非常重要的。處理獨(dú)立的車(chē)輛路徑問(wèn)題和三維裝箱問(wèn)題的時(shí)候，通常采用啟發(fā)式算法進(jìn)行求解，但是兩個(gè)問(wèn)題結(jié)合起來(lái)之后，現(xiàn)有的啟發(fā)式算法已經(jīng)無(wú)法求解。本文設(shè)計(jì)3L-MDCVRP求解算法的基本思路為：1）先求出一個(gè)最優(yōu)配送線路，當(dāng)有了一個(gè)配送線路之后，每條線路上的顧客數(shù)及顧客需求貨物量就會(huì)確定下來(lái)；2）然后再對(duì)每輛車(chē)單獨(dú)設(shè)計(jì)裝箱方案，確保全部貨物裝箱并滿足所有裝箱約束；3）如果所有車(chē)輛都能完成裝箱，則最優(yōu)配送方案產(chǎn)生，否則，重新計(jì)算最優(yōu)配送線路并安排裝箱，如此循環(huán)。在此求解思路之上，本文提出一種改進(jìn)的遺傳算法和引導(dǎo)式局部搜索算法結(jié)合的混合算法進(jìn)行求解，改進(jìn)的遺傳算法（GeneticAlgorithm，GA）求解車(chē)輛路徑問(wèn)題，引導(dǎo)式局部搜索算法（GuidedLocalSearch，GLS）求解裝箱問(wèn)題。在2.1節(jié)中提出改進(jìn)遺傳算法，在2.2節(jié)中給出引導(dǎo)式局部搜索啟發(fā)式算法，在2.3節(jié)中提出完整的混合啟發(fā)式算法。2.1遺傳算法遺傳算法是一種有效的全局搜索算法，由美國(guó)Michigan大學(xué)的J.Holland教授在1975年提出。遺傳算法是一種并行搜索算法，模擬自然進(jìn)化中的自然選擇和優(yōu)勝劣汰極值，主要包括染色體種群、選擇算子、交叉算子和變異算子等部分。本節(jié)給出遺傳算法各部分的策略，并根據(jù)3L-MDCVRP的特點(diǎn)提出一些改進(jìn)策略。1）編碼規(guī)則。根據(jù)3L-MDCVRP模型中存在多個(gè)車(chē)場(chǎng)的特點(diǎn)，本文提出兩段式編碼方式，把染色體分為每個(gè)配送中心每輛車(chē)服務(wù)顧客數(shù)和車(chē)輛服務(wù)顧客順序。假設(shè)有2個(gè)配送中心、10個(gè)顧客、每個(gè)配送中心都有2輛車(chē)，則可給出一個(gè)染色體編碼方式，如圖4所示。圖4中給出的染色體可表示如下配送方案：配送中心1的第一輛車(chē)按順序服務(wù)顧客6和8，配送中心1的第二輛車(chē)按順序服務(wù)顧客2、10和5；配送中心2的第一輛車(chē)按順序服務(wù)顧客9、1和3，配送中心2的第二輛車(chē)按順序服務(wù)顧客7和42）適應(yīng)度函數(shù)。一般文獻(xiàn)中采用目標(biāo)函數(shù)的倒數(shù)作為染色體適應(yīng)度，但是這樣計(jì)算出的適應(yīng)度值會(huì)比較小，且處理不同問(wèn)題時(shí)取值范圍相差很大，因此泛化能力較差。本文提出如下公式作為適應(yīng)度函數(shù)：其中表示所有節(jié)點(diǎn)之間行駛距離總和，每個(gè)問(wèn)題只須計(jì)算一次。處理不同問(wèn)題時(shí)，式（17）可以維持適應(yīng)度值在一個(gè)比較穩(wěn)定的范圍內(nèi)。3）選擇算子。選擇算子提供了遺傳進(jìn)化的驅(qū)動(dòng)力，驅(qū)動(dòng)力太大則遺傳搜索會(huì)過(guò)早終止，驅(qū)動(dòng)力太小則進(jìn)化過(guò)程會(huì)非常緩慢。本文采用Holland提出的輪盤(pán)賭選擇策略，其基本原理是根據(jù)每個(gè)染色體適應(yīng)度的比例來(lái)確定該個(gè)體的選擇概率或生存概率［16］。4）交叉算子。交叉操作是交換兩個(gè)父代染色體部分基因的遺傳操作。根據(jù)交叉概率選擇進(jìn)入配對(duì)池的父代個(gè)體，把配對(duì)染色體的部分基因加以替換重組，產(chǎn)生子代個(gè)體。根據(jù)染色體編碼由兩部分組成的特點(diǎn)，本文提出一種混合交叉算子，具體操作方式為：第一部分采用均勻交叉；第二部分采用順序交叉。均勻交叉算子：首先隨機(jī)產(chǎn)生一個(gè)與染色體第一部分基因串等長(zhǎng)的二進(jìn)制串，0表示不交換，1表示交換，根據(jù)二進(jìn)制串判斷是否交換父代個(gè)體對(duì)應(yīng)位置上的基因。由于染色體中沒(méi)有表示配送中心的基因，因此需要采用新的順序交叉算子。順序交叉算子：在父代染色體的第一部分基因串中隨機(jī)選擇一個(gè)基因，該基因?qū)?yīng)的數(shù)字作為第二部分基因串的交叉段，然后把交叉段內(nèi)的基因互換，把換出基因放在換入基因原來(lái)的位置上，當(dāng)父代基因?qū)?yīng)的數(shù)字不相同時(shí)，第二個(gè)父代向后移動(dòng)至數(shù)字相同位置，如找不到相同數(shù)字則取消本次交叉操作。如圖5所示，以A和B兩個(gè)父代個(gè)體為例進(jìn)行混合交叉操作，X為二進(jìn)制串，設(shè)產(chǎn)生的子代個(gè)體為C和D。5） 變異算子。變異操作依據(jù)變異概率對(duì)每代種群中的染色體進(jìn)行基因突變，常用的基因突變方式有均勻、交換、逆轉(zhuǎn)和位移等。根據(jù)兩段式編碼方式的特點(diǎn)，本文提出一種混合變異算子，第一部分基因使用均勻變異算子，第二部分基因使用位移變異算子，具體過(guò)程如圖6所示。6） 非可行解調(diào)整。經(jīng)過(guò)交叉操作和變異操作，染色體對(duì)應(yīng)的解可能變成非可行解，因此需要對(duì)其進(jìn)行調(diào)整。顧客數(shù)是固定的，因此染色體第一部分基因串上的數(shù)字之和必須等于顧客數(shù)，當(dāng)基因值之和小于顧客數(shù)時(shí)，隨機(jī)選擇一個(gè)基因值加1，當(dāng)基因值之和大于顧客數(shù)時(shí)，隨機(jī)選擇一個(gè)基因值減1，重復(fù)操作至基因值之和與顧客數(shù)相等為止。在生成初始種群及進(jìn)行遺傳操作的時(shí)候，可能會(huì)有一些染色體不符合模型中的一個(gè)或多個(gè)約束條件。顯然對(duì)于本文的染色體編碼方式，所有染色體都自然滿足約束（2）、（3）、（8）和（9），因此，調(diào)整非可行解的時(shí)候只須檢查約束（4）、（5）、（6）和（7）。采用的約束控制策略是根據(jù)染色體對(duì)約束的違反程度降低其適應(yīng)度值。6）記憶庫(kù)。為了減少3L-CVRP的求解時(shí)間，本文在遺傳算法中加入記憶庫(kù)機(jī)制，具體作用在后面給出，這里只給出記憶庫(kù)的形成原理。設(shè)定記憶庫(kù)的最大規(guī)模為MemSize，把每代種群中的最優(yōu)個(gè)體保存到記憶庫(kù)中，當(dāng)最優(yōu)個(gè)體數(shù)超過(guò)記憶庫(kù)規(guī)模時(shí)，去掉記憶庫(kù)中適應(yīng)度最小的個(gè)體。當(dāng)遺傳算法達(dá)到最大迭代次數(shù)之后，把當(dāng)前種群全部加入記憶庫(kù)中，按適應(yīng)度值從大到小排列所有個(gè)體，刪除適應(yīng)度較小的個(gè)體，維持記憶庫(kù)規(guī)模為MemSize。引導(dǎo)式局部搜索本節(jié)討論如何把貨物裝入車(chē)廂內(nèi)，且滿足第1章中的裝載約束。一般裝箱問(wèn)題以裝載貨物數(shù)最大為目標(biāo)，而3L-MDCVRP的裝箱問(wèn)題中每輛車(chē)裝載的貨物數(shù)是固定的，因此其解空間僅是一般裝箱問(wèn)題解空間的一個(gè)子集。針對(duì)這樣的特點(diǎn)，設(shè)計(jì)算法的時(shí)候只須要在局部進(jìn)行搜索即可，通過(guò)一系列的引導(dǎo)策略尋找問(wèn)題的局部最優(yōu)解。3L-MDCVRP的裝箱過(guò)程包括確定貨物的裝載順序和尋找可行的裝貨位置兩個(gè)子問(wèn)題，下面分別給出這兩個(gè)子問(wèn)題的求解策略：1） 初始貨物裝載順序。給定車(chē)輛路線方案，令為由車(chē)輛服務(wù)的顧客所需求的第個(gè)貨物，其中，，。當(dāng)每條線路上車(chē)輛服務(wù)顧客的數(shù)量和順序確定之后，把線路上的貨物按顧客的相反順序進(jìn)行排列，同一顧客的貨物非易碎品排在易碎品之前。按照這個(gè)順序排列裝貨，可以保證先到顧客的貨物后裝、后到顧客的貨物先裝（LIFO規(guī)則），還便于在非易碎品的上面放置其他貨物。例如，圖2-a給出了一輛車(chē)的裝載方案，貨物排列順序?yàn)?，貨物和的上面放置了其他貨物?） 最終貨物裝載順序。本文采用（）規(guī)則中的一個(gè)規(guī)則對(duì)初始貨物順序進(jìn)行調(diào)整，確定最終貨物裝載順序。對(duì)于初始裝貨序列中相同級(jí)別的貨物（屬于相同顧客且同為非易碎品或同為易碎品的貨物），、和分別表示把貨物按體積（）、底面積（）和高度的降序進(jìn)行排列，其意義在于：規(guī)則優(yōu)先裝載體積較大的貨物，以占據(jù)較大的可行裝貨空間；規(guī)則優(yōu)先裝載底面積較大的貨物，為后續(xù)裝載的貨物提供較大的支撐區(qū)域；規(guī)則優(yōu)先裝載較高的貨物，因?yàn)檩^小的貨物更容易放在其他貨物之上。圖2-a中的裝載順序是按照規(guī)則排列的。3） 可行裝貨位置順序。初始可行裝貨位置均在（0,0,0）點(diǎn)上，如圖7-a所示。裝入一個(gè)貨物之后，可行裝貨位置更新，產(chǎn)生A1、A2和A3三個(gè)可行裝貨位置，如圖7-b所示。對(duì)于裝貨序列中的下一個(gè)待裝貨物，需要給出一個(gè)可行裝貨位置的順序，然后逐個(gè)掃描這些位置，直至找到一個(gè)滿足所有裝載約束的可行位置，每個(gè)貨物需要在兩個(gè)方向上進(jìn)行掃描（水平方向可旋轉(zhuǎn)90度）。本文采用引導(dǎo)式排序方法給出可行裝貨位置順序，引導(dǎo)式排序方法包括“Back-Left-Low”、“Left-Back-Low”、“Max-Touching-Area-Y”、“Max-Touching-Area-No-Walls-Y”、“Max-Touching-Area-X”及“Max-Touching-No-Walls-X”等六種［17］，依次選擇六種方法中的一個(gè)，直至找到可行裝載方案。六種規(guī)則的具體操作方法可參考文獻(xiàn)［17］。重復(fù)算法尋找可行解。算法開(kāi)始先選擇規(guī)則安排貨物序列，然后首先使用“Back-Left-Low”方法尋找可行位置。如果有貨物無(wú)法裝入車(chē)廂，則依次選擇后面的五個(gè)排序方法尋找可行位置。如果全部六種排序方法都嘗試之后還有貨物無(wú)法裝入車(chē)廂，則清空車(chē)廂并選擇規(guī)則排列貨物順序，最后選擇規(guī)則。如果三個(gè)規(guī)則都嘗試之后還沒(méi)有找到可行解，那么可以認(rèn)為當(dāng)前的車(chē)輛路徑方案無(wú)法找到相應(yīng)的貨物裝箱方案。2.3混合啟發(fā)式算法本文把改進(jìn)遺傳算法和裝箱啟發(fā)式算法結(jié)合起來(lái)，構(gòu)造求解3L-MDCVRP的引導(dǎo)式局部搜索遺傳算法(GuidedLocalSearchGeneticAlgorithm，GLSGA)。GLSGA的基本思路為：通過(guò)改進(jìn)遺傳算法得出VRP的近似最優(yōu)解，近似最優(yōu)解保存在記憶庫(kù)中；把記憶庫(kù)中的個(gè)體按適應(yīng)度值從大到小排列，選擇第一個(gè)解作為當(dāng)前車(chē)輛路線方案，然后調(diào)用裝箱問(wèn)題的啟發(fā)式算法；如果找到可行裝箱方案，則返回最優(yōu)解，否則，選擇記憶庫(kù)中的下一個(gè)解作為車(chē)輛路線方案；如果記憶庫(kù)中所有車(chē)輛路線方案均找不到可行解，則返回遺傳算法重新求解VRP；重復(fù)算法直至找到可行解，或達(dá)到最大迭代次數(shù)。GLSGA的具體步驟如下：Step1.GLSGA算法初始化：設(shè)定最大循環(huán)次數(shù)，令；Step2.遺傳算法參數(shù)初始化：設(shè)定遺傳算法的種群規(guī)模PopSize和記憶庫(kù)規(guī)模MemSize，設(shè)定交叉概率和變異概率，確定最大迭代次數(shù)M，令；Step3.初始種群生成：對(duì)染色體進(jìn)行編碼，用隨機(jī)方法產(chǎn)生初始種群；Step4?記憶庫(kù)更新：計(jì)算染色體適應(yīng)度，把當(dāng)前種群中的最優(yōu)個(gè)體保存進(jìn)記憶庫(kù)，若記憶庫(kù)規(guī)模超過(guò)MemSize，則去掉適應(yīng)度值較小的個(gè)體；Step5.遺傳操作：對(duì)當(dāng)前種群進(jìn)行選擇、交叉和變異等遺傳操作；Step6.種群更新：更新當(dāng)前種群，當(dāng)時(shí)，令，返回Step4;當(dāng)時(shí)，轉(zhuǎn)Step7；Step7.近似最優(yōu)解集生成：遺傳算法終止，把當(dāng)前種群全部加入記憶庫(kù)中，并按適應(yīng)度值排列染色體，保留適應(yīng)度值最大的MemSize個(gè)染色體形成近似最優(yōu)解集；Step8.裝箱啟發(fā)式算法參數(shù)初始化：令，，；Step9?車(chē)輛路線方案產(chǎn)生：選擇近似最優(yōu)解集中的第個(gè)解作為當(dāng)前車(chē)輛路線方案；Step10初始裝貨序列：按照車(chē)輛服務(wù)顧客順序的相反順序排列貨物，相同顧客的貨物按照非易碎品在前、易碎品在后的順序排列；Step11.最終裝貨序列：按照規(guī)則調(diào)整裝貨順序，確定最終裝貨序列；Step12.可行裝貨位置：按照第個(gè)啟發(fā)式方法掃描所有可能裝貨位置，按裝貨序列給每個(gè)貨物都找到可行裝貨位置；Step13.可行裝貨位置循環(huán)：若所有貨物均找到可行裝貨位置，算法終止，輸出當(dāng)前最優(yōu)解；若有一個(gè)或多個(gè)貨物沒(méi)找到可行裝貨位置，且，令，返回Step12；若，轉(zhuǎn)Step14；Step14?裝貨序列循環(huán)：若，令，返回Step11;若，轉(zhuǎn)Step15；Step15.近似最優(yōu)解集循環(huán)：若，令，返回Step9;若，且，令，返回Step3;若，轉(zhuǎn)Step16；Step16.總循環(huán)：若，令，轉(zhuǎn)Step2；若，算法終止，找不到可行解。GLSGA算法流程如圖5所示。數(shù)值試驗(yàn)平臺(tái)為：Matlab7.1,計(jì)算機(jī)CPU為英特爾酷睿2、2.67GHz,2GB內(nèi)存,32位windows7操作系統(tǒng)。由于標(biāo)準(zhǔn)算例庫(kù)中的問(wèn)題均為單配送中心問(wèn)題，因此本人設(shè)計(jì)兩個(gè)數(shù)值模擬試驗(yàn)：第一個(gè)試驗(yàn)針對(duì)標(biāo)準(zhǔn)算例進(jìn)行計(jì)算，檢驗(yàn)GLSGA算法的有效性；第二個(gè)試驗(yàn)針對(duì)隨機(jī)數(shù)據(jù)進(jìn)行仿真，檢驗(yàn)?zāi)Ｐ偷目山庑浴?.1標(biāo)準(zhǔn)算例庫(kù)試驗(yàn)?zāi)壳把芯?L-CVRP問(wèn)題的文獻(xiàn)較少，作者能夠搜集到的全部相關(guān)文獻(xiàn)均已附在參考文獻(xiàn)中。已發(fā)表的文獻(xiàn)均直接采用文獻(xiàn)［7］的模型，模型同時(shí)處理車(chē)輛路徑問(wèn)題和裝箱問(wèn)題，并提出一些不同的算法進(jìn)行求解，同時(shí)以文獻(xiàn)［7］給出的標(biāo)準(zhǔn)算例庫(kù)進(jìn)行數(shù)值試驗(yàn)。目前，該算例庫(kù)是僅有的3L-CVRP標(biāo)準(zhǔn)算例庫(kù)，針對(duì)文獻(xiàn)［7］的標(biāo)準(zhǔn)算例進(jìn)行數(shù)值試驗(yàn)，以檢驗(yàn)本文所提出新算法的性能。算例庫(kù)中總計(jì)包括27個(gè)3L-CVRP標(biāo)準(zhǔn)算例。算例包含的信息有：配送中心坐標(biāo)，顧客數(shù)及顧客坐標(biāo)；每個(gè)顧客需求的貨物及其需求貨物的重量；每個(gè)貨物的長(zhǎng)、寬、高，易碎品與非易碎品標(biāo)識(shí)；配送中心擁有車(chē)輛數(shù)，車(chē)輛最大載重，車(chē)廂的長(zhǎng)、寬、高。貨物堆疊的時(shí)候，支撐面積與上層貨物底面積的比例最小值為=0.75。為了在檢驗(yàn)算法性能的時(shí)候避開(kāi)模型的影響，該試驗(yàn)直接采用文獻(xiàn)［7］的模型，使用本文設(shè)計(jì)的GLSGA算法進(jìn)行求解。表1給出滿足所有裝箱約束的計(jì)算結(jié)果，以及與其它文獻(xiàn)計(jì)算結(jié)果的比較。從計(jì)算結(jié)果上看，GLSGA算法的計(jì)算結(jié)果較TS算法和GTS算法有明顯的改善，27個(gè)標(biāo)準(zhǔn)算例的車(chē)輛行駛路程幾乎全部減少。與TS算法相比平均路程減少6.38%、最大減幅為14.95%，與GTS算法相比平均路程減少2.16%、最大減幅6.96%。從計(jì)算時(shí)間上看，GLSGA算法較TS算法和GTS算法有大幅度的降低，與TS算法相比平均時(shí)間減少57.06%、最大減幅為82.93%，與GTS算法相比平均時(shí)間減少40.89%、最大減幅為69.79%。通過(guò)與已有文獻(xiàn)的計(jì)算結(jié)果相比，表明GLSGA算法具有良好的計(jì)算性能和較高的計(jì)算效率。由于已有文獻(xiàn)的模型均采用Iori提出的基本3L-CVRP模型，而該試驗(yàn)直接在模型上運(yùn)行GLSGA算法，因此可以判斷本文得到的計(jì)算結(jié)果是由GLSGA算法產(chǎn)生的。隨機(jī)數(shù)據(jù)仿真試驗(yàn)在驗(yàn)證了GLSGA算法的有效性之后，可以用該算法求解3L-MDCVRP模型。首先，給出一個(gè)有2個(gè)配送中心、20個(gè)顧客、每個(gè)配送中心有4輛車(chē)（車(chē)輛限重500、限容1000）的3L-MDCVRP實(shí)例，表2給出隨機(jī)產(chǎn)生的配送中心和顧客節(jié)點(diǎn)坐標(biāo)，表3、表4給出每個(gè)顧客需求的貨物規(guī)格。計(jì)算得出5條線路，總有效路程為4.2435，所有車(chē)輛均滿足裝箱約束，最優(yōu)配送路徑如圖9所示。R1二｛Depot1-13-11-12-10-Depot1｝，總路程為1.0376，載貨總重為302，載貨總體積為795；R2=｛Depot1-3-6-17-5-Depot1｝，總路程為0.6697，載貨總重為342，載貨總體積為561；R3=｛Depot1-15-9-18-20-Depot1｝，總路程為0.5773，載貨總重為400，載貨總體積為508；R4二｛Depot2-7-8-14-19-Depot2｝，總路程為0.9359，載貨總重為391，載貨總體積為855；R5=｛Depot2-16-2-1-4-Depot2｝，總路程為1.023，載貨總重為426，載貨總體積為706。本文研究多車(chē)場(chǎng)車(chē)輛路徑和三維裝箱相結(jié)合的組合優(yōu)化問(wèn)題，在3L-CVRP模型中首次考慮多車(chē)場(chǎng)的情況，建立3L-MDCVRP模型，并提出遺傳算法和引導(dǎo)式局部搜索算法結(jié)合的GLSGA算法進(jìn)行求解，針對(duì)3L-MDCVRP問(wèn)題的特點(diǎn)提出遺傳算法的改進(jìn)策略。本文設(shè)計(jì)了標(biāo)準(zhǔn)算例庫(kù)和隨機(jī)數(shù)據(jù)兩個(gè)數(shù)值試驗(yàn)，兩個(gè)試驗(yàn)均取得了非常理想的結(jié)果。首先采用27個(gè)標(biāo)準(zhǔn)算例檢驗(yàn)GLSGA算法的性能和效率，試驗(yàn)結(jié)果表明GLSGA算法能夠很好的處理3L-CVRP這類問(wèn)題。然后根據(jù)3L-MDCVRP模型的要求隨機(jī)生成仿真數(shù)據(jù)進(jìn)行測(cè)試，試驗(yàn)結(jié)果表明3L-MDCVRP模型可以用GLSGA算法進(jìn)行求解。3L-MDCVRP建立了考慮多車(chē)場(chǎng)和三維裝箱的物流配送模型，極大地滿足了實(shí)際物流配送的要求。下一步還可以考慮加入時(shí)間窗、多車(chē)型等更多因素的模型，并根據(jù)實(shí)際情況設(shè)計(jì)不同的目標(biāo)函數(shù)建立模型，從理論上進(jìn)一步完善3L-CVRP模型體系。IoriM.Meta-heuristicalgorithmforcombinatorialoptimizationproblems[J].4OR:AQuarterlyJournalofOperationsResearch,2005,3(2):163-166.IoriM,Salazar-GonzalezJJ,VigoD.Anexactapproachforthevehicleroutingproblemwithtwo-dimensionalloadingconstraints[J].TransportationScience,2007,41(2):253-264.GendreauM,IoriM,LaporteG,etal.Atabusearchheuristicforthevehicleroutingproblemwithtwo-dimensionalloadingconstraints[J].Networks,2008,51(1):4-18.KhebbacheS,PrinsC,YalaouiA,etal.Memeticalgorithmfortwodimensionalloadingcapacitatedvehicleroutingproblemwithtimewindows[C].InternationalConferenceonComputersandIndustrialEngineering,2009,1(3):1110-1113.LeungS,ZhengJ,ZhangD,etal.Simulatedannealingforthevehicleroutingproblemwithtwo-dimensionalloadingconstraints[J].FlexibleServicesandManufacturingJournal,2010:1-22.LeungSCH,ZhouX,ZhangD,etal.Extendedguidedtabusearchandanewpackingalgorithmforthetwo-algorithmloadingvehicleroutingproblem[J].Computers&OperationsResearch,2011,38(1):205-215.GendreauM,IoriM,LaporteG,etal.Atabusearchalgorithmforaroutingandcontainerloadingproblem[J].TransportationScience,2006,40(3):342-350.MouraA,OliveiraJ.Anintegratedapproachtothevehicleroutingandcontainerloadingproblems[J].ORSpectrum,2009,31(4):775-800.FuellererG,DoernerKF,HartlRF,etal.Metaheuristicsforvehicleroutingproblemswiththree-dimensionalloadingconstraints[J].EuropeanJournalofOperationalResearch,2010,201(3):751-759.IoriM,MartelloS.Routingproblemswithloadingconstraints[J].TOP,2010,18(1):4-27.馬珊靜，陳峰，宋德朝，etal.越庫(kù)配送物流系統(tǒng)車(chē)輛調(diào)度算法的研究[J].現(xiàn)代制造工程，2009(1)：12-15，127.寧愛(ài)兵，熊小華，馬良.城市物流配送中的三維裝箱算法[J].計(jì)算機(jī)工程與應(yīng)用，2009，45(9)：207-208，211.王征，胡祥培，王旭坪.帶二維裝箱約束的物流配送車(chē)輛路徑問(wèn)題[J].系統(tǒng)工程理論與實(shí)踐，2011，31(12)：2328-2341.RuanQF,ZhangZQ,MiaoLX,etal.Ahybridapproachforthevehicleroutingproblemwiththree-dimensionalloadingconstraints[J].Computers&OperationsResearch,2011,38(11):1-11.JunqueiraL,MorabitoR,YamashitaDS.Three-dimensionalcontainerloadingmodeswithcargostabilityandloadbearingconstraints[J].Computers&OperationsResearch,2012,39(1):74-85.HollandJ.AdaptationinNaturalandArtificialSystem[M].Cambridge:MITPress,1992.TarantilisCD,ZachariadisEE,KiranoudisCT.AHybridMetaheuristicAlgorithmfortheIntegratedVehicleRoutingandThree-DimensionalContainer-LoadingProblem[C].TransactionsonIntelligentTransportationSystems,10(2):255-271.Thispaperaddressedanimportantproblemcombiningthree-dimensionalloadingandmulti-depotsvehicleroutingproblems.Abrandnewsolutionhasbeenproposed.Thenewalgorithmwasacombinationoftwointelligentalgorithmsanditpassedthetestwithgoodperformance.Boththecapacityvehicleroutingproblemandthree-dimensionalproblemareNP-hardproblems.Thus,thecombinatorialproblem