【摘要】：本文介紹和研究了考慮時間窗約束的裝箱問題(BPPTW),該問題是物流行業(yè)中普遍存在的實(shí)際問題。快遞公司每天需要將待配送的貨物從配送中心交付到各個客戶手上,在配送之前,就涉及到怎樣裝箱的問題,當(dāng)待配送的物品含有到達(dá)時間窗限制時,由于時間窗沒有交集的兩個物品不能裝入同一個車廂中,此時不能再按照傳統(tǒng)的裝箱方案來裝載物品,必須為考慮時間窗約束的裝箱問題設(shè)計(jì)一個合理的裝箱方案。合理的裝箱方案不僅能為企業(yè)節(jié)省運(yùn)輸費(fèi)用、提高配送效率,還能進(jìn)一步地提高客戶滿意度。假設(shè)配送中心有若干待配送的物品以及足夠的車廂,且這些物品具有不同的重量和配送時間窗,目的是選擇一組具有最低成本或最少數(shù)量的箱子來裝載所有物品。裝載在同一箱子中物品的總重量不得超過該箱子的重量約束,且同一箱子中所有物品的時間窗之間必須有一個共同的時間點(diǎn)。BPPTW是裝箱問題的一個擴(kuò)展,由于裝箱問題是NP難問題,所以BPPTW也是NP難問題,對其進(jìn)行研究能夠豐富組合優(yōu)化領(lǐng)域的內(nèi)容,為以后學(xué)者研究該類問題提供一個基準(zhǔn);同時,研究BPPTW還能提高物流的配送效率,從而為企業(yè)降低運(yùn)輸成本和提高客戶滿意度。因此,研究該問題具有重要的理論價值和實(shí)踐價值。本文首先將時間窗約束考慮到一維裝箱問題中,從而形成了考慮時間窗約束的一維裝箱問題(1DBPP-TW)這一新問題,在綜合考慮裝箱問題和帶時間窗約束的車輛路徑問題的數(shù)學(xué)模型之后,為1DBPP-TW建立了數(shù)學(xué)模型。首先,針對該模型,本文采用了IBM公司開發(fā)的CPLEX對其進(jìn)行求解;接著,提出了基于時間范圍的貪心啟發(fā)式算法(GTR)來快速生成該問題的初始可行解;最后,開發(fā)了一種迭代局部搜索算法(ILS)來進(jìn)一步提高解的質(zhì)量。本文對CPLEX、GTR算法、ILS算法進(jìn)行了大量的實(shí)例測試,結(jié)果表明,CPLEX僅能求解規(guī)模較小的實(shí)例,GTR算法能在很短的時間內(nèi)為1DBPP-TW找到較好的初始解,ILS算法能進(jìn)一步地提高初始解的質(zhì)量。本文繼續(xù)將時間窗約束考慮到變尺寸裝箱問題中,從而形成了考慮時間窗約束的變尺寸裝箱問題(VSBPPTW)這一新問題。首先,本文在1DBPP-TW模型的基礎(chǔ)上為VSBPPTW建立了數(shù)學(xué)模型并采用CPLEX求解該模型;然后,采用著名的最佳適應(yīng)啟發(fā)式算法(BF)為VSBPPTW產(chǎn)生初始可行解;最后,開發(fā)了一種最短路徑解碼器,并在最短路徑解碼器的基礎(chǔ)上開發(fā)了ILS算法來進(jìn)一步地提高解的質(zhì)量。為了檢驗(yàn)ILS算法的有效性,本文采用了文獻(xiàn)中變尺寸裝箱問題(VSBPP)的例子(實(shí)例集Set1和Set2)來進(jìn)行實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表明:ILS算法在求解實(shí)例集Set1時,其計(jì)算結(jié)果都劣于文獻(xiàn)中求解VSBPP最好的變領(lǐng)域搜索算法(VNS),但與VNS計(jì)算結(jié)果的差距很小;ILS算法在求解實(shí)例集Set2時,部分測試實(shí)例的計(jì)算結(jié)果要優(yōu)于VNS算法,但平均結(jié)果微劣于VNS算法。ILS算法是針對VSBPPTW提出的算法,但其在求解VSBPP問題時也表現(xiàn)出較高的性能,與求解VSBPP最好的VNS算法之間的差異很小,可以證明ILS算法的有效性。同樣,本文繼續(xù)使用CPLEX、BF算法、ILS算法求解VSBPPTW實(shí)例。結(jié)果表明,CPLEX僅能求解規(guī)模較小的實(shí)例,BF算法能在很短的時間內(nèi)為VSBPPTW找到較好的初始解,ILS算法能進(jìn)一步地提高初始解的質(zhì)量。因此,本文得出的結(jié)論為:GTR算法和BF算法能為1DBPP-TW和VSBPPTW快速生成問題的初始可行解,ILS算法能進(jìn)一步地提高初始解的質(zhì)量。雖然ILS算法是針對1DBPP-TW和VSBPPTW提出的高效啟發(fā)式算法,但其在求解VSBPP時,也表現(xiàn)出較高的性能。
【學(xué)位授予單位】：江西財(cái)經(jīng)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2019
【分類號】：TP301.6;F253
【圖文】：

考慮時間窗約束的裝箱問題

研究思路圖

NF算法裝箱過程

【參考文獻(xiàn)】

相關(guān)期刊論文 前1條

1 張鐵山;郭曉薇;;社會物流總費(fèi)用變化趨勢與影響因素分析[J];物流工程與管理;2014年09期

本文編號：2751417