ROUTING IN TIME-DEPENDENT AND LABELED NETWORKS
Christopher L. Barrett, Keith Bisset, Riko Jacob, Goran Konjevod, MADHAV V. MARATHE · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 2001
We study routing problems in time-dependent and edge and/or vertex-labeled transportation networks. Labels allow one to express a number of discrete properties of the edges and nodes. The main focus is a unified algorithm that efficiently solves a number of seemingly unrelated problems in transportation science. Experimental data gained from modeling practical situations suggest that the formalism allows interesting compromises between the conflicting goals of generality and efficiency. 1. We use edge/vertex labels in the framework of Formal Language Constrained Path Problems to handle discrete choice constraints. The label set is usually small and does not depend on the graph. Edge labels induct! path labels, which allows us to impose feasibility constraints on the set of paths considered as shortest path candidates. Second, we propose monotonic piecewise-linear traversal functions to represent the time-dependent aspect of link delays. The applications that can be modeled include scheduled transit and time-windows. 3. Third, we combine the above models and capture a variety of natural problems in transportatiou science such as time-window constrained trip-chaining. The results demonstrate the robustness of the proposed formalisms. As evidence for our claims of practical efficiency in a realistic setting, we report preliminary computational experience from TRANSIMS case studies of Portland, Oregon.