mortar board
Vehicle Routing #001

Research and Practise.com

All you need to know, all in one place

The scientific and industrial communities are often unaware of the work of each other. We aim to provide a service where you can find all the information you require, for a specicific specialisation, all on the same web site. We would welcome suggestions for other areas.

Your advert could be here - take a look at our advertising rates
Your advert could be here - take a look at our advertising rates

Vehicle Routing: Models

We are currently preparing this page to outline some of the common (and not so common) models that are used to represent Vehicle Routing Problems.

The surveys page would also be a good place to look if you are looking for a particular model, or just general information about the models that are available.

If you believe that any are missing, please let us know (email: admin@researchandpractise.com)

Models


Capacitated Vehicle Routing Model (Set Partitioning)


This model, for the Capacitated Vehicle Routing Problem, is one of the moset general models. It is based on set-partitioning and the general idea is to minimise the cost, which is represented by cj. The cost could be, for example, the distance. We have a fixed number of customers (V> and also a fixed number of vehicles (K. Note that we are not trying to minimise the number of vehicles used, which is the case in some other formulations.

The model can be formally stated as follows.

CVRP Model

where:

  • q is the the number of feasible routes.
  • cj is the cost associated with route j.
  • xj is a binary variable with xj = 1 if route j is used in the optimal solution; 0 otherwise.
  • aij is a binary variable, where aij = 1 if vertex (customer) i is visited by route j; 0 otherwise.
  • V is the set of vertices (customers).
  • K is the number of vehicles that are available.
  • Constraint (2) ensures that each vertex (customer) is visited exactly once (i.e. it is included in one, and only one, route), with the exception of vertex zero which is usually defined as the depot, where every route starts and ends.
  • Constraint (3) imposes the condition that K circuits (vehicles) are used.
  • Constraint (4) limits the values of xj to zero or one.

We hope you find these pages useful and we welcome your feedback. If you have any comments, please email us at admin@researchandpractise.com.

If you would like to be informed when changes are made to these pages please join our mailing list.