• Martin Macík Faculty of Operation and Economics of Transport and Communications, University of Žilina
  • Jozef Štefunko Faculty of Operation and Economics of Transport and Communications, University of Žilina
Keywords: Postal network, graph theory, heuristic methods, genetic algorithm, traveling salesman


High level of competition on postal market increases demands on reliability of postal services and lowering of transport costs. This can be achieved by optimizing the routing of postal vehicles. The article discusses the possibilities of such optimization by using graph theory. It describes basic methods of finding optimal routes using a graph. The approach, used in this article, assesses the possibility of applying meta-heuristic solution to the traveling salesman problem in the postal sector. Simulation of methods described has been applied on a regional postal network. Results showed that the software used proves to be sufficiently functional for the field of postal transport networks.


Bektas, T. (n.d.). The multiple traveling salesman problem: An overview of formulations and solution procedures. Omega, 209-219.

Bianchi, L., Knowles, J., & Bowler, N. (n.d.). Local search for the probabilistic traveling salesman problem: Correction to the 2-p-opt and 1-shift algorithms. European Journal of Operational Research, 206-219.

Carter, A., & Ragsdale, C. (n.d.). A new approach to solving the multiple traveling salesperson problem using genetic algorithms. European Journal of Operational Research, 246-257.

Čorejová, T., Achimský, K., Fitzová, M., & Kajánek, B. (1995). Projektovanie sietí v pošte I. [Designing networks in postal industry I.]. Žilina, Slovakia: Edičné stredisko VŠDS. 101-143

Daskin, M. S. (2013): Network and discrete location: Models, algorithms and applications (2nd ed.). Hoboken, NJ: John Wiley & Sons. 212-260

Gross, J., & Yellen, J. (1999). Graph theory and its applications. Boca Raton, FL.: CRC Press.

Hynek, J. (2008). Genetické algoritmy a genetické programovaní [Genetic algorithms and genetic programing]. (Vol. 1). Praha, Czech Republic.

Janáček, J. (2006). Optimalizace na dopravních sítích [Optimization of transport networks]. Žilina, Slovakia: EDIS.

Johnson, D., & McGeoch, L. (n.d.). The traveling salesman problem: A case study. S.l.: [s.n.].

Karapetyan, D., & Gutin, G. (n.d.). Lin–Kernighan heuristic adaptations for the generalized traveling salesman problem. European Journal of Operational Research, 221-232.

Madleňák, R. (2007). K možnostiam organizácie pružnej poštovej prepravnej siete [Organizational options for flexible postal transport network]. Perner’s contacts, 2(1) Retrieved March 8, 2015, from http://pernerscontacts.upce.cz. 68-75

Osman, I. (1996). Meta-heuristics: Theory & applications. Boston: Kluwer Academic.

Palúch, S. (2001). Teória grafov [Graph theory]. Žilina, Slovakia: EDIS. 18-39

Seidighpour, M., & Darani, M. N. (2011). An Effective Genetic Algorithm for Solving the Multiple Traveling Salesman Problem. Journal of Optimization in Industrial Engineering, 8, 73-79.

Yadlapalli, S., Malik, W., Darbha, S., & Pachter, M. (n.d.). A Lagrangian-based algorithm for a Multiple Depot, Multiple Traveling Salesmen Problem. Nonlinear Analysis: Real World Applications, 1990-1999.