Search

In this paper we consider a traffic-light network where every node in the network is associated with the constraint consisting of a repeated sequence of time windows. The constraint aims to simulate the operations of traffic-light control in an intersection of roads. With this kind of constraints in place, directions of routes when passing through the intersections can be formally modeled. The objective of this paper is to find the first K shortest looping paths in the traffic-light network. An algorithm of time complexity of O(rK2|V1|3) is developed, where r is the number of different windows of a node and |V1| is the number of nodes in the original network.

The time-constrained shortest path problem is an important generalization of the classical shortest path problem and has attracted much research interest in recent years. We consider a time-window network, where every node in the network has a list of pre-specified windows and departure from a node may take place only in these window periods. The objective of this paper is to find the first K shortest paths in a time-window network. An algorithm of time complexity of O(Kr|V|3) is developed to find the first K shortest paths, where |V| is the numbers of nodes in the network and r represents the maximum number of windows associated with a node.

The time-constrained shortest path problems are generalized from and more realistic than the classical shortest path problem. These problems are most important subproblems in many large-scale real-world problems in the field of transportation. The problem considered in this paper is to find the shortest path in a new kind of time-constrained network, called a mixed time-schedule network, in which departures from some nodes are only allowed at some discrete points. This problem arises in many practical situations. For example, a shipping or transportation from one place to another may be through different kinds of vehicles such as (1) scheduled flights, ocean liners, trains, or buses and (2) rental cars, own cars or own trucks, where the vehicles in (1) have to follow predetermined departure-time schedules and the vehicles in (2) do not have time constraints. The time-constrained shortest path problem is an important generalization of the shortest path problem and has attracted much research interest in recent years. In a recent paper, a new time constraint, namely time-schedule constraint, is introduced. This time constraint assumes that every node in the network has a list of pre-specified departure times and requires that departure from a node take place only at one of these departure times. Therefore, when a time-schedule constraint is considered, the total time in a network includes traveling time and waiting time. In this paper, we consider a network consisting of two types of nodes in terms of their time constraints. The first type of nodes are subject to time-schedule constraints, but the second type is not. For such a network, a set of minimum time (shortest) path problems is studied, including minimization of total time, minimization of total time subject to a total traveling time constraint, minimization of total traveling time subject to a total time constraint and minimization of a weighted sum of total time and total traveling time.

Let N be a network with n nodes and m arcs, and let σ be the amount of data to be transmitted. The quickest path problem is to find a routing path in N such that the time required to ship σ units of data from the source to the sink is minimum. The problem considered in this paper is to find the first k quickest looping paths from the source to the sink, and an algorithm with time complexity of O(m 2 + (m + k)n log n + k 3 2 log k) is developed.

Let N be an input network and σ be the amount of data to be transmitted. The quickest path problem is to find a routing path in N such that the time required to ship σ units of data from the source to the sink is minimum. When the value of σ is given, an O(m2 + nm log m) algorithm is designed to find the quickest path, where m and n are the numbers of arcs and nodes in the network N, respectively. By generalizing this algorithm properly, a more general algorithm with similar time complexity is developed to find quickest paths for all possible values of σ. Using the algorithm, the values of σ can be divided into O(m) ordered regions such that each region has a corresponding quickest path; therefore, if the general algorithm is used as a preprocessing step to handle the input network N, then the problem of finding a quickest path for a given value of σ can be solved in time O(log m).