MDVRPTW问题多阶段迭代启发式算法

计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (26): 217-222.

MDVRPTW问题多阶段迭代启发式算法

洪联系^1,2,董绍华¹

1.北京科技大学机械工程学院,北京 100083
2.集美大学计算机工程学院,福建厦门 361021

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-09-11 发布日期:2007-09-11
通讯作者: 洪联系

Multi-phase iterative heuristic approach for solving MDVRPTW

HONG Lian-xi^1,2,DONG Shao-hua¹

1.University of Science and Technology Beijing,Beijing 100083,China
2.Jimei University,Xiamen,Fujian 361021,China

Received:1900-01-01 Revised:1900-01-01 Online:2007-09-11 Published:2007-09-11
Contact: HONG Lian-xi

摘要/Abstract

摘要： 提出一个求解多车库VRPTW问题的聚类和迭代混合遗传算法。该算法采用三阶段过程：客户聚类分配、路径规划和路径改进,与以往两阶段算法不同,该算法采用混合遗传算法进行路径规划,采用竞争-插入进行路径改进,且路径规划与路径改进有机结合形成迭代路径规划过程。用Cordeau等人提出的算例实验表明该算法能够在可以接受的计算时间内得到可接受的好解。

关键词: MDVRPTW, 混合遗传算法, 聚类

Abstract: The paper proposes a iterative hybrid genetic algorithm based on nodes clustering for solving multi-depot vehicle routing problem with time windows.The approach adopts three phases procedure：customers clustering assignment,routing and routes improvement.Differing from two phases’ algorithm,the algorithm adopts the hybrid genetic algorithm for routing,adopts competition-insertion for improvement routes,and combines the routing with improvement routes to form an iterative routing procedure.The computation results of the instances that are proposed by Cordeau et al. show that the algorithm can gain acceptable good solutions in the reasonable time.

Key words: Multi-Depot Vehicle Routing Problem with Time Windows（MDVRPTW）, hybrid genetic algorithm, clustering

洪联系^1,2,董绍华¹. MDVRPTW问题多阶段迭代启发式算法[J]. 计算机工程与应用, 2007, 43(26): 217-222.

HONG Lian-xi^1,2,DONG Shao-hua¹. Multi-phase iterative heuristic approach for solving MDVRPTW[J]. Computer Engineering and Applications, 2007, 43(26): 217-222.

[1]	兰红，黄敏. 融合KNN优化的密度峰值和FCM聚类算法[J]. 计算机工程与应用, 2021, 57(9): 81-88.
[2]	郭晓静，隋昊达. 改进YOLOv3在机场跑道异物目标检测中的应用[J]. 计算机工程与应用, 2021, 57(8): 249-255.
[3]	李莉，纪欣沅，宋嵩. 回环软件缺陷数量预测模型[J]. 计算机工程与应用, 2021, 57(7): 158-163.
[4]	杨芳，尹曦，司建辉，刘宏媛，汪雪. 基于侧重点聚类的数学表达式相似度计算方法[J]. 计算机工程与应用, 2021, 57(6): 88-93.
[5]	赵凡，张琳，闻治泉，杨林林，蔺广逢. 一种直接高效的自然场景汉字逼近定位方法[J]. 计算机工程与应用, 2021, 57(6): 159-167.
[6]	霍光煜，张勇，孙艳丰，尹宝才. 基于语义的档案数据智能分类方法研究[J]. 计算机工程与应用, 2021, 57(6): 247-253.
[7]	彭启慧，宣士斌，高卿. 分布的自动阈值密度峰值聚类算法[J]. 计算机工程与应用, 2021, 57(5): 71-78.
[8]	李勇振，廖湖声. 基于图卷积神经网络的多视角聚类[J]. 计算机工程与应用, 2021, 57(5): 115-122.
[9]	王昌龙，张远东，缪宏，杨煜恒. 双通道卷积神经网络在南瓜病害识别上的应用[J]. 计算机工程与应用, 2021, 57(5): 183-189.
[10]	胡晓敏，王明丰，张首荣，李敏. 用于文本聚类的新型差分进化粒子群算法[J]. 计算机工程与应用, 2021, 57(4): 61-67.
[11]	王俊玲，卢新明. 基于语义相关的视频关键帧提取算法[J]. 计算机工程与应用, 2021, 57(4): 192-198.
[12]	王芙银，张德生，张晓. 结合鲸鱼优化算法的自适应密度峰值聚类算法[J]. 计算机工程与应用, 2021, 57(3): 94-102.
[13]	陈俊丰，郑中团. WKMeans与SMOTE结合的不平衡数据过采样方法[J]. 计算机工程与应用, 2021, 57(23): 106-112.
[14]	张忠林，赵昱，闫光辉. 自然邻居密度极值聚类算法[J]. 计算机工程与应用, 2021, 57(23): 200-210.
[15]	梅婕，魏圆圆，许桃胜. 基于密度峰值多起始中心的融合聚类算法[J]. 计算机工程与应用, 2021, 57(22): 78-85.