Multiple-path selection for new highway alignments using discrete algorithms

DOI10.1016/J.EJOR.2015.07.039zbMATH Open1346.90856arXiv1508.03064OpenAlexW1952710116MaRDI QIDQ320693FDOQ320693

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)

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.

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

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

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)

Cites Work

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

Cited In (5)

• An automatic method for generating multiple alignment alternatives for a railway bypass
• Designing an ecologically optimized road corridor surrounding restricted urban areas: a mathematical methodology
• 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)