基于蚁群算法的配送路径优化系统研究

基于蚁群算法的配送路径优化系统研究

杨凌杰,李󰀁静,王󰀁辉,孙维维(南京农业大学工学院,江苏南京󰀁210031)

摘要:充分考虑了路况、天气条件、交通条件等因素对配送的影响,在前人研究的基础上建立了包括车辆配送固定费用和其他相关费用,并带有时间窗约束的以运输费用最小为目标函数的数学模型。最后介绍了系统和数据库的设计思路,结合蚁群算法的基本原理,成功实现了该系统,提高了配送效率。

关键词:蚁群算法;路径优化;配送效率

中图分类号:TP3󰀁󰀁󰀁文献标识码:A󰀁󰀁󰀁文章编号:1672-1616(2008)17-0001-04󰀁󰀁当前,我国物流产业正向高度专业化和社会化的方向高速发展,配送环节在物流产业中占有举足轻重的作用。各物流企业对成批次货物运输的路径选择研究已初具规模,但如何针对货物运输特点对单次运输路径进行优化,已成为影响物流企业的业务拓展和增加利润的限制性因素。目前我国大部分物流企业在配送路径选择的方式上还是采用由司机的经验提供行车路线的方式,这种运输配送路线选择方式浪费了相当多的企业资源,因此如何在合理利用企业资源的前提下得到科学的配送路线将是减少配送成本的关键点。为此,本文尝试以目前研究较多的蚁群算法为核心,结合物流配送的特点和有关影响因素,进行单次运输路径优化系统研究和开发,以提高配送效率。

辆数目,从而达到减少成本的模型[1],在此基础上,K.C.Tan提出有随机需求的车辆路线选择的最短运输时间受旅行距离、驾驶员待遇、车辆数目等一系列因素的制约,分析研究并建立和验证了多目标特定启发式路线模拟方法。随后,Chaug-IngHsu又在以减少固定成本为目标的前提下,就运输中的违章等违反时间窗的行为对时间的影响进行研究,将该因素转化为对时间的影响参数,并将其应用到了易腐食品的运输路线选择上。对于新客户订单需求的问题,FranklinT.Hanshar和TomVanWoensel分别进行了研究并取得了一定成果

[4,5]

[3]

[2]

。

本文研究的问题是在普遍的货车计重收费政

策下长距离配送运输的路线费用最小问题。公路网错综复杂,任何两点之间都可能有多种路线存在,且每条路线的总距离以及所经过的节点和路段的长度和类型都不相同,这就给模型求解带来了困难。陈辛等人处理此问题时采用了如下假设[6]。(1)假设每一条路线都是平坦的,没有上坡及急转弯的情况,但不同类型的道路上车辆行驶的速度有差异。(2)对于交通网络中单行线及禁止转向等情况暂不考虑。(3)节点和边的选择应遵循以下原则:道路的交叉点或断头路的终点作为节点,相同起点和终点之间有且只能有一条路段,并且在该路段上道路的类型应相同,比如一级公路、二级公路及高速公路。(4)路段的起点和终点首尾相连。(5)假定运输过程中天气、交通状况以及司机的状

1󰀁路径优化系统的模型

1.1󰀁问题分析

在现代物流中,各企业都十分关注针对企业现状的成本压缩方案的设计,而且目前客户对企业货物配送时间的要求也越来越严格。对于物流企业而言,通过选择合适运输路线来降低成本对获得订

单有着相当大的现实意义,并且在不断满足客户合理的时间约束下,无形之中也在提升企业的客户形象,为企业的进一步发展创造条件。

基于现实情况的考虑,很多研究人员投入到带时间窗车辆路径选择(VRPTW)之中,JorgHomberger在考虑时间窗的约束下提出了减少车

收稿日期:2008-06-16

基金项目:南京农业大学SRT项目(0715A15);江苏省农机基金资助项目(GXS08005)

作者简介:杨凌杰(1987-),男,安徽巢湖人,南京农业大学本科生,主要研究方向为物流工程。

22008年9月󰀁中国制造业信息化󰀁第37卷󰀁第17期

1991年提出的一种模拟自然界蚁群行为的进化算法,其利用了正反馈机理和启发式信息来搜寻最优解,具有很强的并行性和搜索较优解的能力,但容易出现停滞现象[7]。为了最大程度地降低这种现象的影响,本文采用最大-最小策略结合信息素更新方式改进基本蚁群算法,形成最大-最小蚁群算法(MMAS)对车辆路径问题进行求解。

态保持良好,保证运输状态的平稳。本文也将采用以上的假设条件,以方便建模。

1.2󰀁问题的描述和数学模型

本文研究的是2个指定配送区域之间的长距离配送问题,给出了一个连接若干个配送中心和二级、三级城市的网络,两点之间有多条可行的道路,所有车辆的固定费用和单位油价已定,所有经过的路段均为高速公路,且基本费率已定,路桥费用的计算与各省市计重收费政策一致。要求合理选择路线,考虑在路况、天气条件、交通条件等对配送产生影响的情况下,使目标函数最优。

根据上述描述建立的数学模型表示如下:目标函数为minTF=

i󰀁Cj󰀁C

2.2󰀁个体蚂蚁的路线形成过程

若要形成一条正确的路线,其前提是该路线的起点和终点不能是相同的。当系统运行时,首先会判断操作员填写的起、终点是否一致,若一样则会报错并要求重新填写,若不相同则会将起、终点转化为相应的区号,并以起点的区号在表Route中搜索所有StartCity字段值为此区号的路段。待搜索

󰀁󰀁fDijxij+󰀁󰀁MQDijxij+

i󰀁Cj󰀁C

i󰀁Cj󰀁C

󰀁󰀁Cijxij

(1)

到所有的路段后首先判断其中有没有EndCity字段值为终点城市区号的,若有则终止程序并列出结果,若没有则运用蚁群算法的原理在搜索到的路段中选择一条路段供前行,并将该路段的终点城市的区号作为下一次搜索的新起点再次搜索数据库,直到找到指定终点或达到程序设定的迭代次数。将所有走过的路段连接起来,就会得到一条完整的路线。

为防止找到的路线中有重复的城市,在程序中定义一个CityPath()数组专门用来存储当前蚂蚁走过的城市。程序每次得到终点城市都会搜索CityPath()数组以判断是否已经有这个城市,若有,则会按照以上方法重新选择下一条路段直到没有重复的城市,并将这个城市加入CityPath()数组中。CityPath()数组中的内容会随蚂蚁标号的改变而被清空。

最后,为了能得到指定起、终点的所有路线信息,帮助决策,特定义PathNum()自定义数组记录最终搜索到的所有路线,每条路线的基本信息有起点、终点、长度和具体的行走路线。在󰀁运行结果󰀁窗口将基于这个数组按照操作员要求显示所有路线的排序,默认只显示符合要求的此程序认为的最优路线,操作员可以点击相关按钮得到所有路线的排序。操作员可以利用这些信息决定采用哪条行车路线能够更节省成本。具体流程如图1所示。

󰀁󰀁约束条件为

󰀁󰀁

i

j

xijDij

vij󰀁T󰀁i,j󰀁C

(2)(3)

Dij=(RS+W+TP)dij󰀁i,j󰀁C

󰀁󰀁在上述模型中,式(1)中的3个部分依次为固定费用、油费和路桥费。式(2)表示货车在路线中行驶的时间应不大于客户要求到货时间;式(3)定义了不同路况、天气条件、交通政策下的两点(城市)之间距离的计算方法。式(1)中第3项路桥费用Cij的计算按照各省市的计重收费的收费标准进行计算。

最小费用路线模型中有关变量的说明如下:TF为单个货车运输的总费用;f为所有货车的平均固定费用,只与运输距离有关;Dij为i点(城市)与j点(城市)之间的折算运输距离;当货车经过i向j时,xij=1,否则xij=0;M为当前货车的载质量;Q为当前货车的单位距离单位吨数的耗油量;Cij为由i向j路段上的路桥费;vij为当前货车在由i向j路段上的平均速度;T为客户要求的运输时间;C为所有点(城市)的集合;RS为路况对距离的权值;W为天气情况对距离的权值;TP为交通政策对距离的权值;dij为点i与j之间的图上(实际)距离。

2󰀁求解路径优化问题的蚁群算法

2.1󰀁算法思想

蚁群算法是由意大利学者M.Dorigo等人于3󰀁系统设计与实现

3.1󰀁系统需求分析

在企业需求上,这是一个辅助决策系统,它在󰀁企业管理与信息化󰀁󰀂󰀂杨凌杰󰀁李󰀁静󰀁王󰀁辉等󰀁基于蚁群算法的配送路径优化系统研究3设置各路段的路况、天气条件、交通状况等影响配送的因素、行驶平均速度和蚁群算法的必要参数后,能够自动按照一定的次序列出所有符合时间窗要求的路径,或是按照行驶时间长短排列,或是按照配送总费用大小排列,同时推荐系统认为的符合最多要求的最优路径,实现决策层的决策自动化或提供其决策必要的辅助信息,提高配送效率。

库进行操作,而且我们预先输入了浙、苏、皖、沪三省一市的部分城市的信息,可以进行系统的示例。

图2󰀁路径规划系统功能图

3.3󰀁数据库连接和结构设计

路线规划系统的实现首先是VB与数据库的接口部分,因为该软件的一切数据都是来自已经建立完全的数据库,若软件无法读取数据库中的路段信息,也就无法实现以上所列的一系列功能。笔者在VB中引用󰀁MicrosoftActiveXDataObjects2.5Library󰀁和󰀁MicrosoftDataBindingCollection󰀁2个控件并运用字符串成功连接上了数据库。

而如何将路段的基本信息存于数据库中又是另一个要点。经过参考大量数据库方面的书籍和论文,最后我们设计出以下的路段存储方式。

图1󰀁一只蚂蚁的路线形成过程图

把每个省(市)的城市节点之间的基础路线长度,初始化信息素浓度(InformationChroma,这里设为5),并以所对应起、终城市的区号加上路线长度和2个字符的关键字作为一条记录输入数据库中,如南京与合肥相距160km,那么数据库中的这条记录见表1。

表1󰀁路段在数据库中的存储示例

Key025*160*0551

StartCityEndCity025

0551

Length160

InformationChroma

5

需要说明的是,在实际编制该系统时,因该系统数学模型的最小费用与最短路径具有一定的相关性,为了较容易实现系统功能,将使用最短路线来取代最小费用的目标函数。

3.2󰀁系统功能简介

软件系统的功能在明确了软件定位的基础上也很容易明确。对于决策,要求软件能提供全面准确的信息,有一定的可操作性;对于基层员工,只需知道做什么和应该怎么做就行了。另外,有一个友好的界面也能在一定程度上提高员工的工作积极性。

软件的功能结构设计如图2所示。

路径规划功能模块:该模块实现了对指定起、终点路线的求解。软件提供了参数修改功能,可以视不同的实际情况选择最适合的参数,而且我们在提供软件推荐最优路线的同时,还提供了所有的可行路线信息,以供软件操作员根据实际情况选择。

数据库模块:该模块实现了对数据的增、删、改、查询等4项功能,能够在软件中方便地对数据󰀁󰀁这是数据库中的第1个表(Route),对数据库的增、删、改、查询都是基于这种数据库的路段存储结构,只要操作员按照软件的提示操作就不会出现数据库方面的错误。

另外,数据库中还有第2个表(City

ID),它

是用来存储所有城市的区号信息,对另外一个表的一切操作都将基于这个表。其设计实例参见表2。

表2󰀁表City

ID的存储结构示例

ID0250551CityName南京合肥42008年9月󰀁中国制造业信息化󰀁第37卷󰀁第17期

指定起点和终点的所有路线。系统运行后的拷屏如图3所示。

如果选择起点城市为󰀁扬州󰀁,终点城市是󰀁肥

3.4󰀁系统的功能模块运行实例

该软件系统以Access数据库为基础,基于VB平台,结合蚁群算法对数据库进行搜索并最终得到

图3󰀁系统运行结果

东󰀁,设置时间窗为6h,单击󰀁找出路线󰀁按钮,程序即开始搜索数据库,等迭代指定的代数后即可得到所有起点是󰀁扬州󰀁、终点是󰀁肥东󰀁的路线。默认只显示󰀁最优路段󰀁,若起点是󰀁扬州󰀁,终点城市是󰀁肥东󰀁,那么推荐最优路径见表3。

表3󰀁最优路线相关信息

路段标识最优路线

组成路段扬州󰀁无锡󰀁南京󰀁全椒󰀁肥东

长度/km558

行驶时间/h

4.65

关于到货时间的要求。运用该系统可以方便地提供有用的信息,最大程度地减小决策的风险。

4󰀁结束语

本文介绍了当前物流企业配送中心之间路径选择方式及其存在的问题,建立带有路况、天气条件、交通条件等影响因素的模型,并运用最大-最小蚁群算法求解该问题,根据模型设计了车辆路径优化系统。通过该系统的运用,可以更好地提高物流企业的配送效率,从而降低运输成本。参考文献:

[1]󰀁JorgH,HermannG.Atwo-phasehybridmetaheuristicforthe

vehicleroutingproblemwithtimewindows[DB/OL].http://

󰀁󰀁若单击󰀁显示所有的路径<<󰀁按钮,则会显示搜索到的所有路径,以供操作员根据实际情况选择。本实例中搜索到的所有路线只有2条,见表4。

表4󰀁所有路线的信息

路段标识路段一

组成路段扬州󰀁无锡󰀁南京󰀁全椒󰀁肥东

扬州󰀁淮安󰀁江都󰀁

路段二

无锡󰀁南京󰀁全椒󰀁肥东

864

7.2

长度/km558

行驶时间/h

4.65

www.cat.inist.fr/?aModele=afficheN&cpsidt=16436339,2008-05-12.

[2]󰀁TanKC,ChewYH,LeeLH.Ahybridmulti-objective!

evolutionaryalgorithmforsolvingtruckandtrailervehiclerout󰀁ingproblems[DB/OL].http://www.cat.inist.fr/?aModele=afficheN&cpsidt=17652945,2008-05-13.

[3]󰀁HsuC,HungS,LiH.Vehicleroutingproblemwithtime-windowsforperishablefooddelivery[J].JournalofFoodEngi󰀁neering,2007,80(3):465-475.󰀁󰀁很明显的,符合时间窗要求的只有路线一,它的行驶时间为4.65h,小于6h,路段二不符合货主(下转第8页)82008年9月󰀁中国制造业信息化󰀁第37卷󰀁第17期

(2)先易后难的实施步骤。如果企业一下子就

4󰀁结束语

有人说,实施项目的费用是个无底洞,之所以这样是因为ERP项目实施过程存在许多价格陷阱。要避免这些陷阱,一方面要求企业做好项目实施前的调研和规划工作,理解报价的含义,缩短项目实施周期等;另一方面是要引入项目监理,减少信息的不对称,明确项目质量标准,使ERP项目实施成为一项阳光工程。参考文献:

[1]󰀁陈启申.供需链管理与企业资源计划(ERP)[M].北京:企业

管理出版社,2001.

[2]󰀁李󰀁健.企业资源计划(ERP)[M].北京:电子工业出版社,

2004.

[3]󰀁罗󰀁鸿.ERP原理󰀁设计󰀁实施[M].北京:电子工业出版社,

2005:303-309.

[4]󰀁丁󰀁峰.浅析ERP与ISO9000的联系及区别[J].中国管理

信息化,2006(1):19-22.

[5]󰀁杨󰀁丽.跨越管理的断层󰀁󰀁󰀁ERP与ISO9000的结合[EB/

OL].http://www.amteam.org/print.aspx?id=448384,2002-07-31.

实施ERP的全部模块,客户化的难度肯定很多,不确定性就会加大。企业不妨可以考虑先上财务管理系统、供应链管理系统、人力资源管理系统和OA等模块。由于这些模块的流程比较标准化,或者相对较简单,实施的难度会小很多,等企业在应用ERP方面有了较好的经验以后,再实施生产制造管理系统、决策分析和集团应用等模块。

e.引入ERP项目监理,为合同执行保驾护航。从专业知识和经验上看,实施企业的大多数管理人员,对ERP的业务流程和管理理念都了解不多,而软件厂商的实施人员对自己的系统十分了解,这就形成了信息不对称的局面。实施合同如何签订?如何执行?如何才算成功上线和完成产品的交付?这就需要有一个第三方监理机构对项目合同的签订与执行进行把关。引入ERP项目监理或聘请咨询公司虽然会多一笔花费,但却能较好防范价格陷阱和项目风险,实际总费用还会降低,项目效益更能得到保证。

ThePriceTrapintheProcessofERPProjectImplementation

LAOBen-xin

(GuangxiUniversityofFinanceandEconomics,GuangxiNanning,530003,China)

Abstract:ERPprojectisacomplicatedsystemprojectanditsimplementationisverydifficult.Initsimple󰀁mentationprocess,becauseofuncertaintiesofprojectimplementationcycle,information󰀁sasymmetrybe󰀁tweensuppliersanddemanders,difficultytoquantifytheserviceproduct󰀁squalityetc,actualtotalcostoftheprojecthasstronguncertainty.Thiseasilymakestheprojectsidefellinpricetrap.Thearticlefocusesonthefactorsthatcauseprojectimplementationcycleuncertaintyandtheirperformanceledtothepricetrap.Atlastitsuggestscorrespondingmeasures.

Keywords:ERPProjectImplement;ERPProjectCost;PriceTrap

(上接第4页)

[4]󰀁HansharFT,Ombuki-BermanBM.Dynamicvehiclerouting

usinggeneticalgorithms[J].ApplIntell,2007,27(1):89-99.[5]󰀁VanWT,KerbacheL,PeremansH,etal.Aqueueingframe󰀁

workforroutingproblemswithtime-dependenttraveltimes

[J].JMathModelAlgor,2007(6):151-173.

[6]󰀁陈󰀁辛,李󰀁静.基于计重收费的车辆路径优化系统设计与

实现[J].中国制造业信息化,2007,36(17):69-72.[7]󰀁张翠军,张有华,秦󰀁彭,等.基于有时间窗车辆路径问题的

混合蚁群算法[J].计算机工程与设计,2008,29(4):920-922.

RoutingOptimizationSystemBasedontheAntColonyAlgorithm

YANGLing-jie,LIJing,WANGHui,SUNWei-wei(NanjingAgriculturalUniversity,JiangsuNanjing,210031,China)

Abstract:Itaimsattheroadsituation,weatherandtraffic,whichhaveaffectionsonthedistributionefficien󰀁cy.Basedonthesuggestedtime-windowmodel,itconsumesthecostofvehicleandotherrelatedcostsastheconstraints.Itdesignstheantcolonyalgorithm.Thesystemshowssignificanttotheefficiencyofdistribu󰀁tions.

Keywords:TheAntColony;RoutingOptimization;DistributionEfficiency