基于遗传算法的城市物流网络设计研究概要.doc

第17卷 第5期 2008年lO月运 筹 与 管 理OPERATIONS RESEARCH AND MANAGEMENT SCIENCEV01.17,No.5 Oct.2008基于遗传算法的城市物流网络设计研究童明荣12, 薛恒新1(1.南京理工大学经济管理学院,江苏南京210094;2.宁波市政府发展研究中心.浙江宁波315000摘 要:本文探讨的是政府主导下的城市物流网络设计。首先构建了由物流园区、物流中心、配送中心组成的三 层城市正向物流基础设施网络;接着提出了一个混合整数规划模型,优化目标是使整个城市的物流费用达到最 小,并用遗传算法求解;最后给出了一个算例,说明了模型和算法的有效性。关键词:物流工程;城市物流网络;遗传算法;物流系统规划中图分类号:U492.3文章标识码:A 文章编号:1007-3221(200805006904Research on the City Logistics Design Based on Genetic AlgorithmTONG Mingron91”,XUE Hengxin(1.School of Economics&Management,Nanjing University of Science&Technology,Nanjing 210094,China; 2.Ningbo Municipal Development&Research Center,Ningbo 315000,ChinaAbstract:This paper discusses the design of the city logistics net dominated by the government.Firstly,the threelayer city losgitics net composed of the logistics park,the logistics centerand the distribution center is con structed.After that,a mixed-integer programming mode is proposed,the optimal target is to minimize the whole city logistic fees,and the model is solved by genetic algorithm.Finally,a numerical example is given,and the result shows the approach is effective.Key words:logistics engineering;city logistics net;genetic algorithm;logistics system planning0引言城市物流是指物品在城市内部的实体流动,城市与外部区域的货物集散以及城市废弃物清理的过程。 城市物流有两种发展模式:一种是由企业自发地发展各类物流业务,另一种是由政府统一规划,建立城市 物流系统。本文探讨的政府主导下的城市物流基础设施规划。做好城市物流的规划,有利于提升城市物流 行业的水平,缓解城市交通压力,改善城市投资环境。研究表明,构建由物流园区、物流中心、配送中心共同组成的三层物流服务体系是建设现代城市物流 网络的合理途径。根据规划,北京在2010年将初步形成由3个物流园区、4个物流中心和10个配送中心 构成的覆盖全市的高效物流网络;2010年上海市的物流网络则由6个物流园区,lO个物流中心,20个配 送中心构成。理想的城市物流系统运转模式是:市域范围及进出城市的物流量绝大部分都先进入物流园区进行集 中处理,先进的城市物流体系依据物流信息中心的信息统一调度这些商品,将它们少品种大批量地转运到 物流中心,经过集中储存再将它们进行多品种、小批量送到配送中心,配送中心再将商品配送给零售商。收稿日期:2008-02-10基金项目:国家863/CIMS主题资助项目(2002AA414040作者简介:童明荣(1980.男.博士研究生.研究方向:物流工程;薛恒新(1946一,男,教授、博士生导师.研究方向:物流和供应链管理。70运 筹 与 管 理 2008年第17卷目前,研究企业主导的物流网络设计的文献已有不少231,但是政府主导的城市物流网络设计还是较 新的研究领域,目前的研究报道很少。本文提出了一个混合整数规划模型,计算城市整体的物流运输费用 和物流枢纽的建设费用,优化的目标函数是使整个城市的物流费用达到最小。2模型的建立2.1问题的提出考察图1所示的城市物流网络,要解决如下问题:零售点数量及地址确定,在待选的物流园区、物流中 心和配送中心中分别选择开设哪些设施,使城市物流总费用最小。图1城市物流网络结构图2.2模型假设及符号说明为了便于分析和说明问题,我们作了如下的假设和简化:(1单位运输费用与距离成线性关系;(2每个设施之间是相互独立的,不存在互相调用的情况;(3仅在规定的候选地点范围内选址,并且他们均有最大的数量限制;(4各种设施的处理能力以及投资成本、单位运营成本已知;(5仅考虑单周期可计量的经济成本,不考虑时间成本、社会效益等;(6各个零售点在单位时间内的商品需求为已知常量;为方便叙述,引入如下符号:下标f表示已知的零售商的地点,i El,2,;_表示可能开设配送中心的地点,Jl,2,.,;后 表示可能开设物流中心的地点,k1,2,K;Z表示可能开设的物流园区的地点,Z1,2,。A, 表示配送中心的仓库容量;巩表示物流中心的仓库容量;C。表示物流园区的仓库容量;E,F。,G,分别表示 配送中心、物流中心、物流园区的设施投资成本;日,M。,N,分别表示配送中心、物流中心、物流园区单位时 间的运作费用;x,K,Z。分别表示在第_个待选配送中心、第后个待选物流中心和第Z个待选物流园区建 物流设施的决策变量,而x,y和z分别表示允许建立的配送中心、物流中心和物流园区的最大数目;x,= 0,1,Yk=0,1,Z,=0,1表示x,K和z;取值为0或1。髫口。分别为将配送中心_的物品运送到零售点i的数量和单位运输费用;Yjt,bit分别为将物流中心后 的物品运送到配送中心.的数量和单位运输费用;铂,Ckl分别为将物流园区Z的物品运送到物流中心I|的 数量和单位运输费用;u;为零售点i单位时间内产生的物品需求数量。口。,bjk,Ckl等单位运输费用可以通 过物流设施间距离计算得到;茗,降,石“等不同层级物流节点之间商品运输数量,本文借鉴交通规划中的四 阶段理论提出四阶段法预测得到:(1采用组合预测法,对每个零售点物品需求进行分析和预测;(2采用 L-OD小区分类的方法,得出物流量分方向的分布情况;(3确定城市物流网络中的主要物流通道;(4采 用总量分配修正法,确定两层物流节点之间物流量的分配。2.3数学模型以单位时间内系统运作费用最小为目标函数建立混合整数规划模型第5期 童明荣,等:基于遗传算法的城市物流网络设计研究 7lmin:C=荟荟口一乃+善荟%一K+荟荟c萨“K乙+荟(易+马-+ J K L(Ft+M。屹+三(G,+N一zr%=蚝 (2 髫口A,巧,%B。K,:“ctX, (3 膏u=石Il (4 =X,Yk=Y,Zr=Z (5, t l目标函数(1由整个网络系统的运输费用各设施的运作费用组成。约束条件中:式(2表示零售点的物品需求应得到完全满足;式(3表示各设施的容量约束;式(5表 各设施的数量限制。3遗传算法上述模型中,当整个网络节点较多时,问题就变成一个NP难题,用分枝定界法等经典数学方法求解 时不可避免地存在“维数灾”问题,本文用遗传算法求解。3.1基本步骤遗传算法的运行过程为一个典型的迭代过程,其基本步骤为H】:(1选择编码策略,把参数集合和域 转换为位串结构空间;(2定义适应值函数;(3确定遗传策略,包括选择、交叉、变异方法,确定交叉率、变 异率等参数;(4随机初始化生成群体;(5计算群体中个体位串解码后的适应值;(6按照遗传策略,运用 选择、交叉和变异算子作用于群体,形成下一代群体;(7判断迭代中止原则是否满足,不满足则返回步骤 6。3.2参数控制遗传算法中的主要运行参数有:基因串的长度、群体大小M、交叉率P。变异率P。,和进化代数T。M 取值较小可能会导致GA早熟,取值过大时则会降低GA的运行速度,一般取20一50。中止代数是表示遗 传算法中止条件的参数,一般建议取1002000。虽然有大量的文献研究并给出了GA的交叉率、变异率等参数的取值范围,但是对于不同的优化问 题,这些静态的参数控制策略并非总能得到理想的效果。Zbigniew Michalewic1指出遗传算法在本质上是 一个动态的适应过程,演化过程的不同阶段具有不同的最优参数值,而实践表明动态的参数控制策略对 GA来说更积极有效。本文采用确定的参数控制策略,根据某个确定的规则修改参数,即用P(f代替参数 P,其中,t为GA的演化代数。4算例假设系统有20个零售点,17个待选配送中心,8个待选物流中心,4个待选物流园区,配送中心、物流 中心和物流园区的最大允许数目分别为10、4和2。限于篇幅,零售点和各待选物流物流设施的坐标、各 设施相互之间的距离、商品数量和单位运输费用、各设施的仓库容量和单位时间的运作费用等数据表格省 略。采用MATLAB语言编程计算,目前已有几个遗传算法工具箱,本文采用的是MATLAB7.0包含的 GADS工具箱1。编码采用十进制编码,基因交叉采用下式进行:c:l=Otcsn-1+(1一aict茬-1c:=Oict娌-1+(1一aictil-1(6 其中,c:l-1,cZl是父代染色体,c:。,c:2是子代染色体,a。是(0。1问的一个随机数,i=1,2,k,(k是进 行交叉的染色体的对数。72运 筹 与 管 理 2008年第17卷经反复试验,本文采用线性函数,产生得到交叉率和变异率:P。=0.55+0.2X(当前代数/总代数,P。=0.005+0.005X(当前代数/总代数,M=30,T=500。 本文采用最大迭代数作为遗传算法的停止准则。I晨忧崆一向I。、.、弋l、 、;2 1.5 l 0.5O 51015202530l伊 变量维数j=:,。心O 50100150200250300350400450500迭代次数图2算法仿真过程50454035簧30撄25谣2015105O05101520253035404550图3城市物流网络结构图如图2所示,在前50代计算过程中,随着物流枢纽的空间分布和规模的变化,城市物流总费用明显下 降。从第50代的计算开始,遗传算法的适应度值小幅度降低,第50代的适应度值与第100代的适应度值 差别不大。这显示出优化模型具有很好的收敛性,程序运行500代后终止,并得到满意解,运行时间为45秒,城市物流总费用为6.3X 107万元,求解后得出的城市物流网络结构如图3所示,空心图形表示未被选 中的物流设施。5结束语确定城市物流网络节点的数量和位置是个复杂的问题,本文的研究是以零售点的物流需求量的预测 值为数据基础。但由于目前物流需求预测所依据的模型往往难以完全考虑城市经济发展的诸多复杂因 素,因此在进行城市物流网络结构和规模设计时,还应结合定性分析的方法,综合考虑交通区位条件、城市 产业布局和城市用地规划等因素。参考文献:1张晓东.物流园区布局规划理论研究M.北京:中国物资出版社,2004.4449.2Guide Jr V D R,Jayaraman V,Linton J D.Building contingency planning for closedloop supply chains with priduet recovery J.Journal of Operations Management,2003.3胡长英.逆向物流闭环双层优化模型及算法J.运筹与管理,2007,(163:26-3