Abstract
In order to analyze the vehicle routing problem under sudden road blockage in grid transportation network, a vehicle routing model was proposed by using the methods of online problem and competitive strategy, direction greedy strategy and multi-alternative moving strategy were designed, and the competitive ratios of two strategies were computed. Analysis result indicates that the cost of direction greedy strategy is 3 times than the optimal cost under sudden road blockage state, multi-alternative moving strategy has a good performance with practical restriction for different cases, the cost of multi-alternative moving strategy is 2 times than the optimal cost in the worst case, the competitive ratios of two strategies are not more than the infimum of the competitive ratio for unexpected blockage problem in general networks. 3 figs, 17 refs.
| Original language | English |
|---|---|
| Pages (from-to) | 110-115 |
| Number of pages | 6 |
| Journal | Journal of Traffic and Transportation Engineering |
| Volume | 8 |
| Issue number | 6 |
| State | Published - Dec 2008 |
Keywords
- Competitive analysis
- Grid transportation network
- Online problem
- Traffic transportation
- Vehicle routing