Multiple-path selection for new highway alignments using discrete algorithms

DOI10.1016/J.EJOR.2015.07.039MaRDI QIDQ320693zbMATH OpenOpenAlexFDO

Authors Yasha Pushak, Yves Lucet, Warren L. Hare

Publication date 7 October 2016

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1508.03064

zbMATH Keywords

shortest path\(A^*\) algorithm\(k\)-shortest pathhorizontal alignment optimizationOR in road design (natural resources)

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Applications of mathematical programming (90C90) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: This paper addresses the problem of finding multiple near-optimal, spatially-dissimilar paths that can be considered as alternatives in the decision making process, for finding optimal corridors in which to construct a new road. We further consider combinations of techniques for reducing the costs associated with the computation and increasing the accuracy of the cost formulation. Numerical results for five algorithms to solve the dissimilar multipath problem show that a "bidirectional approach" yields the fastest running times and the most robust algorithm. Further modifications of the algorithms to reduce the running time were tested and it is shown that running time can be reduced by an average of 56 percent without compromising the quality of the results.

Recommendations

• On finding dissimilar paths
• On finding dissimilar Pareto-optimal paths
• Routing with nonlinear multiattribute cost functions
• scientific article; zbMATH DE number 792650
• Alternative routes in road networks

Cites work

• A Method for the Solution of the N th Best Path Problem
• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
• Alternative routes in road networks
• Benchmarking optimization software with performance profiles.
• Engineering Route Planning Algorithms
• Finding the K Shortest Loopless Paths in a Network
• Finding the k Shortest Paths
• Generalized route planning model for hazardous material transportation with VaR and equity considerations
• Heuristics for the bi-objective path dissimilarity problem
• Models and algorithms to improve earthwork operations in road design using mixed integer linear programming
• Models and strategies for efficiently determining an optimal vertical alignment of roads
• Multiobjective GRASP with path relinking
• On finding dissimilar Pareto-optimal paths
• On finding dissimilar paths
• Optimizing horizontal alignment of roads in a specified corridor
• Tabu search and GRASP for the maximum diversity problem

Cited in

(5)

• Designing an ecologically optimized road corridor surrounding restricted urban areas: a mathematical methodology
• An automatic method for generating multiple alignment alternatives for a railway bypass
• Optimum ramp design in open pit mines
• Model and algorithm of routes planning for emergency relief distribution in disaster management with disaster information update
• On finding dissimilar paths

This page was built for publication: Multiple-path selection for new highway alignments using discrete algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q320693)