Route search system and route search method

• US 6,510,384 B2
• Filed: 11/15/2001
• Issued: 01/21/2003
• Est. Priority Date: 11/15/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Okano, Hiroyuki
• Primary Examiner(s): Beaulieu, Yonel
• Application Number:
  US09/998,957
• Publication Number:
  US 20020082772A1
• Time in Patent Office: 432 Days
• Field of Search: 701/202, 701/201, 701/209, 701/210, 701/25, 701/26, 342/357.09, 342/357.13
• US Class Current: 701/209
• CPC Class Codes: G01C 21/343 Calculating itineraries, i.e. routes leading from a starting point to a series of categorical destinations using a global route restraint, round trips, touristic trips travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

A method for increasing the execution speed of a cost-minimizing routing algorithm, as employed in trucking or job shop scheduling. Penalty functions for succeeding transit points along a route are added and examined for validity during trial route evaluation. A soft time window is set for each transit point, and proposed routes are evaluated using a total cost including all soft time windows along the route and the length of the route. A static soft time window function and a dynamic soft time window function are correlated with each transit point. The dynamic soft time window function for each transit point is the sum of the static soft time window function for the Transit point and the dynamic soft time window function for a succeeding transit point in the direction of travel.

Claims

1. A route search system comprising:

dynamic penalty function addition means;

route segment dynamic penalty function calculation means;

route segment penalty cost calculation means;

route evaluation means; and

dynamic penalty function validity determination means,

wherein a static penalty function f, which is a cost function of an arrival time variable

t and is a base for calculation of a penalty cost, is set for each transit point, wherein said static penalty function f is so defined that said static penalty functions for

individual transit points are enabled to be added, wherein an original route and a trial route are evaluated based on the total cost CT

that includes, for each route, at least a penalty cost CS and a length cost CL, wherein the direction toward the first of a route is called the inverse direction of

travel and the direction toward the end of said route is called the direction of

travel, and wherein a dynamic penalty function F is correlated with each transit point.

2. The route search system according to claim 1,

wherein said dynamic penalty function addition means calculates said dynamic penalty function F for each transit point along said route, extending backward, in the direction opposite to that of normal propagation, from the last transit point P_z,

wherein, when an arbitrary transit point is called P1 and a succeeding transit point in the direction of travel is called P2, said dynamic penalty function addition means calculates a dynamic penalty function F for P1 based on the sum of a static penalty function f for P1 and the dynamic penalty function F for P2, while, it should be noted, for the dynamic penalty function addition, a t in said dynamic penalty function F for P2 is defined as a t in said static penalty function f, to which a value equal to the difference between the arrival time for P2 and the arrival time for P1 is added.

3. The route search system according to claim 2,

wherein, when the first and last transit points along a target route segment to be changed on the original route are called P1 and P2 (P2=P1 may be established) and the succeeding transit point, following P2, along said original route in the direction of travel is called P3, and when said dynamic penalty function validity determination means determines that the dynamic penalty functions for transit points following P1, along said original route, are valid, said route segment dynamic penalty function calculation means, the dynamic penalty function F for said target route segment is calculated based on the results obtained by subtracting the dynamic penalty function F for P3 from the dynamic penalty function F for P1, while, it should be noted, a t in the dynamic penalty function for P3 is defined as said t in the dynamic penalty function for P1, to which the difference between the arrival time for P3 and the arrival time for P1 is added,

wherein, when the first transit points along said target route segments of said original route and a trial route are defined as P1, said route segment penalty cost calculation means calculates penalty costs for said target route segments by substituting the arrival times at said transit points P1 along said original route and said trail route into arrival time variables t in said dynamic penalty functions of said route segments that are obtained by said route segment dynamic penalty function calculation means.

4. The route search system of claim 3, wherein said route evaluation means evaluates said original route and said trial route by comparison of said penalty costs for said target change route segments.

5. The route search system according to claim 4, wherein, when the succeeding transit points of the last target route segments to be changed on said original route and of said trial route in the direction of travel are defined as P3, and when route segments from the transit points P3 to Pz are called forward route segments, said route segment penalty cost calculation means calculates the penalty costs for said forward route segments of said original route and of said trial route by substituting the arrival times at said transit points P3 along said original route and along said trial route into the arrival time variables t for the dynamic penalty functions for said transit points P3;

and wherein said route evaluation means evaluates said original route and said trial route based on the comparison of said penalty costs for said forward route segments of said original route and of said trial route.

6. The route search system according to claim 5, further comprising:

time offset holding means,

wherein, as an arrival time, a time offset is employed that is represented by an offset, held by said time offset holding means, from a reference time Tb, and

wherein, when the total cost CT of said trial route is smaller than the total cost CT of said original route, and each time said original route is updated to a trial route, said time offset holding means updates said reference time Tb based on a change L_reduce for the time re-calculation length of the updated route.

7. The route search system according to claim 6, further comprising:

first arrival time offset calculation means, for calculating an arrival time offset a that, through inverse propagation initiated at said last transit point Pz, is set for each transit point along a route,

wherein, when an arbitrary transit point is defined as P1 and an immediately succeeding transit point in the direction of travel is defined as P2, said first arrival time offset calculation means calculates an arrival time offset a_P1, for said transit point P1, based on the results obtained by subtracting from an arrival time offset a_P2, for said transit point P2, the sum of the time d(P1, P2), for the travel between P1 and P2, and a working time w_P1, for said transit point P1, and

wherein said dynamic penalty function addition means determines, as said arrival time offset a, which is obtained by said first arrival time offset calculation means, an arrival time that is to be used by said dynamic penalty function addition means for calculating an arrival time difference.

8. The route search system according to claim 7, further comprising second arrival time offset calculation means,

wherein it is ascertained that the arrival time offset a is changed at all the transit points along said trial route from a point whereat a target route segment to be changed is inserted or extracted,

wherein the preceding transit point along the first target route segment to be changed on said original route in the direction of travel is defined as P0,

wherein said second arrival time offset calculation means calculates an arrival time offset a_i at a transit point i using an arrival time offset a_P0 at P0 along a trial route in the direction of travel,

wherein, when an arbitrary transit point is defined as P1 and an immediately succeeding transit point in the direction of travel is defined as P2, said second arrival time offset calculation means calculates an arrival time offset a_P2 at said transit point P2 based on the results obtained by adding an arrival time offset a_P1, at said transit point P1, to the sum of a working time w_P1 for P1, and time d(P1, P2) for the travel between P1 and P2,

wherein said route segment penalty cost calculation means determines an arrival time, which is to be substituted into t in the dynamic penalty function for said route segment obtained by said route segment dynamic penalty function calculation means, as the time obtained by adding said reference time Tb to said arrival time offset a, that is obtained by said second arrival time offset calculation means for the first transit point along said route segment.

9. The route search system according to claim 8, further comprising:

first dynamic earliest arrival time calculation means for calculating, through inverse propagation originating at the last transit point Pz, a dynamic earliest arrival time E that is correlated with a static earliest arrival time e that is set for each transit point along a route to inhibit an arrival earlier than said static earliest arrival time e,

wherein, when an arbitrary transit point is defined as P1 and the immediately succeeding transit point in the direction of travel is defined as P2, said first dynamic earliest arrival time calculation means determines said dynamic earliest arrival time E for P1, as a later time, either a static earliest arrival time e_P1 for P1, or the value obtained by subtracting from a dynamic earliest arrival time E_P2 for P2, the sum of a work time w_P1 for P1, and a time d(P1, P2) for the travel between P1 and P2, and

wherein, when the time obtained by adding said reference time Tb to said arrival time offset a, which is obtained for said forward route segment of said trial route by said first arrival time offset calculation means, is earlier than said dynamic earliest arrival time E for said forward route segment, which is obtained by said first dynamic earliest arrival time calculation means, said penalty cost calculation means halts the calculation of a penalty cost for said forward route segment of said trial route.

10. The route search system according to claim 9, further comprising:

second dynamic earliest arrival time calculation means, for calculating the dynamic earliest arrival time E for a target route segment to be changed,

wherein, when the first and the last transit points along said target route segment to be changed are called P1 and P2 (P2=P1 may be established), said second dynamic earliest arrival time calculation means determines, as said dynamic earliest arrival time E for said target route segment to be changed, which is the later time, the static earliest arrival time e_P1 for P1, or a value obtained by subtracting from the static earliest arrival time e_P2 for P2, the difference between a_P2 and a_P1, which are arrival time offsets for P2 and P1 obtained by said first arrival time offset calculation means, and

wherein, when the time value obtained by adding said reference time Tb to the arrival time offset a, which is calculated by said first or second arrival time offset calculation means for said target route segment to be changed on said trial route, precedes said dynamic earliest arrival time E for said target route segment that is obtained by said second dynamic earliest arrival time calculation means, said penalty cost calculation means halts the calculation of the penalty cost for said target route segment to be changed on said trial route.

11. The route search system according to claim 10, further comprising:

first dynamic latest arrival time calculation means for calculating, through inverse propagation originating at the last transit point Pz, a dynamic latest arrival time L that is correlated with a static latest arrival time 1 that is set for each transit point along a route to inhibit an arrival later than said static latest arrival time 1,

wherein, when an arbitrary transit point is defined as P1 and the immediately succeeding transit point in the direction of travel is defined as P2, said first dynamic latest arrival time calculation means determines said dynamic latest arrival time L for P1, as an earlier time, either a static latest arrival time l_P1 for P1, or the value obtained by subtracting from a dynamic latest arrival time L_P2 for P2, the sum of a work time w_P1 for P1, and a time d(P1, P2) for the travel between P1 and P2, and

wherein, when the time obtained by adding said reference time Tb to said arrival time offset a, which is obtained for said forward route segment of said trial route by said first arrival time offset calculation means, is later than said dynamic latest arrival time L for said forward route segment, which is obtained by said first dynamic latest arrival time calculation means, said penalty cost calculation means halts the calculation of a penalty cost for said forward route segment of said trial route.

12. The route search system according to claim 11, further comprising:

second dynamic latest arrival time calculation means, for calculating the dynamic latest arrival time L for a target route segment to be changed,

wherein, when the first and the last transit points along said target route segment to be changed are called P1 and P2 (P2=P1 may be established), said second dynamic latest arrival time calculation means determines, as said dynamic latest arrival time L for said target route segment to be changed, which is the earlier time, the static latest arrival time l_P1 for P1, or a value obtained by subtracting from the static latest arrival time l_P2 for P2, the difference between a_P2 and a_P1, which are arrival time offsets for P2 and P1 obtained by said first arrival time offset calculation means, and

wherein, when the time value obtained by adding said reference time Tb to the arrival time offset a, which is calculated by said first or second arrival time offset calculation means for said target route segment to be changed on said trial route, precedes said dynamic latest arrival time L for said target route segment to be changed that is obtained by said second dynamic latest arrival time calculation means, said penalty cost calculation means halts the calculation of the penalty cost for said target route segment to be changed on said trial route.

13. The route search system according to claim 9, further comprising:

first dynamic length calculation means for calculating a dynamic length W, which is correlated with each transit point along a route, through inverse propagation originating at the last transit point Pz;

arrival time offset validity determination means; and

second dynamic length calculation means.

14. The route search system according to claim 13,

wherein, when an arbitrary transit point is defined as P1 and the immediately succeeding transit point in the direction of travel is defined as P2, said first dynamic length calculation means determines, as a dynamic length W_P1 for P1, a value based on the results obtained by adding a dynamic length W_P2 for P2, to the sum of the travel time between P1 and P2 and a working time for P1,

wherein, when said arrival time offset validity determination means ascertains that arrival time offsets for transit points following P1 along the original route are valid, and when the first and last transit points along said target route segment to be changed are called P1 and P2 (P2=P1 may be established) and the succeeding transit point, following P2, along the original route in the direction of travel is called P3, said second dynamic length calculation means obtains said dynamic length W for said target route segment to be changed by subtracting from a dynamic length W_P1 for P1, the sum of a dynamic length W_P3 for P3, and the travel time between P2 and P3, and

wherein, when a dynamic length for said target route segment obtained by said second dynamic length calculation means is defined as W, said second arrival time offset calculation means calculates an arrival time offset of a_P3 for P3, based on the results obtained by adding an arrival time offset a_P1 for P1, to the sum of said dynamic length W and the travel time between P2 and P3.

15. The route search system according to claim 14, further comprising:

rank provision means for providing ranks, in descending order in the direction of travel, for transit points along a route;

rank storage means for, when said dynamic penalty function addition means initiates the propagation of said dynamic penalty function, storing the ranks at the foremost transit point from a transit point that has been propagated,

wherein, when a transit point has a rank value equal to or smaller than a value stored in said rank storage means, said dynamic penalty function validity determination means ascertains that a dynamic penalty function for said transit point is valid, and

wherein, when said original route is updated to a trial route, and when P0 and P3 denote transit points in the inverse direction of travel and in the forward direction of travel from a point on the updated route whereat a target route segment to be changed is inserted, said rank provision means provides intermediate ranks between the rank for P0 and the rank for P3 for the individual transit points in the descending order in the direction of travel along said target route segment to be changed on said updated route.

16. The route search system according to claim 15, wherein the inverse propagation, by the individual means, of said dynamic penalty function F, said dynamic earliest arrival time E, said dynamic latest arrival time L and said dynamic length W occurs simultaneously;

and wherein said dynamic penalty function validity determination means also serves as means for determining whether said dynamic earliest arrival time E, said dynamic latest arrival time L and said dynamic length W for each transit point are valid.

17. The route search system according to claim 16, further comprising:

a transit point pointer, for, when inverse propagation of said dynamic penalty function F, said dynamic earliest arrival time E, said dynamic latest arrival time L and said dynamic length W is employed, pointing at the foremost transit point from a transit point that has been inversely propagated,

wherein the contents of said transit point pointer are updated, so that said transit point pointer designates as the next transit point a transit point that, in the direction of travel, is adjacent to the last target route segment to be changed on the updated route, and

wherein inverse propagation is next employed for said dynamic penalty function F, said dynamic earliest arrival time E, said dynamic latest arrival time L and said dynamic length W, beginning at a transit point preceding the transit point pointed at by said transit point pointer.

18. The route search system according to claim 4, wherein changes effected for a route segment of a route include the movement and the deletion of a route segment and the insertion of said route segment into another predetermined location in another route.

19. A route search method comprising:

a dynamic penalty function addition step;

a route segment dynamic penalty function calculation step;

a route segment penalty cost calculation step;

a route evaluation step; and

a dynamic penalty function validity determination step,

wherein a static penalty function f, which is a cost function of an arrival time variable

t and is a base for calculation of a penalty cost, is set for each transit point, wherein said static penalty function f is so defined that said static penalty functions for

individual transit points are enabled to be added, wherein, among two routes to be compared, a reference route is called an original

route, and a route obtained by changing said original route is called a trial route, wherein an original route and a trial route are evaluated based on the total cost CT

that includes, for each route, at least a penalty cost CS and a length cost CL, wherein a dynamic penalty function F is correlated with each transit point.

20. The route search method according to claim 19,

wherein, at said dynamic penalty function addition step, said dynamic penalty function F is calculated for each transit point along said route, extending backward, in the direction opposite to that of normal propagation, from the last transit point P_z,

wherein, when an arbitrary transit point is called P1 and a succeeding transit point in the direction of travel is called P2, at said dynamic penalty function addition step, a dynamic penalty function F for P1 is calculated based on the sum of a static penalty function f for P1 and the dynamic penalty function F for P2, while, it should be noted, for the dynamic penalty function addition, a t in said dynamic penalty function F for P2 is defined as a t in said static penalty function f, to which a value equal to the difference between the arrival time for P2 and the arrival time for P1 is added.

21. The route search method according to claim 20,

wherein, when the first and last transit points along a target route segment to be changed on the original route are called P1 and P2 (P2=P1 may be established) and the succeeding transit point, following P2, along said original route in the direction of travel is called P3, and when it is determined at said dynamic penalty function validity determination step that the dynamic penalty functions for transit points following P1, along said original route, are valid, at said route segment dynamic penalty function calculation step, the dynamic penalty function F for said target route segment is calculated based on the results obtained by subtracting the dynamic penalty function F for P3 from the dynamic penalty function F for P1, while, it should be noted, a t in the dynamic penalty function for P3 is defined as said t in the dynamic penalty function for P1, to which the difference between the arrival time for P3 and the arrival time for P1 is added,

wherein, when the first transit points along said target route segments to be changed of said original route and a trial route are defined as P1, at said route segment penalty cost calculation step, penalty costs for said target route segments are calculated by substituting the arrival times at said transit points P1 along said original route and said trail route into arrival time variables t in said dynamic penalty functions of said route segments that are obtained at said route segment dynamic penalty function calculation step.

22. The route search method according to claim 21,

wherein, at said route evaluation step, said original route and said trial route are evaluated by comparison of said penalty costs for said target change route segments.

23. The route search method according to claim 22, wherein, when the succeeding transit points of the last target route segments to be changed on said original route and of said trial route in the direction of travel are defined as P3, and when route segments from the transit points P3 to Pz are called forward route segments, at said route segment penalty cost calculation step, the penalty costs for said forward route segments of said original route and of said trial route are calculated by substituting the arrival times at said transit points P3 along said original route and along said trial route into the arrival time variables t for the dynamic penalty functions for said transit points P3;

and wherein, at said route evaluation step, said original route and said trial route are evaluated based on the comparison of said penalty costs for said forward route segments of said original route and of said trial route.

24. The route search method according to claim 23, further comprising:

a time offset holding step,

wherein, as an arrival time, a time offset is employed that is represented by an offset, held at said time offset holding step, from a reference time Tb, and

wherein, when the total cost CT of said trial route is smaller than the total cost CT of said original route, and each time said original route is updated to a trial route, at said time offset holding step, said reference time Tb is updated based on a change L_reduce for the time re-calculation length of the updated route.

25. The route search method according to claim 24, further comprising:

a first arrival time offset calculation step, of calculating an arrival time offset a that, through inverse propagation initiated at said last transit point Pz, is set for each transit point along a route,

wherein, when an arbitrary transit point is defined as P1 and an immediately succeeding transit point in the direction of travel is defined as P2, at said first arrival time offset calculation step, an arrival time offset a_P1 for said transit point P1 is calculated based on the results obtained by subtracting from an arrival time offset a_P2 for said transit point P2, the sum of the time d(P1, P2) for the travel between P1 and P2, and a working time w_P1 for said transit point P1, and

wherein an arrival time that is to be used at said dynamic penalty function addition step for calculating an arrival time difference is said arrival time offset a, which is obtained at said first arrival time offset calculation step.

26. The route search method according to claim 25, further comprising:

a second arrival time offset calculation step,

wherein it is ascertained that the arrival time offset a is changed at all the transit points along said trial route from a point whereat a target route segment to be changed is inserted or extracted,

wherein the preceding transit point along the first target route segment to be changed on said original route in the direction of travel is defined as P0,

wherein, at said second arrival time offset calculation step, an arrival time offset a_i at a transit point i is calculated using an arrival time offset a_P0 at P0 along a trial route in the direction of travel,

wherein, when an arbitrary transit point is defined as P1 and an immediately succeeding transit point in the direction of travel is defined as P2, at said second arrival time offset calculation step, an arrival time offset a_P2 at said transit point P2 is calculated based on the results obtained by adding an arrival time offset a_P1, at said transit point P1, to the sum of a working time w_P1 for P1, and time d(P1, P2) for the travel between P1 and P2.

27. The route search method according to claim 26,

wherein, at said route segment penalty cost calculation step, an arrival time, which is to be substituted into t in the dynamic penalty function for said route segment obtained at said route segment dynamic penalty function calculation step, is determined as the time obtained by adding said reference time Tb to said arrival time offset a, that is obtained at said second arrival time offset calculation step for the first transit point along said route segment.

28. The route search method according to claim 27, further comprising:

a first dynamic earliest arrival time calculation step of calculating, through inverse propagation originating at the last transit point Pz, a dynamic earliest arrival time E that is correlated with a static earliest arrival time e that is set for each transit point along a route to inhibit an arrival earlier than said static earliest arrival time e,

wherein, when an arbitrary transit point is defined as P1 and the immediately succeeding transit point in the direction of travel is defined as P2, at said first dynamic earliest arrival time calculation step, which is the later time, either a static earliest arrival time e_P1 for P1, or the value obtained by subtracting from a dynamic earliest arrival time E_P2 for P2, the sum of a work time w_P1 for P1 and a time d(P1, P2) for the travel between P1 and P2, is determined as said dynamic earliest arrival time E for P1, and

wherein, when the time obtained by adding said reference time Tb to said arrival time offset a, which is obtained for said forward route segment of said trial route at said first arrival time offset calculation step, is earlier than said dynamic earliest arrival time E for said forward route segment, which is obtained at said first dynamic earliest arrival time calculation step, the calculation of a penalty cost for said forward route segment of said trial route is halted at said penalty cost calculation step.

29. The route search method according to claim 28, further comprising:

a second dynamic earliest arrival time calculation step of calculating the dynamic earliest arrival time E for a target route segment to be changed,

wherein, when the first and the last transit points along said target route segment to be changed are called P1 and P2 (P2=P1 may be established), at said second dynamic earliest arrival time calculation step, a later time, either the static earliest arrival time e_P1 for P1, or a value obtained by subtracting, from the static earliest arrival time e_P2 for P2, the difference between a_P2 and a_P1, which are arrival time offsets for P2 and P1 obtained at said first arrival time offset calculation step, is determined as said dynamic earliest arrival time E for said target route segment to be changed, and

wherein, when the time value obtained by adding said reference time Tb to the arrival time offset a, which is calculated at said first or second arrival time offset calculation step for said target route segment to be changed on said trial route, precedes said dynamic earliest arrival time E for said target route segment to be changed that is obtained at said second dynamic earliest arrival time calculation step, the calculation of the penalty cost for said target route segment to be changed on said trial route is halted at said penalty cost calculation step.

30. The route search method according to claim 29, further comprising:

a first dynamic latest arrival time calculation step of calculating, through inverse propagation originating at the last transit point Pz, a dynamic latest arrival time L that is correlated with a static latest arrival time 1 that is set for each transit point along a route to inhibit an arrival later than said static latest arrival time 1,

wherein, when an arbitrary transit point is defined as P1 and the immediately succeeding transit point in the direction of travel is defined as P2, at said first dynamic latest arrival time calculation step, an earlier time, either a static latest arrival time l_P1 for P1, or the value obtained by subtracting from a dynamic latest arrival time L_P2 for P2, the sum of a work time w_P1 for P1 and a time d(P1, P2) for the travel between P1 and P2, is determined as said dynamic latest arrival time L for P1, and

wherein, when the time obtained by adding said reference time Tb to said arrival time offset a, which is obtained for said forward route segment of said trial route at said first arrival time offset calculation step, is later than said dynamic latest arrival time L for said forward route segment, which is obtained at said first dynamic latest arrival time calculation step, the calculation of a penalty cost for said forward route segment of said trial route is halted at said penalty cost calculation step.

31. The route search method according to claim 30, further comprising:

a second dynamic latest arrival time calculation step, of calculating the dynamic latest arrival time L for a target route segment to be changed,

wherein, when the first and the last transit points along said target route segment to be changed are called P1 and P2 (P2=P1 may be established), at said second dynamic latest arrival time calculation step, which is the earlier time, the static latest arrival time l_P1 for P1, or a value obtained by subtracting from the static latest arrival time l_P2 for P2, the difference between a_P2 and a_P1, which are arrival time offsets for P2 and P1 obtained at said first arrival time offset calculation step, is determined as said dynamic latest arrival time L for said target route segment to be changed, and

wherein, when the time value obtained by adding said reference time Tb to the arrival time offset a, which is calculated at said first or second arrival time offset calculation step for said target route segment to be changed on said trial route, precedes said dynamic latest arrival time L for said target route segment to be changed that is obtained at said second dynamic latest arrival time calculation step, the calculation of the penalty cost for said target route segment to be changed on said trial route is halted at said penalty cost calculation step.

32. The route search method according to claim 31, further comprising:

a first dynamic length calculation step of calculating a dynamic length W, which is correlated with each transit point along a route, through inverse propagation originating at the last transit point Pz;

an arrival time offset validity determination step; and

a second dynamic length calculation step,

wherein, when an arbitrary transit point is defined as P1 and the immediately succeeding transit point in the direction of travel is defined as P2, at said first dynamic length calculation step, a value based on the results obtained by adding a dynamic length W_P2 for P2, to the sum of the travel time between P1 and P2 and a working time for P1, is determined as a dynamic length W_P1 for P1,

wherein, when it is ascertained at said arrival time offset validity determination step that arrival time offsets for transit points following P1 along the original route are valid, and when the first and last transit points along said target route segment to be changed are called P1 and P2 (P2=P1 may be established) and the succeeding transit point, following P2, along the original route in the direction of travel is called P3, at said second dynamic length calculation step, said dynamic length W for said target route segment is obtained by subtracting from a dynamic length W_P1 for P1, the sum of a dynamic length W_P3 for P3, and the travel time between P2 and P3.

33. The route search method according to claim 32,

wherein, when a dynamic length for said target route segment obtained at said second dynamic length calculation step is defined as W, at said second arrival time offset calculation step, an arrival time offset of a_P3 for P3 is calculated based on the results obtained by adding an arrival time offset a_P1 for P1, to the sum of said dynamic length W and the travel time between P2 and P3.

34. The route search method according to claim 33, further comprising:

a rank provision step of providing ranks, in descending order in the direction of travel, for transit points along a route;

a rank storage step of, when the propagation of said dynamic penalty function is initiated at said dynamic penalty function addition step, storing the ranks at the foremost transit point from a transit point that has been propagated,

wherein, when a transit point has a rank value equal to or smaller than a value stored at said rank storage step, it is ascertained at said dynamic penalty function validity determination step that a dynamic penalty function for said transit point is valid, and

wherein, when said original route is updated to a trial route, and when P0 and P3 denote transit points in the inverse direction of travel and in the forward direction of travel from a point on the updated route whereat a target route segment to be changed is inserted, at said rank provision step, intermediate ranks between the rank for P0 and the rank for P3 are provided for the individual transit points in the descending order in the direction of travel along said target route segment to be changed on said updated route.

35. The route search method according to claim 34, wherein the inverse propagation, at the individual steps, of said dynamic penalty function F, said dynamic earliest arrival time E, said dynamic latest arrival time L and said dynamic length W occurs simultaneously;

and wherein said dynamic penalty function validity determination step also serves as a step of determining whether said dynamic earliest arrival time E, said dynamic latest arrival time L and said dynamic length W for each transit point are valid.

36. The route search method according to claim 35, further comprising:

a transit point pointer setting step of, when inverse propagation of said dynamic penalty function F, said dynamic earliest arrival time E, said dynamic latest arrival time L and said dynamic length W is employed, setting a transit pointer at the foremost transit point from a transit point that has been inversely propagated,

wherein the contents of said transit point pointer are updated, so that said transit point pointer designates as the next transit point a transit point that, in the direction of travel, is adjacent to the last target route segment to be changed on the updated route, and

wherein inverse propagation is next employed for said dynamic penalty function F, said dynamic earliest arrival time E, said dynamic latest arrival time L and said dynamic length W, beginning at a transit point preceding the transit point pointed at by said transit point pointer.

37. The route search method according to claim 22, wherein changes effected for a route segment of a route includes the movement and the deletion of a route segment and the insertion of said route segment into another predetermined location in another route.