Online selection model and competitive analysis of vehicle routing in grid transportation network

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.