this is why other solutions will not be quite
traversed, creating lock situations around not so
optimal solutions.
Figure 7: Solving time sum for every algorithm.
In Figure 7 it can be seen as all the algorithms show
similar resolution times, with the exception of
AS
rank
, but this is quite logical due to the nature of
the algorithm, as it ranks groups of ants, which of
course takes some calculation power in the ordering
and selection of the agents depending on the quality
of the solution found.
4 CONCLUSIONS
The many daily problems that appear in road
transport show the great need of applications
destined to help in the management of road fleets;
applications capable of finding the best possible
routes, and assigning them efficiently to the different
vehicles that form up the fleet. This is why it is
important to make the right choice of the algorithm
better suited for the problem to solve.
ACO meta-heuristic has some very beneficial
features for the resolution of this kind of situations:
it is capable of finding and optimal or quasi-optimal
solution in a reasonable time, it can optimize
multiple criteria simultaneously and it can be
adapted to work in a dynamic environment. But
these optimization techniques present themselves
under several different algorithms; this is why we
will have to choose what algorithm use in order to
solve each part of the problem.
Once all performance testing and the studies of those
algorithms over the solution of the transport fleet
management problem (both the optimal route
calculation and the resource allocation) were over
we were able to see that there are two algorithms
whose solutions’ quality stood out from the rest:
• The AS
rank
algorithm finds the best solution to
the route calculation problem, but its time and
resources consumption is something higher than
the rest of the algorithms (it can get better using
other ordering faster method). However when it
gets to the resource allocation module, it shows
a more irregular behaviour, spends more time
than the rest and does not easily find the optimal
solution.
• ACS is far from ideal in the route calculation
module; it is however the best in the allocation
part: it finds the higher quality solutions; it is
quite stable and offers a reasonable execution
time.
After analyzing the conclusions shown in this
document, the next step will be the incorporation of
dynamic parameters to the system (road network
status, weather conditions, etc.) when determining
the optimal route.
REFERENCES
Asmar, D. C., Elshamli, A., Areibi, S. A Comparative
Assessment of ACO Algorithms Within a TSP
Environment. DCDIS 2005, Guelph, Ontario, Canada.
July 2005.
Bonabeau, E., Dorigo, M. and Theraulaz, G. Swarm
Intelligence: From Natural to Artificial Systems,
Oxford University Press, 1999.
Bullnheimer, B., Hartl, R. F., Strauβ, C. A new Rank-
Based Version of the Ant System – A Computational
Study. Technical Report, Institute of Management
Science, University of Vienna, 1997.
Cordón, O., Fernández, I., Herrera, F. and Moreno, L. A
New ACO Model Integrating Evolutionary
Computation Concepts: The Best-Worst Ant System.
From Ant Colonies to Artificial Ants: Second
International Workshop on Ant Algorithms
(ANTS'2000), pp. 22-29. Brussels (Belgium), 2000.
Corne, D., Dorigo, M. and Glover, F. New Ideas in
Optimization, McGraw-Hill. 1999.
Dorigo, M. and Di Caro, G. and Gambardella, L. M. Ant
Algorithms for Discrete Optimization. Artificial Life,
5(2), 137-172. 1999.
Dorigo, M. and Gambardella, L.M. Ant colony system: a
cooperative learning approach to the travelling
salesman problem. IEEE Transactions on Evolutionary
Computation,1(1):53-66. 1997.
Dorigo, M. and Stützle, T. Ant Colony Optimization.
Massachussets Institute of Technology. 2004.
Perozo Rondón, F. J. Sistema de gestión dinámica de
flotas usando localización GPS/GSM y programación
evolutiva para la optimización de recursos. Tesis
doctoral. University of Valladolid, 2002.
Stützle, T. and Hoss, H. MAX-MIN Ant System. Preprint
submitted to Elsevier Science, 5. November 1999.
ACO BASED METHOD COMPARATION APPLIED TO FLEET MANAGEMENT PROBLEM
539