The equity constrained shortest path problem

DOI10.1016/0305-0548(90)90006-SMaRDI QIDQ910348zbMATH OpenOpenAlexFDO

Authors Ram Gopalan, Rajan Batta, Mark H. Karwan

Publication date 1990

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0305-0548(90)90006-s

zbMATH Keywords

equality constraintsheuristiclabelingLagrangean dualLagrangean relaxationshortest pathsubgradient algorithm

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Programming involving graphs or networks (90C35)

Review text

The shortest path problem with equality constraints is examined. A subgradient algorithm is developed to solve the Lagrangean dual, and a labeling procedure is used to close any remaining duality gap. The authors present a heuristic procedure and report some computational experience with the model.

Recommendations

• A note on the constrained shortest-path problem
• On the complexity of equal shortest path routing
• On an exact method for the constrained shortest path problem
• Shortest path under rational constraint
• Shortest Path Problems with Resource Constraints
• Probabilistic shortest path problems with budgetary constraints
• Exact algorithms for the equitable traveling salesman problem
• The Variance-Constrained Shortest Path Problem
• Shorter Path Constraints for the Resource Constrained Shortest Path Problem
• Extensive facility location problems on networks with equity measures

Cites work

• Finding the K Shortest Loopless Paths in a Network
• Iterative methods for determining the k shortest paths in a network
• Modeling Equity of Risk in the Transportation of Hazardous Materials
• New Polynomial Shortest Path Algorithms and Their Computational Attributes
• Surrogate Dual Multiplier Search Procedures in Integer Programming
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• The Relaxation Method for Linear Inequalities
• The Relaxation Method for Linear Inequalities
• Utility Functions for Equity and Public Risk

Cited in

(13)

• A review of extensive facility location in networks
• Equity measurement in facility location analysis: A review and framework
• A routing and scheduling approach to rail transportation of hazardous materials with demand due dates
• The undirected \(m\)-capacitated peripatetic salesman problem
• The maximin HAZMAT routing problem
• A note on the constrained shortest-path problem
• Generalized route planning model for hazardous material transportation with VaR and equity considerations
• Heuristiques pour le Problème du Vendeurm-Péripatétique
• scientific article; zbMATH DE number 3961370 (Why is no real title available?)
• CONSTRAINED SHORTEST PATH ALGORITHMS FOR NETWORK CONTROL
• scientific article; zbMATH DE number 1910903 (Why is no real title available?)
• Finding minimum and equitable risk routes for hazmat shipments
• A tabu search approach for scheduling hazmat shipments

This page was built for publication: The equity constrained shortest path problem

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