计算机应用 ›› 2017, Vol. 37 ›› Issue (12): 3602-3607.DOI: 10.11772/j.issn.1001-9081.2017.12.3602

• 应用前沿、交叉与综合 • 上一篇    下一篇

易腐生鲜货品车辆路径问题的改进混合蝙蝠算法

殷亚, 张惠珍   

  1. 上海理工大学 管理学院, 上海 2300093
  • 收稿日期:2017-06-29 修回日期:2017-09-04 出版日期:2017-12-10 发布日期:2017-12-18
  • 通讯作者: 张惠珍
  • 作者简介:殷亚(1993-),女,江苏盐城人,硕士研究生,主要研究方向:物流工程、智能优化;张惠珍(1979-),女,山西沂州人,副教授,博士,主要研究方向:运筹学、智能优化。
  • 基金资助:
    国家自然科学基金资助项目(71401106);上海市教委科研创新项目(14YZ090);教育部人文社会科学研究项目(16YJA630037)。

Improved hybrid bat algorithm for vehicle routing problem of perishable fresh goods

YIN Ya, ZHANG Huizhen   

  1. School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China
  • Received:2017-06-29 Revised:2017-09-04 Online:2017-12-10 Published:2017-12-18
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (71401106), the Shanghai Municipal Education Commission Scientific Research Innovation Project (14YZ090), the Humanities and Social Science Project of Ministry of Education (16YJA630037).

摘要: 针对配送易腐生鲜货品的车辆其配送路径的选择不仅受货品类型、制冷环境变化、车辆容量限制、交货时间等多种因素的影响,而且需要达到一定的目标(如:费用最少、客户满意度最高),构建了易腐生鲜货品车辆路径问题(VRP)的多目标模型,并提出了求解该模型的改进混合蝙蝠算法。首先,采用时间窗模糊化处理方法定义客户满意度函数,细分易腐生鲜货品类型并定义制冷成本,建立了最优路径选择的多目标模型;然后,在分析蝙蝠算法求解离散问题易陷入局部最优、过早收敛等问题的基础上,精简经典蝙蝠算法的速度更新公式,并对混合蝙蝠算法的单多点变异设定选择机制,提高算法性能;最后,对改进混合蝙蝠算法进行性能测试。实验结果表明,与基本蝙蝠算法和已有混合蝙蝠算法相比,所提算法在求解VRP时能够提高客户满意度1.6%~4.2%,且减小平均总成本0.68%~2.91%。该算法具有计算效率高、计算性能好和较高的稳定性等优势。

关键词: 非同类易腐货品, 车辆路径问题, 混合蝙蝠算法, 多目标, 模糊时间窗

Abstract: The choice of distribution route for vehicle with perishable fresh goods is not only affected by various factors such as the type of goods, the change of refrigeration environment, vehicle capacity limit and delivery time, but also needs to reach the certain targets such as the least cost and the highest customer satisfaction. In order to solve the problem, a multi-objective model for Vehicle Routing Problem (VRP) of perishable fresh goods was constructed and an improved hybrid bat algorithm was proposed to solve the constructed model. Firstly, the time window fuzzy processing method was used to define the customer satisfaction function, and the multi-objective model of optimal path selection was established by subdividing the perishable fresh goods types and defining the refrigeration cost. The bat algorithm is easy to fall into local optimum and premature convergence in solving discrete problems. Then, on the basis of analyzing the above problems, the speed update formula of classical bat algorithm was simplified, and the singlepoint or multipoint mutation selection mechanism of the hybrid bat algorithm was set up to improve the performance of the algorithm. Finally, the performance of the proposed algorithm was tested. Compared with the basic bat algorithm and several existing hybrid bat algorithms, the customer satisfaction of the proposed improved hybrid bat algorithm is improved by 1.6%-4.2% in solving VRP and the average total cost is reduced by 0.68%-2.91%. The proposed algorithm has better computational performance, higher computational efficiency and stability.

Key words: different type of perishable goods, Vehicle Routing Problem (VRP), hybrid bat algorithm, multi-objective, fuzzy time window

中图分类号: