ANTROUTE - LARGE SCALE DYNAMIC OPTIMISATION OF VEHICLE ROUTES AND FLEETS

Dario Coltorti
AntOptima SA, Lugano, Switzerland

ABSTRACT

The software product AntRoute is developed by AntOptima, a spin off company of the Swiss Research Institute for Artificial Intelligence IDSIA, Istituto Dalle Molle di Studi sull'Intelligenza Artificiale. IDSIA is one of the leading Institutes in Ant Colony Optimisation (ACO), a powerful method to solve different types of combinatorial optimisation problems, especially vehicle routing.
The developed algorithms are among the best currently worldwide available and they have found new best-known solutions for many benchmark instances.
With AntRoute AntOptima implements this technology for Logistics provider to speed up their business in terms of time and efficiency. The integrated high performance Tour Optimizer of AntRoute based on ACO and is automatically able to optimize thousands of daily orders in a few minutes considering the company related constraints like truck fleet, client time windows, unit load, access limitation, etc. The Tour Optimizer can be adapted to the needs of the most transportation industries, how different AntRoute implementations demonstrate.

Key words: Ant Colony Optimisation, Transport Planning, Vehicle Routing, AntOptima, Logistics provider.

INTRODUCTION

Most problem faced by logistics providers have been known for centuries, think of the Chinese postman problem, first formulated by Euler in 1736. These problems have the ugly characteristic of being combinatorial, that is, all the possible combinations of the decisions and variables must be explored to find a solution of the problem. The downside of this is that as the number of decisions and variables increase (and in real world problems is quite easy to find problems with hundreds of variables) the time required to find a solution becomes rapidly unaffordable.

Heuristics methods have been devised to explore only parts of the search space, concentrating in those parts that appear to promise a probable improvement of the solutions, thus reducing the time required to obtain a solution, which is often sub-optimal, but already a good improvement from the starting situation. A heuristic makes use of peculiar characteristics of a problem and exploits them to find a solution. Other empirical methods do not exploit only the problem characteristics but especially the analogy with other optimisation methods found in Nature.
Such heuristic methods, independent of the problem, are called Metaheuristics.

Ant Colony Optimisation (ACO) is such a heuristic. Based on the observation that ants find the optimal path between a food source and their nest, a computer analogy has been implemented and applied to various problems, ranging form the traveling salesman problem, to the sequential ordering problem and the vehicle routing problem.

FROM THEORY TO PRACTICE

Metaheuristics are a powerful tool to solve combinatorial optimisation problems, which are so frequent in logistics and transports, but they cannot be applied blindly.

In transportation one of the most important tasks is: Given a fleet of vehicles and a set of customers asking for pick-up and delivery operations the goal is to minimize a given cost function. In theory this challenge is known as vehicle routing problem, where metaheuristics, especially ACO, are finding best solutions in terms of efficiency and calculation time. Due to the excellent theory results from Swiss Research Institute Dalle Molle for Artificial Intelligence (IDSIA) and the support of Swiss National Science Foundation ACO reached the international scientific break through.

To apply these methods in practice further steps had been necessary. The algorithms had to be adapted to many different practical constraints of transportation sector:

• Accessibility based on vehicle type,
  
• Distribution areas,
  
• Deliveries with multiple time windows,
  
• Urgent requests,
  
• Stochastic travel time,
  
• Multiple days planning,
  
• Stochastic customer demand,
  
• Unexpected events.
  

Inspired from the scientific success IDSIA was and is involved in projects where the Institute in collaboration with industrial partners and the support of European Commission and Swiss Commission of Technology and Innovation develops vehicle routing algorithms, which are customized to the transportation sector to reduce the economical and environmental impact.

After several successful practice implementations the market requested concrete applications. AntOptima as a spin off of IDSIA was founded with the mission to parameterize the powerful algorithms for transportation companies and to satisfy the transportation industries needs. One of the present main application product is AntRoute.

ANTROUTE

AntRoute optimizes distribution logistics thanks to an integrated approach to the various features of the problem, thus rapidly enabling the user to:

• optimize the use of the vehicle fleet (type and quantity of the used vehicles, workload scheduling, capacity optimisation),
  
• improve the efficiency (less kilometers, less time, more delivered goods, all of this within the time constraints),
  
• increase customer satisfaction, thanks to the focus on service level and punctuality.
  

The automatic generated and practical tours of AntRoute consider:

• multiple goal functions,
  
• flexible areas,
  
• tour building attributes,
  
• different loads units,
  
• heterogeneous fleet (trailers, semi-trailers, etc.),
  
• single and multi-depot optimisation problems,
  
• third-party vehicles.
  

AntRoute can be used to strategically plan the management of the fleet of vehicles and of the resources under alternative scenarios. It also allows to gather and analyze statistical data on the distribution process and to deduce trends and make forecast. It can be easily integrated in existing company systems and it can dialogues with most supply-chain management software tools.

The product uses standard road network data and it can perform the daily optimisation of fleets in primary and secondary distribution processes ranging from a few tens to thousands of vehicles, how the two following case studies show.

REAL CASE STUDY PINA PETROLI (SME)

With many years of experience, Pina Petroli SA is now a constant presence in Ticino economy. The development that the company knew from 1949, year of its foundation, is quite visible in the dimension of the depot of Grancia, with fifteen great tanks, twelve vehicles and thirty employees. These technical and human resources make Pina Petroli a leader in the area, profit in heating oil distribution in the whole Ticino and Grigioni southern valley. Everyday Pina Petroli carries out hundred of deliveries, satisfying the customers needs and their details. Pina Petroli chose AntOptima to implement new technologies in order to optimize transportations and to serve the customer with always greater efficiency and precision.

AntRoute (resulting from Dyvoil project) was parameterized as a software application for the management and optimisation of heating oil distribution, which allows to:

• optimize the use of the fleet of vehicles,
  
• forecast the customers' consumption and reduce the costs of distribution,
  
• improve the efficiency (less miles, less time, more deliveries),
  
• increase customer satisfaction, thanks to real time management of urgent deliveries.
  

REAL CASE STUDY NUMBER 1 LOGISTICS GROUP

Number 1 Logistics Group is the Italian logistic operator leader in grocery with 400.000.000 of necks managed, 2.500.000 delivers for about 2.100.000 tons, 250.000.000 of km traveled in a year, 2.600 vehicles and 110.000 customers served. At the beginning its activity was born to distribute Barilla's products in different depots and supermarkets and to transport the grain from the production areas to the productive sites. Once activated this logistic process, it has thought to develop it by offering the same service to other companies that should transport goods in the same depots and supermarkets.

A primary phase allows the goods to come from the origin zone to the final distribution zone using big trucks. When it is possible and suitable, the final customer is served directly by these trucks, otherwise the goods are collected in local logistic centers. In these centers the goods are consolidated and distributed locally by smaller trucks (secondary phase).

Number 1 chose AntRoute for the automatisation of the route creation phase and for the optimization of the goods distribution. The goal is to maximize the transportations efficiency respecting the constraints on the opening time of the different depots and the limits established from the law on the travel times of each vehicle. The routes considered cover the whole Italy with services in one, two and sometimes also three days. Based on initial information, AntRoute optimizes in a few minutes pick-up & delivery orders to satisfy the requirements and the specific needs of Number1.

CONCLUSIONS

AntRoute is a powerful instrument for Transportation companies, which would like to improve their planning and distribution processes in terms of efficiency and calculation time. The intelligent software uses state-of-the art optimisation algorithms, invented at the IDSIA, during various project, co-financed by the Swiss National Research Fund and by the Swiss Commission for Technology and Innovation. These algorithms, inspired by ant colonies, learn from past experience, adapt to unforeseen circumstances, and they are able to solve with extreme speed complex combinatorial optimisation problems, intractable with traditional algorithms.

Given the great effort in the recent years of logistics and transportation companies in the integration with the existing data exchange infrastructure it brings new great opportunities to make an intelligent use of the data and AntRoute is ready to take this chance.

Other powerful products of AntOptima are AntNgage (Tariffoptimisation of transport services considering external and internal fleet) and Tourplanner (software tool for the dynamic optimisation of vehicle routes and logistic flows, especially designed for the needs of SMEs).

REFERENCES

Bonabeau E., Dorigo M., Theraulaz G., 2000. Nature, Inspiration for optimisation from social insect behavior, Volume 406 Number 6791, London, 39-42.

Bonabeau E., Meyer Ch., 2001. Harvard Business Review, A Whole New Way to Think about Business, 5/2001, Boston, 106-114.

Casagrande, N., Gambardella L.M., Rizzoli A.E., 2001. ECCO XIV, Conference of the European Chapter Solving the vehicle routing problem for heating oil distribution using Ant-Colony Optimisation on Combinatorial Optimisation, May 31-June 2 2001, Bonn, Germany.

Coltorti D., 2005. Ameisensysteme, Verfahrensüberblick und betriebswirtschaftliche Anwendungs-potenziale.

Dorigo M., Di Caro G. and Gambardella L. M., 1999. Artificial Life, Ant Algorithms for Discrete Optimisation, 5 (2), Cambridge MA, 137-172.

Gambardella L.M., Taillard E., Agazzi G., 1999. MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows, In D. Corne, M. Dorigo and F. Glover, editors, New Ideas in Optimisation, McGraw-Hill, London, 63-76.

Gambardella L.M., Dorigo M., 2000. INFORMS Journal on Computing, An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem, vol.12(3), Cincinnati, 237-255.

Gambardella L.M., Taillard E., Dorigo M., 1999. Journal of the Operational Research Society, Ant colonies for the Quadratic Assignment Problem, 50, Hampshire, 167-176.

Heinzelmann E., 2006. Logistik & Fördertechnik, Intelligenz von Ameisen im Dienst der Logistik, 10/2006, Basel, 38-39.

Heinzelmann E., 2003. Swiss Engineering, Machen wir's den Ameisen nach, 06/2003, Zürich, 2-6.

Kloss K., 2006. DVZ, Auf die Ameisen gekommen, Nr.38, Hamburg, 6.

Schmundt H., 2000. Der Spiegel, Der Duft der Daten, n.46, November 13th, Hamburg.

http://www.derspiegel.de/spiegel/0,1518,102399,00.html.

ANTROUTE - WIELKOSKALOWA OPTYMALIZACJA ZARZĄDZANIA FLOTĄ POJAZDÓW

STRESZCZENIE Oprogramowanie AntRoute zostało opracowane przez AntOptima, firmę stworzoną przez Swiss Research Institute for Artificial Intelligence IDSIA oraz Istituto Dalle Molle di Studi sull'Intelligenza Artificiale. IDSIA to jeden z wiodących instytutów w dziedzinie Ant Colony Optimisation (ACO), metody rozwiązywania różnego typu złożonych zagadnień optymalizacyjnych, szczególnie w zakresie optymalizacji tras.
Zastosowane w tym rozwiązaniu algorytmy są obecnie najlepszymi z dostępnych na rynkach światowych są używane w wielu wiodących implementacjach.
AntRoute umożliwia Logistyce poprawić zarówno wydajność jak i efektywność działalności. Zintegrowany Tour Optimiser (moduł optymalizacji tras), oparty na ACO umożliwia optymalizację tysięcy dziennych zamówień w przeciągu paru minut, przy uwzględnieniu takich ograniczeń jak: posiadana flota samochodowa, żądany czas dostawy, jednostki załadunkowe, ograniczenia ruchu, itp. Tour Optimiser może być dostosowany do potrzeb większości przedsiębiorstw spedycyjnych, czego dowodzą już przeprowadzone wdrożenia.

Słowa kluczowe: Ant Colony Optimisation, planowanie transportu, trasa pojazdu, AntOptima, dostawca logistyczny.

ANTROUTE - DYNAMISCHE OPTIMIERUNG DER ROUTEN UND DES LOGISTISCHEN GÜTERFLUSSES

ZUSAMMENFASSUNG. Das Softwareprodukt AntRoute wurde von der Firma AntOptima entwickelt, eine Spin-off des Schweizerischen Forschungsinstituts für Künstliche Intelligenz (IDSIA), Istituto Dalle Molle di Studi sull'Intelligenza Artificiale. IDSIA ist eines der führenden Institute in Ant Colony Optimisation (ACO), eine leistungsstarke Methode um verschiedene Arten von kombinatorischen Optimierungsproblemen zu lösen, besonders was Vehicle Routing Problems betrifft. Die entwickelten Algorithmen gehören aktuell zu den international Stärksten und Sie haben neue Bestmarken für viele Benchmark Instanzen erzielt.
Mit AntRoute implementiert AntOptima diese Technologie für Logistikdienstleister um Ihre Prozesse zu beschleunigen bezüglich Zeit und Effizienz. Der integrierte Tourenoptimierer von AntRoute basiert auf ACO und ist automatisch in der Lage tausende Bestellungen für einen Tag innerhalb von wenigen Minuten zu optimieren. Dabei werden die unternehmensspezifischen Bedingungen wie Flotte, Kundenzeitfenster, diverse Masseinheiten, Zutrittsbedingungen, etc. mitberücksichtigt. Der Tourenoptimierer kann auf die Bedürfnisse der meisten Transportsektoren angepasst werden, wie verschiedene AntRoute Implementationen zeigen.


Codewörter: Ant Colony Optimisation, Transportplanung, Vehicle Routing, AntOptima, Logistikdienstleister.

Dario Coltorti, lic.rer.pol.
Business Developer
AntOptima SA
Via Fusoni 4 CH- 6900 Lugano
Tel.direct: +41 41 781 39 35
e-mail: dario.coltorti@antoptima.com
www.antoptima.com