Anticipatory route selection problems

Mobile communication technologies enable communication between dispatchers and drivers and hence can enable fleet management based on real-time information. We assume that such communication capability and real-time information exists. In this dissertation, we then show how these two capabilities can be used to improve routing through the anticipation and communication of information important to the vehicle's route. We examine two problems: the vehicle routing problem with anticipated customer demand and the stochastic and dynamic shortest path problem with anticipation (SDSPPA).; For the vehicle routing problem with customer demand, we assume a single pick-up and delivery vehicle and that we know the likelihood, as a function of time, that each of the vehicle's potential customers will make a pick-up request. We then model and analyze the problem of constructing a minimum expected total cost route from an origin to a destination that anticipates and then responds to service requests, if they occur, while the vehicle is en route. We model this problem as a Markov decision process and present several structured results associated with the optimal expected cost-to-go function and an optimal policy for route construction. We illustrate the behavior of an optimal policy with several numerical examples and demonstrate the superiority of an optimal anticipatory policy, relative to a route design approach that reflects the reactive nature of current routing procedures for less-than-truckload pick-up and delivery.; The SDSPPA examines an analogous problem. We consider a single vehicle from a known origin to a known destination in finite time when certain arcs en route are congested. We assume that we know a probability distribution over time on the likelihood that the congested arcs will become uncongested and then less costly to traverse. Our objective is to construct a minimum expected cost path that anticipates changes in arc congestion. The problem is modeled as a Markov decision process, and we present bounds on the cost-to-go function and structural results on the optimal policy. We also design a simple heuristic and compare its performance to the optimal anticipatory strategy.