郭 宇

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

1 問(wèn)題描述

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

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

2 算法設(shè)計(jì)

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

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

子問(wèn)題用于求解貨物運(yùn)輸量的問(wèn)題。

2）（SPy）的對(duì)偶問(wèn)題可以表示為

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

3 算例測(cè)試

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