routingtools.optimization module

Optimization of vehicle routes.

This module contains classes and functions to solve vehicle routing optimization problems. It uses the Google OR Tools library as a workhorse.

class routingtools.optimization.RouteOptimizer(**params)[source]

Bases: object

Interface to solve a vehicle routing optimization problem.

The goal of the route optimizer is to find the best routes for a fleet of vehicles (i.e. buses) visiting a set of locations (i.e. bus stops).

In general, optimization problems consist of an objective accompanied by constraints. The objective specifies the quantity to be optimized. The constraints describe restrictions on the set of possible solutions, based on specific requirements of the problem.

In the vehicle routing case, the objective is to minimize the travel cost of the most expensive route. The travel cost is quantified as the time it takes to travel the route. As a constraint, a route can never be longer than the given maximum route duration. A second, optional constraint relates to capacities of the vehicles. At each bus stop there is a number of people to pick up (i.e. the demand), and each bus has a maximum number of people it can fit (i.e. the capacity). The constraint is that a vehicle can, along its route, never pick up more people than its maximum capacity.

The optimization process will first use a specified method to find an initial solution. Then, a specified local search metaheuristic will be used to search the solution space around that initial solution, and see if there are better solutions to be found. Some metaheuristics can escaped local minima. That is, solutions cheaper than all nearby solutions, but NOT the overall cheapest solution possible.

The route optimizer uses the Google OR Tools library to perform the optimization process. See https://developers.google.com/optimization/routing. Internally, three main components need to be set before solving the problem:

  • The Data Model: stores the data needed to solve the problem, in a format that can be easily queried by the other components.

  • The Routing Index Manager: converts OR Tools internal indices to node indices that correspond to the position of stop nodes in the data model.

  • The Routing Model: provides an interface that can set the objective and constraints of the problem, and solve it accordingly.

The route optimizer can be initialized with a set of parameters, either as keyword arguments or as a dictionary. Most of the parameters have default values. The parameters are:

  • event: List of event objects. Required parameter with no default. An event object is a dictionary with the following keys:

    • name: The name of the event as a string.

    • coordinates: The location of the event as a dictionary with a lat key referring to an integer value describing the latitude coordinate of the location, and a lon key referring to an integer value describing the longitude coordinate of the location. Coordinate values should be expressed in the WGS84 geographic coordinate reference system (i.e. EPSG:4326).

  • stops: List of stop objects. Required parameter with no default. A stop object is a dictionary with the following keys:

    • name: The name of the stop as a string.

    • coordinates: The location of the stop as a dictionary with a lat key referring to an integer value describing the latitude coordinate of the location, and a lon key referring to an integer value describing the longitude coordinate of the location. Coordinate values should be expressed in the WGS84 geographic coordinate reference system (i.e. EPSG:4326).

    • load: The number of people to be picked up at the stop as integer.

  • vehicles: List of vehicle objects. required only when capacity constraints should be applied. If not given, it will be created automatically with create_vehicle_data(). A vehicle object is a dictionary with the following keys:

    • name: The name of the vehicle as a string.

    • coordinates: The start location of the vehicle as a dictionary with a lat key referring to a float describing the latitude coordinate of the location, and a lon key referring to a float describing the longitude coordinate of the location. Coordinate values should be expressed in the WGS84 geographic coordinate reference system (i.e. EPSG:4326). This key is not required when vehicle start locations should be arbitrary.

    • capacity: The maximum number of people that fit in the vehicle.

  • vehicleCount: Integer, describing the number of available vehicles. Required only when capacity constraints should not be applied and no vehicle data are given. In other cases, it will be automatically derived from the vehicle data.

  • standardVehicleSizes: List of integers, each describing the maximum capacity of a commonly available bus type. Required only when capacity constraints should be applied and no vehicle data are given. Default value set to [8, 19, 37, 49, 57].

  • fixedVehiclePenalty: Integer, describing the penalty that should be given when using an extra vehicle, expressed in terms of route cost units (generally travel time in seconds). Alternatively, it can be set to “max”, which refers to the maximum cost value of the cost matrix (i.e. the maximum travel time between two nodes). Required only when vehicle usage should be penalyzed, ignored otherwise. Default value set to max.

  • maxRouteDuration: Integer, describing the maximum allowed travel time of a route, in seconds. Default value set to 7200 (i.e. 2h).

  • globalSpanCostCoefficient: Integer, serving as a weight in the objective function of the optimization. The objective function to minimize is A + xB, where A is the total cost of all routes, B is the cost of the most expensive route, and x is the global span cost coefficient. Hence, a value of x = 1 gives equal importance to A and B while high values give more importance to B, and values close to zero give more importance to A. Default value set to 1.

  • firstSolutionStrategy: String, describing the algorithm to use for finding a first solution to the problem. Default value set to PATH_CHEAPEST_ARC. See https://developers.google.com/optimization/routing/routing_options#first_sol_options for all available options.

  • localSearchMetaheuristic: String, describing the algorithm to use for performing local search. Default value set to GUIDED_LOCAL_SEARCH. See https://developers.google.com/optimization/routing/routing_options#local_search_options for all available options.

  • searchTimeLimit: Integer, describing the maximum amount of time a solution search may take, in seconds. If no solution is found within this time, an error will be returned. Default value set to 10.

  • arbitraryStarts: Boolean, describing if the start location of a vehicle should be arbitrary or not. Default value set to True. Note that if this is set to False, vehicle data should always be given, with each vehicle object containing a coordinate object which describes the start location of the vehicle.

  • capacityConstraints: Boolean, describing if capacity constraints should be applied or not. Default value set to True. Note that if this is set to True, vehicle data should always be given, with each vehicle object containing a capacity key describing the maximum capacity of the vehicle.

  • multipleVisits: Boolean, describing if visits of multiple vehicles to the same stop should be allowed. Default value set to True. Ignored when capacity constraints are not applied.

  • vehicleUsagePenalties: Boolean, describing if a cost penalty should be given whenever an extra vehicle is used. If set to True, the fixedVehiclePenalty parameter should be set. Default value set to True.

Example

>>> event = [
...   {
...     "name": "Empire St. Martin",
...     "coordinates": {
...       "lon": 14.0603747,
...       "lat": 48.416865
...     }
...   }
... ]
>>> stops = [
...   {
...     "name": "Grieskirchen Bahnhof (Johannesstraße 3)",
...     "coordinates": {
...       "lon": 13.834073000000002,
...       "lat": 48.232506
...      },
...     "load": 33
...   },
...   {
...     "name": "Ried im Innkreis (Busbahnhof)",
...     "coordinates": {
...       "lon": 13.49006,
...       "lat": 48.20989
...     },
...     "load": 14
...   }
... ]
>>> optimizer = RouteOptimizer(event = event, stops = stops)
>>> optimizer.get_solution()
static create_vehicle_data(stop_nodes, vehicle_sizes)[source]

Automatically creates the required vehicle data.

Creates the required vehicle input data by assuming that the standard vehicle sizes are available without a limit. Without a limit means that each stop can possibly be served only by vehicles from a single standard size. The vehicles will not have a start location associated with them.

Parameters

  • stop_nodes (dict) – The stops object of the input parameters.

  • vehicle_sizes (list) – A list of the most common vehicle capacities.

get_solution()[source]

Solves the specified vehicle routing problem.

Returns

A result object. See the API reference for details.

Return type

dict

parse_event_data()[source]

Parses the event data into a format that can be easiliy queried by the model.

parse_stop_data()[source]

Parses the stop data into a format that can be easiliy queried by the model.

parse_vehicle_data()[source]

Parses the vehicle data into a format that can be easiliy queried by the model.

set_data_model()[source]

Initializes the data model.

The data model stores the data needed to solve the problem, in a format that can be easily queried by the other components.

set_routing_index_manager()[source]

Initializes the routing index manager.

The routing index manager converts OR Tools internal indices to node indices that correspond to the position of stop nodes in the data model.

set_routing_model()[source]

Initializes the routing model.

The routing model provides an interface that can set the objective and constraints of the problem, and solve it accordingly.

static split_stops(stop_nodes, vehicle_sizes)[source]

Distributes the load of stop nodes over multiple sub-nodes.

This is needed to allow mulitple visits to a single node.

The rules for splitting are the following:

1) Stop nodes with a total load smaller than or equal to the minimum standard vehicle size will not be splitted, i.e. they will only have a single sub-node with a load equal to the total load of the stop node.

2) Stop nodes with a total load larger than the minimum standard vehicle size will be splitted into sub-nodes with loads that equal the minimum standard vehicle size.

3) However, if the total load of a stop node is larger than 10 times the minimum standard vehicle size, the node will instead be splitted into sub-nodes with loads that equal the second smallest standard vehicle size. This is to prevent that too many sub-nodes get created, which would slow the routing algorithm down.

4) Again, if the total load of a stop node is larger than 10 times the second smallest standard vehicle size, the node will be splitted into sub-nodes with loads that equal the third smallest standard vehicle size, et cetera.

5) Stop nodes with a total load larger than the maximum standard vehicle size will always be splitted into sub-nodes with loads that equal the maximum standard vehicle size.

After splitting the total load of a stop node into equally loaded sub-nodes, the remainder is handled as follows:

1) The remainder will first be splitted in sub-nodes with loads that equal the size of a standard vehicle of one level smaller than the standard vehicle which size was used to do the initial split.

2) Then, the remainder of that split operation will be splitted in sub-nodes with loads that equal the size of a standard vehicle of two levels smaller than the standard vehicle which size was used to do the initial split, et cetera.

3) If there are no smaller vehicle sizes (anymore), the remainder is added to the last created sub-node.

Parameters

  • stop_nodes (dict) – The stops object of the input parameters.

  • vehicle_sizes (list) – A list of the most common vehicle capacities.

routingtools.osrm module

Interaction with the Open Source Routing Machine.

This module contains functions that send requests to the OSRM routing engine. A running OSRM server is required.

routingtools.osrm.get_cost_matrix(cost, coords)[source]

Retrieves a matrix from the OSRM routing engine, describing the travel cost between two locations, for each possible combination of locations.

Parameters

  • cost (str) – The type of travel cost to be used, either ‘duration’ or ‘distance’.

  • coords (list) – List of coordinate pairs, where each coordinate pair describes a location in geographical space and is a list [a, b] with a and b being respectively the longitude and latitude coordinates of the location. Dummy locations, with a coordinate value of [None] instead of [a, b], will be ignored.

Returns

A list in which each element is again a list.

Each of those sub-lists is representing a single row of the cost matrix, and each of its elements is an integer describing the calculated travel cost between the two respective locations.

Return type

list

routingtools.osrm.get_route(coords)[source]

Retrieves the shortest route between multiple locations from the OSRM routing engine. The locations will be visited in the order they are provided.

Parameters

coords (list) – List of coordinate pairs, where each coordinate pair describes a location in geographical space and is a list [a, b] with a and b being respectively the longitude and latitude coordinates of the location. Dummy locations, with a coordinate value of [None] instead of [a, b], will be ignored.

Returns

An OSRM route result - http://project-osrm.org/docs/v5.5.1/api/#result-objects.

Return type

dict

routingtools.exceptions module

Custom error classes.

This module contains several error classes that are customized for the routing package.

exception routingtools.exceptions.CostConstraintTooLowError[source]

Bases: Exception

Not all stops could be served within the maximum route duration.

exception routingtools.exceptions.NoSolutionFoundError[source]

Bases: Exception

Route optimizer could not find a solution.

exception routingtools.exceptions.OSRMError[source]

Bases: Exception

OSRM request failed.