带时间窗动态车辆路径问题的优化调度策略

doi:10.3969/j.issn.1000-3428.2012.13.041

计算机工程 ›› 2012, Vol. 38 ›› Issue (13): 137-141.doi: 10.3969/j.issn.1000-3428.2012.13.041

带时间窗动态车辆路径问题的优化调度策略

王君¹，李波²，卢志刚¹

(1. 天津财经大学商学院，天津 300222；2. 天津大学管理与经济学部，天津 300072)

收稿日期:2011-12-31 出版日期:2012-07-05 发布日期:2012-07-05
作者简介:王君(1983－)，男，博士，主研方向：物流工程，智能优化；李波，教授、博士生导师；卢志刚，教授
基金项目:
国家社科基金资助项目(11CGL102)；新世纪优秀人才支持计划基金资助项目(NCET-06-0236)；高等学校博士学科点专项科研基金资助项目(20100032110034)；天津财经大学科研发展基金资助项目(Y1110, Q1208)

Optimization Schedule Strategy for Dynamic Vehicle Routing Problem with Time Window

WANG Jun ¹, LI Bo ², LU Zhi-gang ¹

(1. School of Business, Tianjin University of Finance & Economics, Tianjin 300222, China; 2. College of Management and Economics, Tianjin University, Tianjin 300072, China)

Received:2011-12-31 Online:2012-07-05 Published:2012-07-05

摘要/Abstract

摘要： 针对带时间窗动态车辆路径问题(DVRPTW)，根据优化时间点的选取建立DVRPTW的一系列静态子模型，研究优化调度策略，分别是基于新顾客插入后的重复优化方法、批处理的方法或两者的混合。通过定义紧急顾客，提出一种新的紧急顾客插入和分批驱动调度策略，该策略只需实时插入紧急顾客，具有快速响应、计算负荷小和路径计划更新频率低的优点。仿真对比实验比较了4种策略的优劣，并探讨分批优化间隔长度对调度性能的影响。

关键词: 动态车辆路径问题, 调度策略, 批优化, 实时优化, 时间窗, 紧急顾客

Abstract: Aiming at the Dynamic Vehicle Routing Problem with Time Windows(DVRPTW), a series of static DVRPTW sub-models are established according to the optimization times, and four dynamic schedule strategies are provided to optimize the DVRPTW. Three of the strategies are based on a repeated reoptimization of various instances of the static problem, the batch optimization and a hybrid of both. The fourth is a new one called the emergency customer insertion and batch optimization strategy. This strategy only distinguishes the emergency customers and inserts them into real-time routing plan, and hence has the advantages of quick response, small computational load and low update frequency while routing the vehicles. Simulation experiments compare four strategies and discuss the impact of batch schedule intervals on the schedule performance.

Key words: Dynamic Vehicle Routing Problem(DVRP), schedule strategy, batch optimization, real-time optimization, time window, emergency customer

中图分类号:

TP29

王君, 李波, 卢志刚. 带时间窗动态车辆路径问题的优化调度策略[J]. 计算机工程, 2012, 38(13): 137-141.

WANG Jun, LI Bei, LEI Zhi-Gang. Optimization Schedule Strategy for Dynamic Vehicle Routing Problem with Time Window[J]. Computer Engineering, 2012, 38(13): 137-141.

[1]	杨凯琪, 姚培, 赵玉龙, 汤凌韬. 面向异构容器云的应用迁移方法[J]. 计算机工程, 2019, 45(8): 42-47.
[2]	彭晓燕,张彬,贾明菲,温开虎. FlexRay总线静态段消息重传调度策略[J]. 计算机工程, 2019, 45(5): 99-104.
[3]	刘彪,王宝生,邓文平. 云环境下支持弹性伸缩的容器化工作流框架[J]. 计算机工程, 2019, 45(3): 7-13.
[4]	张阳,李雄飞. 基于时间窗口的舆情异动量化模型[J]. 计算机工程, 2019, 45(3): 315-320.
[5]	王劲松,李军燕,张洪玮. 基于IPv6的大规模网络异常流量检测系统设计[J]. 计算机工程, 2018, 44(10): 14-21.
[6]	郭小波,李松涛,张德贤. 基于联合退避-功率感知机制的物联网节点信息防碰撞算法[J]. 计算机工程, 2017, 43(6): 46-52.
[7]	焦文喆,翟正军,王国庆. 时间触发AFDX调度设计及实时性分析[J]. 计算机工程, 2016, 42(7): 42-48.
[8]	刘静. 应用混合队列调度策略的AFDX实时性优化研究[J]. 计算机工程, 2015, 41(11): 135-141.
[9]	韦炜,全渝娟,卓奕涛,陈学亮,林艳. 基于多阶马尔可夫预测的个性化推荐算法[J]. 计算机工程, 2015, 41(11): 59-66.
[10]	陈曙光,马志超. 无线体域网中基于能量有效性的动态调度策略[J]. 计算机工程, 2015, 41(1): 103-109.
[11]	王群,戴秀岳,杨莉. 一种基于直觉模糊理论的P2P动态信任模型 [J]. 计算机工程, 2014, 40(8): 133-137.
[12]	杨春明，张晖，石大文. BBS网络舆情的在线自适应话题演化模型[J]. 计算机工程, 2014, 40(7): 317-321.
[13]	张艳梅,王璐. 适应用户兴趣变化的社会化标签推荐算法研究[J]. 计算机工程, 2014, 40(11): 318-321.
[14]	王连锋, 宋建社, 曹继平, 叶庆. 带硬时间窗模糊车辆路径问题的多目标优化[J]. 计算机工程, 2013, 39(4): 9-13,17.
[15]	黄国伟, 陈志. P2P流媒体数据块的优化调度策略[J]. 计算机工程, 2013, 39(2): 90-93.

带时间窗动态车辆路径问题的优化调度策略

Optimization Schedule Strategy for Dynamic Vehicle Routing Problem with Time Window

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10