Abstract:
A method for obtaining a many-to-many route searching process with a reasonable amount of computation. The method includes preparing a graph expressing road segments as edges and route intersections as nodes, the weight of each road segment being approximated by a monotonically increased piecewise linear function, searching the graph for the shortest routes, establishing the obtained routes as a set of routes to be processed, solving an objective function so as to minimize the maximum value obtained by dividing the required time from each departure point to each destination point by the shortest required time with respect to the set of a plurality of departure points and destination points, and removing those routes whose minimum cost is greater than or equal to that of the current best solution, and any unused routes added in the previous iteration, while repeating the solving of the objective function.

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
     This application is a National Phase application based on PCT/JP2011/075664 which claims priority from Japanese Patent Application No. 2010-263649 filed Nov. 26, 2010, the entire contents of both of which are incorporated herein by reference. 
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to a system, a method, and a program for selecting routes such as traffic routes. 
     2. Description of Related Art 
     Car navigation systems have a function which searches for and displays traffic routes. The algorithm in this process, for example, treats intersections as nodes and road segments as edges, and searches for the shortest route in a weighted graph in which the lengths of routes are weighted. 
     However, at this time, a large number of automobiles have car navigation systems that are used to simultaneously search for routes, and each automobile independently determines the shortest route. When this causes an overlap of traffic routes for a plurality of automobiles, the frequency of use of particular routes or edges increases, and congestion occurs in some of these routes. At this time, as shown in  FIG. 1 , the times for each route are believed to increase rapidly as traffic volume increases. 
     In automobiles, traffic information provided by the Vehicle Information and Communication System (VICS) is referenced so that the car navigation system can calculate an alternate route. However, when a large number of vehicles reference the same traffic information, similar alternate routes are eventually selected and this causes further congestion as shown in  FIG. 2 . 
     Therefore, there is a need for a central server to take into account the occurrence of congestion due to a concentration of vehicles and, as shown in  FIG. 3 , perform many-to-many routing to alleviate congestion. In other words, there is a possibility of reducing required times if congestion can be mutually avoided. However, the calculations performed in many-to-many routing usually experience difficulties, and it is difficult to come up with a solution in a reasonable amount of time. 
     A system is disclosed in Japanese Patent Publication No. 2001-331564 for realizing an effective plan by calculating routes for each means of transport in a transportation plan using a means optimized for the necessary precision and calculation time of each plan. This system, which has at least an input/output device, a processor and a storage device, and which creates a distribution plan, comprises: a base information registration step for inputting position information for a base such as a factory, a relay base, and a supplier, a transportation service information registration step for inputting transportation delivery information including bases that each transportation service visits and load quantities, a condition registration step for inputting target information including the necessary accuracy and limit time of a transportation plan, an algorithm selection step for selecting an algorithm used for route preparation, a route preparation step for preparing a route for a delivery service from this information, and an output step for outputting the result. 
     Japanese Patent Publication No. 2004-12312 discloses a route searching device comprising a first searching means for searching for a minimum cost route along which the parameter accompanying the route becomes the minimum among the parameters accompanying the routes from a starting point to a destination, a weighting means for weighing the parameter of each road section constituting a first shortest route, and an area limiting means for finding a specific map area as a limited area based on the calculated data of the first searching means. This device also comprises a second searching means for searching for a route only in the limited area found by means of the area limiting means by regarding the area as an object to be searched. The time required for a subsequent search is shortened by limiting the search range by utilizing information obtained during the previous search. 
     Japanese Patent Publication No. 2009-19932 discloses a route search system for searching for a moving route for an autonomous moving body reaching a moving end point from a moving start point, which comprises a region dividing portion for dividing a moving region into a plurality of regions, a plurality of evaluation value calculating portion for calculating an evaluation value of each region, corresponding to the plurality of regions divided by the region dividing part, and a route determining portion for determining the route, based on the evaluation values calculated by the evaluation value calculating parts. The evaluation value calculating portion has an evaluation value processing portion for calculating an evaluation value based on the evaluation value of a region existing nearby and moving cost from a nearby region to its own region. Paragraph 0073 states that “the number of regions indicated as moving start points and moving end points can be applied to the present invention whether it is many-to-one, one-to-many, or many-to-many. 
     However, none of the prior art literature discloses a technique for obtaining many-to-many route search processing with a reasonable amount of computation, even though a simple solution requires an enormous amount of computation. 
     SUMMARY OF THE INVENTION 
     Therefore, it is an object of the present invention to provide a technique for obtaining a many-to-many route searching process with a reasonable amount of computation. 
     It is another object of the present invention to provide a technique for obtaining a route searching process with a reasonable amount of computation and while taking into account the level of congestion due to the transit of a plurality of vehicles. 
     In the present invention, the occurrence of congestion due to an increase in traffic volume is modeled by describing traffic routes as a graph, and approximating the required time of each edge using a monotonically increased piecewise linear function. This model approximates a curve of the relationship between levels of congestion and required times shown in  FIG. 1 . 
     When information is requested by a car navigation system indicating a departure point and a destination point, all of the vehicles can be treated fairly and completely rational routing can be realized using an objective function in which “the maximum value of all values obtained by dividing the actual required time for all requests by the shortest required time is minimized”. This finding of the present invention can be described as a mixed integer programming (MIP) problem, and solved using a predetermined solver. 
     However, the MIP description requires the explicit enumeration of all possible routes, and the number of candidate routes could be exponential in accordance with the size of the graph. This implies that this problem is an NP-hard problem and difficult to solve in reality. 
     In a characteristic of the present invention, the number of candidate routes could be exponential, but an explosion in the number of candidate routes is suppressed by solving the MIP problem while gradually and repeatedly adding promising routes from the initial state. 
     In another characteristic of the present invention, by searching for new routes using the actual routes at the end of an iteration, routes with a high utility value are preferentially searched for as alternate routes. At this time, any route having a minimum cost greater than the best solution at the time, and any unused route added in the previous iteration is removed as an unpromising route. 
     In another characteristic of the present invention a plurality of routes from a departure point to a destination point are obtained along with their utilization ratio as a result of MIP calculations. These results can be used to optimize routing so as to alleviate congestion. 
     In yet another characteristic of the present invention, by keeping the routes used during the previous iteration when updating the route candidates, the solution of the previous iteration can be used as the initial value in the MIP problem, and the computation time can be greatly reduced. 
     In the present invention, many-to-many routes can be calculated with a reasonable amount of computations by using a mixed integer programming problem and by removing unpromising routes and keeping routes used in the previous iteration so as to start iterative calculations from a promising value. 
     In the present invention, the desired routing can be obtained which alleviates congestion using a reasonable amount of computation by approximating the required times of each edge using a monotonically increased piecewise linear function. 
    
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         FIG. 1  is a diagram showing the relationship between traffic volumes and required times. 
         FIG. 2  is a diagram showing how a vehicle avoids a certain route using congestion information. 
         FIG. 3  is a diagram showing how a vehicle is guided to a route in the appropriate manner. 
         FIG. 4  is a block diagram of an example of a hardware configuration used to embody the present invention. 
         FIG. 5  is a block diagram of an example of a functional configuration used to embody the present invention. 
         FIG. 6  is a diagram showing how to approximate using a monotonically increased piecewise linear function. 
         FIG. 7  is a diagram showing a flowchart of the route selecting process of the present invention. 
         FIG. 8  is a diagram showing a flowchart of the route selecting process of the present invention. 
         FIG. 9  is a diagram showing an example of output of the processing of the present invention. 
     
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     The following is an explanation of an example of the present invention with reference to the drawings. The same reference numbers are used to denote the same objects in all of the drawings except where otherwise indicated. The following explanation is of an embodiment of the present invention, and the present invention is by no means intended to be limited to the content explained in the example. 
       FIG. 4  is a block diagram of computer hardware used to realize the system configuration and processing in an example of the present invention. In  FIG. 1 , a CPU  404 , main memory (RAM)  406 , a hard disk drive (HDD)  408 , a keyboard  410 , a mouse  412 , and a display  414  are connected to a system bus  402 . The CPU  404  is preferably based on 32-bit or 64-bit architecture, and can be a Pentium® 4, Core® 2 Duo or Xeon® from Intel Corporation, or an Athlon® from Advanced Micro Devices, Inc. The main memory  406  preferably has a capacity of 4 GB or more. The hard disk drive  408  preferably has a capacity of 500 GB or more in order to store a large amount of data. Main memory  406  and hard disk drive  408  are examples of computer readable storage mediums. Computer readable storage mediums are hardware capable of storing information such as data, computer readable instructions, program code in functional form, and/or other suitable information on a temporary basis and/or permanent basis. 
     A preferred example of such a hardware configuration is the IBM® System X series. However, the present invention is not limited to this. It can even be embodied in a personal computer. 
     While not shown in any of the drawings, the hard disk drive  408  includes a pre-installed operating system. The operating system can be any operating system compatible with the CPU  404 . Examples include Linux®, Windows XP®, Windows 2000®, and Windows 2008 Server® from Microsoft Corporation, or Mac OS® from Apple, Inc. 
     The hard disk drive  408  stores the main routine  502 , traffic route graph data  504 , request data  506 , solver  508 , route searching module  510 , and route updating module  512  described below. 
     The main routine  502 , solver  508 , route searching module  510 , and route updating module  512  are created in an existing programming language such as C, C++, C# or Java™, and are loaded into the memory  406  at system startup and by the action of the operating system, if necessary. 
     The display  414  is preferably a liquid crystal display. Any resolution can be used, including XGA (resolution: 1024×768) or UXGA (resolution: 1600×1200). While not shown in the drawings, the display  414  is used to display operating screens for starting and stopping the processing program of the present invention, and for displaying traffic route data. 
     The following is an explanation of the logic function structure used to embody the present invention with reference to the function block diagram of  FIG. 5 . In  FIG. 5 , the main routine  502  is the program that manages the overall process, displays operating screens (not shown) on the display  414 , and starts and stops the process in response to user operations entered using the keyboard  410  and mouse  412 . 
     The traffic graph data  504  is weighted graph data in which routes are described in graph form with roads expressed as edges and intersections as nodes, and in which the weight of each road is approximated by a monotonically increased piecewise linear function to model the occurrence of congestion due to an increase in traffic volume. The graph is typically expressed as a matrix or list to make it computer readable and storable in media such as a hard disk. However, the graph can assume any form able to achieve the object of the present invention. 
       FIG. 6  is a diagram showing the piecewise linearity of the edges and required times. Here, x is traffic volume expressed in the number of vehicles transiting per hour. This is a piecewise linear approximation of the graph shown in  FIG. 1 . As shown in the drawing, the piecewise linear functions used are required time t=a 1 x+b 1  where 0≦x&lt;x 1 , required time t=a 2 x+b 2  where x 1 ≦x&lt;x 2 , and required time t=a 3 x+b 3  where x 2 ≦x, where a i &gt;0 (i=1, 2, 3). Here, only three zones are shown, but this is merely an embodiment. If necessary, zones of any number and width can be used. The piecewise linear functions are not limited to this. For example, it can be implemented as a linear function indicated from each edge and referencing a table in memory. In other words, a table is prepared so that {a 1 , b 1 } is returned in response to a value for traffic volume of ≦x 1 , and {a 2 , b 2 } is returned in response to a value for traffic volume of x 1 ≦x&lt;x 2 , etc. 
     The coefficient groups such as {a 1 , b 1 }, {a 2 , b 2 } for performing piecewise linear approximation of each edge are determined according to the actual condition of the road. In other words, a coefficient such as {a i , b i } (i=1, 2, 3, etc.) is preferably determined in proportion to the actual length of the edge. However, {a i , b i } is made larger for a road going uphill, and {a i , b i } is made smaller for a road going downhill. Also, {a i , b i } is made larger for a road with a large curve, {a i , b i } is made smaller for a road with many lanes, and {a i , b i } is made larger for a narrow road. In addition, {a i , b i } is made smaller for a road with good pavement, and {a i , b i } is made larger for a road with no pavement. 
     In a preferred example, the required time for each edge is t=max i {a i x+b i }. Here, a i &gt;0. 
     The request data  506  is provided as a set of {departure point, destination point, demand level}. This request data can be collected, for example, using probe car data. Traffic data collection techniques using probe car data are common in the art. For examples, see Japanese Patent Publication No. 2004-110458, Japanese Patent Publication No. 2004-156982, Japanese Patent Publication No. 2007-193705, and Japanese Patent Publication No. 2004-241987. Because the number of vehicles traveling between each {departure point, destination point} pair is known over a given period of time, these techniques can be used prepare request data  506  so that the number of vehicles is set as the level of demand, the {departure point, destination point, demand level} sets are sorted in descending order by level of demand, and a predetermined number of pairs is saved from the top to a hard disk drive  408 . 
     The solver  508  uses as the objective function a minimized maximum value of all values obtained by dividing the actual required time for all requests by the shortest required time, and solves a mixed integer programming (MIP) problem, providing as output to each request a plurality of routes and their utilization ratio (real number). There are no restrictions on the solver, but a preferred example is IBM® ILOG CPLEX. The MIP formulation is explained below in greater detail. 
     The route searching module  510  performs a weighted graph route search using any well-known algorithm such as Dijkstra&#39;s Algorithm or an A* search technique. The algorithm can also be a revised A* search technique described in Japanese Patent Publication No. 2008-157698. 
     The route updating module  512  arbitrarily eliminates routes in order to reduce the amount of computation or adds useful routes. The process executed by the route updating module  512  is explained in greater detail below with reference to the flowchart in  FIG. 8 . 
     The following is an explanation of the route selecting process of the present invention with reference to the flowchart in  FIG. 7  and  FIG. 8 . 
     In Step  702  of  FIG. 7 , the main routine  502  calls up the route searching module  510 , and searches for the lowest cost route, or shortest route, from a departure point to a destination point for the {departure point, destination point} pair in request data  506  where x=0 is placed in the formula for t=max i {a i x+b i }. 
     In Step  704 , the main routine  502  calls up the solver  508 , and solves a mixed integer programming (MIP) problem with the candidate routes at the present time. In the loop consisting of Step  704 , Step  706  and Step  708 , the calculation time can be reduced by using the previous solution as the initial value in the second and subsequent iterations. 
     The following is an explanation of the MIP formulation. The formulation is intended to use an objective function in which the maximum value of all values obtained by dividing the actual required time for all requests by the shortest required time is minimized. This is expressed as graph G=(V, E), where V is the set of nodes and E is the set of edges in the traffic graph data  504 . Referencing the piecewise linear approximation in  FIG. 6 , the traveling time for moving along edge e E is expressed by the following equation, where the volume of traffic is x.
 
 t   e ( x )=max i ( a   ei   x b   ei )
 
     Here, a ei &gt;0. 
     Request i (i=1, k) has the following attributes. 
     The node of the departure point: s i  V 
     The node of destination point: g i  V 
     The level of demand: d i  R, d i &gt;0 
     Also, let P i * be the set of all routes not including the cycle from node s i  to node g i . Then, p P i * is expressed as a permutation of the connecting edge.
 
 p =( e   i   ·e   2    . . . ,e   |p| )
 
     Here, |p| is the number of edges connected to p. 
     Therefore, let T i * be the minimum required time from node s i  to node g i  when traffic volume x is 0. In other words, T i * is expressed by the following equation. 
     
       
         
           
             
               
                 
                   
                     T 
                     i 
                     * 
                   
                   = 
                   
                     
                       min 
                       
                         p 
                         ∈ 
                         
                           P 
                           i 
                           * 
                         
                       
                     
                     ⁢ 
                     
                       
                         ∑ 
                         
                           e 
                           ∈ 
                           p 
                         
                       
                       ⁢ 
                       
                         
                           t 
                           e 
                         
                         ⁡ 
                         
                           ( 
                           0 
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   1 
                 
               
             
           
         
       
     
     At this time, let the cost of each edge e E be t e (0), and Ti* can be determined, for example, by calling up the route searching module  510  and executing the shortest route search algorithm, even though all of the elements of Pi* are not explicitly enumerated. 
     Also, sequential numbers are given to the elements of candidate route set P i * for request i, and the jth route of P i * (j=1, . . . , |P i *|) is expressed by p i . In addition, L is a sufficiently large positive constant, and y ij  is an integer variable, which takes 0 or 1 expressing whether or not candidate route j for request i is used. These definitions are used to formulate a mixed integer programming problem in the following manner. 
                     min   ⁢           ⁢   λ     ⁢     
     ⁢             s   .   t   .     
     ⁢     Ly   ij       +       ∑     e   ∈     p   ij         ⁢       t   e     ⁡     (     x   e     )           ≤       λ   ⁢           ⁢     T   i   *       +     L   ⁢           ⁢   for   ⁢           ⁢   i         =   1     ,   …   ⁢           ,   k   ,     
     ⁢     j   =   1     ,   …   ⁢           ,          P   i   *            ⁢     
     ⁢       x   e     =         ∑       (     i   ,   j     )     =     {     i   ,     j   |     e   ∈     p   ij           }         ⁢       x   ij     ⁢           ⁢   for   ⁢           ⁢   e       ∈   E       ⁢     
     ⁢           ∑   j     ⁢     x   ij       =         d   i     ⁢           ⁢   for   ⁢           ⁢   i     =   1       ,   …   ⁢           ,   k     ⁢     
     ⁢           x   ij     ≤       d   i     ⁢     y   ij     ⁢           ⁢   for   ⁢           ⁢   i       =   1     ,   …   ⁢           ,   k   ,     j   =   1     ,   …   ⁢           ,          P   i   *            ⁢     
     ⁢         x   ij     ≥   0     ,         x   ij     ∈     R   ⁢           ⁢   for   ⁢           ⁢   i       =   1     ,   …   ⁢           ,   k   ,     j   =   1     ,   …   ⁢           ,          P   i   *            ⁢     
     ⁢           y   ij     ∈       {     0   ,   1     }     ⁢           ⁢   for   ⁢           ⁢   i       =   1     ,   …   ⁢           ,   k   ,     j   =   1     ,   …   ⁢           ,          P   i   *          ,             Equation   ⁢           ⁢   2               
where expressions below s.t. (such that) represent constraints.
 
     Thus, x ij  resulting from the solution of the mixed integer programming problem expresses the traffic volume of the jth route in request i. In other words, x ij /d i  is the utilization ratio of the jth route in request i. This utilization ratio is expressed in  FIG. 9  as a percentage associated with each of a plurality of routes from the departure point  1  to the destination point  1 . 
     Next, in Step  706 , the main routine  502  determines whether or not the termination conditions have been satisfied. The termination conditions have been satisfied, for example, when the calculation time exceeds a time set in advance, or the number of iterations has exceeded a predetermined number. 
     When the main routine  502  has determined that the termination conditions have been satisfied, the process is terminated. At this time, a plurality of routes from the departure point to the destination point of each request, and the utilization ratio of each route are obtained. 
     When the main routine  502  in Step  706  determines that the termination conditions have not been satisfied, the process proceeds to Step  708 , where the main routine  502  calls up the route updating module  512  and updates the candidate routes. The candidate routes are updated by deleting unused routes and unpromising routes, and adding promising routes. This process is explained below in greater detail with reference to the flowchart in  FIG. 8 . 
     After the candidate routes have been updated in Step  708 , the MIP is again solved by the solver  508  in Step  704  based on the updated candidate routes. 
     The following is an explanation of the processing performed in the route updating module  512  with reference to the flowchart in  FIG. 8 . In other words, in Step  802 , the route updating module  512  eliminates the following routes in each request as unpromising routes.
         Those routes whose lowest cost is equal to or greater than the cost of current best solution. Here, the lowest cost is the cost when traffic volume x=0.   Those routes that was added in the previous iteration, but not used. An unused route is determined in the calculation results of the solver  508  in Step  704  by a value of 0 for variable y ij .       

     An explosion in the number of candidate routes is suppressed by eliminating these routes. 
     In Step  804 , the route updating module  512  sets those requests whose “actual required time/shortest required time” is maximum and “actual required time” for all the candidates is same to bottleneckRequest&#39;s, and sets those edges included in the candidate route to bottleneckEdge&#39;s. In other words, the route updating module  512  identifies bottleneck requests and bottleneckEdge sets in the results of each iteration. Those requests that determine the object function value are defined as bottleneckRequest&#39;s, and those edges included in candidate routes of the request are defined as bottleneckEdge&#39;s. 
     In Step  806 , the route updating module  512  searches for routes in each bottleneckRequest whose cost is less than the current best solution which satisfy the following conditions.
         With the current cost, those routes that do not use bottleneckEdge&#39;s will be searched.   If not found, with the current cost, those routes that may use bottleneckEdge&#39;s will be searched.       

     Any route found in this manner is added. In other words, routes which lower the objective function value when added, or routes with a high probability of lowering the objective function value can be efficiently added. 
     In Step  808 , the route updating module  512  determines whether or not a candidate route was found in Step  806 . If found, returning from the subroutine shown in  FIG. 8 , the process goes back to Step  704  in  FIG. 7 . 
     When the route updating module  512  determines in Step  808  that a candidate route was not found, the route updating module  512  in Step  810  searches for a route satisfying the following conditions if there is no route concerning each non-bottleneckEdge which worsens the solution at the time and increases the flow, that is, traffic volume.
         With the current cost, those routes that do use bottleneckEdge&#39;s will be searched.   If not found, those route that may use bottleneckEdge&#39;s will be searched.       

     If a route is found, it is added. Returning from the subroutine shown in  FIG. 8 , the process goes back to Step  704  in  FIG. 7 . 
     The reason why the process in Step  810  is performed is that even those requests that are not bottleneck may improve the objective function value by adding candidate routes. At this time, for those requests that have the candidate routes satisfying the following conditions, the objective function value cannot be improved no matter which route is added for such the requests.
         None of the edges of the candidate route is a bottleneckEdge and the route itself is not a route to determine the current objective function value.       

     These conditions assume the cost function of the edge is a cost function that strictly increases monotonically. In other words, for the required time function of the “ax+b”, “a&gt;0” should be used instead of “a 0”. 
     Returning to the flowchart in  FIG. 7 , when the MIP has been calculated in Step  704  and it has been determined in Step  706  that the termination conditions have been satisfied, a plurality of routes is returned for each request, and a utilization ratio is returned for each route. 
     When the desired routes between many-to-many departure points and destination points and the utilization ratios of the desired routes have been obtained in this manner, those can be applied to the routing of traffic in order to alleviate steady or permanent congestion, such as during rush hour, and regular congestion around certain facilities. 
     It can also be applied to crowd control in order to plan efficient routes for crowd movement at event venues, and to plan effective evacuation routes in case of fire. 
     The present invention was explained with reference to a particular embodiment, and one type of hardware configuration was illustrated. However, the present invention can also be used in any other hardware environment, such as a multiprocessor environment or a network-connected crown computing environment.