English

运筹学学报 >

2015 , Vol. 19 >Issue 2: 72 - 82

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2015.02.008

运筹学

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

展开
  • 1. 大连海事大学信息科学技术学院, 辽宁大连 116026; 2. 大连交通大学软件学院, 辽宁大连 116045

收稿日期: 2014-09-28

  网络出版日期: 2015-06-15

基金资助

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

收起

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

Expand
  • 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 date: 2014-09-28

  Online published: 2015-06-15

Fold

摘要

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

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

本文引用格式

宁涛, 陈荣, 郭晨, 梁旭 . 一种基于双链量子编码的动态车辆路径问题解决策略[J]. 运筹学学报, 2015 , 19(2) : 72 -82 . DOI: 10.15960/j.cnki.issn.1007-6093.2015.02.008

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

参考文献

 
 Teodorovic D, Radivojevic G. A fuzzy logic approach to dynamic Dial-A-Ride problem [J].  Fuzzy Set and Systems, 2000, 116(16): 23-33.

 张建勇, 郭耀煌, 李军. 模糊需求信息条件下的车辆路径问题研究 [J]. 系统工程学报, 2004, 19(1): 74-78.
 Fu Z, Eglese R, Li LY. Corrigendum: A new tabu search algorithm for the open vehicle routing problem [J]. Journal of the Operational Research Society, 2006, 57(8): 1008-1018.
宁涛. 混合量子算法在车辆路径问题中应用的研究 [D]. 大连: 大连海事大学, 2013.

 Ishibuchi H, Murata T. A multi-objective genetic local search algorithm and its application to flow shop scheduling [J]. IEEE Transactions on Systems, Man, and Cybernetics-Part C: Applications and Reviews, 1998, 28(3): 392-403.

 Fattahi P, Fallahi A. dynamic scheduling in flexible job shop systems by considering simultaneously efficiency and stability [J]. Journal of Manufacturing Science and Technology, 2010, 2(2): 114-123.

 Bagheri A, Zandith M, Mahdavi I, et al. An artificial immune algorithm for the flexible job-shop scheduling problem [J]. Future Generation Computer Systems, 2010, 26(4): 533-541.

 汤健超. 基于混合进化算法的若干调度问题研究 [D]. 广州: 华南理工大学, 2012.

 张利平. 作业车间预反应式动态调度理论与方法研究 [D]. 武汉: 华中科技大学, 2013.

 Seyed H A, Rahmat M, Zandieh M Y. Developing two multi-objective evolutionary algorithms for the multi-objective flexible job shop scheduling problem [J]. The International Journal of Advanced Manufacturing Technology, 2013, 64(5): 915-932.

 

Options
文章导航

/

〈 〉