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

计算机工程与应用 ›› 2013, Vol. 49 ›› Issue (2): 24-28.

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

王君

天津财经大学商学院，天津 300222

出版日期:2013-01-15 发布日期:2013-01-16

Differential evolution hybrid algorithm for vehicle routing problem with time windows

WANG Jun

School of Business, Tianjin University of Finance & Economics, Tianjin 300222, China

Online:2013-01-15 Published:2013-01-16

摘要/Abstract

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

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

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

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

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

[1]	姚洪刚，沐年国. EMD-LSTM模型对金融时间序列的预测[J]. 计算机工程与应用, 2021, 57(5): 239-244.
[2]	许德刚，李凡，王露，郭奕欣，邢奎杰，梁腾翔. 优化烟花算法在医疗物资应急调度中的应用[J]. 计算机工程与应用, 2021, 57(24): 249-258.
[3]	李倩，蒋丽，梁昌勇. 基于模糊时间窗的多目标冷链配送优化[J]. 计算机工程与应用, 2021, 57(23): 255-262.
[4]	王琛，茅健. 基于时间窗模型的双向机器人路径规划方法[J]. 计算机工程与应用, 2021, 57(23): 287-294.
[5]	钱峥远，曾国荪. 精英化岛屿种群引导的差分进化算法[J]. 计算机工程与应用, 2021, 57(20): 73-81.
[6]	马艳芳，李保玉，杨屹夫，冯翠英. 客户分类下生鲜配送两级路径问题与算法研究[J]. 计算机工程与应用, 2021, 57(20): 287-298.
[7]	马龙，王春嬉，张正义，董睿. 多目标多时间窗车辆路径问题的鸽群-水滴算法[J]. 计算机工程与应用, 2021, 57(2): 237-250.
[8]	丁一，张成成. 集装箱码头送箱外集卡预约优化研究[J]. 计算机工程与应用, 2021, 57(19): 267-273.
[9]	付朝晖，刘长石. 多物流中心共同配送的车辆路径问题研究[J]. 计算机工程与应用, 2021, 57(16): 291-298.
[10]	崔彩霞，毕超超，范勤勤. 基于隐马尔可夫链的自适应MODE及应用[J]. 计算机工程与应用, 2021, 57(14): 83-94.
[11]	张凯，靳鹏，崔勇. 带时间窗的多车型需求可拆分揽收配送问题[J]. 计算机工程与应用, 2021, 57(14): 281-288.
[12]	李荣，贺兴时，杨新社. 基于差分进化的飞蛾算法在电力调度中的应用[J]. 计算机工程与应用, 2021, 57(13): 258-268.
[13]	陈展，公建宁，刘媛媛，徐京邦. 基于禁忌搜索的多AGV系统路径优化算法[J]. 计算机工程与应用, 2021, 57(10): 273-278.
[14]	付朝晖，刘长石. 生鲜电商配送的开放式时变车辆路径问题研究[J]. 计算机工程与应用, 2021, 57(1): 271-278.
[15]	梁承姬，黄帅. 考虑时间窗的集装箱港口场桥全局调度优化[J]. 计算机工程与应用, 2020, 56(8): 226-232.