疫情期間生活物資集散點(diǎn)選址問題的降階回溯算法

打開文本圖片集

摘 要：疫情爆發(fā)后，封控區(qū)內(nèi)居民的生活物資發(fā)放問題成為亟待解決的焦點(diǎn)問題之一，該問題可抽象為疫情期間生活物資集散點(diǎn)選址問題，其實(shí)質(zhì)為組合優(yōu)化中的NP-hard問題。基于疫情封控期間的應(yīng)急生活物資集散點(diǎn)選址問題的精確算法進(jìn)行研究，首先得出一些可以降低問題規(guī)模的數(shù)學(xué)性質(zhì)并證明利用這些性質(zhì)可以減小問題規(guī)模，降低問題的求解難度；然后設(shè)計(jì)出分配子算法、上下界子算法以及降階子算法；基于這些子算法提出一種可以減小問題規(guī)模同時(shí)得到最優(yōu)解的降階回溯算法；最后通過分析和求解若干個(gè)示例進(jìn)一步闡述該算法的原理和執(zhí)行過程，結(jié)果表明該算法能通過減小問題規(guī)模來降低問題求解的難度。（剩余10379字）