物流网络选址与路径优化问题模型与

1、物流网络选址与 路径优化问题的 模 型 与 启发 式 解法陈松岩 山东交通学院交通与物流工程系， 山东济南 ，今井昭夫 2(1 . 摘250023; 2.神户大学海事科学部， 日本神户658-0022)要:以商品从供应商，经过物流中心（或配送中心 ），配送到最终用户的整 个过程中所产生的费用最小化为目标函数，提出了求解供 应商的最佳位置与数量、配送中心的 最佳位置与数量以及从配送中心到最终用户的最佳配送路径 优化问题， 建立了问题的数学模型， 利用传统启发式算法与模拟 退火法开发了问题求解的混合启发 式解法，并利用人工生成数据和实例 进行了计算验证。对于小规模问题，通过与数理规划软件所 求得的

2、最优解进行比较可以看出， 所提出的数学模型可以准确地 描述此类问题，所提出的混合启发式 解法能够在短时间内求解问题，并得 到非常接近于最优解的近 似解;对于大规模问题， 虽然无法求得 最优解进行比较，但从实例计算结果 来看，所求解也是较好 的，因此可以认为所提出的解法是 有效和良好的，具有较高的实用价 值关键词 :物流工程 ;选址与路径优化 ;模 拟退火 ;混合启发式算法 ;物流网络优 化中图分类号 :U491 文献标识码 :AModel and heuristic solution for location routingproblems of logistics networkChen S

3、ong-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 delivered from su

4、ppliers ，through logistics centers (ordistribution 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 ofdistribution cen

5、ters ，the optimalr outes from distribution centers to ultimate.cu stomers,amathematic 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 studied cases.

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

7、mal result can not be gotthe result also is better. 2 tabs， 3 figs ， 9 refs.Key words:logistics engineering;location routing optimization;simulated annealing; mixedheuristic solution; logistics network optimization收稿日期 :2006-01-15作者简介 :陈松岩 (1963-) ，男，山东招远人， 山东交 通学院副教授，工学博士，从事物流工程与管理研 究。第 3期陈松岩， 等:物流

8、网络选址与路径 优化问题的模型与启发式解法 119Author resume:csylhj2l)msn.Chen Song-yan(1963-) ，male ，PhD,associate professor, 86-531-80683124 ， com .及货物的运输配送路径进行同时优 化，并用拉格朗 日松弛法导出了下界值 E1;G ena 提出了将生产、配 送与库存问题组合起来，对生产设施 的选址、配送路径及库存调整进行同时优化的问 题，并利用基于Spanning Tree 法的遗传算法开 发了近似解法 81本文 以商 品从供应商，经过物流 中心（或配送中 心），配送到最终用户的整个过程中

9、产生的费用最小 化为目的，求得供应商的最佳位置 与数量、配送中心 的最佳位置与数量以及从配送中心 到最终用户的最佳配送路径优化问题，即MSDLRP , 提出了数学模 型和基于启发式算法与智能算法的 混合近似解法。1 问题的描述1.1 问题的假设多个 客 户 分散在各个不同的地 区，每天的需求量是随机的 ;多个物流中心 （配送中心 ） 分散在各个 不同的地区，可以为任意的客户提 供配送服务 ;多个 商品供应商分散在各个不同的地 区，可以为任意的 物流中心供货 ;物流中心 （配送中心 ） 每天的货流量有容量限制 ;从物流中心 （配送中心 ）到 客户的配送 车辆为同一种类型的车辆，有载质 量限制 ;

10、一条配送路径上至少有 2个（含2个）以上的客户。不考 虑 库 存问题。1.2 问题的数学描述最 小 目 标函数为Cyx ijk+(1 )气J 1(- 、 /-W艺艺L,i P+艺H;w;+艺艺sEG :ET iETUC JETUC云。习 d;z;J + 习 FkiEr JEJ *EK约束条件为习习 xgk、夕、 1了卜、产9 口乃 j 4产r、了 、了 r、艺艺x。一 1kEKiETUCziik= 0Q E C) (iE TUC,kEK)(k K)、. 了、夕、 ./ 、，产二d八b1价6了、了、 rr 、子了、0 引言物流 网 络 优化问题包括商品从原材料供应商到制造商，经过最终客户的整11

11、间库存和配送中心到个流程中有关设施选址、 物流路径、 产量、运输量及 库存量的确定等决策项目，其目的是在满足客户需 求的基础，使设施设置费用、生产费用、运输与配送费用及库存费用最小化。但是由 于这些决策项目 涉及到多个阶段和多个层次，利用数 理手段解决此类问题变得异常复杂和困难， 为此， 许多研究者将问题分为若个子问题，将子问题作为 独立的问题进行研究，取得了可喜的成果，如车辆路径问题(VRP)、设施选址问题(FLP)等。但这些问题只能解决物流网络中的局部优化，无法解决物流网络的 整体优化，为此，许多研究者将局 部优化问题加以整 合与扩展，进行了大量的更贴近现 实的研究。Dhaenens-Fl

12、ip 。提出了多个设施的 生产与配送问题(Multi-Facility Production andDistribution Prob lem) ， 将生产与配送问题组合在一起进行 整体优 化，并采用分枝定界法求得了 最优解 C7;M elkote 与Daskin 将设施选址与运输网络问题 加以整合，提出 了选址与网络同时优化问题，并利 用混合整数规划 软件求得了最优解 21;G oetschalckx3 提出 T 将国 际运输问题与生产、配送问题整合 在一起进行同时 优化的数学模型，并采用主分割 法 (Primal Decom position) 等启发式算法开发 T 近似解 法 ;Hwan

13、g 提 出了在保证既定的服务水平的前提 下，将工厂、仓库 与配送中心的选址及配送路径进行 同时优化的问题，并利用集合覆盖问题 (Set-Covering Problem) 的 方法、 0-1 规划法 (0-1 Programming Method) 及改 良的遗传算法 (Improved Genetic Algorithm) 进行T求解41;Wu利用模拟退火法(Simulated Annea ling:SA )和禁忌搜索法 (Tabu-Search:TS)开发T多物流中心条件下的 LRP (Multi-Depot Location- RoutingP roblem :M DLRP) 的近 似解

14、法 6;S y am将古典 FLP 加以扩展，提出了将 原材料库存成本、 生产成本、成品库存成本、订货成 本、运输成本及工 厂与仓库固定成本进行同时优化的 问题，并利用模 拟退火法与拉格朗日松弛法分别 求得最优解 6Amiri 提出了供应链系统中的运输与 配送网络优化 问题，将工厂、仓库与配送中心的位置、数量与容量(jE C,k E K)习 y，一 1ZD,y;k2,isi芝，kEK ) (13)U;A Ujk+Nx ijk G N 一 1 (i,j Es,k E K)习 Pi)艺 Djz;j i E T )a 任 c jEC(14)(15) 问题规模目标值运行时间 /sNc=3,NT=3,N

15、c=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为供应商数量，NT为配送中心数量，Nc为客 户数量。见 pe Be(9任G)(i,jETUC,kC-K)(任 T)(iET,jEC)(任C,k任K)(16)xijk 任 0，1W；任(0, 1z;i任 0, 1Y k 任0, 1(17)(18)(19)(20)式中:G为供应商的集合;T为配送中 心的集合 ;C为客户的集合；K为车辆的集合;q为 车辆k的最大载质量；S%C的部分集合；C。为从 点i到点

16、j的距离;Bg为供应商9的最大供应量；V 为配送中心i的最大货物通过量；D;为客户j的需 求量；H，为配送中心的固定费用；L，为从 供应商 9到配送中心i的单位运输费用；F*为车辆k的固 定费用刀为与通过量有关的系数;x，为对于 车辆k，如果点i以后的访问点是点J，即为1否则 为。;y;k为如果点1的货物由车辆k配送，即为1,否则 为。 ;二为如果使用配送中心i，即为1,否则为 0;z。为如果客户J由配送中心 提供服务，即为1， 否则为O;p。为从供 应商g到配送中心i的供应量。其 中 x;k,z v ;,y; k, z和P，为决策变量2 问题的求解述数学模型的正确为 了验 证 上 性，用数理

17、规划 商用软件 LINGO 8.0 对小规模问 题进行了数值计 算，结果见表 1。可以看 题的规模扩大， 计算时间急剧增加 ;当客户达到 14个 时，计算时间长达45 h,显然无法满足解决现实问 题的需要。为 了满足解决现实问题的需要，有必 要开发出一种能 够在合理的时间内求得准最优解的 近似算法。传统 启 发 式算法能够在短时间内求得局部最优 解，但往往容易陷于局部最优，而 无法求得全局最优 解。智能启发式算法能够求得全局 最优解，但计算时 间相对较长。如果能够将两者结合 起来，既可以防止 求解过程陷于局部搜索无法跳出， 保证全局解的搜 索，又可以缩短搜索时间，达到在 短时间内求得全局 最优

18、解的目的。基于上述考虑，本文提出了图 1的将 用启发式算法求得初期解 通过交换配送中心间的路径进行第 t 次 解 的 改 善 通过交换同一路径中客户的位置 （2- OPT 法）进行第2次解的改善 通过交换不同路径中的客户 进 行 第3 次解的改善图 1 基 于 S A 的混 合 启 发 式 算 法 Fig .1 M ixe dh eu ris tic a lgorithm basedo nS A 传统启发式算法与智能启发式算法 相结合的混合算 法，以期在短时间内求得全局 最优解 1913 计算分析为了对SA的参数进行设定，进行了预备实验，并确定参数如下 :初始温度 To 为200，冷却率a为0

19、.7，与温度相关的循环次数调整参数 召为飞 .1，最 大循环次数将按照问题规模的大小 做适当的设定， 数据采用人工生成数据，在 200 km X 200 km 的区 域内随机生成指定个数的供应商、 配送中心和客户， 并生成距离矩阵和客户需求量 ;采用 C 语言编程，计算结果见表 2。从表 2中的结果比较可以看出，表2 最优解与近似解比较Ta b.2 Comparisono fo ptimal.solutiona nda pproximates olution问题规模最优解近似解误差 /目标值 运行时间 /5 目标值运行时间 /5 %Na=3,NT=3,Nc=8 388.5 3 396. 5 1

20、 2. 1坑=3,N T= 3,NC=1O 421.2 21421.2 1 0.0Nc=3,NT=3,Nc=12 685.0 580 692.0 1 1.0NC=3,NT=3,NC=14 874. 1 162 000 889.5 1 2.1 第 _在_ 应 用 实 例中，将港口作为供 应商来考虑，以进 口货物从港口经配送中心配送到客 户过程中发生的 费用最小化为目的，以港口的数量和 位置、配送中心数量和位置作为对象进行优化。实 例的区域选择山 东省，候选港口为天津港、烟台港、 威海港、青岛港、 日照港和连云港等 6处，候选配送中心设置于山东 省除港口城市以外的 13个地级市,设定客户分别位于90个县 （包括县级市 ）。为了分析候 选港口和配 送中心的数量及位置与目标值之间过程中,候选港口和配送中心的数量分别从 1开始增加 （港口的位置为随机选择 ）,计算 结果见图 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 港口数量配送中心数量 图 2 港 口 数 量 与 图