电子学报 ›› 2015, Vol. 43 ›› Issue (4): 658-664.DOI: 10.3969/j.issn.0372-2112.2015.04.006

• 学术论文 • 上一篇    下一篇

求解带软时间窗车辆路径问题的改进伊藤算法及其收敛性分析

易云飞1,2,3, 董文永1, 林晓东2, 蔡永乐1   

  1. 1. 武汉大学计算机学院, 湖北武汉 430079;
    2. 河池学院计算机与信息工程学院, 广西宜州 546300;
    3. 广西混杂计算与集成电路设计分析重点实验室, 广西南宁 530006
  • 收稿日期:2014-03-10 修回日期:2014-08-22 出版日期:2015-04-25 发布日期:2015-04-25
  • 作者简介:易云飞 男,1981年出生于广西资源,武汉大学计算机学院博士生,副教授,研究方向为智能计算、机器学习等.E-mail:gxyiyf@163.com;董文永 男,1973年出生于河南南阳,武汉大学计算机学院教授,博士生导师,长期从事演化计算、机器学习、数据挖掘等方面的研究工作E-mail:hubei_001@163.com
  • 基金资助:

    国家自然科学基金(No.60873114,No.61170305);广西自然科学基金(No.2013GXNSFBA019282);广西混杂计算与集成电路设计分析重点实验室开放基金课题(No.HCI201411);国家级大学生创新创业训练计划(No.201310605017,No.201310605018)

The Improved ITO Algorithm to Solve the Vehicle Routing Problem with Soft Time Windows and Its Convergence Analysis

YI Yun-fei1,2,3, DONG Wen-yong1, LIN Xiao-dong2, CAI Yong-le1   

  1. 1. Computer School, Wuhan University, Wuhan, Hubei 430079, China;
    2. College of Computer and Information Engineering, Hechi University, Yizhou, Guangxi 546300, China;
    3. Guangxi Key Laboratory of Hybrid Computation and IC Design Analysis, Nanning, Guangxi 530006, China
  • Received:2014-03-10 Revised:2014-08-22 Online:2015-04-25 Published:2015-04-25

摘要:

针对伊藤算法在求解离散组合优化问题时效率较低、收敛性较差等缺陷,本文提出的改进伊藤算法引入了协同扩散过程的漂移系数,采用局部搜索能力强的爬山法确定波动系数,将漂移和波动同步进行,当找到可行解之后再进行一定程度的波动.为了验证算法的有效性,将改进后的伊藤算法用于求解带软时间窗的车辆路径问题.仿真结果表明,改进后的算法效率更高,收敛速度更快,算法稳定性和健壮性也更好.此外,本文还根据马尔科夫链移向吸引元的性质及其各状态之间的转换关系,探讨了构造伊藤随机微分方程的马尔科夫链近似模拟算法及其收敛性证明.

关键词: 伊藤算法, 漂移算子, 波动算子, 收敛性分析, 带软时间窗车辆路径问题

Abstract:

In order to overcome the shortcoming of the efficiency of the Ito algorithm for the discrete combinatorial optimization problems,an improved Ito algorithm based on collaborative diffusion coefficient and Hill climbing was proposed in this paper.To be consistent with the principle of Brownian motion,the drift and wave should be moved simultaneously,when it found a feasible solution,which continued to be a degree of renewed volatility.Experimental results show that the improved Ito algorithm for solving vehicle routing problem with a soft time window is valid,with the convergence speed,robustness and stability,especially Ito algorithm combines the ability of local search algorithms after climbing method performance has been greatly improved.Finally,according the nature of Markov chain to move to its attractive element and the transformation of the relationship between each state,the Markov chain approximation simulation algorithm which structures the Ito stochastic differential equation and its convergence was proved in this paper.

Key words: Ito algorithms, drift operator, wave operator, convergence analysis, vehicle routing problem with soft time windows

中图分类号: