| 摘要 |
To provide a technique for obtaining multipoint-to-multipoint route search processing with a rational amount of calculation. When information for indicating a start point and a destination point is requested, an objective function is described as a mixed integer programming problem (MIP) in which the function is set as a "minimization of the maximum of a value obtained by dividing actual required time for all the requests by the shortest required time". Then, from an initial state, prospective routes are gradually added, and the MIP is repeatedly solved, thereby suppressing an explosion of the number of candidate routes. A new route is searched with the use of an actual route at a certain point of time when the repetition is ended, thereby giving priority to search a route which has high usage value as an alternative route. At this time, a route having the minimum cost which is equal to or more than the best solution at that time and a route which has been added but has not been used in a preceding repetition are removed as routes which are not prospective. In updating the route candidates, the route which has been used in the preceding repetition is sure to be remained, thereby making it possible to use a solution of the preceding repetition in the MIP as an initial value, with the result that calculation time is reduced. |
