Optimal routes for bus transport to events¶

This repository contains the implementation of triply’s route optimization algorithm for bus transport to events. The aim of this engine is to find the optimal set of routes for a given fleet of busses that need to visit a given set of bus stops, taking into account that each bus can only fit a limited amount of people. To do so, it uses a combination of the OSRM routing engine and the Google OR Tools optimization toolbox.

Summary
Technical implementation
Installation and usage
API reference
Demo usage

Summary¶

The goal of the route optimization process 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.

Technical implementation¶

The code of the route optimization algorithm is bundled in a Python package named routingtools. The algorithm can be easily executed through an API.

Routingtools package¶

Currently, the routingtools package contains two core modules.

The osrm module handles the interaction with the OSRM routing engine. It can request either a cost matrix or a route from a locally running OSRM server (see OSRM setup).

The optimization module contains the RouteOptimizer class. This is an interface to solve a vehicle routing optimization problem, given a set of parameters. The route optimizer uses the Google OR Tools library to perform the optimization process. 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.

An instance of the RouteOptimizer class can be initialized with a set of parameters, either as keyword arguments or as a dictionary. Most of these parameters have sensible defaults and are thus not required to be set by the user. The only two required parameters are the location of the event and the locations of the bus stops. See here for detailed information about all parameters. Given the required information is present, an end-user with generally only call the get_solution method. Hence:

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()

A response object is returned in the form of a dictionary. See here for detailed information about the elements of such a response object.

API¶

There is a simple wsgi wrapper around the optimization script which is defined in the app.py script. It only exposes a generateRoute REST method. A usage example can be viewed on postman.

Installation¶

The easiest way to get the code is by cloning this repository with git:

git clone https://bitbucket.org/triply_at/os-routing

After moving to the cloned directory, the dependencies can be installed using the requirements.txt file. It is assumed that you have the Python package manager pip installed already.

pip install -r requirements.txt

Alternatively, it is also possible to install routingtools as a standalone package:

python3 setup.py install

OSRM setup¶

A running OSRM server is required for the executing the algorithm. The easiest way to set up OSRM on your own server is by using Docker images that they provide. Obviously, this requires Docker to be installed.

Before setting up OSRM, OpenStreetMap data need to be downloaded. This goes fast and easy with geofabrik, who provide country wide data in neat osm.pbf format. For example, one can download the complete OSM data of Austria in ‘only’ a 570 MB file.

wget http://download.geofabrik.de/europe/austria-latest.osm.pbf

With OSRM, these data now need to be converted into a network structure suitable for routing. One needs to specify the profile that is going to be used for this, i.e. for which type of vehicle the network is created. In case of buses, the car profile is used. Then, in three steps the data is pre-processed and analysis ready. The data pre-processing only has to be done when the new data is used (i.e. when setting up OSRM for the first time or when updating to the most recent data).

docker run -t -v "${PWD}:/data" osrm/osrm-backend osrm-extract -p /opt/car.lua /data/austria-latest.osm.pbf
docker run -t -v "${PWD}:/data" osrm/osrm-backend osrm-partition /data/austria-latest.osrm
docker run -t -v "${PWD}:/data" osrm/osrm-backend osrm-customize /data/austria-latest.osrm

The flag -v "${PWD}:/data" creates the directory /data inside the docker container and makes the current working directory "${PWD}" available there. Of course, this can be changed into any directory, in case the downloaded data is not stored in the current working directory.

With the pre-processed data, the OSRM routing engine can be started as follows.

docker run -t -i -p 5000:5000 -v "${PWD}:/data" osrm/osrm-backend osrm-routed  --max-table-size=10000 --algorithm mld /data/austria-latest.osrm

This will start a local routing server on port 5000. The --max-table-size parameter sets the maximum number of nodes to be used when creating cost matrices. By default, this is 100, which is often too small for big events. The --algorithm parameter defines the algorithm to be used for finding shortest routes. In this case, it is the recommende Multi-Level Dijkstra (MLD) algorithm.

For a full installation guide of OSRM, see their documentation

API reference¶

This sections describes in detail the structure of a API request and of the returned response object.

Request¶

A request send to the route optimization service needs the algorithm configuration parameters as data-raw argument. These parameters should be provided as a JSON object, either directly, or as a path to a .json file. When using the routingtools package directly inside a Python shell, the same parameters should be provided either as dictionary or keyword arguments while initializing the RouteOptimizer instance. Note that required parameters without a default value must always be provided. Required parameters with default values, as well as optional parameters, can optionally be provided. An example parameter object can be found here. The object can contain the following key/value pairs:

event | An array containing a single event object. | required | no default | stops | An array containing multiple stop objects. | required | no default | vehicles | An array containing multiple vehicle objects. This parameter is required only when capacity constraints should be applied. If not given, it will be automatically created internally, assuming unlimited availability of standard vehicle sizes by guaranteeing that each stop can possibly be served only by vehicles of a single standard size. | conditionally required | default automatically calculated | vehicleCount | A positive integer describing the number of available vehicles. This parameter is 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, and any given value will be ignored. | conditionally required | no default | standardVehicleSizes | An array of integers, each describing the maximum capacity of a commonly available vehicle type. This parameter is required only when capacity constraints should be applied and no vehicle data are given. | conditionally required | [8, 19, 37, 49, 57] | fixedVehiclePenalty | An 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). This parameter is required only when vehicle usage should be penalyzed, and ignored otherwise. | conditionally required | max | maxRouteDuration | A positive integer describing the maximum allowed travel time of a route, in seconds | required | 7200 | globalSpanCostCoefficient | A positive 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 | required | 1 | firstSolutionStrategy | A string describing the algorithm to use for finding a first solution to the problem. See here for all available options. | required | PATH_CHEAPEST_ARC | localSearchMetaheuristic | A string describing the algorithm to use for performing local search of the solution space. See here for all available options. | required | GUIDED_LOCAL_SEARCH | searchTimeLimit | A positive 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. | required | 10 | arbitraryStarts | A boolean describing if the start location of a vehicle should be arbitrary or not. Note that if this is set to false, vehicle data should always be given, with each vehicle object containing a coordinate object describing the start location of the vehicle. | required | true | capacityConstraints | A boolean describing if capacity constraints should be applied or not. | required | true | multipleVisits | A boolean describing if visits of multiple vehicles to the same stop should be allowed. Ignored when capacity constraints should not applied. | required | true | vehicleUsagePenalties: A boolean describing if a cost penalty should be given whenever an extra vehicle is used. Note that if this is set to true, the fixedVehiclePenalty parameter should always be set. | required | true |

Event object¶

An event object provides information about the location of the event. It should contain the following key/value pairs:

Stop object¶

A stop object provides information about the locations and loads of the selected bus stops. It should contain the following key/value pairs:

Vehicle object¶

A vehicle object provides information about the capacities and optionally start locations of the available vehicles. It should contain the following key/value pairs:

Coordinate object¶

A coordinate object provides information about the geographical coordinates of a location. These coordinate values should always be expressed in the WGS84 geographical coordinate reference system (i.e. EPSG:4326). It should contain the following key/value pairs:

Response¶

A response to a request send to the route optimization service is a JSON object. When using the routingtools package directly inside a Python shell, it is a Python dictionary instead. An example response object can be found here. The response object contains the following key/value pairs:

routeCount | An integer describing the number of routes in the solution | routes | An array of route objects |

Route object¶

A route object provides information about a single route that is part of the solution. Next to general route information, it also specifies the nodes visited by the route, and the vehicle assigned to travel the route (only if capacity constraints where applied) The nodes are set of the vehicle start location (only if starts where not arbitrary), the stops and the event. A route object contains the following key/value pairs:

routeIndex | An integer that serves as a unique identifier of the route. | routeName | A string describing the name of the route. This is “Route 1” for the first route, etc. | routeObjects | An array containing a single OSRM route object. The full geometry of the route in GeoJSON format is accessible through the geometry key of that object | nodeIndices | An array of integers describing the indices of the nodes that are visited by the route, in the correct order. | nodeNames | An array of strings describing the names of the nodes that are visited by the route, in the correct order. | nodeCoords | An array of arrays in the form [longitude, latitude] describing the coordinates of the nodes that are visited by the route, in the correct order. | vehicleIndex | An integer describing the unique index of the vehicle assigned to the route. Only present when capacity constraints where applied. | vehicleName | A string describing the name of the vehicle assigned to the route. Only present when capacity constraints where applied. | vehicleCapacity | An integer describing the capacity of the vehicle assigned to the route. Only present when capacity constraints where applied. | cumulativeLoads | An array of integers describing for each of the stops vistited by the route how many people are in the vehicle after the visit to that stop. | cumulativeCosts | An array of integers describing for each of the stops visited by the route what the total route cost is after the time of visit to that stop. |

Demo usage¶

To get both OSRM and the route optimization API running locally as fast as possible, you can just use the provided docker-compose script. If you have docker-compose installed (see installation instructions here) you can just run docker-compose up -d locally. This will make the route optimization service available at localhost:5050. Then, send a request as follows:

curl --location --request POST 'http://localhost:5050/generateRoute' --header 'Content-Type: application/json' --data-raw '{"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},{"name":"Bad Ischl (Busterminal)","coordinates":{"lon":13.62571,"lat":47.71197},"load":63},{"name":"Steyr (Reithoffergelände)","coordinates":{"lon":14.41944,"lat":48.039359999999995},"load":86},{"name":"Gmunden Bahnhof (Vorplatz)","coordinates":{"lon":13.782589999999999,"lat":47.924620000000004},"load":73},{"name":"Linz (Hauptplatz)","coordinates":{"lon":14.287679999999998,"lat":48.305161},"load":53},{"name":"Enns (Stadthalle)","coordinates":{"lon":14.476878,"lat":48.217563},"load":12},{"name":"Schärding (Friedhofsparkplatz)","coordinates":{"lon":13.4305,"lat":48.45755},"load":9},{"name":"Ebensee (Landungsplatz)","coordinates":{"lon":13.77462,"lat":47.81243},"load":19},{"name":"Traunkirchen (Bräuwiese)","coordinates":{"lon":13.78385,"lat":47.85761},"load":4}],"vehicleCount":10,"standardVehicleSizes":[8,19,37,49,57],"maxRouteDuration":7200,"firstSolutionStrategy":"PATH_CHEAPEST_ARC","localSearchMetaheuristic":"GUIDED_LOCAL_SEARCH","searchTimeLimit":30,"arbitraryStarts":true,"capacityConstraints":true,"multipleVisits":true}'

Alternatively, you can run a OSRM server locally (as desribed in OSRM setup), and then execute the demo.py script by:

python3 demo.py

By default, this will use the parameter object from the demo_files folder, and store the response object there as response.json, and an interactive map of the solution as map.html. These defaults can be changed by providing arguments to the Python script. Also, you can change the level of log messages to be displayed on the console (defaults to INFO). For example:

python3 demo.py --req "somedir/params.json" --res "somedir/out.json" --map "somedir/map.html" --log "DEBUG"