电子学报 ›› 2018, Vol. 46 ›› Issue (3): 672-679.DOI: 10.3969/j.issn.0372-2112.2018.03.024

• 学术论文 • 上一篇    下一篇

带时间窗的车辆路径问题的离散蝙蝠算法

戚远航1, 蔡延光1, 蔡颢2, 黄何列1   

  1. 1. 广东工业大学自动化学院, 广东广州 510006;
    2. 奥尔堡大学健康科学与工程系, 丹麦奥尔堡 9220
  • 收稿日期:2016-09-30 修回日期:2016-12-21 出版日期:2018-03-25
    • 通讯作者:
    • 蔡延光
    • 作者简介:
    • 戚远航,男,1993年6月出生,广东湛江人.现为广东工业大学博士生,从事供应链物流及智能算法的研究.E-mail:qiyuanhang77@163.com
    • 基金资助:
    • 国家自然科学基金 (No.61074147); 广东省自然科学基金 (No.S2011010005059); 广东省教育部产学研结合项目 (No.2012B091000171,No.2011B090400460); 广东省科技计划项目 (No.2012B050600028,No.2014B010118004,No.2016A050502060); 广州市花都区科技计划项目 (No.HD14ZD001); 广州市科技计划项目 (No.201604016055)

Discrete Bat Algorithm for Vehicle Routing Problem with Time Window

QI Yuan-hang1, CAI Yan-guang1, CAI Hao2, HUANG He-lie1   

  1. 1. School of Automation, Guangdong University of Technology, Guangzhou, Guangdong 510006, China;
    2. Department of Health Science and Technology, Aalborg University, Aalborg 9220, Denmark
  • Received:2016-09-30 Revised:2016-12-21 Online:2018-03-25 Published:2018-03-25

摘要: 本文提出了一种离散蝙蝠算法求解带时间窗的车辆路径问题(vehicle routing problem with time window).该算法提出了蝙蝠位置的定义、速度的定义、位置更新操作、速度更新操作、频率更新操作,并采用惩罚机制与向量比较机制相结合的方法处理相关约束条件.该算法引入了随机插入策略、最少客户车辆插入搜索、普通插入搜索、交换搜索、带时间窗的2-Opt搜索等策略来扩大搜索空间、加强算法的收敛效率.实验结果表明:所提出算法具有较强的寻优能力、较高的鲁棒性、较少的时间耗费;本文所采用的关键参数值和策略能提高所提出算法的性能;通过假设检验证明了所提出算法与对比算法之间的算法性能均有显著性差异.

关键词: 离散蝙蝠算法, 车辆路径问题, 时间窗, 2-Opt

Abstract: This paper presents a discrete bat algorithm to solve the vehicle routing problem with time window (VRPTW).The proposed algorithm defines position,velocity,updated operation of the position,updated operation of the velocity and updated operation of the frequency,and uses a method which combines the penal function with vectorial comparison to deal with constrained conditions.The proposed algorithm adopts random inserted strategy,inserted research strategy for the vehicle with minimum customers,ordinary inserted research strategy,exchanged research strategy and 2-Opt strategy with time window to expand the search space and enhance the convergent rate.Experimental results show that,the proposed algorithm has a stronger optimization capability,higher robustness and less time consumption,key parameter values and strategies used in this paper can improve performances of the proposed algorithm,and according to the hypotheses testing,there exsits a significant difference between the proposed algorithm and comparative algorithms.

Key words: discrete bat algorithm, vehicle routing problem, time window, 2-Opt

中图分类号: