检索结果-内蒙古大学图书馆

Search for the best compromise solution on multiobjective shortest path problem

Electronic Notes in Discrete Mathematics 2010年第C期36卷 615-622页

作者： Sauvanet, G. Néron, E. Laboratoire d'Informatique Université François Rabelais - Polytech'Tours 37200 Tours 64 av. Jean Portalis France

This paper deals with the multiobjective shortest path problem in the context of routing for cycling. Many studies focus on the computation of the entire set of Pareto paths. Here we focus on the determination of a well-balanced trade-off path between the objectives. We recall the original Best Compromise A method and then we present two improvements in order to speed up the search of the best compromise solution. Finally we present various numerical tests on real-life instances, that prove the efficiency of the improved methods. © 2010 Elsevier B.V.

关键词： Best Compromise A multiobjective shortest path problem

来源：评论

学校读者我要写书评

暂无评论

multiobjective shortest path problems with lexicographic goal-based preferences

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2014年第1期239卷 89-101页

作者： Javier Pulido, Francisco Mandow, Lawrence Perez de la Cruz, Jose Luis Univ Malaga Dept Lenguajes & Ciencias Computac E-29071 Malaga Spain

multiobjective shortest path problems are computationally harder than single objective ones. In particular, execution time is an important limiting factor in exact multiobjective search algorithms. This paper explores the possibility of improving search performance in those cases where the interesting portion of the Pareto front can be initially bounded. We introduce a new exact label-setting algorithm that returns the subset of Pareto optimal paths that satisfy a set of lexicographic goals, or the subset that minimizes deviation from goals if these cannot be fully satisfied. Formal proofs on the correctness of the algorithm are provided. We also show that the algorithm always explores a subset of the labels explored by a full Pareto search. The algorithm is evaluated over a set of problems with three objectives, showing a performance improvement of up to several orders of magnitude as goals become more restrictive. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Combinatorial optimization multiobjective shortest path problem Label-setting search Heuristic search Goal programming

来源：评论

学校读者我要写书评

暂无评论

A comparison of heuristic best-first algorithms for bicriterion shortest path problems

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2012年第1期217卷 44-53页

作者： Machuca, E. Mandow, L. Perez de la Cruz, J. L. Ruiz-Sepulveda, A. Univ Malaga Dpto Lenguajes & Ciencias Computac E-29071 Malaga Spain

A variety of algorithms have been proposed to solve the bicriterion shortest path problem. This article analyzes and compares the performance of three best-first (label-setting) algorithms that accept heuristic information to improve efficiency. These are NAMOA*, MON*, and Tung & Chew's algorithm (TC). A set of experiments explores the impact of heuristic information in search efficiency, and the relative performance of the algorithms. The analysis reveals that NAMOA* is the best option for difficult problems. Its time performance can benefit considerably from heuristic information, though not in all cases. The performance of TC is similar but somewhat worse. However, the time performance of MOA* is found to degrade considerably with the use of heuristic information in most cases. Explanations are provided for these phenomena. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Search theory Combinatorial optimization multiobjective shortest path problem Best-first search Heuristic search Artificial intelligence

来源：评论

学校读者我要写书评

暂无评论

Dimensionality reduction in multiobjective shortest path search

引用

COMPUTERS & OPERATIONS RESEARCH 2015年 64卷 60-70页

作者： Pulido, Francisco-Javier Mandow, Lawrence Perez-de-la-Cruz, Jose-Luis Univ Malaga Dept Lenguajes & Ciencias Computac E-29071 Malaga Spain

One-to-one multiobjective search in graphs deals with the problem of finding all Pareto-optimal solution paths between given start and goal nodes according to a number of distinct noncommensurate objectives. The problem is inherently more complex than single objective graph search. Time requirements are dominated by the facts that (a) many different non-dominated labels may need to be explored for each node;(b) each new label under consideration must be checked for dominance against various subsets of previously generated labels. This paper describes how a dimensionality reduction technique can be applied to exact label-setting algorithms, reducing the number of dominance checks and allowing for much faster multiobjective search. The technique is applied to NAMOA*, a state of the art exact label-setting multiobjective search algorithm, achieving reductions in time requirements of more than an order of magnitude over problems in random grids and realistic road maps. Tests include problems with three, four, and five objectives. (C) 2015 Elsevier Ltd. All rights reserved.

关键词： Combinatorial optimization multiobjective shortest path problem Exact label-setting algorithms Lower bounds

来源：评论

学校读者我要写书评

暂无评论

multiobjective heuristic search in road maps

引用

EXPERT SYSTEMS WITH APPLICATIONS 2012年第7期39卷 6435-6445页

作者： Machuca, E. Mandow, L. Univ Malaga Dpto Lenguajes & Ciencias Computac E-29071 Malaga Spain

This article considers the application of exact multiobjective techniques to search in large size realistic road maps. In particular, the NAMOA* algorithm is successfully applied to several road networks from the DIMACS shortest path implementation challenge with two objectives. An efficient heuristic function previously proposed by Tung and Chew is evaluated. Heuristic values are precalculated with search. The precalculation effort is shown to pay off during the multiobjective search stage. An improvement to the calculation procedure is also proposed, resulting in added improved time performance in many problem instances. (C) 2011 Elsevier Ltd. All rights reserved.

关键词： multiobjective shortest path problem Best-first search Heuristic search Artificial intelligence Road networks

来源：评论

学校读者我要写书评

暂无评论

Speeding up Martins' algorithm for multiple objective shortest path problems

引用

4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH 2013年第4期11卷 323-348页

作者： Demeyer, Sofie Goedgebeur, Jan Audenaert, Pieter Pickavet, Mario Demeester, Piet Univ Ghent Dept Informat Technol INTEC IBBT B-9050 Ghent Belgium

The latest transportation systems require the best routes in a large network with respect to multiple objectives simultaneously to be calculated in a very short time. The label setting algorithm of Martins efficiently finds this set of Pareto optimal paths, but sometimes tends to be slow, especially for large networks such as transportation networks. In this article we investigate a number of speedup measures, resulting in new algorithms. It is shown that the calculation time to find the Pareto optimal set can be reduced considerably. Moreover, it is mathematically proven that these algorithms still produce the Pareto optimal set of paths.

关键词： multiobjective shortest path problem Labeling algorithm Stop condition Bidirectional routing Pareto optimal set

来源：评论

学校读者我要写书评

暂无评论

A method for finding a least-cost corridor on an ordinal-scaled raster cost surface

引用

ANNALS OF GIS 2023年第2期29卷 205-225页

作者： Seegmiller, Lindsi Shirabe, Takeshi Royal Inst Technol KTH Sch Architecture & Built Environm Geoinformat Div Stockholm Sweden

The least-cost path problem is a widely studied problems in geographic information science. In raster space, the problem is to find a path that accumulates the least amount of cost between two locations based on the assumptions that the path is a one-dimensional object (represented by a string of cells) and that the cost (per unit length) is measured on a quantitative scale. Efficient methods are available for solution of this problem when at least one of these assumptions is upheld. This is not the case when the path has a width and is a two-dimensional object called a corridor (represented by a swath of cells) and the cost (per unit area) is measured on an ordinal scale. In this paper, we propose one additional model that characterizes a least-cost corridor on an ordinal-scaled raster cost surface - or a least ordinal-scaled cost corridor for short - and show that it can be transformed into an instance of a multiobjective optimization problem known as the preferred path problem with a lexicographic preference relation and solved accordingly. The model is tested through computational experiments with artificial landscape data as well as real-world data. Results show that least ordinal-scaled cost corridors are guaranteed to contain smaller areas of higher cost than conventional least-cost corridors at the expense of more elongated and winding forms. The least ordinal-scaled cost corridor problem has computational complexity of O(n(2.5)) in the worst case, resulting in a longer computational time than least-cost corridors. However, this difference is smaller in practice.

关键词： Raster cost surface wide path multiobjective shortest path problem preferred path problem scales of measurement

来源：评论

学校读者我要写书评

暂无评论

An Improved multiobjective shortest path Algorithm

引用

COMPUTERS & OPERATIONS RESEARCH 2021年 135卷 105424-105424页

作者： de las Casas, Pedro Maristany Sedeno-Noda, Antonio Borndoerfer, Ralf Zuse Inst Berlin Takustr 7 D-14195 Berlin Germany Univ La Laguna Dept Matemat Estadist & Invest Operat San Cristobal De La Lagu 38271 Santa Cruz De T Spain

We present a new label-setting algorithm for the multiobjective shortest path (MOSP) problem that computes a minimum complete set of efficient paths for a given instance. The size of the priority queue used in the algorithm is bounded by the number of nodes in the input graph and extracted labels are guaranteed to be efficient. These properties allow us to give a tight output-sensitive running time bound for the new algorithm that can almost be expressed in terms of the running time of Dijkstra's algorithm for the shortest path problem. Hence, we suggest to call the algorithm multiobjective Dijkstra Algorithm (MDA). The simplified label management in the MDA allows us to parallelize some subroutines. In our computational experiments, we compare the MDA and the classical label-setting MOSP algorithm by Martins, which we improved using new data structures and pruning techniques. On average, the MDA is 2 to 9 times faster on all used graph types. On some instances the speedup reaches an order of magnitude.

关键词： multiobjective shortest path problem Network optimization Output-sensitive multiobjective combinatorial problems

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：