Benders分解算法求解帶有容量約束的選址問題

郭 宇

（沈陽理工大學(xué)，遼寧 沈陽 110168）

1 問題描述

帶有容量約束的選址問題是指，在物流配送網(wǎng)絡(luò)中，根據(jù)客戶的位置、客戶對產(chǎn)品的需求量以及各配送中心的最大容量，確定配送中心的位置，以及由選定的配送中心發(fā)往不同客戶的發(fā)貨量，使得總的運輸費用和管理費用達到最小。一般可描述為如下的混合整數(shù)規(guī)劃：

其中：m表示客戶數(shù)，n表示備選的配送中心數(shù)量，di表示客戶i對某種特定物品的需求量，sj表示配送中心j的最大容量，cij表示將單位物品由配送中心j運往客戶i的單位運輸費用，fj表示建造配送中心j的固定費用。變量yj表示是否開放配送中心j，xij表示由配送中心j運往客戶i的貨物量。

2 算法設(shè)計

Benders分解算法是J.F.Benders[1]在1962年首次提出的，目的是用于求解線性混合整數(shù)規(guī)劃的算法，該算法將線性混合整數(shù)規(guī)劃分解成只包含連續(xù)變量的子問題和只包含整數(shù)變量的主問題，首先通過確定復(fù)雜變量（即整數(shù)變量）將原問題轉(zhuǎn)化成只包含連續(xù)變量的易于求解的線性規(guī)劃，再根據(jù)對偶理論利用解的的連續(xù)變量構(gòu)造Benders割反作用于主問題，通過連續(xù)反復(fù)地求解主問題和子問題，最終獲得原問題的最優(yōu)解。

針對本文中的帶有容量約束的選址問題，設(shè)計Benders分解算法如下。

子問題用于求解貨物運輸量的問題。

2）（SPy）的對偶問題可以表示為

3）根據(jù)對偶理論構(gòu)造Benders割，則可得到如下的主問題（MPT）：

3 算例測試

為測試算法的有效性，選取了Beasley[2]中提供的三組不同規(guī)模的問題集進行測試。三組規(guī)模分別為：①10個客戶，10個備選配送中心；②20個客戶，30個備選配送中心；③50個客戶，50個備選配送中心。實驗結(jié)果表明，本文設(shè)計的算法可以在合理的時間內(nèi)獲得較高質(zhì)量的近似解。