汪洋廣, 陳 振

(中國(guó)科學(xué)技術(shù)大學(xué) 管理學(xué)院, 合肥 230026)

1 引言

在物流運(yùn)輸系統(tǒng)中, 當(dāng)需要為車隊(duì)中的車輛規(guī)劃最優(yōu)行駛路線和安排相應(yīng)的貨物裝載方案時(shí), 就會(huì)涉及到車輛路徑問(wèn)題(VRP)和裝箱問(wèn)題(BPP)的求解.這兩個(gè)優(yōu)化問(wèn)題均屬于NP難問(wèn)題, 雖然文獻(xiàn)中已存在了大量的論文對(duì)兩者進(jìn)行了研究[1], 但對(duì)兩者的組合問(wèn)題進(jìn)行研究的論文仍然較少.組合后的新問(wèn)題需要同時(shí)進(jìn)行車輛路徑的規(guī)劃和貨物的裝載方案的設(shè)計(jì), 這將無(wú)疑增加了求解的復(fù)雜性.

VRP問(wèn)題中最具代表性的是帶容量限制的車輛路徑問(wèn)題(CVRP)[2].CVRP根據(jù)一組客戶提出的配送需求為車隊(duì)設(shè)計(jì)一個(gè)最優(yōu)路線集合, 使總的運(yùn)輸成本最小.CVRP的一個(gè)常見(jiàn)擴(kuò)展是帶回程取貨約束的車輛路線問(wèn)題(VRPB)[3,4], 它包括兩種類型的客戶: 待送貨客戶, 本文稱之為配送客戶; 待取貨客戶, 本文稱之為回程客戶.VRPB與CVRP不同之處在于它將送貨和取貨過(guò)程結(jié)合起來(lái), 從而顯著降低了車輛在返程時(shí)的空載率, 進(jìn)而降低了運(yùn)輸成本.

在相關(guān)文獻(xiàn)中, Iori等人[5]首次考慮了CVRP和二維裝箱問(wèn)題的組合, 提出了2L-CVRP問(wèn)題, 并給出了一般性的求解算法.在2L-CVRP問(wèn)題中, 每個(gè)貨物形狀被假設(shè)為一個(gè)長(zhǎng)方體, 并且由于貨物的易碎性特征或?qū)Χ询B的穩(wěn)定性的要求而不允許貨物的堆疊擺放.在相關(guān)文獻(xiàn)中, 該問(wèn)題進(jìn)一步衍生出了4個(gè)變體[6,7]: 根據(jù)在裝載時(shí)是否允許貨物旋轉(zhuǎn)和是否有先后次序可將原問(wèn)題細(xì)分為4種具體類型的子問(wèn)題, 即有序定向裝載、有序旋轉(zhuǎn)裝載、無(wú)序定向裝載和無(wú)序旋轉(zhuǎn)裝載.

在相關(guān)文獻(xiàn)中, 據(jù)我們所知只有Malapert等人和Dominguez等人研究過(guò)此類問(wèn)題[6,8].Malapert等人[8]考慮了2L-VRPB的有序定向裝載版本, 并基于調(diào)度方法提出了一個(gè)多約束規(guī)劃模型, 但他們沒(méi)有提出解決該問(wèn)題的具體算法.Dominguez等人[6]同時(shí)考慮了該問(wèn)題的有序旋轉(zhuǎn)裝載和有序定向裝載, 并進(jìn)一步提出了一種基于有偏隨機(jī)化的鄰域搜索元啟發(fā)式算法, 該算法通過(guò)對(duì)CWS[9]、Best Fit[10]和MTP[11]算法進(jìn)行有偏隨機(jī)化進(jìn)而成功得到了問(wèn)題的高質(zhì)量的解.

在本文中, 我們具體研究2L-VRPB中的兩種新變體, 即無(wú)序定向裝載和無(wú)序旋轉(zhuǎn)裝載, 這兩種變體的應(yīng)用實(shí)例可以在設(shè)備維修、家具以及工業(yè)機(jī)械的運(yùn)輸中找到[6,12].為此, 本文提出了一種新的混合模因算法(Hybrid Memetic Algorithm, HMA), 通過(guò)在搜索過(guò)程中維持可行種群和不可行種群的迭代和更新, 使得當(dāng)前最好解不斷逼近全局最優(yōu)解.

本文在相關(guān)文獻(xiàn)的基礎(chǔ)上, 提出了一個(gè)具有實(shí)際應(yīng)用價(jià)值的帶二維裝箱約束的車輛路徑問(wèn)題.考慮到新問(wèn)題所帶來(lái)的求解復(fù)雜性的提升, 我們基于組合化策略、全局優(yōu)化和有偏隨機(jī)化策略設(shè)計(jì)了一個(gè)增強(qiáng)型裝箱求解算法, 并將其整合到一個(gè)模因算法的搜索框架中.最后, 基于VRPB和2L-VRPB問(wèn)題的標(biāo)準(zhǔn)測(cè)試算例的實(shí)驗(yàn)表明, 本文提出的HMA算法能在可接受的時(shí)間內(nèi)對(duì)VRPB和2L-VRPB問(wèn)題產(chǎn)出高質(zhì)量的解,同時(shí)本文提出的二維裝箱算法同文獻(xiàn)中的主流二維裝箱算法相比也有明顯的性能優(yōu)勢(shì).

2 問(wèn)題描述與數(shù)學(xué)模型

令G=(V,E)是一個(gè)圖, 其中V={0,1,···,N}是頂點(diǎn)集,E={(i,j)|i,j∈V,i≠j}是邊集.頂點(diǎn)集V由3個(gè)子集V=V0∪Vl∪Vb組成: 子集V0僅包含一個(gè)頂點(diǎn)v0, 代表配送中心; 子集Vl和Vb分別代表配送客戶集合和回程客戶集合, 令Vc=Vl∪Vb.對(duì)于邊(i,j)∈E, 行駛成本cij定義為從vi到vj或從vj到vi的直接行駛距離.在配送中心, 有K輛同類型的運(yùn)輸車輛組成的車隊(duì), 每輛車具有最大裝載能力D且其矩形裝載面積為S=W×L, 其中W代表車廂寬度,L代表長(zhǎng)度.每個(gè)客戶i∈Vc有mi個(gè)矩形貨物, 其集合表示為Ii, 并且該mi個(gè)矩形貨物總質(zhì)量為di.每件貨物Iir∈Ii的寬度和長(zhǎng)度分別記作wir(r=1,2,···,mi)和lir(r=1,2,···,mi).因此,Ii中所有的貨物所占的總面積為

2 L-VRPB問(wèn)題的目標(biāo)是找到能夠?yàn)樗信渌秃突爻炭蛻籼峁┓?wù)的一組車輛行駛路線集合, 使得總的服務(wù)成本(即車隊(duì)的總行駛里程)最小.該問(wèn)題對(duì)應(yīng)的約束可以被分為兩個(gè)部分, 第一部分是關(guān)于車輛路徑的相關(guān)約束, 第二部分是關(guān)于裝箱可行性的相關(guān)約束.兩個(gè)部分的約束的語(yǔ)意描述如下:

(1) 每輛車都在配送中心出發(fā), 完成任務(wù)后返回該配送中心.

(2) 車隊(duì)中最多只有K輛同類型的車可供使用.

(3) 每個(gè)客戶(配送客戶或回程客戶)僅被訪問(wèn)一次.

(4) 每條路線至少包括一個(gè)配送客戶.

(5) 對(duì)于每條路線, 必須先服務(wù)完所有的配送客戶才能繼續(xù)服務(wù)回程客戶, 即先完成送貨任務(wù)再考慮取貨任務(wù).

(6) 在每一條路線中, 所裝載的貨物總重量不能超過(guò)車輛的最大承載重量.

(7) 分配給同一車輛的所有貨物, 在裝載時(shí)不可堆疊, 并且貨物的最終放置位置的邊緣必須與車廂的邊緣平行.

(8) 根據(jù)裝載方式的不同, 本文將問(wèn)題細(xì)分為不允許旋轉(zhuǎn)的裝載(無(wú)序定向裝載, UOL)和允許旋轉(zhuǎn)的裝載(無(wú)序旋轉(zhuǎn)裝載, URL).我們使用VRPB-UOL表示無(wú)序定向裝載的2L-VRPB, VRPB-URL表示無(wú)序旋轉(zhuǎn)裝載的2L-VRPB.

2 L-VRPB問(wèn)題的路徑規(guī)劃部分的數(shù)學(xué)模型如下:

s.t.

約束(1)旨在最大程度地降低總運(yùn)輸成本.約束(2)確保離開(kāi)配送中心的車輛數(shù)量等于返回配送中心的車輛數(shù)量.約束(3)和約束(4)確保每個(gè)客戶只能被一輛車訪問(wèn)一次, 且車輛在訪問(wèn)完客戶后必須離開(kāi)該客戶.約束(5)和約束(6)確保僅在服務(wù)完所有配送客戶之后才能為回程客戶提供服務(wù).約束(7)要求使用車輛的數(shù)量不超過(guò)車隊(duì)中的最大可用車輛數(shù)量.約束(8)和約束(9)確保配送客戶的貨物總重量和總裝載面積必須不超過(guò)車輛的最大載重能力和最大裝載表面積,約束(10)和約束(11)對(duì)回程客戶的貨物做了同樣的約束.

第二部分是關(guān)于裝箱可行性的約束.在本文中, 我們將車輛的裝載表面視為笛卡爾坐標(biāo)系下的一個(gè)矩形區(qū)域.因此, 坐標(biāo)(αir,βir)表示客戶i的貨物r的左下角在車廂表面的笛卡爾坐標(biāo).對(duì)于特定路線Rk, 可以將將其分為兩個(gè)子路線: 一個(gè)由配送客戶組成, 稱為linehaul子路線; 另一個(gè)由回程客戶組成, 稱為backhaul子路線.對(duì)一條路線進(jìn)行裝箱可行性檢查等同于分別對(duì)兩條子路線進(jìn)行檢查.為了簡(jiǎn)化表示, 令R表示其中的一條子路線.此外我們使用二進(jìn)制變量 μir來(lái)表示客戶i的貨物r在裝載時(shí)是否允許旋轉(zhuǎn).涉及子路線R的裝箱約束如下:

約束(13)、約束(14)和約束(15)確保每輛車的貨物均能被無(wú)重疊的放置在裝載面上.

3 改進(jìn)的模因算法設(shè)計(jì)

改進(jìn)的模因算法(IMA)是在具有自適應(yīng)性機(jī)制的混合遺傳搜索算法(HGSADC)[13-15]的基礎(chǔ)上進(jìn)行改進(jìn)得到.我們?cè)趥€(gè)體評(píng)價(jià)方法、本地搜索程序(個(gè)體變異)、個(gè)體接受標(biāo)準(zhǔn)和種群多樣性機(jī)制等方面進(jìn)行了重新設(shè)計(jì), 從而顯著提升了模因算法對(duì)于2L-VRPB問(wèn)題的求解能力.在本節(jié)中我們將介紹IMA算法的各個(gè)部分: 第3.1小節(jié)簡(jiǎn)要介紹了搜索空間和新個(gè)體的評(píng)價(jià)方法; 第3.2小節(jié)介紹了種群中新個(gè)體的產(chǎn)生機(jī)制; 第3.3小節(jié)介紹了本地搜索(個(gè)體變異)機(jī)制; 第3.4小節(jié)介紹了種群在進(jìn)化過(guò)程中的多樣化管理機(jī)制.

3.1 搜索空間和種群個(gè)體表示

VRP相關(guān)的文獻(xiàn)表明, 對(duì)非可行解的有效利用可以顯著的提升解的質(zhì)量[13].本文中, 我們將模因算法的搜索空間定義為兩種類型的解的集合, 即可行解的集合和非可行解的集合, 后者通過(guò)放松車輛最大可承載重量約束(8)和裝載可行性約束(9)、(13)、(14)和(15)獲得.

此外, 為了促進(jìn)非可行解向可行解的轉(zhuǎn)化, IMA將根據(jù)不可行解的可行性偏離程度對(duì)其適應(yīng)度值進(jìn)行相應(yīng)的“懲罰”, 偏離程度越大, “懲罰”越嚴(yán)苛.令R(w)表示解w的路線集合, 路線r∈R(w)表示集合中的單條線路.令rl和rb分別表示r的配送子路線和回程子路線,則解w的總適應(yīng)度值 φ (w)可由約束(16)求得.相關(guān)符號(hào)的表示如下:d(rl)、d(rb)分別表示rl和rb各自的貨物總重量;s(rl)、s(rb)分別表示rl和rb各自所裝載的貨物占用的面積; ωD和ωS表示相應(yīng)的懲罰系數(shù), 初始值均設(shè)為1; φ (r)表示路線r的適應(yīng)度值, 它定義為rl和rb的總行駛距離和各自的懲罰值的累加; φ (w)表示為解w的適應(yīng)度值, 它為所有路線的適應(yīng)度值的累加和.

3.2 新個(gè)體的產(chǎn)生

在每次迭代中, IMA通過(guò)二元錦標(biāo)賽方法[13]從可行種群和不可行種群的聯(lián)合種群中隨機(jī)選擇兩個(gè)父代個(gè)體.隨后, 父代個(gè)體的各條線路被依次連接為一條巡回路線, OX交叉方法[13]將作用于兩條巡回路線并生成兩個(gè)新的巡回路線.伯努利分布將選擇其中的一個(gè)巡回路線, 隨后Split算法[16]將作用于該路線并生成一個(gè)新的完整的個(gè)體, 新個(gè)體將進(jìn)一步通過(guò)本地搜索程序予以改進(jìn).

3.3 本地搜索

本地搜索程序?qū)?duì)種群個(gè)體采用swap, relocate,intra2opt和inter2opt操作算子進(jìn)行變異操作.由Split算法產(chǎn)生的新個(gè)體將先后經(jīng)歷兩個(gè)階段.在本文中, 我們將本地搜索程序的首次執(zhí)行稱為“教育過(guò)程”,第2和第3次執(zhí)行則被稱為“修復(fù)過(guò)程”, 其中“修復(fù)過(guò)程”旨在促使非可行解向可行解的轉(zhuǎn)化.對(duì)于一個(gè)新個(gè)體, 其將首先經(jīng)歷一次本地搜索以提升自身解的質(zhì)量.隨后, 若改善后的解不可行, 則以概率Pm決定是否執(zhí)行修復(fù)過(guò)程.在修復(fù)過(guò)程中, 在第2次執(zhí)行前會(huì)將懲罰參數(shù)乘以10, 如果得到的解仍不可行, 則將懲罰系數(shù)乘以100再執(zhí)行第3次.

為了提升本地搜索程序的搜索能力, 我們對(duì)變異操作設(shè)計(jì)了新的接受標(biāo)準(zhǔn), 當(dāng)標(biāo)準(zhǔn)中的任一情況得以滿足時(shí)將接受和執(zhí)行當(dāng)前變異操作.同文獻(xiàn)中普遍采用的接受標(biāo)準(zhǔn)相比, 本文提出的接受標(biāo)準(zhǔn)顯著提升了本地搜索的效率, 其包含以下3種情形(為了簡(jiǎn)述該標(biāo)準(zhǔn), 假定變異操作涉及兩條路線):

(1)在執(zhí)行變異操作之后, 相關(guān)路線中從回程客戶到配送客戶的弧的數(shù)量減少.

(2)變異操作所涉及的路線的總成本降低, 并且相關(guān)路線在執(zhí)行該操作后均可行.

(3)在執(zhí)行變異操作之前, 相關(guān)路線中至少一條是不可行的.在執(zhí)行操作之后, 兩者路線均可行.

在本地搜索程序的一次執(zhí)行中, 對(duì)于每一次迭代,若變異操作將被接受, 迭代過(guò)程將重新開(kāi)始.該過(guò)程將不斷重復(fù), 直到無(wú)法再產(chǎn)生能夠被接受的新的變異操作.

此外, 本文采取了“鄰域修剪”策略[13,15]以提升對(duì)解的改進(jìn)效率.對(duì)于給定的客戶vi, 其相應(yīng)的“有希望”的客戶的集合 Γ (vi)定義為|Γ |個(gè)與其最接近的客戶.可以將 Γ (vi)所包含的客戶視為從vi出發(fā)去訪問(wèn)下一站的理想目的地, 對(duì)于vj∈ Γ(vi), 弧 (vi,vj)即為“有希望的”邊的子集.對(duì)某次變異操作, 只有當(dāng)其產(chǎn)生了至少一個(gè)有“希望的”邊[15]才會(huì)去進(jìn)一步評(píng)估其是否符合接受標(biāo)準(zhǔn).

3.4 種群管理機(jī)制

在進(jìn)化過(guò)程中模因算法會(huì)始終維持兩個(gè)種群, 即可行解種群和非可行解種群.每個(gè)種群的個(gè)體數(shù)量均保持在 λ和 λ +δ之間, 其中 λ表示最小種群數(shù)量, δ表示能允許的最大新增數(shù)量.在初始化階段, IMA將隨機(jī)生成 4 μ個(gè)新個(gè)體并根據(jù)可行性將其添加到對(duì)應(yīng)的種群中.為了避免解的過(guò)早收斂和保持種群的多樣性, 我們對(duì)種群中的個(gè)體實(shí)行嚴(yán)格的分散化規(guī)則, 任何兩個(gè)個(gè)體之間的適應(yīng)度值 φ (w)的間隔必須大于0.5, 其中違背分散化規(guī)則的個(gè)體將被丟棄.對(duì)于每個(gè)種群, 當(dāng)其種群大小達(dá)到最大上限 λ +δ時(shí), IMA將觸發(fā)篩選機(jī)制, 該機(jī)制會(huì)剔除種群中適應(yīng)度值最差的 δ 個(gè)個(gè)體.最后, 當(dāng)IMA每執(zhí)行itdiv次迭代而未能更新當(dāng)前最好解時(shí)便會(huì)觸發(fā)一個(gè)多樣化程序.在該程序中, IMA僅保留每個(gè)種群中最好的 λ /3個(gè)個(gè)體, 然后執(zhí)行初始化, 即生成 4 μ個(gè)新個(gè)體并將其添加到對(duì)應(yīng)的種群中.

4 MultiPack啟發(fā)式裝箱算法設(shè)計(jì)

本文在5種基本的裝箱構(gòu)造算法的基礎(chǔ)上提出了MultiPack啟發(fā)式算法來(lái)檢查裝載的可行性, 它通過(guò)采用5種裝箱構(gòu)造算法和2種額外的提升策略來(lái)生成貨物放置方案.MultiPack算法由3個(gè)部件構(gòu)成, 每個(gè)部件均可獨(dú)立的產(chǎn)生可行的裝載方案.這3個(gè)部件會(huì)依次被調(diào)用, 只有當(dāng)當(dāng)前部件無(wú)法生成可行裝載方案時(shí)才會(huì)調(diào)用下一個(gè)更復(fù)雜的部件.第1個(gè)部件采用了5種啟發(fā)式裝箱構(gòu)造算法, 第2個(gè)部件是在對(duì)第1個(gè)部件采用全局最優(yōu)策略進(jìn)行改進(jìn)得到, 第3個(gè)部件通過(guò)對(duì)最大接觸邊界(MTP)裝箱啟發(fā)式算法采用有偏隨機(jī)化改造得到.

對(duì)于單條路線上的客戶集Rset,Rseq表示按照某種排序規(guī)則將客戶集Rset的所有貨物進(jìn)行排序之后的序列.freeList表示車輛裝載表面上的空閑矩形列表.在裝載之前,freeList中只有一個(gè)矩形, 即車輛的矩形表面,之后每裝載一件貨物, 所選的目標(biāo)矩形將從freeList中刪除, 同時(shí)新生成的空閑矩形將被添加到freeList中,隨后freeList中的所有可用矩形將經(jīng)歷一輪檢查, 以刪除不必要的矩形.

在MultiPack的第1個(gè)部件中, 5種構(gòu)造算法Heuri(i=1,2,···,5)將依次被調(diào)用.對(duì)于任一個(gè)構(gòu)造裝箱算法Heuri, 將依據(jù)貨物在Rseq中的先后次序依次安排其所對(duì)應(yīng)的最佳放置位置.不同的基本裝箱構(gòu)造算法具有不同的“最佳匹配”評(píng)估標(biāo)準(zhǔn), 相關(guān)描述如下:

Heur1: 對(duì)于所有在freeList里的可放置的空閑矩形, BL (Bottom-Left)啟發(fā)式方法[17]總是選擇一個(gè)左下角的橫縱坐標(biāo)最小的矩形.

Heur2: 在所有freeList里的可放置的空閑矩形中,BAU (Best Area Utilization)啟發(fā)式方法[18]選擇表面積最小的矩形, 使得所選矩形在放置貨物之后的面積利用率最高.

Heur3: 在freeList里的可放置的空閑矩形中, BSEM(Best Short-Edge Match)選擇“剩余邊”較短的最短矩形.令和表示其中一個(gè)空閑矩形的寬度和長(zhǎng)度,wi和li分別表示當(dāng)前待放貨物的寬度和長(zhǎng)度.BSEM啟發(fā)式方法將在可放置的空閑矩形中選擇目標(biāo)值min(w′j-wi,-li)最小的矩形.

Heur4: 在freeList中的可放置的空閑矩形中, BLEM(Best Long-Edge Match)啟發(fā)式選擇目標(biāo)值max(,-li)最小的可行空閑矩形來(lái)放置當(dāng)前貨物.

Heur5: 在freeList的所有可行的空閑矩形中, MTP(Maximum Touch Perimeter)[11]選擇一個(gè)使接觸周長(zhǎng)最大的空閑矩形來(lái)放置新貨物.

在第1個(gè)部件中, 每種基本的裝箱構(gòu)造算法Heuri(i=1,2,···,5)將根據(jù)貨物序列Rseq進(jìn)行裝載.這些算法的優(yōu)勢(shì)是運(yùn)行效率很高, 但是在某些極端情況下, 其效果可能會(huì)很差.因此, 第1個(gè)部件中的5種基本啟發(fā)式方法適用于處理簡(jiǎn)單的裝箱情況.

為了應(yīng)對(duì)更復(fù)雜的情況, 我們采用全局最優(yōu)策略來(lái)改進(jìn)第1個(gè)部件中的5種基本算法.在第2個(gè)組件中包含5種改進(jìn)后的裝箱算法, 標(biāo)記為impHeuri(i=1,2,···,5),每種impHeuri都 是通過(guò)對(duì)Heuri采用全局最優(yōu)策略進(jìn)行改進(jìn)得到.改進(jìn)后的impHeuri將不再根據(jù)輸入序列Rseq來(lái)進(jìn)行裝載, 而是在每一次裝載時(shí)將對(duì)每個(gè)待裝載的貨物和該貨物的所有可放置位置進(jìn)行評(píng)估, 然后選擇最佳位置.

對(duì)于給定的貨物集合, 第2個(gè)部件中的改進(jìn)啟發(fā)法算法極大地?cái)U(kuò)展了給定貨物及其相關(guān)可行位置的搜索范圍, 因而可以生成更好的裝載方案.我們采用類似Burke等人[10]的算法實(shí)現(xiàn)方式來(lái)提升算法的運(yùn)行性能.

最后, 為了提升MultiPack算法對(duì)更為復(fù)雜的裝箱情形的處理能力, 本文采用了有偏隨機(jī)化技術(shù)[6]來(lái)改進(jìn)MTP裝箱構(gòu)造算法, 標(biāo)記為Biased-MTP, 它構(gòu)成了MultiPack算法的第3個(gè)部件.在每一次裝載時(shí), Biased-MTP會(huì)評(píng)估每個(gè)未裝箱的貨物及其對(duì)應(yīng)的所有可行放置位置, 對(duì)所有生成的可行放置將基于接觸周長(zhǎng)來(lái)排序,隨后將使用幾何分布來(lái)決定執(zhí)行哪個(gè)可行裝載.Biased-MTP使用兩個(gè)參數(shù) θ和PackIter來(lái)校準(zhǔn)算法: 前者表示單次伯努利實(shí)驗(yàn)成功的概率, 后者表示為某個(gè)貨物尋找其放置位置時(shí), 若一直無(wú)法找到可行的放置位置, 則隨機(jī)MTP啟發(fā)式算法將會(huì)被調(diào)用的最大次數(shù).

為了降低調(diào)用MultiPack帶來(lái)的時(shí)間開(kāi)銷, 本文使用了特殊的數(shù)據(jù)結(jié)構(gòu)(Trie)[19]來(lái)記錄已檢查路線的裝箱可行性.在這里, 我們將Trie樹(shù)中的最大存儲(chǔ)數(shù)量限制為10 000 000.當(dāng)Trie樹(shù)中的數(shù)量達(dá)到上限時(shí), 將僅保留最近生成的2/3部分的元素.

5 數(shù)值實(shí)驗(yàn)

在本節(jié)中, 我們首先測(cè)試HMA算法在經(jīng)典VRPB基準(zhǔn)算例上的性能表現(xiàn), 并將實(shí)驗(yàn)結(jié)果與其他最新啟發(fā)式算法進(jìn)行比較.然后, 我們進(jìn)一步在2L-VRPB算例上進(jìn)行測(cè)試, 檢驗(yàn)HMA算法針對(duì)本文提出來(lái)的2L-VRPB問(wèn)題的求解性能.HMA算法基于C++編程語(yǔ)言實(shí)現(xiàn),運(yùn)行平臺(tái)為Windows 10, 硬件環(huán)境為3.4 GHz Intel i7 6700處理器和16 GB RAM.

5.1 VRPB的計(jì)算結(jié)果

由于2L-VRPB問(wèn)題是在經(jīng)典的VRPB問(wèn)題上的擴(kuò)展, 故我們首先檢驗(yàn)HMA算法在求解原VRPB問(wèn)題的求解性能, 這將體現(xiàn)HMA的路徑規(guī)劃的能力.基于Goetschalckx和Jacobs-Blecha發(fā)布的VRPB基準(zhǔn)算例[20], HMA的求解結(jié)果同文獻(xiàn)中的相關(guān)算法的求解結(jié)果的對(duì)比如表1所示.所引用文獻(xiàn)中的算法的描述如下: LS12表示Zachariadis等人提出的本地搜索算法[21],ILS14表示由Palhazi Cuervo等人提出的迭代局部搜索算法[22], DILS16表示Brand?o等人提出的確定性局部迭代搜索算法[4], HMA表示本文提出的混合模因算法.HMA的參數(shù)設(shè)置和終止條件與Vidal等人[13]的設(shè)置相同.

在表1中, 對(duì)于每個(gè)實(shí)例, BKS指的是所列出文獻(xiàn)中得到的已知最好解[12], Gap列表示HMA的求解結(jié)果同已知最好解的百分比偏差, Time表示HMA的平均耗時(shí).在所有的測(cè)試算例中, 只有3個(gè)實(shí)例(C1、G1、I5)沒(méi)有達(dá)到已知最好水平, 其對(duì)應(yīng)的百分比偏差均小于0.5%.綜合來(lái)看, HMA對(duì)于求解VRPB問(wèn)題是一種極具競(jìng)爭(zhēng)力的元啟發(fā)式算法, 它擁有很強(qiáng)的路徑尋優(yōu)能力.

表1 （續(xù)） VRPB的計(jì)算結(jié)果

表1 VRPB的計(jì)算結(jié)果

5.2 2L-VRPB的計(jì)算結(jié)果

2 L-VRPB是2L-CVRP的擴(kuò)展, Toth等人采用了一種從經(jīng)典VRP數(shù)據(jù)集生成VRPB數(shù)據(jù)集的方法[23].本文采用Dominguez等人[6]的方法從Gendreau等人[24]的經(jīng)典2L-CVRP基準(zhǔn)算例來(lái)生成2L-VRPB算例.具體而言, 即在2L-CVRP的每個(gè)算例中, 每隔4個(gè)客戶便將最后1個(gè)客戶指定為回程客戶, 前面的3個(gè)指定為配送客戶.生成的新的2L-VRPB數(shù)據(jù)集中包含180個(gè)算例, 總共分為5個(gè)類別, 每個(gè)類別包含36個(gè)算例, 算例中的客戶規(guī)模從10到255.在第1個(gè)類別中,由于所有的貨物的長(zhǎng)寬均設(shè)置為單位1, 故其可以視為純VRPB問(wèn)題.對(duì)于第2類到第5類, 每個(gè)客戶對(duì)應(yīng)著一組不同尺寸的矩形貨物, 且裝箱復(fù)雜程度依次增加.

針對(duì)2L-VRPB基準(zhǔn)算例, 我們選取部分中等規(guī)模的算例進(jìn)行初步實(shí)驗(yàn)以校準(zhǔn)HMA算法的參數(shù).這里,itmax用來(lái)設(shè)置停機(jī)條件, 表示HMA在交叉了itmax次之后終止運(yùn)行.在對(duì)解的質(zhì)量和求解時(shí)間進(jìn)行權(quán)衡之后,我們給出了最終的參數(shù)設(shè)定值: λ=12, δ=20, |Γ|=40,Pm=0.5, 4μ=50,itdiv=600,itmax=6000.

對(duì)2L-VRPB的每一個(gè)算例, HMA算法將執(zhí)行3次, 每次執(zhí)行將設(shè)置一個(gè)不同的隨機(jī)數(shù)種子, 3次執(zhí)行的結(jié)果中的最好值將作為HMA的解.文本將解決2L-VRPB的兩個(gè)變體, 即無(wú)序定向裝載(記為VRPBUOL), 和無(wú)序旋轉(zhuǎn)裝載(VRPB-URL), 最終的求解結(jié)果如表2所示.由于兩個(gè)變體在針對(duì)算例中的第1類的結(jié)果是一樣的, 故不再重復(fù)列出.class1為HMA對(duì)2L-VRPB在無(wú)序裝載模式下的求解結(jié)果(不再區(qū)分定向裝載和旋轉(zhuǎn)裝載), class2到class5為HMA針對(duì)VRPB-UOL的求解結(jié)果, class6到class9為HMA針對(duì)VRPB-URL的求解結(jié)果.在本文所設(shè)置的停機(jī)條件下, 所有的算例均在可比較的時(shí)間內(nèi)完成了計(jì)算.對(duì)于同一算例, 旋轉(zhuǎn)裝載的解要好于定向裝載的解, 這是由于在可旋轉(zhuǎn)的條件下裝箱算法有更大的靈活性.

表2 2L-VRPB實(shí)驗(yàn)結(jié)果

為了進(jìn)一步驗(yàn)證HMA對(duì)2L-VRPB問(wèn)題的求解性能, 尤其是驗(yàn)證MultiPack算法在復(fù)雜裝箱情況的求解能力, 我們對(duì)VRPB-UOL和VRPB-URL兩個(gè)變體分別設(shè)計(jì)了3組對(duì)比實(shí)驗(yàn).在IMA算法的基礎(chǔ)上, 我們采用3種不同的裝箱算法來(lái)代替HMA算法中的MultiPack, 并在基準(zhǔn)算例上測(cè)試其性能.首先, 我們用Leung等人[25]提出的裝箱啟發(fā)式算法(PHB)來(lái)代替HMA中的MultiPack.此外, 在PHB裝箱算法的基礎(chǔ)上, 我們對(duì)其基本裝箱構(gòu)造算法采用全局化策略進(jìn)行改進(jìn), 并將改進(jìn)后的部分同PHB串聯(lián), 得到新的裝箱算法并記為ImpPHB.最后, 我們將Dominguez等人[6]提出的隨機(jī)有偏化MTP算法[11]記為BiasMTP.

表3和表4分別給出了4種算法在VRPB-UOL問(wèn)題和VRPB-URL問(wèn)題上的平均性能表現(xiàn), 每一個(gè)值都是特定算例在類別2到5的數(shù)據(jù)上的平均值.BKS表示4種算法所給出的結(jié)果中的最好值, Gap表示各個(gè)算法同當(dāng)前最好值之間的百分比偏差, 由于值越小越好, 故百分比偏差越小則表示該算法的性能越優(yōu).

由表3和表4可看出, 對(duì)于小、中和大規(guī)模算例,在4種算法中, HMA對(duì)于所有算例均能給出最好解.

表3 VRPB-UOL問(wèn)題的計(jì)算結(jié)果

表4 VRPB-URL問(wèn)題的計(jì)算結(jié)果

在VRPB-UOL問(wèn)題中, HMA算法給出的解在所有算例上的平均值為999.52, 該值同所有算例的已知最好解的平均值相同.BiasMTP算法給出的解的平均值同已知最好解的平均值的百分比偏差為0.011%, ImpPHB算法對(duì)應(yīng)的偏差為0.006%, PHB對(duì)應(yīng)的偏差為0.021%,由于0.021%＞0.011%＞0.006%＞0.000%, 4種算法的性能表現(xiàn)為 HMA＞ImpPHB＞BiasMTP＞PHB; 對(duì)于 VRPBURL問(wèn)題, HMA算法在所有算例上的平均值為977.49,BiasMTP算法同其相比的百分比偏差為0.008%,ImpPHB算法為0.004%, PHB對(duì)應(yīng)的偏差為0.014%,可得0.014%＞0.008%＞0.004%＞0.000%, 4種算法的性能表現(xiàn)為 HMA＞ImpPHB＞BiasMTP＞PHB.綜合 4 種算法在VRPB-UOL和VRPB-URL問(wèn)題上的性能表現(xiàn),HMA算法的性能顯著優(yōu)于ImpPHB算法、BiasMTP算法和PHB算法.由此可得出結(jié)論, 本文提出的Multi-Pack算法同文獻(xiàn)中的主流二維裝箱算法相比很有競(jìng)爭(zhēng)力, 同時(shí)本文提出的混合模因算法(HMA)對(duì)于2LVRPB問(wèn)題是一個(gè)高效的求解算法.

6 結(jié)束語(yǔ)

本文研究了一個(gè)新的組合優(yōu)化問(wèn)題, 即帶回程取貨和二維裝箱約束的車輛路徑問(wèn)題(2L-VRPB), 該問(wèn)題可以在實(shí)際物流系統(tǒng)中找到相應(yīng)的應(yīng)用實(shí)例.本文首次研究了該問(wèn)題的無(wú)序定向裝載和無(wú)序旋轉(zhuǎn)裝載兩種變體.為了求出該問(wèn)題的高質(zhì)量的解, 本文提出了一種新的混合模因算法(HMA), 該算法通過(guò)改進(jìn)的模因算法(IMA)完成路徑規(guī)劃, 并通過(guò)定制化的組合裝箱啟發(fā)式算法(MultiPack)完成特定貨物的裝載方案的設(shè)計(jì).通過(guò)在VRPB問(wèn)題和2L-VRPB問(wèn)題的基準(zhǔn)算例上設(shè)計(jì)對(duì)比實(shí)驗(yàn), 本文提出的混合模因算法對(duì)兩種問(wèn)題均能在可接受的時(shí)間范圍內(nèi)給出高質(zhì)量的解, 這表明該算法對(duì)VRPB問(wèn)題和2L-VRPB問(wèn)題均為一種高效的求解算法.同時(shí), 該算法可進(jìn)一步應(yīng)用于其他更復(fù)雜的車輛路徑和裝箱問(wèn)題相結(jié)合的問(wèn)題的求解中.本文的組合化策略、全局優(yōu)化和有偏隨機(jī)化策略對(duì)于求解三維裝載問(wèn)題以及其他更為復(fù)雜的組合優(yōu)化問(wèn)題的算法設(shè)計(jì)都有很好的借鑒意義.