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

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

2、所 求得的最优解进行比较可以看出， 所提出的数学模型可以准确地 描述此类问题，所提出的混合启发式 解法能够在短时间内求解问题，并得 到非常接近于最优解的近 似解 ;对于大规模问题， 虽然无法求得 最优解进行比较，但从实例计算结果 来看，所求解也是较好 的，因此可以认为所提出的解法是 有效和良好的，具有较高的实用价 值。关键词 :物流工程 ;选址与路径优化 ;模 拟退火 ;混合启发式算法 ;物流网络优 化中图分类号 :U491 文献标识码 :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-) ，男，山东招远人， 山东交 通学院副教授，工学博士，从事

8、物流工程与管理研 究。第3期陈松岩， 等:物流网络选址与路径 优化问题的模型与启发式解法 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 问题的假设 多个 客 户 分散在各个不同的地 区，每天的需求量是随机的 ;多个物流中心 （配送中心 ） 分散在各个 不同的地区，可以为任意的客户提 供配送服务 ;多个 商品供应商分散在各个不同的地 区，可以为任意的 物流中心供货 ;物流中心 （配送中心 ） 每天的货流量有容量限制 ;从物流中心 （配送中心 ）到 客户的配

10、送 车辆为同一种类型的车辆，有载质 量限制 ;一条配送路径上至少有 2个（含2个）以上的客户。不考 虑 库 存问题。1.2 问题的数学描述 最 小 目 标函数为 Cyx ijk+(1 )气J 1(- 、 /-W艺艺L,ip+ 艺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、包括商品从 原材料供应商到 制造商，经过中间库存和配送中心到 最终客户的整 个流程中有关设施选址、 物流路径、 产量、运输量及 库存量的确定等决策项目，其目的 是在满足客户需 求的基础上，使设施设置费用、生产 费用、运输与配 送费用及库存费用最小化。但是由 于这些决策项目 涉及到多个阶段和多个层次，利用数 理手段解决此 类问题变得异常复杂和困难， 为此， 许多研究者将问 题分为若干个子问题，将子问题作为 独立的问题进 行研究，取得了可喜的成果，如车 辆路径问题(VRP)、设施选址问题(FLP)等。但 这些问题只能解决物流网络中的局部优化，无法 解决物流网络的 整体优化，为此，许多研究者将局 部

12、优化问题加以整 合与扩展，进行了大量的更贴近现 实的研究。Dhaenens-Flip 。提出了多个设施的 生产与配送问题(Multi-Facility Production and Distribution Prob lem) ， 将生产与配送问题组合在一起进行 整体优 化，并采用分枝定界法求得了 最优解 C7;M elkote 与 Daskin 将设施选址与运输网络问题 加以整合，提出 了选址与网络同时优化问题，并利 用混合整数规划 软件求得了最优解 21;G oetschalckx3 提出 T 将国 际运输问题与生产、配送问题整合 在一起进行同时 优化的数学模型，并采用主分割 法 (Pri

13、mal Decom position) 等启发式算法开发 T 近似解 法 ;Hwang 提 出了在保证既定的服务水平的前提 下，将工厂、仓库 与配送中心的选址及配送路径进行 同时优化的问题，并利用集合覆盖问题 (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-Depo

14、t Location- RoutingP roblem :M DLRP) 的近 似解法 6;S y am将古典 FLP 加以扩展，提出了将 原材料库存成本、 生产成本、成品库存成本、订货成 本、运输成本及工 厂与仓库固定成本进行同时优化的 问题，并利用模 拟退火法与拉格朗日松弛法分别 求得最优解 6Amiri 提出了供应链系统中的运输与 配送网络优化 问题，将工厂、仓库与配送中心的 位置、数量与容量(jE C,k E K)习 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 交通运输工程学报 2006年见d，二。G V;w;j任C习 (Xi,+ -hjk) 一 zj2,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,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为供应商数量，NT为配送中心数量，Nc为客 户数

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为供应商的集合;T为配送中 心的集合 ;C为客户的集合；K为车辆的集合;q为 车辆 k 的最大载质量；S%C的部分集合；C。为从 点i到点j的距离;Bg为供应商9的最大供应量;V 为配送中心i的最大货物通过量；D;为客户j的需 求量;H，为配送中心的固定费用；L，为从供应商 9到配送中心i的单位运输费用；F*为车辆k的固 定费用刀为与通过量有关的系数;x,为对于 车辆k，如果点i以 后

17、的访问点是点 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，为决策变量。问题的求解 为 了验 证 上述数学模型的正确 性，用数理规划 商用软件 LINGO 8.0 对小规模问 题进行了数值计 算，结果见表 1。可以看出，随着问 题的规模扩大， 计算时间急剧增加 ;当客户达到 14个 时，计算时间 长达45 h,显然无法满足解决现实问 题的需要。为 了满足解决现实问题的需要，有

18、必 要开发出一种能 够在合理的时间内求得准最优解的 近似算法。传统 启 发 式算法能够在短时间 内求得局部最优 解，但往往容易陷于局部最优，而 无法求得全局最优 解。智能启发式算法能够求得全局 最优解，但计算时 间相对较长。如果能够将两者结合 起来，既可以防止 求解过程陷于局部搜索无法跳出， 保证全局解的搜 索，又可以缩短搜索时间，达到在 短时间内求得全局 最优解的目的。基于上述考虑，本 文提出了图 1的将 用启发式算法求得初期解 通过交换配送中心间的路径进行第 t 次 解 的 改 善 通过交换同一路径中客户的位置 （2- OPT 法）进行第 2次解的改善 通过交换不同路径中的客户 进 行 第

19、3 次解的改善 图 1 基 于 S A 的混 合 启 发 式 算 法 Fig .1 M ixe dh eu ris tic a lgorithm basedo nS A 传统启发式算法与智能启发式算法 相结合的混合算 法，以期在短时间内求得全局 最优解 191计算分析为了对SA的参数进行设定，进行 了预备实验， 并确定参数如下 :初始温度 To 为 200,冷却率a为0.7，与温度相关的循环次数调整参数 召为飞 .1，最 大循环次数将按照问题规模的大小 做适当的设定， 数据采用人工生成数据，在 200 km X 200 km 的区 域内随机生成指定个数的供应商、 配送中心和客户， 并生成距离矩

20、阵和客户需求量 ;采用 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 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 第_在_ 应 用 实 例中，将港口作为供 应商来考虑，以进 口货物从港口经配送中心配送到客 户过程中发生的 费用最小化为目的，以港口的数量和 位置、配送中心 数量和位置作为对象进行优化。实 例的区域选择山 东省，候选港口为天津港、烟台港、 威海港、青岛港、 日照港和连云港等 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