汪洋廣, 陳 振

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

1 引言

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

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

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

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

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

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

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

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

2 L-VRPB問題的目標是找到能夠為所有配送和回程客戶提供服務(wù)的一組車輛行駛路線集合, 使得總的服務(wù)成本(即車隊的總行駛里程)最小.該問題對應(yīng)的約束可以被分為兩個部分, 第一部分是關(guān)于車輛路徑的相關(guān)約束, 第二部分是關(guān)于裝箱可行性的相關(guān)約束.兩個部分的約束的語意描述如下:

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

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

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

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

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

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

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

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

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

s.t.

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

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

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

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

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

3.1 搜索空間和種群個體表示

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

此外, 為了促進非可行解向可行解的轉(zhuǎn)化, IMA將根據(jù)不可行解的可行性偏離程度對其適應(yīng)度值進行相應(yīng)的“懲罰”, 偏離程度越大, “懲罰”越嚴苛.令R(w)表示解w的路線集合, 路線r∈R(w)表示集合中的單條線路.令rl和rb分別表示r的配送子路線和回程子路線,則解w的總適應(yīng)度值 φ (w)可由約束(16)求得.相關(guān)符號的表示如下: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 新個體的產(chǎn)生

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

3.3 本地搜索

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

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

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

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

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

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

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

3.4 種群管理機制

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 數(shù)值實驗

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

5.1 VRPB的計算結(jié)果

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

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

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

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

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

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

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

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

表2 2L-VRPB實驗結(jié)果

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

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

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

表3 VRPB-UOL問題的計算結(jié)果

表4 VRPB-URL問題的計算結(jié)果

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

6 結(jié)束語

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