物流配送车辆路径问题的优化研究

J4 ›› 2011, Vol. 33 ›› Issue (5): 106-111.

物流配送车辆路径问题的优化研究

巩固，胡晓婷，卫开夏，郝国生

（徐州师范大学计算机科学与技术学院，江苏徐州 221116）

收稿日期:2010-04-16 修回日期:2010-08-13 出版日期:2011-05-25 发布日期:2011-05-25
作者简介:巩固(1976),男,安徽宿州人，硕士生，讲师，研究方向为智能计算和数据挖掘。胡晓婷(1977),女,甘肃秦安人，硕士，讲师，研究方向为密码学和安全协议。卫开夏(1965),男，安徽芜湖人，博士，副教授，研究方向为计算机测控及应用技术。郝国生(1972),男，河北万全人，硕士生，副教授，研究方向为进化计算。
基金资助:
江苏省高校自然科学基础研究（09KJB120003）；徐州师范大学项目基金（08XBL14）

Optimized Performance Research of the Vehicle Routing Problem in Industry Logistics

GONG Gu,HU Xiaoting,WEI Kaixia,HAO Guosheng

（School of Computer Science and Technology,Xuzhou Normal University,Xuzhou 221116,China）

Received:2010-04-16 Revised:2010-08-13 Online:2011-05-25 Published:2011-05-25

摘要/Abstract

摘要：

物流中的车辆路径问题（VRP）是目前组合优化领域的研究热点问题，VRP为NPhard问题。本文在对VRP分析的基础上，建立数学模型，提出了一种适合求解该问题的蚁群遗传融合优化算法。提出的优化算法首先采用蚁群算法在局部阶段产生最好解，然后利用遗传算法的优良基因在全局阶段对优化解进一步优化，以获取最好路径解。实验结果表明，提出的融合算法能高效解决VRP问题，且优化效果比单算法好。

关键词: 车辆路径问题, 融合优化算法, 蚁群算法, 遗传算法, 路径优化

Abstract:

The logistics distribution VRP, which is a typical NPhard problem, is a hot topic in the combinatorial optimization field at present. Based on the analysis about VRP, a mathematical model is built. Aiming at solving the vehicle routing problem, the paper puts forward a combinatorial optimization algorithm of ant colony and genetics in order to gain optimization. The combinatorial optimization algorithm adopts the ant colony algorithm to gain local optimization solution, and then makes use of the genetic algorithm which reserves some elitist genetic sense units that can steadily pass down to the son generation to optimize the local optimization solution for gaining a global optimization solution. The experimental results show that the combination optimization algorithm is efficient in solving VRP, and the optimization efficiency of the improved algorithm is superior to that of a single algorithm such as the ant colony algorithm or the genetic algorithm.

Key words: vehicle routing problem;combination optimization algorithm;ant colony algorithm;genetic algorithm;route optimization

巩固，胡晓婷，卫开夏，郝国生. 物流配送车辆路径问题的优化研究[J]. J4, 2011, 33(5): 106-111.

GONG Gu,HU Xiaoting,WEI Kaixia,HAO Guosheng. Optimized Performance Research of the Vehicle Routing Problem in Industry Logistics[J]. J4, 2011, 33(5): 106-111.

[1]	李成冉, 方佳豪, 尹首一, 魏少军, 胡杨. 基于遗传算法的晶圆级芯片映射算法研究[J]. 计算机工程与科学, 2024, 46(06): 993-1000.
[2]	任晟岐, 宋伟. 基于GGInformer模型的多维时间序列特征提取与预测研究[J]. 计算机工程与科学, 2024, 46(04): 590-598.
[3]	孙睿男, 初翔, 陈昱, 闫明宁. 基于混合启发式算法的快递末端选址路径优化研究[J]. 计算机工程与科学, 2024, 46(01): 159-169.
[4]	李中华, 袁杰, 郭振宇. 基于信息启发的目标导向Bi-RRT机器人路径规划[J]. 计算机工程与科学, 2023, 45(12): 2237-2245.
[5]	郭艺, 何廷年, 李爱斌, 毛君宇. 融合GA-CART和Deep-IRT的知识追踪模型[J]. 计算机工程与科学, 2023, 45(09): 1691-1700.
[6]	王扬, 陈智斌. 一种求解CVRP的动态图转换模型[J]. 计算机工程与科学, 2023, 45(05): 859-868.
[7]	顾楚梅, 曹建军, 王保卫, 徐雨芯, . 基于蚁群参数优化的LightGBM辐射源个体识别[J]. 计算机工程与科学, 2023, 45(01): 85-94.
[8]	赵广元, 赵英. 基于改进蚁群优化算法的养殖场机器人路径规划[J]. 计算机工程与科学, 2022, 44(05): 910-915.
[9]	刘雨青, 向军, 曹守启. 基于改进蚁群算法的水下自主航行机器人路径规划[J]. 计算机工程与科学, 2022, 44(03): 536-544.
[10]	胡平志, 李泽滔. 基于改进蚁群算法的四足机器人步态规划[J]. 计算机工程与科学, 2021, 43(12): 2253-2262.
[11]	宋阿妮, 包贤哲. 精英扩散蚁群优化算法求解运输无人机三维路径规划[J]. 计算机工程与科学, 2021, 43(10): 1891-1900.
[12]	毛媛媛, 石恩雅, 蒋从锋, 仇烨亮, 贾刚勇, 万健, 闫龙川. 基于遗传算法的数据中心能效仿真[J]. 计算机工程与科学, 2021, 43(08): 1341-1352.
[13]	胡新荣, 刘嘉文, 刘军平, 彭涛, 何儒汉, . 基于改进GA-BP-MC神经网络的人体三维尺寸预测[J]. 计算机工程与科学, 2021, 43(08): 1443-1453.
[14]	张瑾, 洪莉, 戴二壮. 求解带容量和时间窗约束车辆路径问题的改进蝙蝠算法[J]. 计算机工程与科学, 2021, 43(08): 1479-1487.
[15]	李静, 莫思敏 . 基于改进遗传算法的深度神经网络优化研究[J]. 计算机工程与科学, 2021, 43(08): 1503-1511.