求解双目标带时间窗车辆路径问题的蚁群算法

交通运输系统工程与信息 ›› 2018, Vol. 18 ›› Issue (4): 156-162.

求解双目标带时间窗车辆路径问题的蚁群算法

柴获^{a, b}，何瑞春^*b，苏江省^b，宋宇博^a，代存杰^a，马昌喜^b

兰州交通大学 a. 机电技术研究所；b. 交通运输学院，兰州 730070

收稿日期:2017-12-12 修回日期:2018-02-05 出版日期:2018-08-25 发布日期:2018-08-27
作者简介:柴获(1982-)，男，甘肃静宁人，讲师，博士生.
基金资助:
国家自然科学基金/National Natural Science Foundation of China (61364026)；兰州交通大学校青年基金/ Youth Foundation of Lanzhou Jiaotong University (2015026)；兰州交通大学优秀科研平台(团队)资助计划/Excellent Platform of Lanzhou Jiaotong University(201604).

An Ant Colony Optimization for the Bi-objective Vehicle Routing Problem with Time Windows on Mutilgraph

CHAI Huo^{a, b}, HE Rui-chun^b, SU Jiang-sheng^b, SONG Yu-bo^a, DAI Cun-jie^a, MA Chang-xi^b

a. Mechatronics Technology and Research Institute; b. School of Traffic and Transportation, Lanzhou Jiaotong University, Lanzhou 730070, China

Received:2017-12-12 Revised:2018-02-05 Online:2018-08-25 Published:2018-08-27

摘要/Abstract

摘要：

针对运输网络为多重图的双目标带时间窗车辆路径问题设计了蚁群算法.首先，建立了多重图的双目标带时间窗车辆路径问题的数学模型，提出了针对该问题解的搜索空间构建方法，定义了一种综合考虑各优化目标、时间窗和信息素等启发信息的状态转移概率公式. 为了对比说明该算法的有效性，同时设计基于NSGA-II的多目标遗传算法.针对本文算例，对蚁群算法中的各参数进行了敏感性分析，根据分析结果设定算法参数，获得了算例的Pareto最优路径集，同时与NSGA-II算法及相关文献算法针对运行时间、收敛性和群体多样性进行比较.结果显示，本文设计的蚁群算法在这3个指标上均明显优于NSGA-II算法；在相同蚂蚁数量情况下，本文的算法在收敛性和群体多样性方面优于相关文献算法.

关键词: 交通工程, 带时间窗的车辆路径问题, 多目标优化, 蚁群算法, NSGA-II, 状态转移概率, 多重图

Abstract:

An ant colony algorithm is designed for the vehicle routing problem with time windows on multigraph. A mathematical bi-objectives optimization model of vehicle routing problem with time windows on multigraph is established firstly, and a search space construction method for the solution of the problem is proposed. Then, a state transition probability formula that combines the heuristic information about optimization objectives, time windows, pheromones is defined. In order to illustrate the effectiveness of the algorithm by comparison, a multi-objective genetic algorithm based on NSGA-II is designed at the same time. In the example, the sensitivity of each parameter in the ant colony algorithm is analyzed. According to the analysis results, the algorithm parameters are set up, and the Pareto-optimal path set of the example is obtained. The CPU time, convergence and population diversity are compared with the NSGA-II algorithm and existing ant colony algorithm. The comparison results show that the three indexes of the ant colony algorithm designed are more competitive than the NSGA-II algorithm, and convergence and population diversity are better than existing ant colony algorithm.

Key words: traffic engineering, vehicle routing problem with time windows, multi-objective optimization, ant colony optimization, NSGA-II, transition probability, mutilgraph.

中图分类号:

U492.3
TP312

柴获，何瑞春，苏江省，宋宇博，代存杰，马昌喜. 求解双目标带时间窗车辆路径问题的蚁群算法[J]. 交通运输系统工程与信息, 2018, 18(4): 156-162.

CHAI Huo, HE Rui-chun, SU Jiang-sheng, SONG Yu-bo, DAI Cun-jie, MA Chang-xi. An Ant Colony Optimization for the Bi-objective Vehicle Routing Problem with Time Windows on Mutilgraph[J]. Journal of Transportation Systems Engineering and Information Technology, 2018, 18(4): 156-162.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract19675.shtml

http://www.tseit.org.cn/CN/Y2018/V18/I4/156

参考文献

[1] JOZEFOWIEZ N, SEMET F, TALBI E. Multi-objective vehicle routing problems[J]. European Journal of Operational Research, 2008, 189(2): 293-309.

[2] WANG J, ZHOU Y, WANG Y, et al. Multiobjective vehicle routing problems with simultaneous delivery and pickup and time windows: Formulation, instances, and algorithms[J]. IEEE Transactions on Cybernetics, 2016, 46(3): 582-594.

[3] KOVACS A A, PARRAGH S N, HARTL R F. The multiobjective generalized consistent vehicle routing problem[J]. European Journal of Operational Research, 2015, 247(2): 441-458.

[4] BALDACCI R, BODIN L, MINGOZZI A. The multiple disposal facilities and multiple inventory locations rollon-rolloff vehicle routing problem[J]. Computers & Operations Research, 2006, 33(9): 2667-2702.

[5] GARAIX T, ARTIGUES C, FEILLET D, et al. Vehicle routing problems with alternative paths: An application to on-demand transportation[J]. European Journal of Operational Research, 2010, 204(1): 62-75.

[6] BEN TICHA H, ABSI N, FEILLET D, et al. Empirical analysis for the VRPTW with a multigraph representation for the road network[J]. Computers & Operations Research, 2017, 88(Supplement C): 103-116.

[7] LAI D S W, CALISKAN DEMIRAG O, LEUNG J M Y. A tabu search heuristic for the heterogeneous vehicle routing problem on a multigraph[J]. Transportation Research Part E: Logistics and Transportation Review, 2016(86): 32-52.

[8] PRADHANANGA R, TANIGUCHI E, YAMADA T, et al. Bi-objective decision support system for routing and scheduling of hazardous materials[J]. SocioEconomic Planning Sciences, 2014, 48(2): 135-148.

[9] 唐泳, 马永开. 用改进蚁群算法求解多目标优化问题 [J]. 电子科技大学学报, 2005, 34(2): 281-284. [TANG Y, MA Y K. An improved ant colony algorithm for multi-objective optimization[J]. Journal of University of Electronic Science and Technology of China, 2005, 34 (2): 281-284.]

[10] DORIGO M, BLUM C. Ant colony optimization theory: A survey[J]. Theoretical Computer Science, 2005, 344(2): 243-278.

[11] GAMBARDELLA L M, TAILLARD, AGAZZI G. MACSVRPTW: A multiple ant colony system for vehicle routing problems with time windows[R]. Manno: Istituto Dalle Molle Di Studi Sull Intelligenza Artificiale, 2001.

[12] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.

[13] ZITZLER E, DEB K, THIELE L. Comparison of multiobjective evolutionary algorithms: Empirical results[J]. Evolutionary Computation, 2000, 8(2): 173-195.

[14] DEB K, MOHAN M, MISHRA S. A fast multi-objective evolutionary algorithm for finding well-spread paretooptimal solutions[R]. Kanpur, India: Indian Institute of Technology, 2003.

[1]	林建新, 刘博, 赵霞, 张蕾. 基于混合约束自编码器的机动车工况智能构建方法[J]. 交通运输系统工程与信息, 2022, 22(2): 109-116.
[2]	戢晓峰, 耿昭师. 山区双车道公路货车碰撞预测的双变量冲突极值模型[J]. 交通运输系统工程与信息, 2022, 22(2): 230-238.
[3]	张建波, 孙建平, 徐春玲, 郭镜霞, 温慧敏, 宋国华. 考虑交通运行条件影响的驾驶员特征聚类[J]. 交通运输系统工程与信息, 2022, 22(2): 330-336.
[4]	马景峰, 任刚, 李豪杰, 曹奇, 杜建玮. 电动自行车与机动车事故严重性影响因素分析[J]. 交通运输系统工程与信息, 2022, 22(2): 337-348.
[5]	宗芳, 王猛, 贺正冰. 考虑多车影响的分子动力学智能网联跟驰模型[J]. 交通运输系统工程与信息, 2022, 22(1): 37-48.
[6]	马小龙, 余强, 刘建蓓. 基于路侧毫米波雷达的车辆碰撞概率计算方法[J]. 交通运输系统工程与信息, 2022, 22(1): 57-66.
[7]	廖鹏, 唐铁桥. 基于车辆动力传动和转向系统的换道轨迹优化策略[J]. 交通运输系统工程与信息, 2022, 22(1): 98-105.
[8]	刘永红, 罗霞, 胡剑鹏. 考虑临时和预约需求的共享泊位动态分配方法[J]. 交通运输系统工程与信息, 2022, 22(1): 171-181.
[9]	袁振洲, 郭曼泽, 彭泳鑫, 杨洋. 基于梯度关联规则的老年行人交通事故风险识别[J]. 交通运输系统工程与信息, 2022, 22(1): 195-208.
[10]	张玉婷, 陈波佑, 张双焱, 闫学东, 李晓梦. 抵近信控交叉口分心驾驶识别模型[J]. 交通运输系统工程与信息, 2022, 22(1): 217-224.
[11]	宋浪, 王健, 杨滨毓, 安实. 连续流交叉口左转非机动车交通组织创新设计[J]. 交通运输系统工程与信息, 2022, 22(1): 225-233.
[12]	白婧荣, 唐伯明, 孙宗元, 毕辉云, 向恬君. 毗邻互通立交特长隧道驾驶负荷研究[J]. 交通运输系统工程与信息, 2022, 22(1): 301-310.
[13]	郭彦茹, 罗志雄, 王家川, 何方. 数据驱动的共享单车停放区规划方法研究[J]. 交通运输系统工程与信息, 2021, 21(6): 9-16.
[14]	李君羡, 沈宙彪, 童文聪, 吴志周. 基于分类车头时距的城市道路大型车影响分析[J]. 交通运输系统工程与信息, 2021, 21(6): 55-62.
[15]	卢凯, 周志洁, 张勇刚, 赵世杰, 徐广辉. 面向单向交通路网的绿波协调设计方法[J]. 交通运输系统工程与信息, 2021, 21(6): 74-83.