摘要 |
PROBLEM TO BE SOLVED: To obtain a method for determining a lowest cost route among a combination of routes between a starting point and a goal and determining an effective alternative route for a network comprising nodes and links and including an inter-link transition cost. SOLUTION: The cost of a pair of incoming and outgoing links for a node is set equal to the sum of transition cost between the outgoing link and a link (Fig. (1)). A new network is then constituted of new nodes, i.e., the links, and new links, i.e., the pair of links (Fig. (2)), and a lowest cost route is searched for the new network using Dijkstra's algorithm (Fig. (3)). In the lowest cost route, one or more new link (a pair of links in the original network) to be connected with different lines is disabled and an effective alternative route is searched using Dijkstra's algorithm (fig. (4)). |