物流系統(tǒng)模型和算法研究.pdf

1、物流是企業(yè)的“第三利潤源”，是國民經(jīng)濟發(fā)展的動脈和基礎(chǔ)產(chǎn)業(yè)。加強信息技術(shù)在物流系統(tǒng)中的應(yīng)用，可以有效地降低物流費用。物流系統(tǒng)的模型和算法是計算機科學(xué)和物流科學(xué)當(dāng)前研究的熱點。 物流費用主要包括物流中心的選址費用、物流配送費用和庫存費用。本文以降低物流費用為目標(biāo)，對物流系統(tǒng)的選址、配送和庫存三個環(huán)節(jié)進行了研究。 本文的主要工作和主要創(chuàng)新點包括以下幾個部分： 1．研究了一類特殊的物流中心選址問題——基于交通網(wǎng)絡(luò)的單應(yīng)

2、急中心選址問題。應(yīng)急中心選址不僅要考慮選址費用(建設(shè)費用和運輸費用)，更重要的是要考慮中心的覆蓋范圍和由中心到各需求點的應(yīng)急時間限制。研究者通常使用重心法、層次分析法或者求解選址模型來解決應(yīng)急中心選址問題。重心法無法評估應(yīng)急中心到需求點的應(yīng)急時間限制以及其它影響應(yīng)急中心建設(shè)的因素；單純使用層次分析法，需要考查所有候選點，且必須考查候選點到需求點的費用和時間等因素，因此工作量很大；通過建立選址模型并求解的方法，不是對影響選址的因素缺乏全面

3、的考慮，就是模型復(fù)雜難以求解。 本文以降低應(yīng)急中心選址費用為目標(biāo)，結(jié)合重心法、層次分析法和本文提出的求解K短路徑算法，提出了一個求解單應(yīng)急中心選址問題的三階段算法TSA，并通過實例闡述了TSA算法的求解過程。TSA算法中，第一階段使用重心法來縮小選址范圍。第二階段中，本文提出了一個時間復(fù)雜度小，且易于編程實現(xiàn)的求解K短路徑算法KSP，并使用KSP算法，排除不滿足時間緊迫性限制的候選地點。第三階段使用層次分析法，根據(jù)選址費用和其它

4、影響選址的因素，對剩下的少數(shù)候選地點進行分析，確定最終的選址地點。 TSA算法過程簡單，計算量小，既考慮了影響選址的諸多因素，又考慮了選址費用、覆蓋范圍和應(yīng)急時間限制。是一個解決單一應(yīng)急中心選址問題的有效算法。 2．研究了物流配送方面的三個問題： (1)基于頂點坐標(biāo)的車輛有容量限制的單配送中心車輛路徑安排問題：該問題以最小化車輛行駛距離為目標(biāo)。通常采用的研究方法包括精確算法、啟發(fā)式算法和元啟發(fā)式算法。由于精確算法

5、計算量大，而一般啟發(fā)式算法結(jié)果通常不夠精確，因此，目前大多使用元啟發(fā)式算法研究該問題，其中遺傳算法的研究成果占了相當(dāng)大的比重。但是，遺傳算法存在的“早熟”問題沒有得到很好的解決。 本文設(shè)計了一個求解該問題的混合遺傳算法SHGA。SHGA算法針對簡單遺傳算法因隨機選擇交叉?zhèn)€體而易于“早熟”的問題，提出了遠(yuǎn)親交叉策略，從而很好地解決了這一問題。為了使算法有較快的收斂速度，SHGA算法采用了優(yōu)良個體保留策略，設(shè)計了優(yōu)良個體數(shù)函數(shù)；利用

6、頂點間的位置關(guān)系，設(shè)計了個體優(yōu)化優(yōu)化策略，對個體進行優(yōu)化。 SHGA既很好地解決了遺傳算法的“早熟”問題，又具有較快的收斂速度。 (2)基于交通網(wǎng)絡(luò)的車輛有容量限制的單配送中心車輛路徑安排問題：物流配送通?？偸窃诮煌ňW(wǎng)絡(luò)中進行的，且配送費用并不能完全由車輛行駛距離來衡量。目前基于交通網(wǎng)絡(luò)的車輛路徑安排的研究成果并不多，并且都是以車輛行駛距離來評價配送費用。 本文建立了基于網(wǎng)絡(luò)的單配送中心車輛路徑安排問題的最小配送

7、費用模型，模型考慮了物流配送的固定費用、空載費用和增加費用，設(shè)計了一個求解模型的混合單親遺傳算法HPGA。該算法中提出了基于最短路徑的優(yōu)化策略，通過在兩個頂點之間插入基于配送費用的最短路徑上的頂點，并在其它位置刪除這些頂點，對個體進行優(yōu)化，從而提高了算法的收斂速度。 (3)車輛有容量限制的多配送中心車輛路徑安排問題：目前這方面的研宄成果并不多，并且通常是把多配送中心車輛路徑安排問題轉(zhuǎn)化為單配送中心車輛路徑安排問題來解決，求解結(jié)果

8、不夠精確。蟻群算法具有較強的魯棒性、易于與其它方法結(jié)合等優(yōu)點，已成功應(yīng)用于求解單配送中心車輛路徑安排問題。但是，目前未見有使用蟻群算法求解多配送中心車輛路徑安排問題的研究成果報導(dǎo)。 本文提出了一個求解多配送中心車輛路徑安排問題的混合蟻群算法HACA。HACA算法中，設(shè)計了螞蟻轉(zhuǎn)移策略和可行解構(gòu)造算法，從而成功地將蟻群算法應(yīng)用于多配送中心車輛路徑安排問題的求解。此外，為了提高算法的求解性能，引入K鄰域結(jié)構(gòu)來限制螞蟻的轉(zhuǎn)移目標(biāo)，使用

9、2_Opt優(yōu)化策略來優(yōu)化螞蟻路徑和可行解，并設(shè)計了信息素更新策略。HACA算法有效地解決了蟻群算法在多配送中心車輛路徑安排問題中的應(yīng)用問題，并且具有很好的求解性能。 本文還分別通過數(shù)據(jù)實驗驗證了以上三個算法的有效性。并討論了參數(shù)設(shè)置對這些算法性能的影響。 3．研究了有保質(zhì)期商品隨機性的庫存問題。該問題一般通過建立優(yōu)化模型和計算機仿真兩種方法來研究。目前用建立優(yōu)化模型來研究該問題的成果通常假定訂貨提前期為確定值和/或需求量

10、與需求時間間隔為常數(shù)或特定函數(shù)，而在實際的庫存系統(tǒng)中，這些量都是隨機的；而用計算機仿真方法來研究該問題的成果一般沒有考慮銷售商為消化庫存而采取的促銷行為。 本文以最大化銷售商的利潤為指標(biāo)，基于離散事件仿真原理，建立了有保質(zhì)期商品的訂貨-庫存-銷售仿真模型。模型同時考慮了生產(chǎn)商的訂貨批量價格折扣和隨機的訂貨提前期、銷售商的降低促銷、顧客的隨機的需求量和隨機的需求間隔時間及顧客對降價商品的增加需求量等諸多因素。此外，通過對該模型的擴