Title | ||
---|---|---|
Dynamic Vehicle Dispatching: Optimal Heavy Traffic Performance and Practical Insights |
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. |
Year | DOI | Venue |
---|---|---|
1999 | 10.1287/opre.47.5.675 | Operations Research |
Field | DocType | Volume |
Mathematical optimization,Heuristic,Vehicle routing problem,Static routing,Upper and lower bounds,Queue,Adaptive routing,Consolidation (soil),Mathematics,Operations management | Journal | 47 |
Issue | ISSN | Citations |
5 | 0030-364X | 9 |
PageRank | References | Authors |
1.19 | 16 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Noah Gans | 1 | 613 | 66.60 |
Garrett Van Ryzin | 2 | 1003 | 85.36 |