• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Transportation Research Part B: Methodological >Parametric search and problem decomposition for approximating Pareto-optimal paths
【24h】

Parametric search and problem decomposition for approximating Pareto-optimal paths

机译：近似帕累托最优路径的参数搜索和问题分解

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The multiobjective shortest path problem arises in many transportation and logistics appli-cations, either as a stand-alone network routing problem or a subroutine of a more com-plex multiobjective network optimization problem. It has been addressed by different solution strategies, including labeling methods, ranking methods, constraint methods, and parametric methods. Increasing attention has been paid to parametric methods in recent years, partially because of its simple algorithmic logic and its flexibility of being used in different user-preference decision-making environments. The core idea of a para-metric algorithm is scalarization, by which a multiobjective shortest path problem can be tackled by repeatedly solving a single-objective subproblem. However, existing para-metric algorithms suffer two notorious deficiencies, which considerably limit its further applications: first, typical subroutines for the single-objective subproblem in general can-not capture nonextreme Pareto-optimal paths; second, parametric algorithms for biobjec-tive problems cannot be directly extended to solving multiobjective problems. This paper provides some algorithmic improvements that can partially overcome these deficiencies. In particular, the contribution of this work is twofold: first, in the biobjective parametric solu-tion framework, we propose an approximate label-setting algorithm for the parameterized, constrained single-objective subproblem, which is capable of identifying all extreme paths and a large percentage (i.e., 85-100%) of nonextreme paths; second, we suggest a general projection scheme that can decompose a multiobjective problem into a number of biobjec-tive problems. The approximate parametric algorithm runs in polynomial time. The algo-rithmic design and solution performance of the algorithm for multiobjective shortest path problems are illustrated, and numerically evaluated and compared with a benchmark algorithm in terms of solution completeness and efficiency.
机译：多目标最短路径问题出现在许多运输和物流应用中，它们要么是一个独立的网络路由问题，要么是一个更为复杂的多目标网络优化问题的子例程。它已通过不同的解决方案策略来解决，包括标记方法，排名方法，约束方法和参数方法。近年来，由于其简单的算法逻辑以及在不同的用户偏好决策环境中使用的灵活性，参数化方法受到了越来越多的关注。参数化算法的核心思想是标量化，通过重复求解单目标子问题，可以解决多目标最短路径问题。但是，现有的参数算法存在两个臭名昭著的缺陷，这大大限制了其进一步的应用：首先，一般来说，单目标子问题的典型子例程无法捕获非极端的帕累托最优路径；其次，用于双目问题的参数算法不能直接扩展到解决多目标问题。本文提供了一些算法上的改进，可以部分克服这些缺陷。特别地，这项工作的贡献是双重的：首先，在双目标参数解决方案框架中，我们针对参数化，约束的单目标子问题提出了一种近似标签设置算法，该算法能够识别所有极端路径和很大比例的非极端路径（即85-100％）；其次，我们提出了一种通用投影方案，该方案可以将多目标问题分解为许多双目标问题。近似参数算法以多项式时间运行。阐述了多目标最短路径问题算法的算法设计和求解性能，并在求解完整性和效率方面进行了数值评估，并与基准算法进行了比较。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号