基于VLSN的ILS算法求解選址問題.pdf

1、選址問題是運籌學研究的一個問題，同時在物流學中也是一個研究方向。在本文中，介紹了一個重要的倉庫選址問題：單資源固定容量設備選址問題。問題是決定將這些帶有容量限制的倉庫選在何處，然后怎樣使零售商指派到已使用的倉庫，以確保總費用最少。由于倉庫有一個容量限制，所以零售商并不總是指派到最近的倉庫，而且最優(yōu)的選擇倉庫的合適數(shù)量也增加了問題的難度。這個問題被稱為固定容量設備選址問題(CFLP)，或者是固定容量中心選址問題(CCLP)。 由于

2、大多數(shù)選址問題都已證明是NP-難問題，研究問題的近似算法成為其關鍵技術。本文就是基于大規(guī)模鄰域搜索(VLSN)技術的迭代局域搜索(ILS)算法來解決資源固定容量設備選址問題(CFLP)。其核心思想就是運用這種新的鄰域搜索算法—環(huán)狀交換(cyclictransfer)來尋優(yōu)。本文提出了一種帶有虛擬零售商的改進環(huán)狀交換動態(tài)規(guī)劃算法，并結合了隨機kick的ILS策略求解。 為了說明VLSN技術的有效性，本文又實現(xiàn)了拉格朗日松弛算法以及

3、多點下降算法，并且結合大規(guī)模算法和多點下降算法求得了質量更好的解。 本文結合鋼鐵實際對寶剛原料場料場管理流程進行分析，并針對料場配置建立數(shù)學模型，在模型求解上，本文提出了基于VLSN的ILS算法，并為了證明其有效性及優(yōu)越性，同時也用多點下降算法進行了求解。 所有的實驗程序都是用C語言編寫，并在Pentium4主頻2.4GHZ的計算機上進行實驗仿真。實驗結果表明基于VLSN的ILS算法能解決資源固定容量設備選址問題，并且能