Time-dependent shortest paths through a fixed sequence of nodes:: application to a travel planning problem

被引：32

作者：

Bérubé, JF ^{[1
]}

Potvin, JY ^{[1
]}

Vaucher, J ^{[1
]}

机构：

[1] Univ Montreal, Dept Informat & Rech Operat, Montreal, PQ H3C 3J7, Canada

来源：

COMPUTERS & OPERATIONS RESEARCH | 2006年 / 33卷 / 06期

关键词：

shortest paths; fixed nodes; time-dependent; travel planning;

D O I：

10.1016/j.cor.2004.11.021

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

In this paper, we introduce a travel planning problem which is solved by computing time-dependent shortest paths through a fixed sequence of nodes. Given a predetermined itinerary, our travel planning problem consists in finding the best travel plan, involving planes and hotels, based on the traveler's preferences. Our time-dependent framework therefore models plane flights, hotels, stays in each city as well as global time constraints. Given the large size of time-dependent networks, an exact decomposition algorithm is devised to solve instances of realistic size in reasonable computation times. (c) 2004 Elsevier Ltd. All rights reserved.

引用

页码：1838 / 1856

页数：19

共 27 条

[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 RK, 1993, NETWORK FLOWS THEORY

[3]

[Anonymous], 1956, NETWORK FLOW THEORY

[4]

Bellman R., 1958, Quarterly of Applied Mathematics, V16, P87, DOI [10.1090/qam/102435, DOI 10.1090/QAM/102435]

[5]

BERUBE JF, 2003, THESIS U MONTREAL

[6]

Cai X, 1997, NETWORKS, V29, P141, DOI 10.1002/(SICI)1097-0037(199705)29:3<141::AID-NET2>3.0.CO

[7]

2-H

[8]

CARAMIA M, 1999, P CUPUM 99 COMP URB

[9] Adaptations of the A* algorithm for the computation of fastest paths in deterministic discrete-time dynamic networks [J].

Chabini, I ;

Lan, S .

IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS, 2002, 3 (01) :60-74

[10]

CHABINI I, 1999, SHORTEST PATH PROBLE

← 1 2 3 →