The equity constrained shortest path problem

This paper examines the problem of finding the shortest path on a network subject to ‘equity’ constraints. A Lagrangean dual bounding approach is utilized, which relaxes the ‘complicating constraints’ of the problem. After solving the Lagrangean dual, the duality gap is closed by finding the t shortest paths with respect to the Lagrangean function. Both looping and loopless paths are considered. A quick-and-dirty heuristic procedure is also suggested. The authors report a sampling of their computational experiences with the model.