Time-varying travel times in vehicle routing

被引:147
作者
Fleischmann, B [1 ]
Gietz, M
Gnutzmann, S
机构
[1] Univ Augsburg, Lehrstuhl Prod & Logist, D-86135 Augsburg, Germany
[2] PROLOGOS Planung & Berating, D-21079 Hamburg, Germany
[3] DaimlerChrysler AG, Soc & Technol Res Grp, D-10559 Berlin, Germany
关键词
vehicle routing; dynamic travel times; traffic information systems;
D O I
10.1287/trsc.1030.0062
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
Models and algorithms for vehicle routing are usually based on known constant travel times between all relevant locations, an assumption that is far from reality particularly for urban areas. But the consideration of travel times that vary with the time of day poses two serious problems: the adaptation of the algorithms and the procurement of reliable data about the behavior of the travel times in the road network. This article describes the derivation of travel time data from modern traffic information systems. It presents a general framework for the implementation of time-varying travel times in various vehicle-routing algorithms. Finally, it reports on computational tests with travel time data obtained from a traffic information system in the city of Berlin.
引用
收藏
页码:160 / 173
页数:14
相关论文
共 21 条
[1]   VEHICLE-ROUTEING WITH TIME WINDOWS AND TIME-VARYING CONGESTION [J].
AHN, BH ;
SHIN, JY .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1991, 42 (05) :393-400
[2]  
Ahuja R.K., 1993, NETWORK FLOWS THEORY
[3]   ADAPTING THE SAVINGS ALGORITHM FOR VARYING INTER-CUSTOMER TRAVEL-TIMES [J].
BEASLEY, JE .
OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 1981, 9 (06) :658-659
[4]  
FLEISCHMANN B, 1998, LOGISTIK, P287
[5]   NEW INSERTION AND POSTOPTIMIZATION PROCEDURES FOR THE TRAVELING SALESMAN PROBLEM [J].
GENDREAU, M ;
HERTZ, A ;
LAPORTE, G .
OPERATIONS RESEARCH, 1992, 40 (06) :1086-1094
[6]  
GENDREAU M, 1997, 9738 CRT U MONTR
[7]  
Gietz M, 1994, COMPUTERGESTUTZTE TO
[8]  
HILL AV, 1992, J OPER RES SOC, V43, P343, DOI 10.2307/2583157
[9]   A DECISION SUPPORT SYSTEM FOR THE COURIER VEHICLE SCHEDULING PROBLEM [J].
HILL, AV ;
MABERT, VA ;
MONTGOMERY, DW .
OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 1988, 16 (04) :333-345
[10]  
Horn MET, 2000, NETWORKS, V36, P80, DOI 10.1002/1097-0037(200009)36:2<80::AID-NET2>3.0.CO