AN APPROACH TO TRIP- AND ROUTE-PLANNING PROBLEMS

摘要

Some practical planning problems can be interpreted as set-to-set shortest path problem ( spp ), i.e., as search of a shortest path between two sets of nodes, A and B , of a graph G . A straightforward reduction of such a problem to the search of solutions for point-to-point spp s is impractical because the computational complexity is too high for a huge G . This paper presents a new approach to set-to-set spp for the case of not arbitrary A and B , but those which are represented by some nodes of an additional graph T . The graph T simulates a "geographic system" on G . Under some assumptions natural for many applications, this approach leads to a competitive algorithm for this kind of set-to-set spp . As prospective areas for this technique, two applications are discussed - the problem of route planning for a visually guided robot in a static environment, and the problem of planning a fastest trip by means of all available timetables of all kinds of transport.