The Vehicle Routing Problem (VRP)

In the last session we shorty talked about the Vehicle Routing Problem. A generic name given to a class of problems in which a set of routes for a fleet of vehicles based at one or several depots must be determined for a number of geographical dispersed cities or customers. With this Blog I want you to give the chance to get a deeper dive in this theory.

The objective of such a VRP problem is not always just the minimization of costs many more objectives are possible and depends on the particular problem:

  • Minimize time travel
  • Minimize distance
  • Minimize the number of vehicles used
  • Maximize the time balance of used vehicles

But to reach these goals, several problems can occur which differ from the initial problem.  To overview this problems the literature suggested sever classes of VRP problems, which I now want you to introduce:

Distance Constrained VRP (DVRP)

  • A possible route is constrained by the maximum route duration
  • This reacts on constraints of the maximum driving duration of the drivers or on the problems with highly perishable goods

VRP with Time Window (VRPTW)

  • All customers must/should be served within a certain time window
  • This react on constraint for example of the question “at what time am I allowed to enter pedestrian zones with my vehicle”?

Time Dependent VRP (TDVRP)

  • Travel time between two locations depends both on distance and time of day
  • Reaction on rush hours in the morning and in the evening

There are many more options of this Problem and I just wanted to show how much theory and know-how can be hidden behind a single buzzword like VRP.

Source:

Stadtler, H., Fleischmann, B., Grunow, M., Meyr, H., Sürie, C. (2011) Advanced Planning in Supply Chains – Illustrating the Concepts Using an SAP APO Case Study, Berlin et al., Springer, ISBN 978-3-642-24214-

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s