首页> 外文会议>Science and technology to promote harmonized production >AN EFFICIENT ALGORITHM FOR THE PARETO-SOLUTION OF A MULTI-OBJECTIVE NETWORK WITH SHORTEST PATH PROBLEM AND COMFORTABLE COST
【24h】

AN EFFICIENT ALGORITHM FOR THE PARETO-SOLUTION OF A MULTI-OBJECTIVE NETWORK WITH SHORTEST PATH PROBLEM AND COMFORTABLE COST

机译:具有最短路径问题和可负担成本的多目标网络的Pareto解的高效算法

获取原文
获取原文并翻译 | 示例

摘要

The simple shortest path problem is a well-known optimization problem, which is the problem of finding the shortest path connecting the two specific nodes of a directed or undirected graph. When considering not only the distances between the nodes but also other than the information, for example, toll, fuel cost or longitudinal level, the problem is formulated as a multi-objective shortest path problem that involves multiple conflicting objective functions. To solve the multi-objective single source shortest path problem is difficult because the multiple objectives have to be simultaneously optimized. Thus, few algorithms for this problem have been proposed yet. In this study, we consider two-objective shortest path problem, where the conception of "comfortable driving" are introduced, and propose 3 efficient algorithms for Pareto-solutions, based on “extended Dijkstra's algorithm”. One algorithm finds out all Pareto-solutions and the other two algorithms find out almost Pareto-solutions. From the results of the numerical experiments, we see proposed algorithm is efficient for the calculation of Pareto-solutions for the two-objective shortest path problem.
机译:简单最短路径问题是众所周知的优化问题,这是找到连接有向图或无向图的两个特定节点的最短路径的问题。当不仅考虑节点之间的距离而且考虑其他信息(例如通行费,燃料成本或纵向水平)时,该问题被表述为涉及多个冲突目标函数的多目标最短路径问题。解决多目标单源最短路径问题很困难,因为必须同时优化多个目标。因此,尚未提出用于该问题的算法。在这项研究中,我们考虑引入“舒适驾驶”概念的两目标最短路径问题,并基于“扩展Dijkstra算法”提出了3种有效的帕累托解决方案算法。一种算法找出所有帕累托解,而另两种算法找出几乎帕累托解。从数值实验的结果来看,我们提出的算法对于求解两目标最短路径问题的帕累托解是有效的。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号