車輛路徑與三維裝箱混合問題(3L-CVRP)的研究.pdf

1、本文研究了現(xiàn)代物流算法中兩個(gè)最重要的問題，車輛路徑問題和裝箱問題，這兩個(gè)問題已經(jīng)被證明是NP—Hard，單獨(dú)針對兩個(gè)問題，目前已經(jīng)有大量的論文，但是對這兩個(gè)問題的綜合（3L—CVRP）目前研究還比較少，該問題由2006年首次被提出。 本文使用兩階段的禁忌搜索算法來安排車輛路徑，并通過局部搜索求解帶有各種約束的裝箱問題，最后通過分枝定界法進(jìn)行后續(xù)優(yōu)化。與現(xiàn)有文獻(xiàn)中使用的裝箱方法不同，本文將兩種經(jīng)典的二維裝箱方法Bottom Lef

2、t with Fill和Touching Perimeter進(jìn)行了修改，并將其推廣到三維情形，在綜合考慮了3L—CVRP中各種裝箱約束下，提出了非常高效的實(shí)現(xiàn)算法Deepest Bottom Left with Fill和Touching Area。新的裝箱算法的提出大大增加了車輛的空間利用率，大量的實(shí)驗(yàn)結(jié)果表明，應(yīng)用了Bottom Left with Fill和Touching Area的兩階段禁忌搜索算法無論在求解質(zhì)量上還是求解時(shí)間