烟草配送系统中路径优化问题20O9年第6期第31卷总第180期物INE流E工R程IN与G管AN理DLOGISTICSENGINEERINGANDMANAGEMENT.禽Pll鱼ib配送..1心烟草配送系统中路径优化问题口莫韦嶙,谭勇,张宝华(大连海事大学交通运输管理学院.辽宁大连116026)【摘要】为解决烟草配送路线不合理的问题,根据烟草配送的特点建立烟草配送路径优化模型,基于配送所要到达的零售网点与配送必须经过其所在的道路等同的认识,把烟草配送路径优化问题转化为网络图中的中国邮递员问题,并利用Floyd算法求解烟草配送最短路径.算例分析验证了该模型和算法在烟草配送路径优化中的有效性.【关键词】烟草配送;中国邮递员问题;路径优化【】F251.2【文献标识码】B【】1674-4993(2oo9)o6-oo86-o2RouteOptimizationinTobaccoDistributionSystem口MOWei—lin.TANYong,ZHANGBao-hua(TransportationManagementCollege,DalianMaritimeUniversity,Dalian116026,China)【Abstract】Inordertosolvethepmblemofunreasonabledistributionroute,thetobaccodistributionrouteoptimizationmoddwasestablishedaccordingtothecharacteristicsoftobaccodistribution.BasedontheknowledgeoftheretailpoiIltcouldbetakenastheroutepassingbytheretailpointintobaccodistributionnetwork,thetobaccorouteoptimizationproblemwastransformedtoChinesePostmanProbleminanetworkMap.rloyaalgorithmwasemployedtoacquiretheshortestmuteinto—baccodistribution.ExperimentsshowthatthemodelanditsalgorithmalequiteeffectiveandefficientOilrouteoptimizationintobaccodistributionsystem.【Keywords]tobaccodistribution;ChinesePostmanProblem;routeoptimization1引言目前我国绝大多数烟草企业仅以人工,凭主观,靠经验对配送线路进行优化,也有少部分企业开始借助于信息技术实现配送线路的优化工作,但能够提出完整的物流配送线路优化系统的企业还非常少.而国外的一些路径优化软件由于交通规则,道路规划等各方面不符合我国国情,很难符合改革中的中国烟草的管理流程,因此烟草配送路径优化问题已成为制约我国烟草物流发展的主要因素之一.目前,国内外大多数研究很难一次性形成合适的配送线路,往往需要辅助很多人工干预和调整,增加了工作的复杂性.本文将中国邮路问题引入配送路径的优化中,在邮路问题中引用指派问题来处理奇点对之间增加重复边的问题,大大简化了多奇点对之间增加重复边的繁琐性,试图寻求一种新的适合我国烟草配送系统的路径优化方法,并力求有所突破.2烟草配送路径优化模型2.1模型建立的前提条件及符号规定本文结合我国烟草配送的特点,建立了市区间的烟草配I收稿日期】2009-06-10【作者简介】莫韦嶙,大连海事大学交通运输管理学院.送路径优化的模型,其前提条件如下:①某市卷烟零售网点分布在全市各地,其总体数量大致稳定;②该市根据配送辐射半径,将全市划分多个配送区域,并确定每一区域的配送中心及每个配送中心所覆盖的零售网点;③零售网点的配送任务由所在区域的烟草配送中心负责,所有配送车辆为同一型号.每一区域的烟草需求量都必须在单车车载量以内,区域内各零售网点所在道路的长度可知;④配送车辆由某一区域的配送中心出发,经过该区域内各零售网点,配送完成后车辆返回该物流中心.符号规定如下:N为某烟草配送区域内零售网点d的个数(d=l,2,…N);)【d表示配送路径是否经过第d个零售网点(xl时表示经过,X~--o是表示未经过);G=fv,E)为该区域零售网点所在道路形成的边权连通无向图;V为道路交叉点的集合{v-.vl,点数IVl=n,其中v.表示该区域的烟草配送中心;E表示G中所有道路的集合{,v道路个数IEl=m,(i,j=O,1,…,n);w(vi,vJ表示道路(vI’vi)的长度;r表示G中奇点个数(必第6期莫韦嶙等:烟草配送系统中路径优化问题87为偶数);vv表示G中的某两个奇点,(p,q=l,2,…,r);表示vkp与vkq之间的最短距离(p≠q);C为从烟草配送中心出发经过每个零售网点后重新回到配送中心的一个配送路径;L(c)表示配送路径C的总长度.2.2模型描述对于某一个烟草配送区域,零售网点是固定分布在道路上的,可将配送路径必须经过零售网点的问题转化为必须经过零售网点所在道路的问题,...