GEOGRAPHIC ROUTING ENGINE
A server within an on-demand computing services environment may receive a request to determine a route that involves a set of geographic locations. The server may identify pre-computed path information suitable for responding to the request. A route may be determined based on the identified information, and route information may be transmitted in response to the request.
1 . A method comprising:
receiving a route optimization request message at a server within an on-demand computing services environment, the route optimization request message identifying a first plurality of geographic locations and a designated time period associated with a routing request from a client entity;
identifying via a processor one or more of a plurality of time windows based on the route optimization request message, the identified one or more time windows collectively encompassing the designated time period;
retrieving route optimization information for each of the identified time windows, the route optimization information identifying transit information between each of a plurality of pairs of a second plurality of geographic locations during the identified time windows;
determining a route to traverse the first plurality of geographic locations within the designated time period based on the retrieved route optimization information; and
transmitting, via a communication interface, a response message identifying the route to a client machine associated with the client entity.
2 . The method recited in claim 1 , wherein the identified one or more time windows include two overlapping time windows.
3 . The method recited in claim 1 , wherein the identified one or more time windows include the smallest set of the plurality of time windows that collectively encompass the designated time period.
4 . The method recited in claim 1 , wherein each time window corresponds to a portion of a day.
5 . The method recited in claim 1 , wherein the transit information identifies a first plurality of transit time values, each transit time value identifying a respective transit time between two or more of the second plurality of geographic locations.
6 . The method recited in claim 5 , wherein determining the route to traverse the first plurality of geographic locations involves determining a second plurality of transit time values by interpolating from two or more of the first plurality of transit time values.
7 . The method recited in claim 6 , wherein the route optimization information is retrieved from a zone server configured to determine the transit information for the geographic zone based on one or more observed travel time values.
8 . The method recited in claim 6 , wherein each of the first plurality of transit time values is stored in a shortest path matrix computed by the zone server.
9 . The method recited in claim 1 , wherein the on-demand computing services environment is configured to provide computing services to a plurality of clients via a network, the plurality of clients including the client entity.
10 . A server within an on-demand computing services environment, the server configured to perform a method, the method comprising:
receiving a route optimization request message, the route optimization request message identifying a first plurality of geographic locations and a designated time period associated with a routing request from a client entity;
identifying via a processor one or more of a plurality of time windows based on the route optimization request message, the identified one or more time windows collectively encompassing the designated time period;
retrieving route optimization information for each of the identified time windows, the route optimization information identifying transit information between each of a plurality of pairs of a second plurality of geographic locations during the identified time windows;
determining a route to traverse the first plurality of geographic locations within the designated time period based on the retrieved route optimization information; and
transmitting, via a communication interface, a response message identifying the route to a client machine associated with the client entity.
11 . The server recited in claim 10 , wherein the identified one or more time windows include two overlapping time windows.
12 . The server recited in claim 10 , wherein the identified one or more time windows include the smallest set of the plurality of time windows that collectively encompass the designated time period.
13 . The server recited in claim 10 , wherein each time window corresponds to a portion of a day.
14 . The server recited in claim 10 , wherein the transit information identifies a first plurality of transit time values, each transit time value identifying a respective transit time between two or more of the second plurality of geographic locations.
15 . The server recited in claim 14 , wherein determining the route to traverse the first plurality of geographic locations involves determining a second plurality of transit time values by interpolating from two or more of the first plurality of transit time values.
16 . One or more machine-readable media having instructions stored thereon for performing a method, the method comprising:
receiving a route optimization request message, the route optimization request message identifying a first plurality of geographic locations and a designated time period associated with a routing request from a client entity;
identifying via a processor one or more of a plurality of time windows based on the route optimization request message, the identified one or more time windows collectively encompassing the designated time period;
retrieving route optimization information for each of the identified time windows, the route optimization information identifying transit information between each of a plurality of pairs of a second plurality of geographic locations during the identified time windows;
determining a route to traverse the first plurality of geographic locations within the designated time period based on the retrieved route optimization information; and pg, 70
transmitting, via a communication interface, a response message identifying the route to a client machine associated with the client entity.
17 . The one or more machine-readable media recited in claim 16 , wherein the identified one or more time windows include two overlapping time windows.
18 . The one or more machine-readable media recited in claim 16 , wherein the identified one or more time windows include the smallest set of the plurality of time windows that collectively encompass the designated time period.
19 . The one or more machine-readable media recited in claim 16 , wherein each time window corresponds to a portion of a day.
20 . The one or more machine-readable media recited in claim 10 , wherein the transit information identifies a first plurality of transit time values, each transit time value identifying a respective transit time between two or more of the second plurality of geographic locations.