Planning a Tour using a Distance Matrix

This use case describes how to plan tours with a precomputed distance matrix. Distance matrices play an important role in many tour planning use cases for determining realistic travel times. For example not all vehiclesClosed The term vehicle describes what is being routed or planned for. Vehicles are used in route calculation, distance matrix calculation and effectively also in tour planning. In route calculation, vehicle properties like overall size, weight and speed are in focus. In tour planning, it is vehicle properties like capacity and availability. Commonly a vehicle is motorized, like a truck - including its trailer or a car. However also a bike or even a pedestrian are included in this definition. are allowed to use every road which can lead to significant differences compared to plans estimated with direct distance. Also vehicle and road dependent speed limits play an important role for the travel time. Those can be precisely considered in a distance matrix.

Benefits

  • Distance matrices in the tour planning context lead to more realistic and accurate plans.
  • Estimation by reference matrix reduces the amount of consumed xServer resources for large tour planning problems.
  • Estimation by reference matrix simplifies the usage of the same distance matrix for multiple tour planning problems.

Prerequisites

Please ensure following prerequisites are fulfilled before you start with the use case:

  • Installed and licensed PTV xDima service
  • Installed and licensed PTV xTour service
  • License for as many vehicles as the plan should contain
  • To improve the performance, increase xtour.maxNumberOfThreads in your xserver.conf file.

Concepts

Programming Guide

Existing Distance Matrix

This example provides information on how to plan tours using a global distance matrix.

First we define our locations as OffRoadRouteLocations in the default EPSG:4326 format (see RequestBase.coordinateFormat). You could also use OnRoadRouteLocations, see the technical concept on waypoints and route legs for more information on the different route locationsClosed A route location is the position of an object to be routed to or from, which contains additional information on how to link this position to the road network and whether or or not this position is actually reached. Route locations are used as the input for route calculation and optimization throughout PTV xServer.. Furthermore we define some locations as depot and some as customer sites, see Orders, Locations, and Stops for more details.

The fleet in this example consists of one vehicle type, containing one vehicle instance (defined by the number of vehicle ids). In this use case we do not want the vehicle to use direct distance, but an existing distance matrix (can be set in the distance mode of the request). So we need to define a CreateDistanceMatrixRequest with all the locations needed for the PlanToursRequest. The id of the distance matrix response summary returned by the createDistanceMatrix operation of xDima is then used for the PlanToursRequest.

The last part of the example PlanToursRequest are the orders, in this case only consisting of pickup and delivery orders.

We pass on the request to planTours. Once xTour has processed the request a callback is invoked which gives us access to the result of the calculation in form of a ToursResponse object. After displaying the tour results we delete the before calculated distance matrix with the deleteDistanceMatrix operation to release the required memory.

The customer sites of the request are displayed in gray, the depot sites in orange. The tour of the result is displayed in gray.

The tour consists of two trips because the maximum quantity scenario of the vehicle means that it can carry out three orders in one trip because of their quantities. The usage of a distance matrix leads to a trip including customers Customer2 and Customer4 that are connected via a highway. Therefore Customer3 who is located in town is planned on the second trip.

When changing to direct distance (see comment in the code section) the highway does not play a role in the result. Instead only geographically close-by customers are planned on the same trip.

Existing Distance Matrix Per Vehicle

This example provides information on how to plan tours using a distance matrix per vehicle. For the distance mode of the request we now choose ExistingDistanceMatrixPerVehicle. Therefore each vehicle has to have a distance matrix id set.

Using vehicle parametrization we create two distance matrices using the stored profilesClosed A stored profile is a (partial) profile persisted as an XML file. of a car and a truck with a total permitted weight of 11,99t. For simplification, there are no opening interval restrictions.

The customer sites of the request are displayed in gray, the depot sites in orange. The tours of the result are displayed in gray and blue.

The response consists of two tours because we set single trip per tour and the maximum quantity scenario still restricts to execute at most three orders per trip.

As multiple streets that directly connect two locations are not allowed for trucks, the vehicle with the car as profileClosed A profile is a collection of parameters used to configure the request. Full profiles consist of a number of specialized sub-profiles like the VehicleProfile which describes the properties of a vehicle. is driving the tour to the furthest away customers. If you exchange the vehicle profiles (see comment in the code section), the tours will also be exchanged because it is more efficient to drive the direct connecting routesClosed A route corresponds to a path of a vehicle through the underlying transport network. The main attributes of a route are the distance and the time that the vehicle travels along the path. between the furthest away sites with the vehicle with the car profile.

If both vehicles have a car as profile (see comment in the code section), the structure of the tours seems more intuitively as the tours are not crossing each other.

However if both vehicles have a truck as profile (see comment in the code section), the vehicles have to make the detours to get to each customers.

Estimate by Reference Matrix

This example provides information on how to reduce the size of the distance matrix by defining a nearby reference point for each location. Since multiple nearby locations can have the same reference point, fewer distance matrix relations need to be stored. A reference matrix is a distance matrix that contains all reference locations. The distance and travel time between two locations are estimated based on direct distance, average speed and the detour factor obtained from the reference matrix.

This example is similar to the Existing Distance Matrix example above. Locations, fleet and orders are defined in the same way. For simplification, there are just visit orders and no opening interval restrictions. Instead of considering all locations for the CreateDistanceMatrixRequest we now only calculate relations between reference points. For the distance mode of the request we now choose EstimateByReferenceMatrix. Additionally to the id of the calculated distance matrix, we define a reference location for each location of the request. Note that all reference locations have to be part of the reference matrix but the locations themselves do not have to be considered.

The customer sites of the request are displayed in gray, the corresponding reference locations in blue. The dashed blue lines indicate the mapping of customer locations to reference locations. The dashed green line indicates the calculated relation in the distance matrix. As there are no restrictions, the result consists of just one visit tour.

Instead of five customer locations, just two reference locations are contained in the distance matrix. When changing to existing distance matix and deleting the reference location mappings(see comment in the code section) you will get an exception because the customer locations are not contained in the distance matrix.

Existing Distance Matrix (Multiple Travel Times Distance Matrix)

This example provides information on how to plan tours using a global distance matrix that is calculated by using multiple travel times consideration. The before mentioned distance modes ExistingDistanceMatrixPerVehicle and EstimateByReferenceMatrix can be modified accordingly but if one distance matrix is a multiple travel times distance matrix all other distance matrices of the PlanToursRequest must also be multiple travel times distance matrices.

The CreateDistanceMatrixRequest is extended by a MultipleTravelTimesConsideration that specifies the horizon in which multiple travel times will be considered. A multiple travel times distance matrix cannot be used in a PlanToursRequest if a DrivingTimeRegulation is set. In this example we use the WorkingTimeDirective EU_2002_15_EC. As the working time directive is used to ensure regular breaks for truck drivers the distance matrix is calculated by using truck speed patterns and truck attributes.

In addition to the working time directive the PlanToursRequest must define a planning horizon in the PlanToursOptions.

Only use a multiple travel times distance matrix if needed. The results differ significantly to the ones calculated with a normal distance matrix as the optimization problem gets much more difficult to solve! Have a look at the Technical Concept Working Hours to ensure a valid PlanToursRequest when using multiple travel times distance matrices.