Routing problems in transportation
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:
 Dynamic programming
 Linear programming
 Genetic algorithms
 Bellman Ford Algorithm: It really computes the shortest path so probably it could not be used on routing because there would be some nodes without service. The video is really interesting.
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:
 A vehicle routing problem with stochastic demand – Dimitris J. Bertsimas – MIT: Here Prof. Bertsimas explains how to deal with this kind of problems. It’s interesting because by reading his webpage (research section) he says that his goal is “to propose a tractable theory for optimization under uncertainty”

Planning approximations to the average length of vehicle routing problems with time window constraints – Portland State University: Dr. Miguel Andres Figliozzi studies the average length of vehicle routing problems with time window, route duration and capacity constraints.
 Vehicle routing problem with time windows and a limited number of vehicles – Hoong Chuing Lau, Melvyn Sim and Kwong Meng Teo
Recent comments