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 to it
- weight: that has to be picked-up from it or delivered to it
- cube: the cubic volume, that has to be picked-up from it or delivered to 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
- consumption (for car and truck): in l/100km and kwh/100km (for electric)
- license plate (for car and truck)

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