Postgres, PostGIS & PgRouting: Optimal Route Planning for Electric Vehicles Using Road Specific Data

Postgres, PostGIS & PgRouting: Optimal Route Planning for Electric Vehicles Using Road Specific Data
14/01/2020 Ernestas Konopliovas

Introduction

Traditionally routing has focused on finding the shortest paths in networks with positive, static edge costs representing the distance between two nodes. Energy-optimal routing for electric vehicles creates novel algorithmic challenges, as simply understanding edge costs as energy values and applying standard algorithms does not work. The reason for this is that electric vehicle (EV) reachable distance can vary based on such aspects as a number of passengers, speed, outside temperature or even route incline that influences recuperation. But even taking in mind all these parameters will not allow creating best routes. The reason for this is that in Lithuania EV owners have the privilege to use public transportation lanes for faster movement.

Photo by S. Žiūra

The most popular navigating applications use regular traffic data to create routes for users. Such routes become useless if we take in mind that EV owners can use much faster public transportation lanes while regular lanes have increased vehicular queuing.

We build a database-level system, wrapped by easy-to-use web API, that has all features of greatest route planning tools, but considers EVs priveledges, strong and weak sides, and creates the fastest as well as the most efficient routes for their owners in Vilnius city.

The system is developed by me and Linas Sabaliauskas, supervised by Linas Bukauskas during first semester of Problem-Based Project course of Information Technology study programme of Vilnius University. The system is free to use for non-commercial purposes.


 

How it works

We strongly recommend reading full documentation to have a whole image of how system operates. However, we have the best intentions to save your time, so here is the short story.

In this version we use Postgres, PostGIS and PgRouting in our database side system. Shortest path are gathered using Dijkstra’s algorithm and road specific data with applied advantages of electric vehicles. Every egde cost is calculated using formula:

cost = ((cost in seconds) x (simulated traffic load multiplier)) x (elevation multiplier) x (prioritization multiplier)

Where: 
• Cost in seconds is time during which edge can be passed. Calculated by dividing the length by maximum allowed speed.
• Simulated traffic load multiplier is multiplier which is created when traffic data is simulated. Currently simulates 200-270% traffic load. If the direction of movement is the same as direction of public trasportation lane on the edge, this edges multiplier is conscidered as 1, so it remains with 0% traffic load.
• Elevation multiplier is multiplier which is created when difference between edge start and end point elevation is evaluated.
• Prioritization multiplier is multiplier which helps to create paths prioritizing main roads, roads with higher amount of lanes.


 

How to test it out

You can test the system by following 4 easy steps.

Step 1: Find two points

You will need WGS84 coordinates of routes start and end point. To get them, visit espg.io and grab longitude and latitude of both: start and end point. Note, that for now, we have only Vilnius city roads in the database, so if you choose point out of the city bounds if will be mapped to closest existing road.

Step 2: Make a request

Use any request sender you like. The request method is GET, so you can even use your browser.Get the coordinates that you grabbed earlier in Step 1  and put them into request separating by comma. Here are some examples:

http://api.kono.lt:8888/api/path/25.256195,54.729775,25.283690,54.681663
http://api.kono.lt:8888/api/path/25.256195,54.729775,25.283690,54.681663/charging=1000

In the second example you are also searching for charging stations within 1000 meters radius starting from route end point.

Step 3: Copy path_geojson

In the response body, find and copy json object body called “path_geojson”. It may start like this:

{“type”:”FeatureCollection”,”features”:[{“type”:”Feature”,”properties”:{“id”:-101.0},”geometry”:{“type”:”LineString” … *rest of things in here* }

 

Step 4: Visualize

To do this, visit geojson.io. Clear the input box and paste the geojson that you have copied in Step 3 into it. Voila!


 

Ask for more with API Request

Insertion fields are marked with “{}” symbols.
Request method: GET
Request endpoint: api.kono.lt:8888/api/path/

Required attribute:
{startPointLongitude},{startPointLatitude},{endPointLongitude},{endPointLatitude}

Where:
• startPointLongitude is WGS 84 longitude coordinate of start point of route
• startPointLatitude is WGS 84 latitude coordinate of start point of route
• endPointLongitude is WGS 84 longitude coordinate of end point of route
• endPointLatitude is WGS 84 latitude coordinate of end point of route

Optional attributes:
• traffic={yes/no} declares whether to use traffic while creating path. Default is “yes”
• geojson={yes/no} declares whether add geojson to response or not. Default is “yes”
• charging={integer radius in meters} radius in which DB will look for charging stations. Charging stations search is not used by default.

Request examples:

http://api.kono.lt:8888/api/path/25.194139,54.702333,25.261914,54.700827

http://api.kono.lt:8888/api/path/25.194139,54.702333,25.261914,54.700827/charging=1000

http://api.kono.lt:8888/api/path/25.194139,54.702333,25.261914,54.700827/charging=1000/geojson=no

http://api.kono.lt:8888/api/path/25.194139,54.702333,25.261914,54.700827/traffic=no/charging=10


 

Receive more with API Response

Response body:

API responses with json body containing next attributes:
• traffic_data_used declares whether traffic data was used while finding the shortest path. Type: boolean
• path_length total path length in meters. Type: double
• path_duration total path duration in seconds. Type: double
• path_cost total path cost. Type: double
• bus_lane_edges_used counts how many edges was used in path. Type: integer
• path_geojson visual representation of whole path in geojson format. Type: json object
• path array of edges used to create path. Type: array
This array contains each edge as object with following attributes:
  – gid identifies edge. Type: integer
  – source identifies edges source point. Type: integer
  – target identifies edges target point. Type: integer
  – source_point_longitude longitude of source point. Type: double
  – source_point_latitude latitude of target point. Type: double
  – target_point_longitude longitude of source point. Type: double
  – target_point_latitude latitude of target point. Type: double
  – cost_s edges cost is seconds. Type: double
  – reverse_cost_s edges reverse cost is seconds. Type: double
  – present_cost_s edges cost is seconds effected by traffic load. Type: double
  – present_reverse_cost_s edges reverse cost is seconds effected by traffic load. Type: double
  – direction_reverse declares whether direction was reverse (whether direction was from target to source, or vice versa). Type: boolean
  – length edges length in meters. Type: double
  – bus_lane declares where bus lane is on the edge. Type: integer. Possibilities: 0, -1, 1 or 2
  – bus_lane_used declares whether bus lane was used. Type: boolean
  – source_point_elevation declares source points elevation above see level in meters. Type: integer
  – target_point_elevation declares target points elevation above see level in meters. Type: integer
  – cost declares edges cost. Type: integer
  – agg_cost sum of all previous edges costs. Type: double
  – geojson visual representation of egde in geojson format. Type: json object
API also with responses optional attributes which are returned only if optional attributes are used in request. Those are:
• destination_changed is returned when attribute “charging” is used. Declares whether destination was changed because of found charging station in given radius. Type: boolean
• message is returned when attribute “charging” is used. Gives a human readable message about whether destination was changed because of found charging station in given radius. If it was changed, gives coordinates of new destination point. Type: string

 

Comments (0)

Leave a reply

Your email address will not be published. Required fields are marked *

*