The Median Shortest Path Problem: A Multiobjective Approach to Analyze Cost vs. Accessibility in the Design of Transportation Networks

In this paper the authors introduce the median shortest path problem (MSPP). The MSPP is a bicriterion path problem with the objectives being the minimization of the total path length and the minimization of the total travel time required for demand to reach a node on the path. Potential applications of the MSPP include, among others, the location of new highways, railroad lines and subway lines and the design of airline routes. It is particularly applicable in transportation network design problems where the trade-off between operator costs and user costs is important. An algorithm is presented to identify noninferior solutions to the MSPP. This algorithm incorporates a K shortest path algorithm. The algorithm is demonstrated with a sample problem and the results are compared to those obtained using integer programming.