改进NSGA II算法在车辆路径多目标优化问题中的应用

doi:10.3969/j.issn.1007130X.2010.

J4 ›› 2010, Vol. 32 ›› Issue (10): 117-121.doi: 10.3969/j.issn.1007130X.2010.

改进NSGA II算法在车辆路径多目标优化问题中的应用

徐慧英,赵建民，张泳，朱信忠

（浙江师范大学数理与信息工程学院,浙江金华 321004）

收稿日期:2010-03-29 修回日期:2010-06-05 出版日期:2010-09-29 发布日期:2010-09-25
作者简介:徐慧英(1977-),女,浙江金华人，硕士，讲师，研究方向为GPS/GIS应用、现代物流管理与优化；赵建民,教授,研究方向为制造业信息化与智能系统、模式识别与图像处理等；张泳，硕士生，研究方向为物流配送和路径优化；朱信忠，副教授，研究方向为制造业信息化、模式识别与数字工程、GPS/GIS应用开发等。
基金资助:
浙江省科技计划资助项目(2008C111062)

Application of the Improved NSGA II in Multi Objective Optimization for the Vehicle Routing Problem

XU Huiying,ZHAO Jianmin,ZHANG Yong,ZHU Xinzhong

（School of Mathematics,Physics and Information Engineering,Zhejiang Normal University,Jinhua 321004,China）

Received:2010-03-29 Revised:2010-06-05 Online:2010-09-29 Published:2010-09-25

摘要/Abstract

摘要：

本文选用NSGA II作为求解VRP多目标优化问题的算法基础，分析概括出VRP的三个主要目标函数和三个约束条件，实现了VRP多目标优化问题的数学建模。选择MATLAB作为软件工具进行代码编写，选取Benchmark Problems中C101里的数据作为实验数据进行软件仿真；并且针对NSGA II在设计方面的不足之处，对NSGA II的初始群体确定和交叉算子两个环节进行改进；然后通过对两种算法仿真结果的比较分析，证实了改进算法在克服早熟现象、提高算法效率以及算法稳定性方面的有效性。

关键词: 车辆路径问题, 多目标优化问题, 遗传算法, NSGA II

Abstract:

This paper solves the multobjective optimization for the VRPbased NSGA II. First of all, we analyses and generalizes three object functions and three constraints, and realize the mathematical modeling for VRP. Then we code in MATLAB, and choose the data in C101 of Benchmark Problems as the test data. Furthermore, we improve the determining of initail population and the crossover operator of NSGA II, against the shortcomings of design in NSGA II. By comparing the two algorithms, we verify the improved algorithm is effective in avoiding premature convergence, raising efficiency and stability.

Key words: VRP;multiobjective;optimization;GA;NSGA II

徐慧英,赵建民，张泳，朱信忠. 改进NSGA II算法在车辆路径多目标优化问题中的应用[J]. J4, 2010, 32(10): 117-121.

XU Huiying,ZHAO Jianmin,ZHANG Yong,ZHU Xinzhong. Application of the Improved NSGA II in Multi Objective Optimization for the Vehicle Routing Problem[J]. J4, 2010, 32(10): 117-121.

[1]	彭频, 王欣悦. 基于匮乏理论的应急物资调度模型构建及算法研究[J]. 计算机工程与科学, 2024, 46(11): 2063-2070.
[2]	安园园, 马晓宁. 改进遗传算法与多目标优化模型的航班路径规划[J]. 计算机工程与科学, 2024, 46(09): 1660-1666.
[3]	李成冉, 方佳豪, 尹首一, 魏少军, 胡杨. 基于遗传算法的晶圆级芯片映射算法研究[J]. 计算机工程与科学, 2024, 46(06): 993-1000.
[4]	任晟岐, 宋伟. 基于GGInformer模型的多维时间序列特征提取与预测研究[J]. 计算机工程与科学, 2024, 46(04): 590-598.
[5]	孙睿男, 初翔, 陈昱, 闫明宁. 基于混合启发式算法的快递末端选址路径优化研究[J]. 计算机工程与科学, 2024, 46(01): 159-169.
[6]	郭艺, 何廷年, 李爱斌, 毛君宇. 融合GA-CART和Deep-IRT的知识追踪模型[J]. 计算机工程与科学, 2023, 45(09): 1691-1700.
[7]	王扬, 陈智斌. 一种求解CVRP的动态图转换模型[J]. 计算机工程与科学, 2023, 45(05): 859-868.
[8]	毛媛媛, 石恩雅, 蒋从锋, 仇烨亮, 贾刚勇, 万健, 闫龙川. 基于遗传算法的数据中心能效仿真[J]. 计算机工程与科学, 2021, 43(08): 1341-1352.
[9]	胡新荣, 刘嘉文, 刘军平, 彭涛, 何儒汉, . 基于改进GA-BP-MC神经网络的人体三维尺寸预测[J]. 计算机工程与科学, 2021, 43(08): 1443-1453.
[10]	张瑾, 洪莉, 戴二壮. 求解带容量和时间窗约束车辆路径问题的改进蝙蝠算法[J]. 计算机工程与科学, 2021, 43(08): 1479-1487.
[11]	李静, 莫思敏 . 基于改进遗传算法的深度神经网络优化研究[J]. 计算机工程与科学, 2021, 43(08): 1503-1511.
[12]	李晶晶, 许少华. 基于组合核函数的径向基过程神经网络及其在示功图诊断中的应用[J]. 计算机工程与科学, 2021, 43(04): 746-752.
[13]	季子豪, 江凌云. 一种基于遗传算法的多站点协同计算卸载算法[J]. 计算机工程与科学, 2021, 43(03): 426-434.
[14]	贾俊杰, 秦海涛. 基于遗传算法的动态轨迹匿名算法[J]. 计算机工程与科学, 2021, 43(01): 142-150.
[15]	李丹莲, 曹倩, 徐菲. 基于改进遗传算法的连锁便利店配送路径优化[J]. 计算机工程与科学, 2020, 42(11): 2096-2102.

改进NSGA II算法在车辆路径多目标优化问题中的应用

Application of the Improved NSGA II in Multi Objective Optimization for the Vehicle Routing Problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

相关文章 15

编辑推荐

Metrics

本文评价