节约法用于车辆路径问题的综述和分析

决策树分析是一种将复杂问题简化为一系列决策节点和结果的工具，用于领导决策时理解可能路径 #生活技巧# #领导力技巧# #决策树分析#

　　

摘要：本文在对车辆路径问题中的一种启发式算法—Clarke-Wright法以及各种改进算法进行概论性说明的基础上，本文对Clarke-Wright法不能对原有路线中的内点进行合并这一约束条件进行了证明。最后，本文引入一种节约算法的改进形式——并行节约算法，并利用算例体现了并行算法相对于经典节约算法的优势。

关键词：车辆路径问题  节约法  优化  并行算法

1 引言

车辆路径问题(vehicle routing Problem，VRP)是根据各有关道路情况、客户需求情况、车辆情况，为一些车辆设定访问客户的最佳路线。车辆的最佳路线必须满足：车辆从配送中心出发，完成配送任务，回到配送中心；每个客户由一辆车完成发送任务，且每辆车只能访问客户一次；车辆线路上的配送总任务不能超过车辆容量；完成任务运输费用最少；带有时间窗约束的车辆路径问题还需要满足时间窗的要求。

         车辆路径问题最早由Dantzig和Ramser于1959年提出【1】，并将其作为旅行商问题(TSP)来求解，属于NP难问题(Non-deterministic Polynomial hard problem)。但随着客户数量的增加，组合爆炸的问题随之显现出来，致使其求解过程复杂而耗时，在实际运用的过程中受到了诸多的限制。启发式算法的运用成为解决车辆路径问题一种有效的方法。

目前用于解决车辆路径问题的启发式算法有遗传算法、禁忌搜索法、蚁群算法、模拟退火法、扫描法、两阶段法、神经网络算法等【2】。各种算法在实际运用的过程中各有所长，其中节约法是一种灵活性很高，易于扩展，应用最为广泛的一种算法。【3】

网址：节约法用于车辆路径问题的综述和分析 https://www.yuejiaxmz.com/news/view/324465

相关内容

【创新未发表】基于鱼鹰OOA求解带时间窗的骑手外卖配送路径规划问题，最优路径成本附Matlab代码
物流配送中心的VPR问题的节约里程法课件
节约里程法求解CVRP问题
轨道交通列车综合节能研究综述
混合动力汽车节能机理及节能途径解析
基于节约里程法的配送路线优化研究——以苏宁电器为例
分析及抑制永磁同步电机电磁噪声方法综述
教育对主观幸福感的作用路径分析
城市道路路灯照明节能经济效益分析.pdf
二手车电子商务综述.ppt

随便看看