电子学报 ›› 2019, Vol. 47 ›› Issue (7): 1434-1442.DOI: 10.3969/j.issn.0372-2112.2019.07.006

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

带容量约束的供应链物流运输调度问题的双层变邻域蝙蝠算法

戚远航1, 蔡延光2, 蔡颢3, 杨亮1, YAO Yeboah2   

  1. 1. 电子科技大学中山学院计算机学院, 广东中山 528402;
    2. 广东工业大学自动化学院, 广东广州 510006;
    3. 奥尔堡大学健康科学与工程系, 丹麦奥尔堡 9220
  • 收稿日期:2018-07-09 修回日期:2018-11-19 出版日期:2019-07-25 发布日期:2019-07-25
  • 通讯作者: 蔡延光
  • 作者简介:戚远航 男,1993年6月出生,广东湛江人.2018年在广东工业大学获得工学博士学位,现为电子科技大学中山学院讲师,从事复杂系统建模与优化、智能规划、运输调度的研究.E-mail:qiyuanhang77@163.com
  • 基金资助:
    国家自然科学基金(No.61074147);广东省自然科学基金(No.S2011010005059,No.2016A030313018);广东省教育部产学研结合项目(No.2012B091000171,No.2011B090400460);广东省科技计划(No.2012B050600028,No.2014B010118004,No.2016A050502060);广州市花都区科技计划(No.HD14ZD001);广州市科技计划(No.201604016055);中山市科技计划重点项目(No.2018B1018);中山市重大科技专项(No.2017A1024,No.2017SF0603,No.2016A1028)

Two-Level Bat Algorithm with Variable Neighborhood Search for Capacitated Vehicle Routing Problem in Supply Chain

QI Yuan-hang1, CAI Yan-guang2, CAI Hao3, YANG Liang1, YAO Yeboah2   

  1. 1. School of Computer Science, University of Electronic Science and Technology of China, Zhongshan Institute, Zhongshan, Guangdong 528402, China;
    2. School of Automation, Guangdong University of Technology, Guangzhou, Guangdong 510006, China;
    3. Department of Health Science and Technology, Aalborg University, Aalborg 9220, Denmark
  • Received:2018-07-09 Revised:2018-11-19 Online:2019-07-25 Published:2019-07-25

摘要: 本文考虑了多个供应商、多个制造商和多个零售商的三级供应链物流运输调度,以最大限度地降低采购、加工和运输成本为目标,提出了带容量约束的供应链物流运输调度模型(Capacitated Vehicle Routing Problem in Supply Chain,CVRPSC).进一步地,本文构造了求解CVRPSC的双层变邻域蝙蝠算法(Two-Level Bat Algorithm with Variable Neighborhood Search,TLBAVNS).该算法提出了一种双层蝙蝠位置的定义,引入了相应的蝙蝠算法的更新操作,采用变邻域局部搜索策略加强算法的寻优能力.实验证明:TLBAVNS能在合理的时间内求解CVRPSC;在大部分测试算例中,该算法相对于对比算法均表现出了更强的寻优能力和稳定性.

关键词: 供应链, 车辆路径问题, 蝙蝠算法, 邻域搜索

Abstract: Considering a two-level vehicle routing problem in a three-echelon supply chain with multiple suppliers,multiple manufacturers and multiple stockists,with the aim of minimizing the cost of purchasing,production and transportation,this paper proposes a model for the capacitated vehicle routing problem in supply chain (CVRPSC).Further,a two-level bat algorithm with variable neighborhood search (TLBAVNS) is presented to solve CVRPSC.The algorithm proposes a definition of two-level bat position and introduces the corresponding operations of the bat algorithm.In addition,a variable neighborhood local search is proposed to enhance the optimizing capability of TLBAVNS.The experiments have shown that TLBAVNS can effectively solve the instances of CVRPSC within a suitable amount of time and significantly outperforms all the other alternatives in most of the cases.

Key words: supply chain, vehicle routing problem, bat algorithm, neighborhood search

中图分类号: