The Algorithm of the Time-Dependent Shortest Path Problem with Time Windows

• 作者: Nasser A. El-Sherbeny
• 来源期刊: 应用数学(英文)
• 学科: 数学
• 关键词: Shortest PATH TIME-DEPENDENT Shortest PATH ALT ALGORITHM A* ALGORITHM TIME WINDOWS
• 年，卷（期）: 2014,（17）
• 页码范围: 2764-2770
• 页数: 7页
• 分类号: O1

摘要

In this paper, we present a new algorithm of the time-dependent shortest path problem with time windows. Give a directed graph , where V is a set of nodes, E is a set of edges with a non-negative transit-time function . For each node , a time window ?within which the node may be visited and ?, is non-negative of the service and leaving time of the node. A source node s, a destination node d and a departure time?t0, the time-dependent shortest path problem with time windows asks to find an s, d-path that leaves a source node s at a departure time t0;and minimizes the total arrival time at a destination node d. This formulation generalizes the classical shortest path problem in which ce are constants. Our algorithm of the time windows gave the generalization of the ALT algorithm and A* algorithm for the classical problem according to Goldberg and Harrelson [1], Dreyfus [2] and Hart et al. [3].