物流網(wǎng)絡(luò)選址與路徑優(yōu)化問題模型與

1、物流網(wǎng)絡(luò)選址與 路徑優(yōu)化問題的 模 型 與 啟發(fā) 式 解法 陳松巖 山東交通學(xué)院交通與物流工程系， 山東濟(jì)南 ，今井昭夫 2（1 .摘250023; 2.神戶大學(xué)海事科學(xué)部， 日本神戶 658-0022） 要:以商品從供應(yīng)商，經(jīng)過物流中心（或配送中心 ），配送到最終用戶的整 個過程中所產(chǎn)生的費(fèi) 用最小化為目標(biāo)函數(shù)，提出了求解供 應(yīng)商的最佳位置與數(shù)量、配送中心的 最佳位置與數(shù)量以及從配 送中心到最終用戶的最佳配送路徑 優(yōu)化問題， 建立了問題的數(shù)學(xué)模型， 利用傳統(tǒng)啟發(fā)式算法與模擬 退火法開發(fā)了問題求解的混合啟發(fā) 式解法，并利用人工生成數(shù)據(jù)和實(shí)例 進(jìn)行了計(jì)算驗(yàn)證。對于小 規(guī)模問題，通過與數(shù)理規(guī)劃軟件

2、所 求得的最優(yōu)解進(jìn)行比較可以看出， 所提出的數(shù)學(xué)模型可以準(zhǔn)確地 描述此類問題，所提出的混合啟發(fā)式 解法能夠在短時(shí)間內(nèi)求解問題，并得 到非常接近于最優(yōu)解的近 似解 ;對于大規(guī)模問題， 雖然無法求得 最優(yōu)解進(jìn)行比較，但從實(shí)例計(jì)算結(jié)果 來看，所求解也是較好 的，因此可以認(rèn)為所提出的解法是 有效和良好的，具有較高的實(shí)用價(jià) 值。關(guān)鍵詞 :物流工程 ;選址與路徑優(yōu)化 ;模 擬退火 ;混合啟發(fā)式算法 ;物流網(wǎng)絡(luò)優(yōu) 化中圖分類號 :U491 文獻(xiàn)標(biāo)識碼 :A Model and heuristic solution for location routingproblems of logistics netwo

3、rkChen Song-yan ， Imai Akio (1.D epartmento fT raffica ndL ogisticsE ngineering,S handongJ iaotongU niversity,J inan2 50023 ， Shandong,Ch ina ; 2 . F a cu lty o f M ar iti meS ciences,K obeU niversity,K obe6 58-0022 ，Japan) Abstract: The minimum cost related to the process, in which goods are delive

4、red from suppliers ， through logistics centers (or distribution centers) to ultimate customers ， was taken as the object function, MSDLRP(multi-supplier multi-depot location routing problem)was presented ， including the optimal number and locations of suppliers ，the optimal number and locations of d

5、istribution centers ，the optimalr outes from distribution centers to ultimate.cu stomers,a mathematic model of the problem was put forward ，a mixed heuristic solution was developedbyusing traditional heuristic solution and simulated annealing solution, they were tested by manually generated data and

6、 studied cases. For small-scaled problem, compared with the optimal result got by using planning software, MSDLRP can be described by the mathematic model accurately, the problem can be solved by the heuristic solution during short period ， and theoptimal result is obtained. For big-scaled problem,

7、although the optimal result can not be got ， the result also is better. 2 tabs， 3figs ， 9 refs.Key words:logistics engineering; location routing optimization; simulated annealing; mixed heuristic solution; logistics network optimization 收稿日期 :2006-01-15 作者簡介 :陳松巖 (1963-) ，男，山東招遠(yuǎn)人， 山東交 通學(xué)院副教授，工學(xué)博士，從事

8、物流工程與管理研 究。第3期陳松巖， 等:物流網(wǎng)絡(luò)選址與路徑 優(yōu)化問題的模型與啟發(fā)式解法 119Author resume:csylhj2l)msn.Chen Song-yan(1963-) ，male ，PhD, associate professor, 86-531-80683124 ，com . 及貨物的運(yùn)輸配送路徑進(jìn)行同時(shí)優(yōu) 化，并用拉格朗 日松弛法導(dǎo)出了下界值 E1;G ena 提出了將生產(chǎn)、配 送與庫存問題組合起來，對生產(chǎn)設(shè)施 的選址、配送路 徑及庫存調(diào)整進(jìn)行同時(shí)優(yōu)化的問 題，并利用基于Spanning Tree 法的遺傳算法開發(fā)了近似解法 81本文 以商 品從供應(yīng)商，經(jīng)過物流 中

9、心 （或配送中 心），配送到最終用戶的整個過程中 產(chǎn)生的費(fèi)用最小 化為目的，求得供應(yīng)商的最佳位置 與數(shù)量、配送中心 的最佳位置與數(shù)量以及從配送中心 到最終用戶的最佳配送路徑優(yōu)化問題，即MSDLRP , 提出了數(shù)學(xué)模型和基于啟發(fā)式算法與智能算法的 混合近似解法。問題的描述1.1 問題的假設(shè) 多個 客 戶 分散在各個不同的地 區(qū)，每天的需求量是隨機(jī)的 ;多個物流中心 （配送中心 ） 分散在各個 不同的地區(qū)，可以為任意的客戶提 供配送服務(wù) ;多個 商品供應(yīng)商分散在各個不同的地 區(qū)，可以為任意的 物流中心供貨 ;物流中心 （配送中心 ） 每天的貨流量有容量限制 ;從物流中心 （配送中心 ）到 客戶的配

10、送 車輛為同一種類型的車輛，有載質(zhì) 量限制 ;一條配送路徑上至少有 2個（含2個）以上的客戶。不考 慮 庫 存問題。1.2 問題的數(shù)學(xué)描述 最 小 目 標(biāo)函數(shù)為 Cyx ijk+(1 )氣J 1(- 、 /-W藝藝L,ip+ 藝H;w;+藝藝sEG :ET iETUC JETUC云。習(xí) d;z;J + 習(xí) FkiEr JEJ *EK約束條件為習(xí)習(xí) xgk、夕、 1了卜、產(chǎn)9 口乃 j 4產(chǎn)r、了 、了 r、藝藝 x 。一 1kEKiETUCziik= 0Q E C)(iE TUC,kEK)(k K)、. 了、夕、 ./ 、，產(chǎn)二d八b1價(jià)6了、了、 rr 、子了、0 引言物流 網(wǎng) 絡(luò) 優(yōu)化問題

11、包括商品從 原材料供應(yīng)商到 制造商，經(jīng)過中間庫存和配送中心到 最終客戶的整 個流程中有關(guān)設(shè)施選址、 物流路徑、 產(chǎn)量、運(yùn)輸量及 庫存量的確定等決策項(xiàng)目，其目的 是在滿足客戶需 求的基礎(chǔ)上，使設(shè)施設(shè)置費(fèi)用、生產(chǎn) 費(fèi)用、運(yùn)輸與配 送費(fèi)用及庫存費(fèi)用最小化。但是由 于這些決策項(xiàng)目 涉及到多個階段和多個層次，利用數(shù) 理手段解決此 類問題變得異常復(fù)雜和困難， 為此， 許多研究者將問 題分為若干個子問題，將子問題作為 獨(dú)立的問題進(jìn) 行研究，取得了可喜的成果，如車 輛路徑問題(VRP)、設(shè)施選址問題(FLP)等。但 這些問題只能解決物流網(wǎng)絡(luò)中的局部優(yōu)化，無法 解決物流網(wǎng)絡(luò)的 整體優(yōu)化，為此，許多研究者將局 部

12、優(yōu)化問題加以整 合與擴(kuò)展，進(jìn)行了大量的更貼近現(xiàn) 實(shí)的研究。Dhaenens-Flip 。提出了多個設(shè)施的 生產(chǎn)與配送問題(Multi-Facility Production and Distribution Prob lem) ， 將生產(chǎn)與配送問題組合在一起進(jìn)行 整體優(yōu) 化，并采用分枝定界法求得了 最優(yōu)解 C7;M elkote 與 Daskin 將設(shè)施選址與運(yùn)輸網(wǎng)絡(luò)問題 加以整合，提出 了選址與網(wǎng)絡(luò)同時(shí)優(yōu)化問題，并利 用混合整數(shù)規(guī)劃 軟件求得了最優(yōu)解 21;G oetschalckx3 提出 T 將國 際運(yùn)輸問題與生產(chǎn)、配送問題整合 在一起進(jìn)行同時(shí) 優(yōu)化的數(shù)學(xué)模型，并采用主分割 法 (Pri

13、mal Decom position) 等啟發(fā)式算法開發(fā) T 近似解 法 ;Hwang 提 出了在保證既定的服務(wù)水平的前提 下，將工廠、倉庫 與配送中心的選址及配送路徑進(jìn)行 同時(shí)優(yōu)化的問題，并利用集合覆蓋問題 (Set-Covering Problem) 的 方法、 0-1 規(guī)劃法 (0-1 Programming Method) 及改 良的遺傳算法 (Improved Genetic Algorithm) 進(jìn)行T求解41;Wu利用模擬退火法(Simulated Annea ling:SA )和禁忌搜索法 (Tabu-Search:TS)開發(fā)T多物流中心條件下的 LRP (Multi-Depo

14、t Location- RoutingP roblem :M DLRP) 的近 似解法 6;S y am將古典 FLP 加以擴(kuò)展，提出了將 原材料庫存成本、 生產(chǎn)成本、成品庫存成本、訂貨成 本、運(yùn)輸成本及工 廠與倉庫固定成本進(jìn)行同時(shí)優(yōu)化的 問題，并利用模 擬退火法與拉格朗日松弛法分別 求得最優(yōu)解 6Amiri 提出了供應(yīng)鏈系統(tǒng)中的運(yùn)輸與 配送網(wǎng)絡(luò)優(yōu)化 問題，將工廠、倉庫與配送中心的 位置、數(shù)量與容量(jE C,k E K)習(xí) y，一 1ZD,y;k Q k(j(k任C)任K)L.J.z ijk 一又 x;tk (zE T l JC ,kE K )jETUC藝見 xijk (1 (k 任 K)

15、(9)iET jEC120 交通運(yùn)輸工程學(xué)報(bào) 2006年見d，二。G V;w;j任C習(xí) (Xi,+ -hjk) 一 zj2,isi芝，kEK ) (13)U;A Ujk+Nx ijk G N 一 1 (i,j Es,k E K)習(xí) Pi)藝 Djz;j i E T )a 任 c jEC(14)(15) 問題規(guī)模目標(biāo)值運(yùn)行時(shí)間 /sNc=3,NT=3,Nc=8 388. 5 3Nc=3,N 下=3 , NC=10 421. 2 21Nc=3,NT=3,Nc=12 685. 0 580Nc=3,NT=3,Nc=14 874. 1162 000注:NG為供應(yīng)商數(shù)量，NT為配送中心數(shù)量，Nc為客 戶數(shù)

16、量。見 pe Be（9任G）（i，jETUC，kC-K）（任T）（iET，jEC）（任C,k任K）（16）xijk 任 0，1W；任（0, 1乙任0, 1Y k 任0, 1（17）（18）（19）（20）式中:G為供應(yīng)商的集合;T為配送中 心的集合 ;C為客戶的集合；K為車輛的集合;q為 車輛 k 的最大載質(zhì)量；S%C的部分集合；C。為從 點(diǎn)i到點(diǎn)j的距離;Bg為供應(yīng)商9的最大供應(yīng)量;V 為配送中心i的最大貨物通過量；D;為客戶j的需 求量;H，為配送中心的固定費(fèi)用；L，為從供應(yīng)商 9到配送中心i的單位運(yùn)輸費(fèi)用；F*為車輛k的固 定費(fèi)用刀為與通過量有關(guān)的系數(shù);x,為對于 車輛k，如果點(diǎn)i以 后

17、的訪問點(diǎn)是點(diǎn) J ，即為 1，否則 為。;y;k為如果點(diǎn)1的貨物由車輛k配送，即為1,否則 為。 ;二為如果使用配送中心i，即為1,否則為0;z。為如果客戶J由配送中心提供服務(wù)，即為1， 否則為O;p。為從供應(yīng)商g到配送中心i的供應(yīng)量。其 中 x;k,z v ;,y; k,z和P，為決策變量。問題的求解 為 了驗(yàn) 證 上述數(shù)學(xué)模型的正確 性，用數(shù)理規(guī)劃 商用軟件 LINGO 8.0 對小規(guī)模問 題進(jìn)行了數(shù)值計(jì) 算，結(jié)果見表 1?？梢钥闯?，隨著問 題的規(guī)模擴(kuò)大， 計(jì)算時(shí)間急劇增加 ;當(dāng)客戶達(dá)到 14個 時(shí)，計(jì)算時(shí)間 長達(dá)45 h,顯然無法滿足解決現(xiàn)實(shí)問 題的需要。為 了滿足解決現(xiàn)實(shí)問題的需要，有

18、必 要開發(fā)出一種能 夠在合理的時(shí)間內(nèi)求得準(zhǔn)最優(yōu)解的 近似算法。傳統(tǒng) 啟 發(fā) 式算法能夠在短時(shí)間 內(nèi)求得局部最優(yōu) 解，但往往容易陷于局部最優(yōu)，而 無法求得全局最優(yōu) 解。智能啟發(fā)式算法能夠求得全局 最優(yōu)解，但計(jì)算時(shí) 間相對較長。如果能夠?qū)烧呓Y(jié)合 起來，既可以防止 求解過程陷于局部搜索無法跳出， 保證全局解的搜 索，又可以縮短搜索時(shí)間，達(dá)到在 短時(shí)間內(nèi)求得全局 最優(yōu)解的目的?；谏鲜隹紤]，本 文提出了圖 1的將 用啟發(fā)式算法求得初期解 通過交換配送中心間的路徑進(jìn)行第 t 次 解 的 改 善 通過交換同一路徑中客戶的位置 （2- OPT 法）進(jìn)行第 2次解的改善 通過交換不同路徑中的客戶 進(jìn) 行 第

19、3 次解的改善 圖 1 基 于 S A 的混 合 啟 發(fā) 式 算 法 Fig .1 M ixe dh eu ris tic a lgorithm basedo nS A 傳統(tǒng)啟發(fā)式算法與智能啟發(fā)式算法 相結(jié)合的混合算 法，以期在短時(shí)間內(nèi)求得全局 最優(yōu)解 191計(jì)算分析為了對SA的參數(shù)進(jìn)行設(shè)定，進(jìn)行 了預(yù)備實(shí)驗(yàn)， 并確定參數(shù)如下 :初始溫度 To 為 200,冷卻率a為0.7，與溫度相關(guān)的循環(huán)次數(shù)調(diào)整參數(shù) 召為飛 .1，最 大循環(huán)次數(shù)將按照問題規(guī)模的大小 做適當(dāng)?shù)脑O(shè)定， 數(shù)據(jù)采用人工生成數(shù)據(jù)，在 200 km X 200 km 的區(qū) 域內(nèi)隨機(jī)生成指定個數(shù)的供應(yīng)商、 配送中心和客戶， 并生成距離矩

20、陣和客戶需求量 ;采用 C 語言編程， 計(jì)算結(jié)果見表 2。從表 2中的結(jié)果比較 可以看出， 表2 最優(yōu)解與近似解比較 Ta b.2 Comparisono fo ptimal.solutiona nda pproximates olution 問題規(guī)模最優(yōu)解近似解誤差 / 目標(biāo)值 運(yùn)行時(shí)間 /5 目標(biāo)值運(yùn)行時(shí)間 /5 % Na=3,NT=3,Nc=8 388.5 3 396. 5 1 2. 1 坑=3,N T= 3,NC=1O 421.2 21421.2 1 0.0 Nc=3,NT=3,Nc=12 685.0 580 692.0 1 1.0 NC=3,NT=3,NC=14 874. 1 162

21、 000 889.5 1 2.1 第_在_ 應(yīng) 用 實(shí) 例中，將港口作為供 應(yīng)商來考慮，以進(jìn) 口貨物從港口經(jīng)配送中心配送到客 戶過程中發(fā)生的 費(fèi)用最小化為目的，以港口的數(shù)量和 位置、配送中心 數(shù)量和位置作為對象進(jìn)行優(yōu)化。實(shí) 例的區(qū)域選擇山 東省，候選港口為天津港、煙臺港、 威海港、青島港、 日照港和連云港等 6處，候選配送中心設(shè)置于山東省除港口城市以外的 13個地級市，設(shè) 定客戶分別位于90個縣 （包括縣級市 ）。為了分析候 選港口和配 送中心的數(shù)量及位置與目標(biāo)值之間 的關(guān)系，在計(jì)算 過程中，候選港口和配送中心的數(shù)量 分別從 1開始增加 （港口的位置為隨機(jī)選擇 ），計(jì)算 結(jié)果見圖 2,30 5 r ， 6 r二 4卜一目一 ， 叫口- 口二丫氣人汽才、 _ _X ，! X 4 卜戶氣了、卜。代仁目。刃Zs 2 卜掣、 L;二 】- 2 卜口n ,1 田丁二1一 00o 一一 -*- -* 0 一一 -O 一 01 2 3 4 5 6 1 3 5 7 9 11 13 港口數(shù)量配送中心數(shù)量 圖 2