ROUTE OPTIMIZATION OF MULTIPLE-AGENT TRAVELLING SALESMAN PROBLEM

Mario Galić

doi:10.51704/cjce.2018.vol4.iss1.pp36-42

Authors

Mario Galić Josip Juraj Strossmayer University of Osijek, Faculty of Civil Engineering and Architecture, Vladimira Preloga 3, 31000, Osijek, Croatia

DOI:

https://doi.org/10.51704/cjce.2018.vol4.iss1.pp36-42

Keywords:

Route optimization, travelling salesman problem, multiple-agent, evolutionary algorithm

Abstract

Route optimization is quotidian engineering problem. Problem of finding the optimal and suboptimal routes is one of the most studied optimization problem. In this paper, author firstly presented a short literature overview of the history of routing problems and namely travelling salesman problem (TSP). In the second chapter author presented the usual mathematical formulations for single and multiple agent travelling salesman problem (TSP and mTSP). In chapter three, author used a case study TSP given in the literature which involves one agent and fifteen nodes, modelled the problem in a standard software package (MS Excel’s Visual Basic VBA), solved it by the evolutionary solver in the same software package, confirmed the result and withal verified the model. In the following step, author added one more agent as a hypothetical case of mTSP and solved the problem. In the final chapter author discussed the results and gave conclusions which can be used for further development of the study. The solution was gained in reasonably short computational time and considered as optimal.

Metrics

Metrics Loading ...

References

EULER, L. 1736: Solutio problematis ad geometriam situs pertinentis, Commentarii academiae scientiarum Petropolitanae, Vol. 8, pp. 128-140.

EULER, L. 1759: Solution d’une question curieuse qui ne paroit soumisea aucune analyse, Mémoire de l’Académie des Sciences de Berlin, Vol. 15, pp. 310-337.

BIGGS, N.; LLOYD, E. K.; WILSON, R. J. 1976: Graph Theory 1736-1936, Clarendon Press, Oxford, UK.

LAWLER, E. L.; LENSTRA, J. K.; KAN, A. R.; SHMOYS, D. B. 1985: The traveling salesman problem: a guided tour of combinatorial optimization, Wiley UK.

VOIGT, B. F. 1832: Der Handlungsreisende, wie er sein soll und was er zu thun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiss zu zu sein, Ilmenau, Germany.

FLOOD, M. M. 1956: The traveling-salesman problem, Operations Research, Vol. 4, (1), pp. 61-75.

DANTZIG, G.; FULKERSON, R.; JOHNSON, S. 1954: Solution of a large-scale traveling-salesman problem, Journal of the operations research society of America, Vol. 2, (4), pp. 393-410.

DORIGO, M.; GAMBARDELLA, L. M. 1997: Ant colonies for the travelling salesman problem, biosystems, Vol. 43, (2), pp. 73-81.

WONG, L.-P.; LOW, M. Y. H.; CHONG, C. S. 2010: Bee colony optimization with local search for traveling salesman problem, International Journal on Artificial Intelligence Tools, Vol. 19, (03), pp. 305-334.

OUAARAB, A.; AHIOD, B.; YANG, X.-S. 2014: Discrete cuckoo search algorithm for the travelling salesman problem, Neural Computing and Applications, Vol. 24, (7-8), pp. 1659-1669.

FENG, X.; LAU, F. C.; GAO, D. 2009: A new bio-inspired approach to the traveling salesman problem. International Conference on Complex Sciences: Springer; pp. 1310-1321.

YANG, X.-S.: A new metaheuristic bat-inspired algorithm Nature inspired cooperative strategies for optimization (NICSO 2010), Juan R. González, David Alejandro Pelta, Carlos Cruz, Germán Terrazas, Krasnogor N (ed.), Springer, 65-74, 2010.

JATI, G. K. 2011: Evolutionary discrete firefly algorithm for travelling salesman problem. In: Bouchachia A, editor. Adaptive and Intelligent Systems - ICAIS 2011. Klagenfurt, Austria: Springer; pp. 393-403.

BEKTAS, T. 2006: The multiple traveling salesman problem: an overview of formulations and solution procedures, Omega, Vol. 34, (3), pp. 209-219.