Partially dynamic vehicle routing - models and algorithms

被引:113
作者
Larsen, A
Madsen, O
Solomon, M
机构
[1] Northeastern Univ, Coll Business Adm, Dept Management Sci, Boston, MA 02115 USA
[2] Tech Univ Denmark, IMM, Lyngby, Denmark
[3] Tech Univ Denmark, CTT, Lyngby, Denmark
关键词
vehicle routing; scheduling; heuristics; computational analysis;
D O I
10.1057/palgrave.jors.2601352
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
In this paper we propose a framework for dynamic routing systems based on their degree of dynamism. Next, we consider its impact on solution methodology and quality. Specifically, we introduce the Partially Dynamic Travelling Repairman Problem and describe several dynamic policies to minimize routing costs. The results of our computational study indicate that increasing the dynamic level results in a linear increase in route length for all policies studied. Furthermore, a Nearest Neighbour policy performed., on the average. uniformly better than the other dispatching rules studied. Among these, a Partitioning policy produced only slightly higher average route lengths.
引用
收藏
页码:637 / 646
页数:10
相关论文
共 15 条
[1]   STOCHASTIC AND DYNAMIC VEHICLE-ROUTING WITH GENERAL DEMAND AND INTERARRIVAL TIME DISTRIBUTIONS [J].
BERTSIMAS, DJ ;
VANRYZIN, G .
ADVANCES IN APPLIED PROBABILITY, 1993, 25 (04) :947-978
[2]   STOCHASTIC AND DYNAMIC VEHICLE-ROUTING IN THE EUCLIDEAN PLANE WITH MULTIPLE CAPACITATED VEHICLES [J].
BERTSIMAS, DJ ;
VANRYZIN, G .
OPERATIONS RESEARCH, 1993, 41 (01) :60-76
[3]   A STOCHASTIC AND DYNAMIC VEHICLE-ROUTING PROBLEM IN THE EUCLIDEAN PLANE [J].
BERTSIMAS, DJ ;
VANRYZIN, G .
OPERATIONS RESEARCH, 1991, 39 (04) :601-615
[4]   Stochastic vehicle routing [J].
Gendreau, M ;
Laporte, G ;
Seguin, R .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1996, 88 (01) :3-12
[5]   Parallel tabu search for real-time vehicle routing and dispatching [J].
Gendreau, M ;
Guertin, F ;
Potvin, JY ;
Taillard, É .
TRANSPORTATION SCIENCE, 1999, 33 (04) :381-390
[6]   Diversion issues in real-time vehicle dispatching [J].
Ichoua, S ;
Gendreau, N ;
Potvin, JY .
TRANSPORTATION SCIENCE, 2000, 34 (04) :426-438
[7]  
Larsen A., 2000, Ph.D. thesis
[8]  
LARSON R, 1980, URBAN OPERATIONS RES
[9]  
Lund K., 1996, Vehicle routing problems with varying degrees of dynamism
[10]  
MADSEN O, 1995, ANN OPNS RES, V61, P193