资源描述：
《基于蚁群算法的图书物流中心配送路径规划》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第26卷第4期湖北工业大学学报2011年08月Vol.26No.4JournalofHubeiUniversityofTechnologyAug.2011[文章编号]1003-4684(2011)04001902基于蚁群算法的图书物流中心配送路径规划计三有,王星(武汉理工大学物流工程学院,湖北武汉430063)[摘要]以图书物流中心车辆路径规划问题为研究对象,结合图书配送多品种小批量的特点,以配送路线最短为目标,在考虑车辆容量限制的条件下,建立基于零担运输策略的图书物流中心车辆路径规划模型;针对传统路径规划问题
2、研究的不足,运用GPS导航系统重新定义了配送距离.用蚁群算法对所建模型进行求解与仿真,并结合实际案例给出优化结果,验证了模型及算法的有效性.[关键词]车辆路径规划;图书配送;蚁群算法[中图分类号]U116.2[文献标识码]:ANNK车辆路径问题(VehicleRoutingProblem,minxijkdij.(1)VRP)最早由G.Dantzig和J.Ramser于1959年提j=0i=0k=1[1]N出.VRP问题已经被证明是NPHard问题,针对x0jk1(kK),(2)它的求解算法主要有精确算法和智
3、能算法两类.由j=1N于精确算法在有限的时间内并不是总能得到合适的xi0k1(kK),(3)解,因此,在实际应用中,智能算法要更有效.本文采i=1KN用一种新型的智能算法蚁群算法(AntColonyxijk=1(j{1,2,,N}),(4)k=1i=0Optimization,ACO)进行求解.KNxijk=1(i{1,2,,N},(5)1图书物流车辆路径规划模型k=1j=0NNqixijkCk(k{1,2,,K}),(6)i=0j=0图书因其商品的特殊性质,客户的需求一
4、般体其中:N为客户需求点总数;k代表车辆编号,且k现为高频率、小批量的特点.在这种情况下,单个客{1,2,,K};dij为需求点i与j之间的距离,其户的需求量通常较小,多个客户需求量之和才能达中,ij且i,j{1,2,,N};qi为客户点i的需到一部车辆的有效装载容量.若仍采用不同客户需[23]求量;Ck为车辆k的最大装载量;xijk为判断系数,求分车配送的方式,则大大降低了资源利用率.且1.1模型描述及优化为简化建模过程,优化模型结构,特对物流车辆1当车辆由客户点i到j时,路径规划模型做如下设定:1)配送中心的图书储备
5、xijk=ij,i,j{1,2,N},量能满足所有需求点的需求,不存在缺货情况;2)车0其他.辆顺序地为需求点提供配送服务,只有卸货不带取式(1)为优化目标表达式,使配送路径的总里程数尽货;3)每个客户需求点只被一辆车服务一次;4)配送可能小;式(2)、(3)表示每一辆参与配送的车辆都从车辆由配送中心出发,服务结束后返回配送中心;配送中心出发,并最终回到配送中心;式(4)、(5)表1.2车辆路径规划模型示每个需求点被且仅被一辆车服务一次;式(6)表示根据模型描述及相关假设,基于零担运输策略容量约束,保证每辆车的实际装载量都
6、不超过其容的图书物流车辆规划模型建立如下:量.[收稿日期]2011-03-16[作者简介]计三有(1963-),男,湖北汉川人,武汉理工大学教授,研究方向为机械设计及理论,物流技术及设备,物流管理20湖北工业大学学报2011年第4期最终线路:线路一,122161317192最短距离的改进141;线路二,182318491;线路三,110561271;线路四,1212015目前在VRP问题的研究中,任意两个客户点111.运输总距离为178.9km.间的最短距离,通常采用
7、两点间的直线距离.这样的经统计计算,该次配送的实际运输距离为[5]简化与实际路程并不吻合.207.0km.与之相比,经过优化的配送路径能减少城市交通路况比较复杂,两点之间的距离并非13%的配送里程.是直线距离,而是行车路线中各段路程的代数和,有的时候实际距离与直线距离相差非常大.针对该问题,本文结合实例在计算任意两个客户点之间的最短距离时采取通过GPS导航系统取得的路程数据为基础,进行优化计算.3蚁群算法蚁群算法最早是由MarcoDorigo于1992年在他的博士论文中提出,是一种模仿蚂蚁觅食过程的[6]图1程序运行结果模拟进化算
8、法.为模拟蚂蚁选择路径及路径上信息素的更新过程,定义如下符号:m为蚂蚁数量;dij为城市i,j之5结论间的距离;ij是路段(i,j)的能见度,反映由城市i结合图书配送的特点,在配送车辆装载容量有转移到城市j的启发程度
