# vrp VRP or **Vehicle Routing problem** is a generalization of the *Travelling Salesman Problem*. The goal of the problem is to find the shortest route that visits each node once, starting and finishing from the same node, called a depot, while using a fleet of vehicles. Each vehicle does not need to be at every location, it is enough that every node is visited by at least one vehicle. The problem is *NP-hard* in optimization, and therefore methods such as constraint programming, approximations or heuristics are a good approach for solving. The current implementation of VRP includes constraint programming with *GEKKO* solver which works with 1 depot and an arbitrary number of vehicles. The algorithm uses the distance calculator to determine the distance between driving points, and works only with geographical locations, meaning each node needs to have its *lat* and *lng* property. ```cypher (location:Location {lat: 44.1194, lng: 15.2314}) ``` | Trait | Value | | ------------------- | ---------- | | **Module type** | module | | **Implementation** | Python | | **Graph direction** | undirected | | **Edge weights** | unweighted | | **Parallelism** | sequential | > **Info** > > Too slow? > > If this algorithm implementation is too slow for your use case, open an issue on [Memgraph's GitHub repository](https://github.com/memgraph/memgraph/issues) and request a rewrite to C++! ## Procedures > **Info** > > You can execute this algorithm on [graph projections, subgraphs or portions of the graph](https://memgraph.com/docs/advanced-algorithms/run-algorithms#run-procedures-on-subgraph). ### `route()` The procedure returns a vehicle route. #### Input: - `subgraph: Graph` (**OPTIONAL**) ➡ A specific subgraph, which is an [object of type Graph](https://memgraph.com/docs/advanced-algorithms/run-algorithms#run-procedures-on-subgraph) returned by the `project()` function, on which the algorithm is run. If subgraph is not specified, the algorithm is computed on the entire graph by default. - `depot_node: Vertex` ➡ Depot node with its corresponding *lat* and *lng* coordinate properties. - `number_of_vehicles: integer = 1` ➡ Designates how many vehicles are used. Set to 1 by default. #### Output: - `from_vertex: Vertex` ➡ Beginning point of one part of the route. - `to_vertex: Vertex` ➡ Ending point of one part of the route. - `vehicle_id: integer` ➡ Vehicle ID that will drive the corresponding path (*from_vertex*)->(*to_vertex*) All pairs of the route represent the full route with all vehicles used. #### Usage: To get the vehicle route, use the following query: ```cypher MATCH (d:Depot) CALL vrp.route(d) YIELD from_vertex, to_vertex, vehicle_id RETURN from_vertex, to_vertex, vehicle_id; ``` ## Example ### Database state The database contains the following data: ![](https://memgraph.com/docs/pages/advanced-algorithms/available-algorithms/vrp/vrp-1.png) Created with the following Cypher queries: ```cypher CREATE (:Location {lat:45.81397494712325, lng:15.977107314009686}); CREATE (:Location {lat:45.809786288641924, lng:15.969953021143715}); CREATE (:Location {lat:45.801513169575195, lng:15.979868413090431}); CREATE (:Location {lat:45.80062044456095, lng:15.971453134506456}); CREATE (:Location {lat:45.80443233736649, lng:15.993114737391515}); CREATE (:Location {lat:45.77165828306254, lng:15.943635971437576}); CREATE (:Location {lat:45.785275159565806, lng:15.947448603375522}); CREATE (:Location {lat:45.780581597098646, lng:15.935278141510148}); CREATE (:Location {lat:45.82208303601525, lng:16.019498047049822}); CREATE (:Depot {lat:45.7872369074369, lng:15.984469921454693}); ``` All nodes in the graph are either Location or Depot. ### Get vehicle route To get the vehicle route, use the following query: ```cypher MATCH (d:Depot) CALL vrp.route(d) YIELD from_vertex, to_vertex, vehicle_id CREATE (from_vertex)-[r:Route]->(to_vertex); MATCH (n)-[r:Route]->(m) RETURN n, r, m; ``` Result: ![](https://memgraph.com/docs/pages/advanced-algorithms/available-algorithms/vrp/vrp-2.png) ### Get 2 vehicle route RUn the following query to get a route for two vehicles: ```cypher MATCH (d:Depot, 2) CALL vrp.route(d) YIELD from_vertex, to_vertex, vehicle_id CREATE (from_vertex)-[r:Route]->(to_vertex); MATCH (n)-[r:Route]->(m) RETURN n, r, m; ``` Result: ![](https://memgraph.com/docs/pages/advanced-algorithms/available-algorithms/vrp/vrp-3.png) ```plaintext +------------------------------------------+------------------------------------------+------------------------------------------+ | from_vertex | to_vertex | vehicle_id | +------------------------------------------+------------------------------------------+------------------------------------------+ | (:Depot {lat: 45.7872, lng: 15.9845}) | (:Location {lat: 45.7853, lng: 15.9474}) | 1 | | (:Location {lat: 45.7853, lng: 15.9474}) | (:Location {lat: 45.7806, lng: 15.9353}) | 1 | | (:Location {lat: 45.7806, lng: 15.9353}) | (:Location {lat: 45.7717, lng: 15.9436}) | 1 | | (:Location {lat: 45.7717, lng: 15.9436}) | (:Location {lat: 45.814, lng: 15.9771}) | 1 | | (:Location {lat: 45.814, lng: 15.9771}) | (:Location {lat: 45.8044, lng: 15.9931}) | 1 | | (:Location {lat: 45.8044, lng: 15.9931}) | (:Location {lat: 45.8015, lng: 15.9799}) | 1 | | (:Location {lat: 45.8015, lng: 15.9799}) | (:Location {lat: 45.8006, lng: 15.9715}) | 1 | | (:Location {lat: 45.8006, lng: 15.9715}) | (:Location {lat: 45.8098, lng: 15.97}) | 1 | | (:Location {lat: 45.8098, lng: 15.97}) | (:Depot {lat: 45.7872, lng: 15.9845}) | 1 | | (:Depot {lat: 45.7872, lng: 15.9845}) | (:Location {lat: 45.8221, lng: 16.0195}) | 2 | | (:Location {lat: 45.8221, lng: 16.0195}) | (:Depot {lat: 45.7872, lng: 15.9845}) | 2 | +------------------------------------------+------------------------------------------+------------------------------------------+ ```