Back to Search
Start Over
Cheapest paths in dynamic networks
- Publication Year :
- 2017
-
Abstract
- Flows over time problems relate to finding optimal flows over a capacitated network where transit times on network arcs are explicitly considered. In this article, we study the problem of determining a minimum cost origin-destination path where the cost and the travel time of each arc depend on the time taken to travel from the origin to that particular arc along the path. We provide computational complexity results for this problem and an exact solution algorithm based on an enumeration scheme on the corresponding time expanded network. Finally, we show the efficiency of our approach through a number of experimental tests. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 69(1), 23–32 2017.
- Subjects :
- Scheme (programming language)
shortest path
Mathematical optimization
network flow
Computational complexity theory
Computer science
Computer Networks and Communications
0211 other engineering and technologies
0102 computer and information sciences
02 engineering and technology
Information System
time-dependent network
01 natural sciences
Arc (geometry)
branch and bound
time-expanded network
computer.programming_language
021103 operations research
computational complexity
Branch and bound
Flow network
Exact solutions in general relativity
010201 computation theory & mathematics
Hardware and Architecture
Path (graph theory)
Shortest path problem
Settore MAT/09 - Ricerca Operativa
computer
Software
Information Systems
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....9a4820987fdd01195b15024640c196f7