14.1 Routing

Routes are computed between location elements.

There are three types of location elements: <start_location>, <location> (intermediate locations or waypoints), and <end_location>. A location element can be specified as an address that is geocoded; as a pre-geocoded address, edge id/percentage pair; or as a latitude/longitude pair that is reverse geocoded.

The routing engine can incorporate a start time in its computations. For example, in an urban area, the estimated total driving time from your home to the airport on a weekday can be very different if you start at 8 am as opposed to 7 pm. The time computations are based on historical traffic pattern data, not on any real-time data gathering (for example, they do not factor in any current accidents or severe weather).

To include this optional feature, in the route request specify start_time and optionally start_date values, set return_route_time to true (that is, include the total estimated route time in the response), and make time zone user data available. If return_route_time is true but a start time is not specified, it is assumed to be when the route request is issued. (The relevant attributes are explained in Routing Engine XML API.)

This optional feature does not apply to batched route requests and batch mode requests.

• Simple Route Request
  
• Simple Multi-address Route Request
  
• Traveling Salesperson (TSP) Route Request
  
• Batched Route Request
  
• Batch Mode Route Request
  
• Relationship between Routing Engine and Geocoder
  

14.1.1 Simple Route Request

Simple route requests must contain both a <start_location> and <end_location> element. The response for a simple route request is a single route from the start location to the end location.

Several attributes in a simple route request control how the route is computed and what is returned in the route response. These attributes are discussed in Routing Engine XML API.

14.1.2 Simple Multi-address Route Request

Simple multi-address route requests must contain at least three locations, including a required <start_location> element. Multi-address route requests must also contain one or more <location> elements, and optionally an <end_location> element.

The result of a simple multi-address route request is a single route from the start location, through each intermediate location, to the end location. This single route consists of multiple subroutes. Subroutes are the routes between each of the individual locations.

In a simple multi-address route request, the optimize_route attribute must be absent or set to FALSE. In simple multi-address route requests, all locations are fixed. There is no attempt to optimize the order in which the locations are visited. The locations in the route are visited in the order in which they were specified in the request.

Simple multi-address route requests use the route_type attribute to classify the route as an open or closed tour:

• Open tour: The route ends at the final intermediate location or a specified end location.

• Closed tour: The route returns to the start location.

  If a simple multi-address closed tour route is requested, the <start_location> element specification also used as the end location during route computation. If an <end_location> element is specified in a simple multi-address closed tour route request, an error is returned.

Example: Simple Multi-address Open Tour Route Request

Assume you want to drive from your workplace to customer A, then to customer B, and then to customer C.

• The route request has your workplace as the start location, customers A and B as intermediate locations, and customer C as the end location.

• The returned route has three subroutes: (1) workplace to customer A, (2) customer A to customer B, and (3) customer B to customer C.

• Each subroute probably has multiple segments, each one associated with a specific driving direction step.

Example: Simple Multi-address Closed Tour Route Request

Assume you want to drive from your workplace to customer A, then to customer B, then to customer C, and then back to your workplace.

• The route request has your workplace as the start location, and customers A, B, and C as intermediate locations. Your workplace is also used as the end location. An <end_location> element .should not be specified in the route request. The routing engine adds the subroute from customer C to the workplace automatically when it sees a request for a closed tour.

• The returned route has four subroutes: (1) workplace to customer A, (2) customer A to customer B, (3) customer B to customer C, and (4) customer C back to the workplace.

• Each subroute probably has multiple segments, each one associated with a specific driving direction step.

Simple multi-address requests can contain several attributes specific to each subroute. These attributes include return_subroutes, return_subroute_edge_ids, and return_subroute_geometry. These attributes are explained in Route Request XML Schema Definition.

14.1.3 Traveling Salesperson (TSP) Route Request

A traveling salesperson (TSP) route request must have at least three locations. Unlike simple multi-address route requests, the <start_location> element is optional.

TSP route requests are multi-address requests that have the optimize_route attribute present and set to TRUE. TSP route requests attempt to reorder the unfixed locations in the request to optimize the overall route.

All the locations in a TSP request are classified as unfixed or fixed:

• Unfixed location: If a location is specified with the <location> element, it is considered an unfixed location and is subject to reordering during route computation.

• Fixed location: If the location is specified with a <start_location> or <end_location> element, it is considered a fixed location and is not subject to reordering during route computation.

  If intermediate locations need to be fixed, a simple multi-address route request should be used instead of a TSP route request.

TSP route requests use the route_type attribute to classify the route as an open or closed tour.:

• Open tour: The route does not return to the start location.

• Closed tour: The route returns to the start location.

  If a TSP closed tour route is requested, the <start_location> element must be specified. This start location is also used as the end location during route computation. If an <end_location> element is specified in a TSP closed tour route request, an error is returned. By definition, TSP closed tour routes use a single fixed start and end location but the intermediate locations are still subject to reordering.

Example: TSP Open Tour Route Request

To drive from your workplace, visiting customers A, B, and C:

• The route has the workplace as a fixed start location.

• The route has customers A, B, and C as unfixed intermediate locations. These locations are reordered to optimize the overall route.

• The returned route is an optimized open tour route from the workplace to the first reordered location, through the second reordered location, to the final location.

Example: TSP Closed Tour Route Request

To drive from your workplace, visiting customers A, B, and C, and then returning to your workplace:

• The route has the workplace as a fixed start location. The workplace is also used as a fixed end location. An <end_location> element should not be specified in the route request. The routing engine adds the subroute from last unfixed location to the workplace automatically when it sees a request for a closed tour.

• The route has customers A, B, and C as unfixed intermediate locations. These locations are reordered to optimize the overall route.

• The returned route is an optimized closed tour route from the workplace to the first reordered location, through the second and third reordered locations, and finally back to the start location.

TSP route requests can contain several attributes specific to each subroute. These attributes include return_subroutes, return_subroute_edge_ids, and return_subroute_geometry. These attributes are explained in Route Request XML Schema Definition.

14.1.4 Batched Route Request

Batched route requests are a hybrid of batch mode requests (explained in Batch Mode Route Request) and individual route requests. Batched route requests are a way to process multiple simple, simple multi-address, and TSP route requests in one request to the routing engine. Batching of batch mode requests is not allowed.

Like a batch mode request, the outermost element of a batched route request is <batch_route_request>. Unlike a batch mode request, batched route requests have one or more <route_request> elements nested inside the batch request.

In a batched route request, all attributes associated with the encompassing <batch_route_request> element are ignored. Instead, the attributes associated with the nested <route_request> elements are used when processing each individual route. This allows users to mix simple, simple multi-address, and TSP requests in a single batched individual route request.

The batched route request is useful for submitting multiple variations of a single route request with differing attributes and comparing the results, for example, for comparing the fastest route with the shortest route.

The individual route requests in a batched route request can use any of the attributes from simple route requests. They can also use any of the subroute-specific attributes of simple multi-address and TSP route requests.

All of the individual route requests in a batched route request are standalone; they have no effect on any other route request in the batch.

14.1.5 Batch Mode Route Request

A batch mode route request contains one <start_location> element and one or more <end_location> elements.

The result of a batch mode route request contains multiple routes. Each route is from the start location to one of the end locations. Each route in a batch mode request is completely separate from all the other routes except for the shared start location.

Batch mode route requests may contain several batch mode specific attributes. These attributes include cutoff_distance and sort_by_distance. These attributes are explained in Route Request XML Schema Definition.

14.1.6 Relationship between Routing Engine and Geocoder

The routing engine depends on the geocoder, and therefore the data used for routing and geocoding must be consistent (that is, must be of the same "vintage" from your data provider).

A geocoding request returns an SDO_GEO_ADDR object that includes the following for each road segment: (1) Percent and EdgeID, and (2) Longitude and Latitude. The routing engine considers only the Percent and EdgeID.

The route server edge ID values can be positive or negative, reflecting the direction of the segment. (Geocoding edge IDs are always positive, because direction is irrelevant for geocoding.) The same road segment identifier in the routing and geocoding tables might be different only in the sign.

Consider the following example where an address is geocoded and will be used later for routing:

SELECT SDO_GCDR.GEOCODE('ODF_NA_Q312', 
  SDO_KEYWORDARRAY('5100 Geary Blvd', 'SAN FRANCISCO,CA 94118'), 
  'US', 'RELAX_POSTAL_CODE') 
  FROM dual;

The geocoder may return edgeid = 127806839 with percent = .86 (where EDGEID corresponds to the road_segment_id column of the geocoder GC_ROAD_SEGMENT table). However, the EDGE table used by the routing engine may have that same segment with edge_id -127806839 (different only in the negative sign). If a positive road_segment_id (from GC_ROAD_SEGMENT) matches only negative edge_id (from EDGE), the percent returned by the geocoder should be subtracted from 1 to get the corresponding percent to apply to the reversed edge(edge_id). In this example, 1 - .86 = .14.