Skip to content

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

    • 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