带时间窗口动态车辆路径规划模型及其求解算法

计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (4): 244-248.

• 工程与应用 • 上一篇

带时间窗口动态车辆路径规划模型及其求解算法

洪联系

集美大学计算机工程学院，福建厦门 361021

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2012-02-01 发布日期:2012-04-05

Model of dynamic vehicle routing problem with time windows and its solution algorithm

HONG Lianxi

School of Computer Engineering, Jimei University, Xiamen, Fujian 361021, China

Received:1900-01-01 Revised:1900-01-01 Online:2012-02-01 Published:2012-04-05

摘要/Abstract

摘要： 基于事件触发，把带时间窗口动态车辆路径规划问题（DVRPTW）分解成一系列延迟快照，在快照基础上建立相应的动态数学模型，并提出双缓冲区改进大邻域搜索算法进行求解。利用算法的特点，实现新请求无缝插入。采用Solomon设计的56个100节点范例和Lackner相应的动态测试数据，经不同类型动态实例的实验表明，所建立的模型和给出的算法是有效的。

关键词: 动态车辆路径规划问题（DVRP）, 时间窗口, 大邻域搜索, 实时规划, 启发式算法

Abstract: The Dynamic Vehicle Routing Problem with Time Windows（DVRPTW） is broken down into a series of delaying snapshots based on event-trigger. And a dynamic model of DRPTW is established based on these snapshots. An improved large neighborhood search algorithm with double buffers is presented to solve the problem. The algorithm can implement that the latest requests are inserted steady. Computational results of a large number of test problems, which are cited from Solomon’s static benchmarks and Lacker’s dynamic data set, show that the model and method are valid and are superior to other methods in most instances.

Key words: Dynamic Vehicle Routing Problem（DVRP）, time windows, Large Neighborbood Search（LNS）, real routing, heuristics

洪联系. 带时间窗口动态车辆路径规划模型及其求解算法[J]. 计算机工程与应用, 2012, 48(4): 244-248.

HONG Lianxi. Model of dynamic vehicle routing problem with time windows and its solution algorithm[J]. Computer Engineering and Applications, 2012, 48(4): 244-248.

[1]	姚洪刚，沐年国. EMD-LSTM模型对金融时间序列的预测[J]. 计算机工程与应用, 2021, 57(5): 239-244.
[2]	张呈玲，李进金，林艺东. 基于OE-概念格的形式背景属性约简[J]. 计算机工程与应用, 2021, 57(15): 82-89.
[3]	陆航，师智斌，刘忠宝. 融合用户兴趣和评分差异的协同过滤推荐算法[J]. 计算机工程与应用, 2020, 56(7): 24-29.
[4]	孟鑫，杨琴，郝婷婷，张洁，曹策俊. 不同订单分配和算法下的拣货路径优化组合[J]. 计算机工程与应用, 2020, 56(23): 229-236.
[5]	李雅丽，王淑琴，陈倩茹，王小钢. 若干新型群智能优化算法的对比研究[J]. 计算机工程与应用, 2020, 56(22): 1-12.
[6]	易成岐，郭鑫，童楠楠，窦悦，陈东，王建冬. 基于启发式社团发现模型的创新态势研判算法[J]. 计算机工程与应用, 2020, 56(15): 74-79.
[7]	胡晓敏，梁天毅，王明丰，李敏. 新型树启发式搜索算法的机器人路径规划[J]. 计算机工程与应用, 2020, 56(11): 164-171.
[8]	迟宗正，董绍正，郭童，任志磊，周宽久，郭禾. 求解风力发电机布局问题的超启发式算法研究[J]. 计算机工程与应用, 2019, 55(7): 220-225.
[9]	尚正阳1，顾寄南2，唐仕喜2，孙晓红2. 高效求解三维装箱问题的剩余空间最优化算法[J]. 计算机工程与应用, 2019, 55(5): 44-50.
[10]	侯屿1，2，秦小林2，彭皓月1，2，张力戈1，2. 全局调距和声特征选择算法[J]. 计算机工程与应用, 2019, 55(2): 21-27.
[11]	张钧，贺可太. 求解三维装箱问题的混合遗传模拟退火算法[J]. 计算机工程与应用, 2019, 55(14): 32-39.
[12]	刘竹松，李生. 正余混沌双弦鲸鱼优化算法[J]. 计算机工程与应用, 2018, 54(7): 159-163.
[13]	王长宝1，杨习贝1，2，窦慧莉1，陈向坚1，王平心3. 邻域决策错误率的局部约简方法研究[J]. 计算机工程与应用, 2018, 54(6): 95-99.
[14]	吴伟民，李泽熊，林志毅，吴汪洋，方典禹. 飞蛾纵横交叉混沌捕焰优化算法[J]. 计算机工程与应用, 2018, 54(3): 136-141.
[15]	王转，裴泽平. 启发式路径下节约里程的订单分批算法[J]. 计算机工程与应用, 2018, 54(23): 203-209.

带时间窗口动态车辆路径规划模型及其求解算法

Model of dynamic vehicle routing problem with time windows and its solution algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics