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

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

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

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

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

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

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

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

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

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

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