AIRoutePlan
The project AIRoutePlan (i.e.: Artificial Intelligence for Route Planning) aims to develop a toolkit for solving a wide range of route planning problems of the logistics sector.
Securing the continuous flow of product and goods from the producer to the ultimate consumer is the key-task in the logistics sectors with relevant impacts on the environmental sustainability and Customer satisfaction. The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?". VRP is one of the most common challenges in supply chain management.
AIRoutePlan aims to integrate the GraphHopper – jsprit toolkit (https://github.com/graphhopper/jsprit) within the UP framework with the scope to make available a well-know library for planning of route optimization to the AI4EU community of developers. The GraphHopper - jsprit is a java based, open source toolkit for solving rich Traveling Salesman Problems(TSP), Vehicle Routing Problems (VRP) and many their derivations.
it is an all-purpose meta-heuristic that can be used to solve a number of classical VRP variants and it is based on the “Ruin and Recreate” core algorithm described by Schrimpf et al. (2000) [ Record Breaking Optimization Results Using the Ruin and Recreate Principle]and Pisinger and Ropke (2007) [A general heuristic for vehicle routing problems].
This toolkit is released under Apache License v2 and it is constantly updated since 2014. This guarantees that the development and maintenance of the library is secured in the mid/long term. More over the library is supported by a Company (GraphHopper GmbH) that reduces the risk that this library is abandoned in the short period ensuring the busine continuity in the mid/long term.
The AIRoutePlan library integrates the Unified Planning with JSprit Library allowing to solve Vehicle Routing Problem defining the problem with UPL with the PDDL formalism and specifying the coordinates of the Problems in terms of latitude and longitude.
The library allows to solve VRP both in case coordinates are provided as space-coordinates (x, y) and they are provided as geocoordinates (latitude and longitude). In this last case the library calculate the solution considering the real distances and travel time between locations. To enable this function it is needed to have an API_KEY to access to the GraphHopper API. The routes resulting from the solution can be visualized on a map like the following..
Installation
The library is distributed as python package at the following link on the PiPy repository and it can be installed as follow:
pip install up-jsprit
Examples
Some examples can be found in the github repository of the project and they refers to two different VRPs where:
- Example 1: Coordinates are provided in terms of x and y
- Example 2: Coordinates are provided in terms of latitude and longitude
The up-jsprit library can be used also running standard python command through the following steps:
- Create a python file vrp_domain_generator.py that defines the problem domain using the Unified Planning Library formalism. T
- Create a python file that represents the VRP.
- Create a file solve_vrp_problem.py that solves the problem parsing the VRP defined before and using the up-jsprit library
- Executing the solve_vrp_problem.py
python solve_vrp_problem.py -input .\vrp_problem_generator_xy.py
Two examples are provided:
- Example 1 - vrp_problem_generator_geo.py where the coordinates of locations are provided in terms of x, Y and the distance is calculated as an Euclidean distance.
- Example 2 - vrp_problem_generator_geo.py where the coordinates of locations are provided in terms of latitude and longitude. In this case, the distance and the travel time are calculated query, through API, the GraphHopper engine on the basis of real maps and data.