Planning and optimisation of vehicle routes for fuel oil distribution

Fuel oil distribution companies service their customers with fleets of tanker lorries. The problem is to find a set of routes minimising the number of travelled kilometres and the number of used vehicles, while satisfying customer demand. There are three major problems why traditional Operations Research techniques are not enough to deal with this problem, which is known as the Vehicle Routing Problem. First of all, it is inherently combinatorial, and exact algorithms fail when the dimension of the problem (number of customers and orders) reaches a reasonable size. Secondly, the problem can be extended and made more complex in many ways, for instance, adding more than one depot, considering more than one vehicle type, accounting for stochastic customer demand (the exact requested quantity is known only at delivery time), considering time windows during which the customers must be served, taking into account vehicle accessibility restrictions (some customers cannot be served by some vehicles). Finally, the problem can become very different when we consider on-line distribution, that is, we accept delivery orders for lorries which are en route. There, geolocation of customers and vehicles, online data transfer among lorries and the base station, have an impact as great as the solution strategy.