Routing method and system

• US 7,869,936 B2
• Filed: 07/09/2007
• Issued: 01/11/2011
• Est. Priority Date: 07/11/2006
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gargaro, Gianluca, Martino, Marco, Trinchini, Patrizio, Donatelli, Alessandro
• Primary Examiner(s): Hellner; Mark
• Assistant Examiner(s): Diacou; Ari M.
• Application Number:
  US11/774,770
• Publication Number:
  US 20080015774A1
• Time in Patent Office: 1,282 Days
• Field of Search: 701200-226, 701117-119, 340988-996
• US Class Current: 701/118
• CPC Class Codes: G01C 21/28 with correlation of data from several navigational instruments

Abstract

A method of route determination for mobile elements in a network comprising a plurality of paths each having a predetermined path capacity. The method comprises the steps of registering centrally a plurality of route requests from a corresponding plurality of mobile elements each of said requests defining a journey between an origin and a destination and registering centrally for each route request a journey start time. Routing instructions are centrally determined so as to optimise use of path capacity across all synchronous journeys requests in said network with reference to said registered information, and issued to corresponding mobile elements. The mobile elements adapt their route to comply with the routing instruction. There may be provided further steps of monitoring and rerouting the mobile element whenever new journeys requests can impact its remaining trip.

Claims

1. A method of route determination for mobile elements in a network comprising a plurality of paths each path having a predetermined path capacity, said method comprising:

registering centrally a plurality of route requests from a corresponding plurality of mobile elements each of said requests defining a journey between an origin and a destination;

registering centrally for each route request a journey start time; and

performing, for a first journey in said journeys, further steps of

centrally determining a routing instruction for a first part of the first journey, the routing instruction being sufficient to enable a corresponding mobile element to begin the first part of the first journey,

issuing said routing instruction to the corresponding first mobile element, and

said first mobile element adapting its route to comply with said routing instruction;

computing a second routing instruction for a second part of the first journey such that the second routing instruction causes the first mobile element to use a path in the network,

transmitting the second routing instruction to the first mobile element,

computing whether a second journey by a corresponding second mobile element coincides with the second part of the first journey over the path during a time period common to the first and second journeys,

evaluating, responsive to the computing being affirmative, that the coincidence of the first and the second journeys causes the times for traversing the path to increase for the first and the second mobile elements,

selecting the first journey for rerouting by comparing an effects of rerouting on the first and second journeys,

recomputing the second routing instruction to cause the first mobile element to utilize a second path,

issuing the recomputed second routing instruction to the first mobile element while the first mobile element is in transit on the first part of the first journey, and

the first mobile element adapting its route to comply with the recomputed second routing instruction, thereby allowing optimal use of the path to the second mobile element.

2. The method of claim 1 further comprising,

repeating for the plurality of mobile elements said steps of registering, and performing upon receiving successive further route requests from the plurality of mobile elements;

and

recomputing an issued routing instruction issued to a third mobile element whose third journey will traverse the path, and thereby maintain optimal use of path capacity.

3. The method of claim 1, wherein said step of selecting further takes into account a record of situations when a journey had been modified disadvantageously for a particular mobile element.

4. The method of claim 1, wherein said step of selecting further takes into account the urgency of a journey as asserted by a particular mobile element.

5. The method claim 1, wherein said step of selecting further takes into account how far in advance a particular mobile element notified the system of a proposed journey, how regularly the particular mobile element uses the system, or on payment of a premium for special treatment.

6. A computer readable storage medium including a computer program product comprising instructions for carrying out the steps of a method of route determination for mobile elements in a network comprising a plurality of paths each path having a predetermined path capacity when said computer program is executed on a computer, the method comprising:

registering centrally a plurality of route requests from a corresponding plurality of mobile elements each of said requests defining a journey between an origin and a destination;

registering centrally for each route request a journey start time; and

performing, for a first journey in said journeys, further steps of

centrally determining a routing instruction for a first part of the first journey, the routing instruction being sufficient to enable a corresponding mobile element to begin the first part of the first journey,

issuing said routing instruction to the corresponding first mobile element, and

said first mobile element adapting its route to comply with said routing instruction;

computing a second routing instruction for a second part of the first journey such that the second routing instruction causes the first mobile element to use a path in the network,

transmitting the second routing instruction to the first mobile element,

computing whether a second journey by a corresponding second mobile element coincides with the second part of the first journey over the path during a time period common to the first and second journeys,

evaluating, responsive to the computing being affirmative, that the coincidence of the first and the second journeys causes the times for traversing the path to increase for the first and the second mobile elements,

selecting the first journey for rerouting by comparing an effects of rerouting on the first and second journeys,

recomputing the second routing instruction to cause the first mobile element to utilize a second path,

issuing the recomputed second routing instruction to the first mobile element while the first mobile element is in transit on the first part of the first journey, and

the first mobile element adapting its route to comply with the recomputed second routing instruction, thereby allowing optimal use of the path to the second mobile element.

7. The computer program product of claim 6, wherein the method further comprising,

repeating for the plurality of mobile elements said steps of registering and performing upon receiving successive further route requests from the plurality of mobile elements;

and

recomputing an issued routing instruction issued to a third mobile element whose third journey will traverse the path, and thereby maintain optimal use of path capacity.

8. The computer program product of claim 6, wherein said step of selecting further takes into account a record of situations when a journey had been modified disadvantageously for a particular mobile element.

9. The computer program product of claim 6, wherein said step of selecting further takes into account the urgency of a journey as asserted by a particular mobile element.

10. The computer program product of claim 6, wherein said step of selecting further takes into account how far in advance a particular mobile element notified the system of a proposed journey, how regularly the particular mobile element use the system, or on payment of a premium for special treatment.

11. A system for route determination for mobile elements in a network comprising a plurality of paths each path having a predetermined path capacity, comprising:

a storage device including a storage medium, wherein the storage device stores computer usable program code; and

a processor, wherein the processor executes the computer usable program code, and wherein the computer usable program code comprises;

computer usable code for registering centrally a plurality of route requests from a corresponding plurality of mobile elements each of said requests defining a journey between an origin and a destination;

computer usable code for registering centrally for each route request a journey start time; and

computer usable code for performing, for a first journey in said journeys, further including

computer usable code for centrally determining a routing instruction for a first part of the first journey, the routing instruction being sufficient to enable a corresponding mobile element to begin the first part of the first journey,

computer usable code for issuing said routing instruction to the corresponding first mobile element, and

said first mobile element adapting its route to comply with said routing instruction;

computer usable code for computing a second routing instruction for a second part of the first journey such that the second routing instruction causes the first mobile element to use a path in the network,

computer usable code for transmitting the second routing instruction to the first mobile element,

computer usable code for computing whether a second journey by a corresponding second mobile element coincides with the second part of the first journey over the path during a time period common to the first and second journeys,

computer usable code for evaluating, responsive to the computing being affirmative, that the coincidence of the first and the second journeys causes the times for traversing the path to increase for the first and the second mobile elements, computer usable code for selecting the first journey for rerouting by comparing an effects of rerouting on the first and second journeys,

computer usable code for recomputing the second routing instruction to cause the first mobile element to utilize a second path,

computer usable code for issuing the recomputed second routing instruction to the first mobile element while the first mobile element is in transit on the first part of the first journey, and

the first mobile element adapting its route to comply with the recomputed second routing instruction, thereby allowing optimal use of the path to the second mobile element.

12. The system of claim 11, further comprising,

computer usable code for repeating for the plurality of mobile elements said steps of registering and performing upon receiving successive further route requests from the plurality of mobile elements;

and

computer usable code for recomputing an issued routing instruction issued to a third mobile element whose third journey will traverse the path, and thereby maintain optimal use of path capacity.

13. The system of claim 11, wherein the computer usable code for selecting further takes into account a record of situations when a journey had been modified disadvantageously for a particular mobile element.

14. The system of claim 11, wherein the computer usable code for selecting further takes into account the urgency of a journey as asserted by a particular mobile element.

15. The system of claim 11, wherein the computer usable code for selecting further takes into account how far in advance a particular mobile element notified the system of a proposed journey, how regularly the particular mobile element use the system, or on payment of a premium for special treatment.