Network reduction for the acyclic constrained shortest path problem

Network reduction for the acyclic constrained shortest path problem

0.00 Avg rating0 Votes
Article ID: iaor19961014
Country: Netherlands
Volume: 63
Issue: 1
Start Page Number: 124
End Page Number: 132
Publication Date: Nov 1992
Journal: European Journal of Operational Research
Authors:
Abstract:

This paper presents a procedure for reducing networks used with the constrained shortest path problem. The network considered herein is acyclic with each arc having two attributes; time and length, with a time limit on the shortest length path. The procedure traverses the network twice and depends on establishing time labels for the nodes similar to those established in shortest path algorithms of the label setting type. These labels are used to identify the arcs and nodes that render a path infeasible. The computational requirements of the procedure are modest, which should enhance the application of the constrained shortest path problem.

Reviews

Required fields are marked *. Your email address will not be published.