Generating optimal itineraries based on network connectivity

• US 9,109,897 B2
• Filed: 01/02/2013
• Issued: 08/18/2015
• Est. Priority Date: 12/17/2008
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bauchot, Frederic, Dispensa, Jean-Claude, Drouet, Francois-Xavier, Marmigere, Gerard
• Primary Examiner(s): Kiswanto, Nicholas
• Application Number:
  US13/732,457
• Publication Number:
  US 20130124086A1
• Time in Patent Office: 958 Days
• Field of Search: 701/408
• US Class Current: 1/1
• 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: G01C 21/3461 Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types, segments such as motorways, toll roads, ferries
• CPC Class Codes: G01C 21/3867 Geometry of map features, e.g. shape points, polygons or for simplified maps

Abstract

An approach for generating optimal itineraries based on network connectivity is presented. A computer receives a first message from which a current position of a vehicle on a trip, destination, a service being requested for a mobile device in the vehicle, service providers and network(s) are extracted. Network connectivity measures are retrieved and signal qualities in respective cells are determined based on the network connectivity measures. Based on the signal qualities, an itinerary is determined as paths and a hop indicating a position on one of the paths at which a connectivity change from a first to a second service provider is to occur. A response to the first message indicates the itinerary. Sending the response results in the mobile device making the connectivity change when the vehicle reaches the position indicated by the hop.

Claims

1. A computer system comprising:

a central processing unit (CPU);

a memory coupled to the CPU; and

a computer-readable, tangible storage device coupled to the CPU, the storage device containing instructions that when carried out by the CPU via the memory implement a method of generating optimal itineraries, the method comprising the steps of;

the computer system receiving a first message from a global positioning device that determines a geographic position of a vehicle on a trip, wherein the computer system is remote from the vehicle, and wherein the first message indicates the geographic position of the vehicle, a destination of the trip, a service requested for a mobile device being transported by the vehicle, a plurality of service providers that provide the service, and one or more networks via which the plurality of service providers provide the service to the mobile device;

the computer system determining a first cell in which the service to the mobile device is provided by the plurality of service providers;

for each respective cell of a first plurality of cells adjacent to the first cell, the computer system retrieving a first plurality of measures of network connectivity, each measure of network connectivity included in the first plurality of measures of network connectivity indicating a respective signal quality provided by a respective service provider of the plurality of service providers to any mobile device in the respective cell;

the computer system determining a first measure of network connectivity of the retrieved first plurality of measures of network connectivity indicates a first signal quality provided by a first service provider to any mobile device in a second cell, the first service provider included in the plurality of service providers and the second cell included in the first plurality of cells adjacent to the first cell;

the computer system determining the first signal quality provided by the first service provider to the any mobile device in the second cell is not exceeded by any other signal quality indicated by any other measure of network connectivity of the retrieved first plurality of measures of network connectivity;

based on the first signal quality provided by the first service provider to the any mobile device in the second cell not being exceeded by the any other signal quality indicated by the any other measure of network connectivity of the retrieved first plurality of measures of network connectivity, the computer system identifying the first service provider within the plurality of service providers and selecting the second cell from the first plurality of cells adjacent to the first cell;

the computer system determining a first path within the selected second cell;

subsequent to the step of selecting the second cell and for each respective cell of a second plurality of cells adjacent to the second cell, the computer system retrieving a second plurality of measures of network connectivity, each measure of network connectivity included in the second plurality of measures of network connectivity indicating a respective signal quality provided by a respective service provider of the plurality of service providers to any mobile device in the respective cell of the second plurality of cells;

the computer system determining a second measure of network connectivity of the retrieved second plurality of measures of network connectivity indicates a second signal quality provided by a second service provider to any mobile device in a third cell, the second service provider included in the plurality of service providers and the third cell included in the second plurality of cells adjacent to the second cell;

the computer system determining the second signal quality provided by the second service provider to the any mobile device in the third cell is not exceeded by any other signal quality indicated by any other measure of network connectivity of the retrieved second plurality of measures of network connectivity;

based on the second signal quality provided by the second service provider to the any mobile device in the third cell not being exceeded by the any other signal quality indicated by the any other measure of network connectivity of the retrieved second plurality of measures of network connectivity, the computer system identifying the second service provider within the plurality of service providers and selecting the third cell from the second plurality of cells adjacent to the second cell;

the computer system determining a second path within the selected third cell;

in part based on the first signal quality provided by the first service provider to the any mobile device in the second cell not being exceeded by the any other signal quality indicated by the any other measure of network connectivity of the retrieved first plurality of measures of network connectivity and in part based on the second signal quality provided by the second service provider to the any mobile device in the third cell not being exceeded by the any other signal quality indicated by the any other measure of network connectivity of the retrieved second plurality of measures of network connectivity, the computer system determining an itinerary for the trip as a plurality of paths including a sequence of the first path followed by the second path, and as one or more hops including a hop indicating a position on the first path—

at which a connectivity change is to occur from the first service provider providing the service to the mobile device to the second service provider providing the service to the mobile device; and

the computer system sending a second message as a response to the first message, wherein the second message indicates the itinerary, wherein a result of the step of sending the second message and the vehicle reaching the position indicated by the hop is the mobile device making the connectivity change.

2. The computer system of claim 1, wherein the step of receiving the first message includes the computer system receiving a time window during which the service is requested to be provided to the mobile device, wherein the step of identifying the first service provider within the plurality of service providers includes the computer system determining the first service provider provides the service within the time window, wherein the step of identifying the second service provider within the plurality of service providers includes the computer system determining the second service provider provides the service within the time window, and wherein the time window indicates a period of time during which the service is required by the mobile device.

3. The computer system of claim 1, wherein the step of receiving the first message includes the computer system receiving a cost requirement of the service, wherein the step of identifying the first service provider within the plurality of service providers includes the computer system determining a first cost of the first service provider providing the service does not exceed the cost requirement, wherein the step of identifying the second service provider within the plurality of service providers includes the computer system determining a second cost of the second service provider providing the service does not exceed the cost requirement, and wherein the cost requirement indicates a maximum cost of providing the service to the mobile device.

4. The computer system of claim 1, wherein the method further comprises:

the computer system determining a plurality of itineraries from the geographic position of the vehicle to the destination of the trip, the plurality of itineraries including the itinerary and a second itinerary, the second itinerary based on a shortest distance from the geographic position of the vehicle to the destination of the trip, wherein the itinerary is different from the second itinerary;

the computer system initiating a display of the plurality of itineraries on a display device being transported by the vehicle, each displayed itinerary including a respective plurality of paths, a respective one or more hops indicating one or more positions at which one or more connectivity changes are to occur, a respective one or more service providers that are to provide the service, and a respective one or more networks via which the service is to be provided by the respective one or more service providers; and

the computer system receiving a selection by a user of one itinerary from the displayed plurality of itineraries.

5. The computer system of claim 1, wherein the vehicle is a mode of conveyance by which a person travels, and wherein the mode of conveyance is selected from the group consisting of a motor-driven conveyance, a rail transport conveyance, a watercraft, an aircraft, an animal-powered mode of transportation, and a human-powered mode of transportation.

6. The computer system of claim 1, wherein the first message conforms to a communications protocol, wherein the computer system is configured with a connection stack that defines the communications protocol, and wherein the method further comprises the computer system extracting from the first message the geographic position of the vehicle, the destination of the trip, the service, the service provider, and the one or more networks by applying the communications protocol to the first message.

7. A computer program product, comprising:

a computer-readable, tangible storage device; and

a computer-readable program code stored on the computer-readable, tangible storage device, said computer-readable program code containing instructions that, when executed by a processor of a computer system, implement a method of generating optimal itineraries, said method comprising the steps of;

the computer system receiving a first message from a global positioning device that determines a geographic position of a vehicle on a trip, wherein the computer system is remote from the vehicle, and wherein the first message indicates the geographic position of the vehicle, a destination of the trip, a service requested for a mobile device being transported by the vehicle, a plurality of service providers that provide the service, and one or more networks via which the plurality of service providers provide the service to the mobile device;

the computer system determining a first cell in which the service to the mobile device is provided by the plurality of service providers;

for each respective cell of a first plurality of cells adjacent to the first cell, the computer system retrieving a first plurality of measures of network connectivity, each measure of network connectivity included in the first plurality of measures of network connectivity indicating a respective signal quality provided by a respective service provider of the plurality of service providers to any mobile device in the respective cell;

the computer system determining a first measure of network connectivity of the retrieved first plurality of measures of network connectivity indicates a first signal quality provided by a first service provider to any mobile device in a second cell, the first service provider included in the plurality of service providers and the second cell included in the first plurality of cells adjacent to the first cell;

the computer system determining the first signal quality provided by the first service provider to the any mobile device in the second cell is not exceeded by any other signal quality indicated by any other measure of network connectivity of the retrieved first plurality of measures of network connectivity;

based on the first signal quality provided by the first service provider to the any mobile device in the second cell not being exceeded by the any other signal quality indicated by the any other measure of network connectivity of the retrieved first plurality of measures of network connectivity, the computer system identifying the first service provider within the plurality of service providers and selecting the second cell from the first plurality of cells adjacent to the first cell;

the computer system determining a first path within the selected second cell;

subsequent to the step of selecting the second cell and for each respective cell of a second plurality of cells adjacent to the second cell, the computer system retrieving a second plurality of measures of network connectivity, each measure of network connectivity included in the second plurality of measures of network connectivity indicating a respective signal quality provided by a respective service provider of the plurality of service providers to any mobile device in the respective cell of the second plurality of cells;

the computer system determining a second measure of network connectivity of the retrieved second plurality of measures of network connectivity indicates a second signal quality provided by a second service provider to any mobile device in a third cell, the second service provider included in the plurality of service providers and the third cell included in the second plurality of cells adjacent to the second cell;

the computer system determining the second signal quality provided by the second service provider to the any mobile device in the third cell is not exceeded by any other signal quality indicated by any other measure of network connectivity of the retrieved second plurality of measures of network connectivity;

based on the second signal quality provided by the second service provider to the any mobile device in the third cell not being exceeded by the any other signal quality indicated by the any other measure of network connectivity of the retrieved second plurality of measures of network connectivity, the computer system identifying the second service provider within the plurality of service providers and selecting the third cell from the second plurality of cells adjacent to the second cell;

the computer system determining a second path within the selected third cell;

in part based on the first signal quality provided by the first service provider to the any mobile device in the second cell not being exceeded by the any other signal quality indicated by the any other measure of network connectivity of the retrieved first plurality of measures of network connectivity and in part based on the second signal quality provided by the second service provider to the any mobile device in the third cell not being exceeded by the any other signal quality indicated by the any other measure of network connectivity of the retrieved second plurality of measures of network connectivity, the computer system determining an itinerary for the trip as a plurality of paths including a sequence of the first path followed by the second path, and as one or more hops including a hop indicating a position on the first path—

at which a connectivity change is to occur from the first service provider providing the service to the mobile device to the second service provider providing the service to the mobile device; and

the computer system sending a second message as a response to the first message, wherein the second message indicates the itinerary, wherein a result of the step of sending the second message and the vehicle reaching the position indicated by the hop is the mobile device making the connectivity change.

8. The program product of claim 7, wherein the step of receiving the first message includes the computer system receiving a time window during which the service is requested to be provided to the mobile device, wherein the step of identifying the first service provider within the plurality of service providers includes the computer system determining the first service provider provides the service within the time window, wherein the step of identifying the second service provider within the plurality of service providers includes the computer system determining the second service provider provides the service within the time window, and wherein the time window indicates a period of time during which the service is required by the mobile device.

9. The program product of claim 7, wherein the step of receiving the first message includes the computer system receiving a cost requirement of the service, wherein the step of identifying the first service provider within the plurality of service providers includes the computer system determining a first cost of the first service provider providing the service does not exceed the cost requirement, wherein the step of identifying the second service provider within the plurality of service providers includes the computer system determining a second cost of the second service provider providing the service does not exceed the cost requirement, and wherein the cost requirement indicates a maximum cost of providing the service to the mobile device.

10. The program product of claim 7, wherein the method further comprises:

the computer system determining a plurality of itineraries from the geographic position of the vehicle to the destination of the trip, the plurality of itineraries including the itinerary and a second itinerary, the second itinerary based on a shortest distance from the geographic position of the vehicle to the destination of the trip, wherein the itinerary is different from the second itinerary;

the computer system initiating a display of the plurality of itineraries on a display device being transported by the vehicle, each displayed itinerary including a respective plurality of paths, a respective one or more hops indicating one or more positions at which one or more connectivity changes are to occur, a respective one or more service providers that are to provide the service, and a respective one or more networks via which the service is to be provided by the respective one or more service providers; and

the computer system receiving a selection by a user of one itinerary from the displayed plurality of itineraries.

11. The program product of claim 7, wherein the vehicle is a mode of conveyance by which a person travels, and wherein the mode of conveyance is selected from the group consisting of a motor-driven conveyance, a rail transport conveyance, a watercraft, an aircraft, an animal-powered mode of transportation, and a human-powered mode of transportation.

12. The program product of claim 7, wherein the first message conforms to a communications protocol, wherein the computer system is configured with a connection stack that defines the communications protocol, and wherein the method further comprises the computer system extracting from the first message the geographic position of the vehicle, the destination of the trip, the service, the service provider, and the one or more networks by applying the communications protocol to the first message.