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

SU Bing; XU Yin-feng; YU Shui

Volume 8 Issue 6

Turn off MathJax

Article Contents

Article Navigation > Journal of Traffic and Transportation Engineering > 2008 > 8(6): 110-115

Next Previous

SU Bing, XU Yin-feng, YU Shui. Online selection model and competitive analysis of vehicle routing in grid transportation network[J]. Journal of Traffic and Transportation Engineering, 2008, 8(6): 110-115.

Citation:

SU Bing, XU Yin-feng, YU Shui. Online selection model and competitive analysis of vehicle routing in grid transportation network[J]. Journal of Traffic and Transportation Engineering, 2008, 8(6): 110-115.

Citation:

PDF( 585 KB)

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

SU Bing^{1, 2
,},
XU Yin-feng^{1, 3
,},
YU Shui⁴

1.
School of Management, Xi'an Jiaotong University, Xi'an 710049, Shaanxi, China
2.
School of Economics and Management, Xi'an Technological University, Xi'an 710021, Shaanxi, China
3.
State Key Laboratory for Manufacturing Systems Engineering, Xi'an Jiaotong University, Xi'an 710049, Shaanxi, China
4.
School of Engineering and Information Technology, Deakin University, Melbourne 3125, Victoria, Australia

More Information

Author Bio:
SU Bing (1970-), female, PhD, +86-29-82665034, subing684@sohu.com

XU Yin-feng (1962-), male, professor, +86-29-82665034, yfxu@mail.xjtu.edu.cn
Received Date: 2008-09-09
Publish Date: 2008-12-25

Abstract

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.
- traffic transportation,
- grid transportation network,
- vehicle routing,
- online problem,
- competitive analysis

FullText(HTML)

References(17)

References

[1]	HE Zhu-qing, SUN Lin-yan. Model and algorithmof vehicle routing problemunder dynamic traffic[J]. Journal of Traffic and Transportation Engineering, 2007, 7 (1): 111-115. (in Chinese) doi: 10.3321/j.issn:1671-1637.2007.01.023
[2]	THANGI AH S R, OSMAMI H, SUN T. Hybrid genetic algorithmsi mulated annealing and tabu search met hods for vehicle routing problem with ti me windows[R]. Slippery Rock: Slippery Rock University, 1994.
[3]	ZHANG Bo, YE Jia-wei, HU Yu-cong. Application of opti-mizing the path by si mulated annealing[J]. China Journal of Highway and Transport, 2004, 17 (1): 79-81. (in Chinese) doi: 10.3321/j.issn:1001-7372.2004.01.018
[4]	HU Da-wei, HU Yong, ZHU Zhi-qiang. Solving location routing problembased on space filling curve and dynamic pro-gramming[J]. Journal of Chang an University: Natural Science Edition, 2006, 26 (3): 80-83. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-XAGL200603021.htm
[5]	LI Bing, ZHENG Si-fa, CAO Jian-dong, et al. Method of solving vehicle routing problem with customers dynamic requests[J]. Journal of Traffic and Transportation Engineering, 2007, 7 (1): 106-110. (in Chinese) http://transport.chd.edu.cn/article/id/200701022
[6]	YANG Rui-chen, ZHOU Yong-fu, YUN Qing-xia. Hybrid algorithmfor vehicle s opti mal route[J]. Journal of Traffic and Transportation Engineering, 2005, 5 (1): 102-105. (in Chinese) doi: 10.3321/j.issn:1671-1637.2005.01.024
[7]	MANASSE MS, MCGEOCH L A, SLEATOR D D. Com-petitive algorithms for server problems[J]. Journal of Algo-rithms, 1990, 11: 208-230. doi: 10.1016/0196-6774(90)90003-W
[8]	DAVID S B, BORODI N A. A new measure for the study of the on-line algorithm[J]. Algorithmica, 1994, 11: 73-91. doi: 10.1007/BF01294264
[9]	EI YANI V R, KNAIEL R, LI NEAL N. Competitive opti mal on-line leasing[J]. Algorithmica, 1999, 25: 116-140. doi: 10.1007/PL00009279
[10]	EI YANI V R, FI AT A, KARP R M, et al. Opti mal search and one-way trading online algorithm[J]. Algorithmica, 2001, 30: 101-139. doi: 10.1007/s00453-001-0003-0
[11]	KESKI NOCAK P, RAVI R, TAYUR S. Scheduling and re-liable lead-ti me quotation for orders with availability intervals and lead-ti me sensitive revenues[J]. Management Science, 2001, 47 (2): 264-279. doi: 10.1287/mnsc.47.2.264.9836
[12]	PAPADI MITRIOUC H, YANNAKAKIS M. Shortest paths without a map[J]. Lecture Notes in Computer Science, 1989, 372: 610-620. https://www.sciencedirect.com/science/article/pii/0304397591902632
[13]	XUYin-feng, HU Mao-lin, SUBing, et al. The Canadian traveller problemand its competitive analysis[J]. Journal of Combinatorial Opti mization, 2008, 15 (3): 223-227. doi: 10.1007/s10878-008-9156-y
[14]	SU Bing, XU Yin-feng, ZHU Zhi-jun. Online recoverable Canadian traveler problemon a road[J]. Information, 2004, 7 (4): 477-486. https://www.researchgate.net/publication/266981539_Online_recoverable_Canadian_traveler_problem_on_a_road
[15]	SU Bing, XU Yin-feng. Online recoverable Canadian traveler problemon a continuous network[J]. Systems Engineering, 2004, 22 (8): 10-13. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-GCXT200408003.htm
[16]	SU Bing, XU Yin-feng. Online Canadian traveler problem with stochastic blockages recovery ti me[J]. Systems Engi-neering-theory and Practice, 2005, 25 (10): 108-113. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-XTLL200510015.htm
[17]	SU Bing, XU Yin-feng. Influence analysis of square block for transportation convenience capability on grid network[J]. System Engineering, 2006, 24 (12): 33-39. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-GCXT200612005.htm