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” Vehicle routing problem with time windows and a limited number of vehicles – Hoong Chuing Lau, Melvyn Sim and Kwong Meng Teo
Free time window:
In routing problems it’s interesting the concept of ”Free time window”. It can be defined as a time interval in which the resource load is less than the capacity. The interval should be at least as long as the minimum travel time
Other interesting stuff:
You can also use some specifi software to study this kind of problems. Particularly, Knime is a good open source software that could be useful to modelize this type of problems. I’m still looking how to do it.
You can find here some other interesting slides related with multi stage routing. It shows some interesting applications to airports or traffic control.
Source: