Posts Tagged ‘routing’

Routing problems in transportation

April 10, 2010 2 comments

What is a routing problem?

According to Ann Campbell from University of Iowa, the objective of routing problems in transportation is “to minimize the distribution costs during the planning period without causing stockouts at any of the customers”.

The most general case can be modelized by the Vehicle routing problem that broadly speaking consists on:

  • Service a number of customers.
  • Fleet of vehicles
  • Looking for an optimal solution

It can be applied to several fields. In logistics, for instance, we could use it on invenvtory routing. This is an interesting case study of inventory routing:

“The Inventory Routing Problem (IRP) is concerned with the repeated distribution of a set of products from several facilities to a set of customers over a given planning horizon. The facilities produce these products at given rates and have ample storage capabilities for the products. The customers consume products at a given rate and have limited storage capabilities. A fleet of vehicles is available at each of the facilities as well as a set of drivers. The objective is to minimize the overall costs during the planning period.”

You can get the full case study including some data sheets by clicking here.

How can we solve a routing problem?

There are different ways to solve a routing problem, like:

Using graphs:

Using a graph is a very good way to represent this type of problems. Besides representing it graphically, there are other 2 interesting representations (Introduction to Algorithms Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest):

  • As a collection of adjacency lists: It provides a compact way to represent sparse graphs (|E| is much less than |V|^2).
  • Adjacency matrix: It’s use when the graph is dense (|E| is close to |V|^2).

There is open source software to represent graphs. I like quite a lot one called Grafos. Regardless the webpage is in Spanish,  it’s quite good and simply to use. You can download it by clicking here.

General cases:

Routing vehicles:

Travel salesman problem:

Travel salesman with m routes:

Specific cases of the routing problem:

There are other interesting specific cases, like when you don’t know with certainty when planning customers loads demands. That one is called vehicle routing problem with stochastic demand. Here you can find some articles about this topic:

Read more…

Categories: Distribution Tags: , ,