Refine
Document Type
- Preprint (4)
Language
- English (4)
Has Fulltext
- yes (4)
Keywords
- Dynamic cut (1)
- Earliest arrival augmenting path (1)
- Label correcting algorithm (1)
- Label setting algorithm (1)
- Multiple criteria analysis (1)
- Multiple criteria optimization (1)
- Network flows (1)
- bicriteria shortest path problem (1)
- label setting algorithm (1)
- time-dependent shortest path problem (1)
Faculty / Organisational entity
We generalize the classical shortest path problem in two ways. We consider two - in general contradicting - objective functions and introduce a time dependency of the cost which is caused by a traversal time on each arc. The resulting problem, called time-dependent bicriteria shortest path problem (TdBiSP) has several interesting practical applications, but has not attained much attention in the literature.
In this paper we generalize the classical shortest path problem in two ways. We consider two objective functions and time-dependent data. The resulting problem, called the time-dependent bicriteria shortest path problem (TdBiSP), has several interesting practical applications, but has not gained much attention in the literature.
Abstract: Evacuation problems can be modeled as flow problems in dynamic networks. A dynamic network is defined by a directed graph G = (N,A) with sources, sinks and non-negative integral travel times and capacities for every arc (i,j) e A. The earliest arrival flow problem is to send a maximum amount of dynamic flow reaching the sink not only for the given time horizon T, but also for any time T' < T . This problem mimics the evacuation problem of public buildings where occupancies may not known. For the buildings where the number of occupancies is known and concentrated only in one source, the quickest flow model is used to find the minimum egress time. We propose in this paper a solution procedure for evacuation problems with a single source of the building where the occupancy number is either known or unknown. The possibility that the flow capacity may change due to the increasing of smoke density or fire obstructions can be mirrored in our model. The solution procedure looks iteratively for the shortest conditional augmenting path (SCAP) from source to sink and compute the time intervals in which flow reaches the sink via this path.
In this paper we discuss an earliest arrival flow problem of a network having arc travel times and capacities that vary with time over a finite time horizon T. We also consider the possibility to wait (or park) at a node before departingon outgoing arc. This waiting is bounded by the value of maximum waiting time and the node capacity which also vary with time.