The fastest itinerary in time-dependent decentralized travel information systems
Tóm tắt
A travel information system (TIS) provides customers with information about transportation, transfers, and routings. A decentralized TIS is composed of autonomous subsystems and a central computer, where local subsystems have full control of their data and there is not a complete database in the central computer about the entire TIS. The transportation vehicles are scheduled. A travel itinerary from one spot to another contains the travel path and the schedule of transportations. The approach presented in this paper is for the central computer to identify the fastest itinerary across autonomous subsystems, based on the incomplete local information provided by the independent subsystems.
Tài liệu tham khảo
Ahuja R, Magnanti TL, Orlin JB (1993) Network flows. Prentice Hall, Englewood Cliffs
Frederickson, GN (1987) Fast algorithms for shortest paths in planar graphs, with applications. SIAM J Comput 6:1004–1022
Ford LR Jr, Fulkerson DR (1962) Flows in networks Princeton University Press, Princeton, NJ
Kaempke T, Schaal M (1999) Fast paths. FAW Research Institute of Applied Artificial Intelligence, University of Ulm, Ulm, Germany
Kaempke T, Schaal M. (1998) Distributed generation of fastest paths. Proceedings of Conference on Parallel and Distributed Computing and Systems (PDCS-98), Las Vegas. pp 172–177
Martins EQV et al (1993) An algorithm for the ranking of shortest paths Eur J Oper Res 69:97–106
O’Brien JA (2003) Introduction to information systems. Mcgraw-Hill Irwin, pp 192
Orda A, Row R (1990) Shortest-path and minimum delay algorithms in networks with time dependent edge-length. J ACM 36:607–625
Orda A, Row R (1991) Minimum weight paths in time-dependent networks. Networks 21:295–319
Papadimitriou CH, and Steiglitz K (1998) Combinatorial optimization, algorithms and complexity. Prentice-Hall, Inc., Englewood Cliffs, NJ
Radermacher FJ, Schaal M, Schnittger S (1997) Durchgangige Elektronische Fahrplaninformation – DELFI Proceedings of ITS World Congress, Berlin
Schnittger S (1999) The EU-SPIRIT API approach. Proceedings Conference on Passenger Information, London
Thulasiraman K, Swamy MNS (1992) Graphs: theory and algorithms. Wiley, New York
Wang J, Kaempke T (2004) Shortest path computation in distributed systems. Comp Oper Res 31:1621–1633
Zaumen WT, Garcia-Luna Aceves JJ (1991) Dynamics of distributed shortest-path routing algorithms. Proceedings of ACM Conference on Communications Architecture & Protocols, Zurich, pp 31–42