English

运筹学学报 ›› 2015, Vol. 19 ›› Issue (2): 72-82.doi: 10.15960/j.cnki.issn.1007-6093.2015.02.008

• 运筹学 • 上一篇    下一篇

一种基于双链量子编码的动态车辆路径问题解决策略

宁涛1,2,*, 陈荣1, 郭晨1, 梁旭2   

  1. 1. 大连海事大学信息科学技术学院, 辽宁大连 116026; 2. 大连交通大学软件学院, 辽宁大连 116045
  • 收稿日期:2014-09-28 出版日期:2015-06-15 发布日期:2015-06-15
  • 通讯作者: 宁涛 daliannt@126.com
  • 基金资助:

     国家自然科学基金(No. 61374114), 辽宁省教育厅科学研究项目(No. L2014183), 中央高校基本科研业务费资助项目(No. 3132014321), 辽宁省教育厅高校优秀人才青年学者成长计划(No. LJQ2013048), 大连市计划项目(No. 2014A11GX006)

A scheduling strategy for dynamic vehicle routing problem based on double chains coding

NING Tao1,2,*, CHEN Rong1, GUO Chen1, LIANG Xu2   

  1. 1.College of Information and Technology, Dalian Maritime University, Dalian   116026, Liaoning, China; 2.Institute of Software, Dalian Jiaotong University, Dalian  116045, Liaoning, China
  • Received:2014-09-28 Online:2015-06-15 Published:2015-06-15

PDF

1298

被引次数

12

摘要：

针对配送调度事件动态变化的动态车辆路径问题(DVRP), 以最小化运输成本、最小化配送时间 与最大化载货率为目标, 建立了问题的数学模型, 提出了改进的多相量子粒子群算法. 针对DVRP问题的特点, 提出基于车辆链和货物链的双链量子编码方法; 同时设计了基于周期和 重调度因子驱动的动态调度策略. 最后将方法应用于动态仿真算例, 并与其他经典算法比较, 结果验证了所提出方法的有效性.

关键词: 动态调度策略, 动态车辆路径问题, 多相量子粒子群算法, 双链量子编码

Abstract:

For the purpose of solving the scheduling of dynamic vehicle routing problem, this paper establishes the simulation model to minimize the cost and stability value and maximize the freight rate, and an improved hybrid multi-phases quantum particle swarm algorithm was proposed. Firstly, it proposes the method of double chains structure coding including vehicle allocation chain and goods chain. Secondly, it proposes a dynamic scheduling strategy based on period-driven and event-driven. Finally, a novel method is applied to a dynamic simulation and the result of comparing with other classical algorithms verifies its effectiveness.

Key words: dynamic scheduling strategy, dynamic vehicle routing problem, multi-phases quantum particle swarm algorithm, double chains coding