水果运输调度问题的优化

2014年4月北京联合大学学报Apr. 2014第28卷第2期总96期Journal of Beijing Union UniversityVol. 28 No. 2 Sum No. 96水果运输调度问题的优化朱君，蔡延光，汤雅连(广东工业大学自动化学院,广州 510006)[摘要] 针对带硬时间窗的水果运输调度问题( Fruits in Vehicle Routing Problem with HardTime W indows , FVRPHTW),联系实际应用中水果易腐的特性及运输途中的路况因素,采用蚁群算法、模拟退火算法和禁忌搜索算法来对FVRPHTW求解,并分析3种算法的优缺点。实例证明,这些算法对求解水果运输调度问题是可行的,模拟退火算法略优于其他两种算法。[关键词]硬时间窗;水果运输调度问题;蚁群算法;模拟退火;禁忌搜索[中图分类号] F 252.1[文献标志码] A[文章编号] 1005-0310(2014 )02-0079-06Optimization of Vehicle Routing Problem for FruitsZHU Jun, CAI Yan-guang, TANG Ya-lian( School of Automation, Guangdong University of Technology, Guangzhou 510006 , China)Abstract: Aiming at FVRPHTW ( Fruits in Vehicle Routing Problem with Hard Time W indows)，considering thepractical problem of fruit decay as well as the road condition, the fundamental principle of SA ( simulatedannealing) and TS( tabu search) were introduced, and analysis on the advantages and disadvantages of thesealgorithms were made. The result shows that these algorithms are flexible to solve FVRPHTW, and SA is betterthan the other two algorithms.Key words: Hard time windows; FVRPHTW; Ant colony algorithm; Simulated annealing; Tabu search节性与周期性及水果的易腐性,因此,缩短水果从0引言水果物流集中中心到水果零售店的运输时间,可以随着人们生活水平的日益提高以及保健意识大大降低物流成本,促进水果运输业的发展,水果的增强,水果越来越受到广大消费者的青睐,水果物流主要模式如图1所示。水果零售店由于所处运输逐步得到商家的重视，而水果的产量和流通量地段不一样,且其营业时间也并非都是一-样,所以不断增加,使得全社会对水果的安全和质量也提出本文考虑了不同零售店的时间需求,在合理安排车了更高的要求。随着水果大型批发市场的日益成辆时间和路线的前提下,最大限度地降低成本。熟,加强水果物流技术,合理利用物流网络,能促进JTang等人研究了农产品的冷链运输调度问水果物流业的进一步发展,也能增加果农收人,同.题,以配送中心和20个大型超市之间的带容量约时满足消费者对水果的需求。由于水果消费的季束的农产品配送为例,分别利用节约算法和蚁群算[收稿日期] 2013-10-28 .[基金项目]国家自然科学基金 项目(61074147, 61074185),广东省自然科学基金项目( S201 10005059,5810000000)广东省教育厅产学研结合项目(2012091000171, 2011B090400460),广东省科技计划项目(2012B050600028 ,2010B090301042)。[作者简介]朱君(1991-),男,江西新余人,广 东工业大学自动化学院中国煤化工信息技术与应用:蔡延光(1963-),男,湖北咸宁人,广东工业大学自动化学院教授,博士生导:YHCNMHGI智能、决策支持系统等;汤雅连(1986--),女,湖南常德人,广东工业大学自动化学院博土研究生,册究万向为物流信息技术与应用。.80北京联合大学学报2014年4月种车型。3)硬时间窗约束。4)路况约束。1.2 模型的建立督|有l个零售店,第i个零售店的需求量为g;,需要从车场将水果物流集中中心的水果配送给各零售店,有1个车场可派出载重量为q的货车,已知国外主要水果省外及省内主要批g, rand,也接受S2作为新的当前解,S,= S2;否则保为车辆行驶距离约束,其中dj表示车辆k行驶了留当前解Si。零售店i到j的路程。式(6)和式(7)表示两个变6)如果满足终止条件,则输出S,,结束程序，量之间的关系。式(8)表示车辆完成任务后,回到即在连续若千个Metropolis 链中新解S2都没有被原车场。式(9)表示当某辆车配送水果到零售店的接受时终止算法,或是设定结束温度。否则按衰减个数大于等于1时,则参与了配送服务,否则,没有函数衰减T后返回2)。参与配送。式(10)表示所有零售店都被服务到。设定控制参数 ]式(11)表示不能超过车辆载重量的限制。式(12)厂初始解S表示保证每辆车服务的零售店总数小于等于总零punt=0售店数目。式(13)表示到达零售店i的时间必须在时间窗内。式(14)S.,S。 是要求配送水果的零售店需求关联,S。≤S,表示服务零售店i的时间必须[解变换得到新解S早于到零售店j的时间，由水果物流集中中心人员Metropolis准则判断根据零售店的需求紧急程度制定。式(15)表示到是否接受新解.达j的时间T,为车场到i的时间T.零售店i处的C新的S，k+1 ]卸货时间i与零售店i到零售店j的时间tq之和。N_lbL?2算法设计2.1模拟退火算法 ，count- count+1,T-qT2.1.1算法思想T<结束)终止规则利用当前解的邻域函数得到其将满足藐视准则所有中确定若干候选解，开从的解作为当前解，用其对应的对象替换最早进Y打断是否满足入禁忌表中的对特赦准则象，其余禁忌对象的禁忌任期减↓N1,更新“bes_sofar判断候选解禁忌属性将处于非禁忌状态的最佳候选解作为当前解，用其对应的对象替换最早进入禁忌表中的对象，其余禁忌对象的禁忌任期减1中国煤化工图3禁忌搜索算法的流程框图.MHCNM HGFig.3 The process diagram of tabu search algorithm第28卷第2期朱君等:水果运输调度问题的优化8在第20次迭代后,算法收敛。具体配送信息见法求解结果如表3所示,3种算法对比结果如表4表2,各车场分别派出一辆车,最优配送距离为所示。最优配送网络如图4所示,3种算法一次迭524. 04 km,总配送费用为5171.03 元。蚁群算法.代的收敛情况如图5所示,可见模拟退火算法优于和模拟退火算法求解结果如表2所示,禁忌搜索算另外两种算法。表1零售店信息表Table 1 The information table of retail stores客户编号位置坐标需求量/1时间窗/h(40. 00 ,40.00)1.9[5:00 7:00]2(46. 47 ,46.10)3.3[5:00 6:00](82. 47 ,94.44)2.8[5 :006:00](30. 09 ,92.54)1.2[6:30 7:30](72. 39 ,53.37)2.3(45. 23,17.24)3. 2[6:30 7:00](22. 00 ,56.05)2.5[5:30 6:00](80. 47 ,27.02)1.1[6:30 8:10](47. 20 ,96.29)[7:00 8:00](80. 30 ,37.38)1.5[6:00 8:00]1(14. 05 ,78.12)0.9[6:00 6:30](86. 53 ,47.38)0.6[6:00 7:30](21. 52 ,95.59)0.8[6:30 8:00]4(89.41,67. 13)2. 2(18. 09 ,92.55)1.3[6:00 7:00] .6(95. 00 ,56.00)2.2[5 :30 7:10](19. 00 ,30.00)[5 :50 6:30](44. 00 ,55.00)[5 :00 6:00](66. 00 ,10.00)2.0[7 :00 8:00]20(90. 00 ,95.00)4.5[6:00 7:00 ]表2蚊群算法和模拟退火算法 求解结果Table 2 The results of ant colony algorithm and simulated annealing algorithm路径配送时间里程/km载重/t费用/元0-2-1-17-6-05:00-5:05 -5:24-5:57 -6:36 -7:1999.709.91 007. 030-5-16-12-10-8-19-0 5:00-5:23 -5:56 -6:18-6:40 -7:00 -7:32 -8:25145. 059. 71426.99.0-3-20-14-05:00-5:33 -6:32-7:10 -8:03133. 449.51 287. 680-18-7-11-15-13-4-9 5:00-5:08 -5:40-6:13 -6:38-6:53 -7:12 -7:38-8: 145. 859.81 449.33-34合计524.0438.9.5 171. 03表3禁忌搜索算 法求解结果Table3 The results of tabu search里程/km载重/1费用0-2-1-17-6-19-05:00-5:05 -5:24-5:57 -6:36 -7:08 -8:01131. 6611.9 1 586. 750-5-14-16-12-10-8-0.5:00-5:23-6:00-7:00 -7:22 -7:44-8:04-8:52 129. 389.9 1 300. 860-3-20 -0.5:00-5:33 -6:32 -7:42122. 807.3916. 440-18-7-11-15-13-4-9-05:00-5:08 -5:40-6:13-6:38 -6:53 -7:12 -7:38145. 859.81 449. 33-8:34中国煤化工MYHCNMHG.9 5253.38 ..84北京联合大学学报2014年4月.表43种算法对比结果68优化过程Table4 The compare result of the three algorithms66算法总里程/km费用/元 最优解 所在代数64蚁群算法524. 045 171. 032:目62模拟退火算法13能6001禁忌搜索算法禁忌搜索算法529. 695 253. 383:鸡580i》文献[1]中算法.560100p9054080100070迭代次数60f图5算法收敛情况 .Fig. 5 The convergence condition40中of algorithms3020果运输调度问题模型,并采用模拟退火算法、禁忌902030405060708090100搜索算法及文献[1]中提到的算法对所建立的模型求解,实验证明，模拟退火算法能有效地求解此类图4最优配送 网络.问题且优于另外两种算法。接下来可以进一-步考Fig.4 The best distribution network虑水果运输途中的风险问题、车辆运输的能耗问题道路约束、需求模糊问题、速度约束和运输环境4结束语等问题,超大规模的客户群模型和算法的不断改进文章研究了带硬时间窗的具有需求关联的水.也是下一步需要研究的热点。[参考文献][ 1 ] TangJ, Liu K, Chen Q. Study on cold chain logistics of vehicle rouing problem for agricultural products[C]//SericeOperations and Logistics, and Infomatics (SOLI) , 2013 IEEE Inemational Conference on, IEEE, 2013: 317 -322.[2] 黄华芳，门建婷,陈绍慧，等.基于改进蚁群算法的果蔬运输车辆路径优化的研究[J].保鲜与加工, 2011, 11(3):24 - 27.[3]张 晶成.基于改进蚊群算法的蔬菜物流配送车辆优化调度研究[D].长沙:长沙理工大学, 2008.[ 4] Banos R, OrtegaJ, Gil C, et al. A Simulated Anealing-based parallel muliobjective approach to vehicle routing problemswith time windows[J]. Expert Systems with Applications, 2013, 40(4) :1696 - 1707.[5 ] ZidiI, Mesghouni K, Zidi K, et al. A mulibjective simulated annealing for the muli-criteria dial a ride problem[J].Engineering Applications of Artificial Intelligence, 2012, 25(6):1121 -1131.[6] Cordeau JF, Maischberger M. A parallel iterated tabu search heurstie for vehicle rouing problems [J]. Computers &Operations Research, 2012, 39(9): 2033 - 2050. .[7] Khanh P N, Crainic T C, Toulouse M. A Tabu Search for Time-dependent Multi zone Muli tip Vehicle Routing Problemwith Time w indows[J]. European Jourmal of Operational Research, 2013, 231(1):43 -56.(责任编辑 李亚青)中国煤化工MHCNMHG.