Dynamic Vehicle Dispatching: Optimal Heavy Traffic Performance and Practical Insights
Operations Research · 1999 · Volume 47 · Issue 5
Abstract
We analyze a general model of dynamic vehicle dispatching systems in which congestion is the primary measure of performance. In the model, a finite collection of tours are dynamically dispatched to deliver loads that arrive randomly over time. A load waits in queue until it is assigned to a tour. This representation, which is analogous to classical set-covering models, can be used to study a variety of dynamic routing and load consolidation problems. We characterize the optimal work in the system in heavy traffic using a lower bound from our earlier work (Gans and van Ryzin 1997) and an upper bound which is based on a simple batching policy. These results give considerable insight into how various parameters of the problem affect system congestion. In addition, our analysis suggests a practical heuristic which, in simulation experiments, significantly outperforms more conventional dispatching policies. The heuristic uses a few simple principles to control congestion, principles which can be easily incorporated within classical, static routing algorithms.
Keywords
transportation, freight/materials handling, queueing analysis of dynamic load, consolidation problems, transportation, vehicle routing, queueing analysis of dynamic routing problems, queues, applications, dynamic vehicle dispatching
Enable JavaScript for citation tools and additional paper interactions.