 Parametric search and problem decomposition for approximating Pareto-optimal pathsChi Xie and S. Travis Waller Transportation Research Part B: Methodological, 2012, vol. 46, issue 8, 1043-1067 Abstract: The multiobjective shortest path problem arises in many transportation and logistics applications, either as a stand-alone network routing problem or a subroutine of a more complex 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 parametric algorithm is scalarization, by which a multiobjective shortest path problem can be tackled by repeatedly solving a single-objective subproblem. However, existing parametric algorithms suffer two notorious deficiencies, which considerably limit its further applications: first, typical subroutines for the single-objective subproblem in general cannot capture nonextreme Pareto-optimal paths; second, parametric algorithms for biobjective 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 solution 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 biobjective problems. The approximate parametric algorithm runs in polynomial time. The algorithmic 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. Keywords: Pareto-optimal solution; Biobjective shortest path; Constrained shortest path; Parametric algorithm; Multiobjective problem decomposition (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:46:y:2012:i:8:p:1043-1067 Ordering information: This journal article can be ordered from DOI: 10.1016/j.trb.2012.03.005 Access Statistics for this article Transportation Research Part B: Methodological is currently edited by Fred Mannering More articles in Transportation Research Part B: Methodological from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.