The Real-Time Vehicle Routing Problem with Stochastic Demands (VRPSD)
Date
2006-06
Authors
Novoa, Clara
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The vehicle routing problem with stochastic demands (VRPSD) is to design minimum cost routes from a depot to a customer set in such a way that all vehicles start and end their route at the depot and customer demands are satisfied. Route length is the main component for computing route cost. Customer demands follow known probability distributions but actual demands are only revealed when the vehicle arrives at each customer. Consequently, a route may fail if a customer demand exceeds the current vehicle capacity and a recourse action, such as sending the vehicle back to the depot and forth to the customer, must be taken at extra cost. Most previous research designs routes before demands become known and they are unchanged during real-time execution. Novoa (2005) and Secomandi (2001) use a more flexible approach called dynamic that construct routes as demand is revealed. These works are only for single-vehicle.
This RFP research solved a multiple (VRPSD) using a dynamic algorithm. It required development of computer models coded in C++ to represent the general problem, and generation of 140 instances to resemble real-life situations. Instances varied number and capacity for the vehicles, and number, location and demand distribution for the customers. Routes resulted 1%-2% shorter than those from static models were and its generation took less than 2 CPU seconds. This research tested also the benefits from a distributed computing cluster acquired by our department and provided one further research idea. A paper to the Transportation Science Journal is In-progress.
Description
Research Enhancement Program Final Report
Keywords
vehicle routing, stochastic demands, VRPSD
Citation
Novoa, C. (2006). <i>The real-time vehicle routing problem with stochastic demands (VRPSD)</i>. Research Enhancement Program, Texas State University, San Marcos, TX.