The Virtual Path (VP) concept has been proposed to simplify traffic control and resource management in future BISDN's. In particular, call setup processing can be significantly reduced when resources are reserved on VP's. However, this advantage is offset by a decrease in statistical multiplexing gains of the networks. The focus of this paper is on how to improve bandwidth efficiency through adaptive routing when capacity is reserved on all VP's. We first examine two VP capacity reservation strategies. We then design and evaluate computationally feasible Markov decision process based routing algorithms and show that the network blocking probability can be significantly reduced by MDP routing.