需求與供應(yīng)變化運(yùn)輸問題最小總費(fèi)用上界的智能優(yōu)化算法.pdf

1、從多源點(diǎn)到多目的地的最小總費(fèi)用運(yùn)輸問題研究在實(shí)際生活中扮演著重要的角色，求解需求與供應(yīng)固定時(shí)的最小總費(fèi)用問題是運(yùn)輸問題研究的主要對象。自運(yùn)輸問題提出后的相當(dāng)一段時(shí)間里，研究人員對求解需求與供應(yīng)固定時(shí)的最小總費(fèi)用問題給了相當(dāng)大的關(guān)注。然而由于某些原因，一段時(shí)間內(nèi)每個(gè)產(chǎn)品的供應(yīng)與需求數(shù)量可能有所不同，這種變化也會(huì)使最小總運(yùn)輸費(fèi)用在一定范圍內(nèi)變化。為了做出合適的決策，有關(guān)各方可能對這種因供應(yīng)與需求在一定范圍內(nèi)變化引起最小總運(yùn)輸費(fèi)用也發(fā)生變化的

2、情況更感興趣。然而，即使是供應(yīng)與需求量在一定的范圍內(nèi)變化，但需求與供應(yīng)量的可能選擇還是會(huì)隨著供應(yīng)商與需求商的增多而呈現(xiàn)出急劇式的增加。
　　雖然學(xué)者Liu(2003)建立了需求與供應(yīng)變化運(yùn)輸問題(Transportation Problem withVaryingDemand andSupply，TPVDS)最小總費(fèi)用界限的數(shù)學(xué)模型，還給出了求解該模型的方法，但求TPVDS最小總費(fèi)用上界卻是一個(gè)NP困難問題。后來 Juman和Ho

3、que（2014）證明了Liu(2003)的方法并不能找到TPVDS最小總費(fèi)用的準(zhǔn)確上界，并開發(fā)出求解該問題的啟發(fā)式算法。然而，我們在求某些稍大規(guī)模TP VDS最小總費(fèi)用上界時(shí)發(fā)現(xiàn)，該啟發(fā)式算法也找不到準(zhǔn)確上界。這里，我們在Liu(2003)、Juman和Hoque（2014）的研究基礎(chǔ)上，提出了一種智能優(yōu)化算法TP VDS-A，并證明了如果供應(yīng)商的供應(yīng)下界之和不小于需求商需求上界之和，則算法TPVDS-A可以在一個(gè)多項(xiàng)式時(shí)間內(nèi)找到TP