The Inverse Shortest Paths Problem With Upper Bounds on Shortest Paths Costs

. We examine the computational complexity of the inverse shortest paths problem with upper bounds on shortest path costs, and prove that obtaining a globally optimum solution to this problem is NP-complete. An algorithm for finding a locally optimum solution is proposed, discussed and tested. 1 Belgian National Fund for Scientific Research Department of Mathematics Facult'es Universitaires ND de la Paix B-5000 Namur, Belgium 2 IBM T.J. Watson Research Center Yorktown Heights, USA 3 Department of Mathematics Facult'es Universitaires ND de la Paix B-5000 Namur, Belgium Keywords : computational complexity, shortest paths, inverse problems, traffic modelling. 1 Introduction Shortest paths problems form a fundamental part of transportation research, because they naturally arise in a large number of related optimization problems [9]. Shortest path techniques are applied in fields as diverse as traffic modelling [8] and computerized tomography [16]. Very efficient algorithms have been..