Differential evolution hybrid algorithm for vehicle routing problem with time windows

Abstract

Abstract: The Vehicle Routing Problem with Time Windows（VRPTW）is addressed in this paper.A mathematical model is built and a discrete differential evolution hybrid algorithm for VRPTW is designed.In the algorithm，the population is initialized by a random vehicle loading method，and improved by new discrete mutation and crossover operators.Moreover，the tabu search is introduced to enhance the local searching capability of the algorithm，in which insertion and 2-Opt feasible neighborhoods are used to search feasible solutions.Experimental results show the effectiveness of the proposed approach for the VRPTW.

Key words: Vehicle Routing Problem（VRP）, time window, differential evolution algorithm, tabu search

摘要： 研究了带时间窗的车辆路径问题（Vehicle Routing Problem with Time Windows，VRPTW），建立了数学模型，并设计了求解VRPTW的离散差分进化混合算法。算法采用随机车辆配载方法构造初始解，并通过构造新的变异和交叉算子进行改进。进一步，利用插入可行邻域和2-Opt可行邻域两种搜索可行解的邻域结构，引入禁忌搜索进一步进行局部搜索以提高算法的寻优能力。实验结果表明该算法是求解VRPTW的一种有效方法。

关键词: 车辆路径问题, 时间窗, 差分进化算法, 禁忌搜索

WANG Jun. Differential evolution hybrid algorithm for vehicle routing problem with time windows[J]. Computer Engineering and Applications, 2013, 49(2): 24-28.

王君. 带时间窗车辆路径问题的差分进化混合算法[J]. 计算机工程与应用, 2013, 49(2): 24-28.

[1]	YAO Honggang, MU Nianguo. Prediction of Financial Time Series by EMD-LSTM Model [J]. Computer Engineering and Applications, 2021, 57(5): 239-244.
[2]	XU Degang, LI Fan, WANG Lu, GUO Yixin, XING Kuijie, LIANG Tengxiang. Application of Optimized Fireworks Algorithm in Emergency Dispatching of Medical Supplies [J]. Computer Engineering and Applications, 2021, 57(24): 249-258.
[3]	LI Qian, JIANG Li, LIANG Changyong. Multi-objective Cold Chain Distribution Optimization Based on Fuzzy Time Window [J]. Computer Engineering and Applications, 2021, 57(23): 255-262.
[4]	WANG Chen, MAO Jian. Path Planning Method of Bidirectional Robot Based on Time Window Model [J]. Computer Engineering and Applications, 2021, 57(23): 287-294.
[5]	MA Long, WANG Chunxi, ZHANG Zhengyi, DONG Rui. Pigeon-Inspired Optimization and Intelligent Water Drops Algorithm for Multiple-objective Vehicle Routing Problem with Multiple Time Windows [J]. Computer Engineering and Applications, 2021, 57(2): 237-250.
[6]	DING Yi, ZHANG Chengcheng. External Trucks’ Appointment Optimization of Delivering Containers from Outside at Container Terminal [J]. Computer Engineering and Applications, 2021, 57(19): 267-273.
[7]	CUI Caixia, BI Chaochao, FAN Qinqin. Self-Adaptive MODE Based on Hidden Markov Chain and Application [J]. Computer Engineering and Applications, 2021, 57(14): 83-94.
[8]	ZHANG Kai, JIN Peng, CUI Yong. Multi-vehicle Split Pickup and Delivery Problem with Time Windows [J]. Computer Engineering and Applications, 2021, 57(14): 281-288.
[9]	WEN Da, CUI Shuangxi, FAN Xiaochao, JIANG Guojun. Two-Level Optimal Dispatching of Active Distribution Network Considering Source-Load Interaction [J]. Computer Engineering and Applications, 2021, 57(10): 259-265.
[10]	CHEN Zhan, GONG Jianning, LIU Yuanyuan, XU Jingbang. Multi-AGV System Path Optimization Algorithm Based on Tabu Search [J]. Computer Engineering and Applications, 2021, 57(10): 273-278.
[11]	LIANG Chengji, HUANG Shuai. Scheduling Optimization of Multiple Container Blocks with Multiple Yard Cranes at Container Terminal Based on Time Window [J]. Computer Engineering and Applications, 2020, 56(8): 226-232.
[12]	LU Hang, SHI Zhibin, LIU Zhongbao. Collaboration Filtering Recommendation Algorithm Based on User Interest and Ratings Difference [J]. Computer Engineering and Applications, 2020, 56(7): 24-29.
[13]	SHEN Xin, ZOU Dexuan, ZHANG Qiang. Adaptive Differential Evolution Algorithm Using Double Mutation Strategies and Its Application [J]. Computer Engineering and Applications, 2020, 56(4): 146-157.
[14]	CHEN Guangfeng, YU Lichao. Multi-frame Time Window Rotation Algorithm to Plan Storage Multiple AGV Car Path [J]. Computer Engineering and Applications, 2020, 56(23): 270-278.
[15]	MA Yanfang, YING Bin, KANG Kai, LUAN Xinfeng. Algorithms for Green Simultaneous Pickup and Delivery Problem with Fuzzy Demand [J]. Computer Engineering and Applications, 2020, 56(16): 248-257.

Differential evolution hybrid algorithm for vehicle routing problem with time windows

带时间窗车辆路径问题的差分进化混合算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics