考慮三維裝箱約束的多車場車輛路徑問題

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