TY - JOUR

T1 - Finding the first K shortest paths in a time-window network

AU - Chen, Yen Liang

AU - Yang, Hsu Hao

N1 - Funding Information:
The research was supported in part by MOE Program for Promoting Academic Excellence of Universities under the Grant Number 91-H-FA07-1-4.

PY - 2004/4

Y1 - 2004/4

N2 - 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. Time window has been a common form of time constraint considered in the literature. Basically, a time window is a time period, defined by the earliest and latest times, when a node is available for traveling through. There are many practical situations where time windows can be used to describe the time constraints associated with the nodes and arcs on a network. For example, a time window in a transportation network may be the time period that a service or transition facility is available for the traveler to pass through. Although there are many researchers on the transportation problem in time-window networks, no previous researches study how to find the first K shortest paths in a time-window network; hence, this paper studies this extended problem. The extension has many potential applications in practice. For example, there may be some complex constraints associated with the nodes and/or arcs of the network, which are difficult to incorporate into the model formulation. A solution strategy is to temporarily ignore these constraints and obtain a list of paths in nondecreasing order in terms of their total times. The optimal solution can be found by identifying the first path in the list that satisfies the constraints. Another use of the result is a quick selection of an alternative path when encountering temporary disconnection of the active shortest path.

AB - 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. Time window has been a common form of time constraint considered in the literature. Basically, a time window is a time period, defined by the earliest and latest times, when a node is available for traveling through. There are many practical situations where time windows can be used to describe the time constraints associated with the nodes and arcs on a network. For example, a time window in a transportation network may be the time period that a service or transition facility is available for the traveler to pass through. Although there are many researchers on the transportation problem in time-window networks, no previous researches study how to find the first K shortest paths in a time-window network; hence, this paper studies this extended problem. The extension has many potential applications in practice. For example, there may be some complex constraints associated with the nodes and/or arcs of the network, which are difficult to incorporate into the model formulation. A solution strategy is to temporarily ignore these constraints and obtain a list of paths in nondecreasing order in terms of their total times. The optimal solution can be found by identifying the first path in the list that satisfies the constraints. Another use of the result is a quick selection of an alternative path when encountering temporary disconnection of the active shortest path.

KW - Network

KW - Shortest path

KW - Simple path

KW - Time-window constraint

UR - http://www.scopus.com/inward/record.url?scp=0347900476&partnerID=8YFLogxK

U2 - 10.1016/S0305-0548(02)00230-7

DO - 10.1016/S0305-0548(02)00230-7

M3 - 期刊論文

AN - SCOPUS:0347900476

VL - 31

SP - 499

EP - 513

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

IS - 4

ER -