# Vehicle routing problem (VRP)¶

Easily find the best route/routes to visit a multitude of stops using one or more vehicles.

## Concepts¶

### Stop¶

It is the location that has to be visited (a customer).

- It has the following fields:
- the descriptive fields:
id: it is automatically assigned after the stop is saved; the user cannot set it

name

address

email

phone number

- the restrictive fields:
type: pick up or delivery

number of pieces: that have to be picked-up from it or delivered at it

weight: that has to be picked-up from it or delivered at it

cube: the cubic volume, that has to be picked-up from it or delivered at it

service time: how much time does the vehicle stay at this stop to do its job (ex: to unload the pieces)

time-window: within which the stop must be visited

revenue: which has to be received from this stop

### Vehicle¶

It is used to visit the stops. It can be a car or pedestrian (*soon: bike and truck*).

- It has the following fields:
- common fields:
id: it is automatically assigned after the vehicle is saved; the user cannot set it

name

type: car or pedestrian (

*soon: bike and truck*)is operational

- car (
*bike,truck*) fields: manufacturer

model

- fuel type (for car and
*truck*) gasoline standard

gasoline premium

diesel standard

diesel premium

electric

lpg

- fuel type (for car and
consumption (for car and

*truck*): in l/100km and kwh/100km (for electric)license plate (for car and

*truck*)

- car (

### Optimization¶

It is the input of the vehicle routing problem.

- It has the following fields:
id: it is automatically assigned after the optimization is saved; the user cannot set it

stops: the stops the have to be visited

configuration parameters (see below): the parameters of the optimization

number of vehicles: how many vehicles can be used to visit the stops

vehicles constraints (see below): it can be set one set of constraints for each vehicle or only one set for all the vehicles

start stops: from which stop to start the route; it can be set one start stop for each route or only one start stop for all the routes

end stops: by default the vehicle will return to the start stop, but you can set to end the route at a certain stop; it can be set one end stop for each route or only one end stop for all the routes

### Route¶

It is a part of the optimization’s solution. The solution is a list of routes.

- It has the following fields:
id: it is automatically assigned after the route is saved

id optimization: the id of the optimization for which the route was created

stops: the visited stops, arranged in the optimal visiting order

configuration parameters (see below): the parameters of the route

vehicle constraints: the constraints of the route’s vehicle

start stop: the stop from which the route starts

end stop: the stop to which the route ends

total distance: the total distance of the route in the distance unit set in the configuration parameters

cost: the cost of the fuel that is needed to travel the route

### Configuration parameters¶

Are a set of parameters used to customize the entire optimization and the search of the solution (for example: if the optimization is optimized by time or by distance, the distance unit, the type of the vehicles that are used to visit the stops, etc). They are set to an optimization and to its routes.

- It has the following fields:
name: the name of the optimization or the route

ignore time-window: specifies if the time-window has to be ignored or not

optimization criterion: specifies if the optimization is made by time or by distance

- optimization quality: specifies the accuracy of the result
fast: the first solution found, not an accurate one

optimized: an optimized solution

best: the best solution found in the amount of time specified by the parameter “maximum search time”

maximum search time: how long can the algorithm search for a solution

maximum wait time: set how much time is a vehicle allowed to wait at a stop or before visiting the next stop, in order to arrive at the next stop between its time-window

- route type: the type of the routes of the returned solution
round route: the route ends at the start stop (circuit)

end anywhere: the route will end at the most efficient stop selected by the algorithm

specified end stops: the route will end at the specified stops

vehicle type: what type of vehicle will be used to visit the stops; it can be car or pedestrian (

*soon: bike and truck*)distance unit: in what unit is the distance calculated (meters or miles)

- matrix build type: what formula it is used to calculate the distance matrix (and time matrix)
set: by the user using the “distance matrix” and “time matrix” parameters

euclidian: the distance between 2 stops is calculated with the Euclidian distance formula (in straight line) and the result is rounded up to the next integer

exact euclidian: similar to the euclidian formula but without rounding up the result

geodesic: the distance between 2 stops is calculated in straight line taking into consideration the curve of the Earth

manhattan: the distance between 2 stops is calculated with the Manhattan distance formula

real: real values for the distance and time values are used

- restrictions: if the “matrix build type” is “real” you can set the road type that you want to avoid for the calculation of the distance and time matrices
none

tolls

highways

distance matrix: if the “matrix build type” is “set”, use this parameter to set the distance matrix values

time matrix: if the “matrix build type” is “set”, use this parameter to set the time matrix values

sequence pairs: you can specify a list of sequence pairs; a sequence pair is a pair of two stops; both stops will be visited in the same route, the second stop will be visited after the first one and the number of pieces, weight and cube from the first stop will be delivered at the second stop

fixed stops sequences: you can specify that some stops have to be visited in a specific fixed order

### Vehicle constraints¶

Are a set of constraints that will be applied to the optimization’s vehicle(s) (for example the maximum number of weight that the vehicle can carry, the maximum distance that the vehicle can travel, etc).

- It has the following fields:
vehicle: the vehicle on which these contraints are applied

start time: when the vehicle can start its route

end time: the vehicle should end its route before this time

maximum number of pieces: that the vehicle can carry

maximum weight: that the vehicle can carry

maximum cube: maximum cubic volume that the vehicle can carry

mininum number of stops: that the vehicle must visit

maximum number of stops: that the vehicle can visit

minimum distance: that the vehicle must travel

maximum distance: that the vehicle can travel

### Territory¶

It is used to group stops together in order to easily use them in an optimization.

- It has the following fields:
id: it is automatically assigned after the territory is saved; the user cannot set it

name

type: polygon, circle, rectangle

- data: defines the terriory
for polygon: a list of points

for circle: the coordinates of the circle’s center and the radius (in meters)

for rectangle: 2 diagonally opposite points

color

stops: the stops from the agenda that are located inside the territory

- Add optimization with a single vehicle
- Add optimization with a single vehicle and different start and end stops
- Add optimization with multiple vehicles and a single start stop
- Add optimization with multiple vehicles and multiple start stops
- Add optimization with multiple vehicles and multiple end stops
- Add optimization with fixed stops sequences
- Add optimization with sequence pairs
- Add optimization with set matrices
- Add optimization where the stops have the all fields set
- Generate territories
- Extra