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.

Rights

Rights Holder

Rights License

Rights URI