擴(kuò)展過道布置問題的建模與改進(jìn)分散搜索優(yōu)化研究.pdf

1、隨著全球經(jīng)濟(jì)的快速發(fā)展，縮短生產(chǎn)周期、降低生產(chǎn)成本是當(dāng)今企業(yè)贏得市場的首要因素。合理的設(shè)施布局不僅可以節(jié)約10％-30％的成本，還能減少物料傳輸距離、降低在制品的停留時間等。作為設(shè)施布局問題的一種，過道布置問題(CorridorAllocation Problem，CAP)不僅在服務(wù)部門領(lǐng)域應(yīng)用廣泛，在工業(yè)制造領(lǐng)域亦具有重要的潛在應(yīng)用價值。因此，對過道布置問題的研究具有重要的理論價值和現(xiàn)實意義。
　　過道布置問題以最小化設(shè)施間的總

2、流量成本為優(yōu)化目標(biāo)，將給定的一系列設(shè)施布置到過道兩側(cè)，屬于典型的組合優(yōu)化問題，具有NP-hard屬性和較大的求解難度。本文基于此提出了一種改進(jìn)分散搜索（Improved Scatter Search，ISS）算法。該算法引入一種兩階段混合改進(jìn)策略——先利用加速插入法對解進(jìn)行局部改進(jìn)，再通過模擬退火操作進(jìn)一步優(yōu)化當(dāng)前參考集中的最優(yōu)解，以提高算法獲得全局最優(yōu)解的概率;采用包含高質(zhì)量和多樣性解的雙層參考集替代傳統(tǒng)參考集，擴(kuò)大搜索范圍，避免算法

3、陷入局部最優(yōu);同時，采用動態(tài)參考集更新方法，及時替換參考集中質(zhì)量或多樣性方面較差的解，加快算法的收斂速度，并改進(jìn)子集產(chǎn)生方法，避免產(chǎn)生重復(fù)的解，從而提高算法的求解效率。對一系列不同規(guī)模的測試問題進(jìn)行驗算與對比，結(jié)果表明:改進(jìn)分散搜索算法在求解質(zhì)量和平穩(wěn)性方面均優(yōu)于基本模擬退火算法和分散搜索算法，且較已有的6種方法更具求解優(yōu)勢。
　　針對現(xiàn)有研究忽略通道寬度和總流量入口的不足，考慮到這兩個因素會對總流量成本產(chǎn)生影響這一實際情況，本文

4、構(gòu)建了擴(kuò)展過道布置問題的混合整數(shù)規(guī)劃模型，并運用GUROBI軟件進(jìn)行精確求解，驗證了模型的正確性。進(jìn)而利用改進(jìn)分散搜索算法進(jìn)行求解，不僅求得了小規(guī)模問題的最優(yōu)解，還在合理的時間內(nèi)快速獲得了大規(guī)模問題的近優(yōu)解。對比分析發(fā)現(xiàn)，若在布局設(shè)計初期就考慮通道寬度的影響，則設(shè)施間總流量成本最多可節(jié)約27.59％，若同時考慮通道寬度和總流量入口的影響，則總流量成本至少可降低6.08％。接著，為便于算法應(yīng)用，對算法的相關(guān)性能進(jìn)行了分析，探討了不同種子解