Competitive analysis of a dispatch policy for a dynamic multi-period routing problem

被引：22
作者：
Angelelli, Enrico
Savelsbergh, Martin W. P. [1 ]
Speranza, M. Grazia
机构：
[1] Georgia Inst Technol, H Milton Stewart Sch Ind & Syst Engn, Atlanta, GA 30332 USA
[2] Univ Brescia, Dept Quantitat Methods, I-25121 Brescia, Italy
来源：
OPERATIONS RESEARCH LETTERS | 2007年 / 35卷 / 06期
关键词：
dynamic vehicle routing; dispatch policies; competitive analysis;
D O I：
10.1016/j.orl.2007.02.006
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
We analyze an on-line algorithm (dispatch policy) for a dynamic multi-period routing problem. The objective is to minimize the total cost over all periods. We show that the competitive ratio of this policy for instances with customers located on the non-negative real line is 3/2. (C) 2007 Elsevier B.V. All rights reserved.
引用
收藏
页码：713 / 721
页数：9
相关论文
共 10 条
[1]   Competitive analysis for dynamic multiperiod uncapacitated routing problems [J].
Angelelli, Enrico ;
Speranza, M. Grazia ;
Savelsbergh, Martin W. P. .
NETWORKS, 2007, 49 (04) :308-317
[2]  
Ascheuer N, 2000, LECT NOTES COMPUT SC, V1770, P639
[3]   Algorithms for the on-line travelling salesman [J].
Ausiello, G ;
Feuerstein, E ;
Leonardi, S ;
Stougie, L ;
Talamo, M .
ALGORITHMICA, 2001, 29 (04) :560-581
[4]   The online TSP against fair adversaries [J].
Blom, M ;
Krumke, SO ;
de Paepe, WE ;
Stougie, L .
INFORMS JOURNAL ON COMPUTING, 2001, 13 (02) :138-148
[5]   The online target date assignment problem [J].
Heinz, S ;
Krumke, SO ;
Megow, N ;
Rambau, J ;
Tuchscherer, A ;
Vredeveld, T .
APPROXIMATION AND ONLINE ALGORITHMS, 2006, 3879 :230-+
[6]   On-line algorithms for the dynamic traveling repair problem [J].
Irani, S ;
Lu, XW ;
Regan, A .
JOURNAL OF SCHEDULING, 2004, 7 (03) :243-258
[7]   Online routing problems: Value of advanced information as improved competitive ratios [J].
Jaillet, Patrick ;
Wagner, Michael R. .
TRANSPORTATION SCIENCE, 2006, 40 (02) :200-210
[8]   News from the online traveling repairman [J].
Krumke, SO ;
de Paepe, WE ;
Poensgen, D ;
Stougie, L .
THEORETICAL COMPUTER SCIENCE, 2003, 295 (1-3) :279-294
[9]  
PSARAFTIS HN, 1988, VEHICLE ROUTING METH, P223
[10]   AMORTIZED EFFICIENCY OF LIST UPDATE AND PAGING RULES [J].
SLEATOR, DD ;
TARJAN, RE .
COMMUNICATIONS OF THE ACM, 1985, 28 (02) :202-208
1