發(fā)布時(shí)間：2020-07-12 04:26

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

考慮時(shí)間窗約束的裝箱問(wèn)題

研究思路圖

NF算法裝箱過(guò)程

【參考文獻(xiàn)】

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

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

本文編號(hào)：2751417