OPTIMIZATION OF POSTAL ROUTES BY GENETIC ALGORITHM FOR SOLVING THE MULTIPLE TRAVELING SALESMAN PROBLEM
Abstract
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.References
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.
Copyright information
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License (Creative Commons Attribution License 3.0 - CC BY 3.0) that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
info@iseic.cz, www.iseic.cz, ojs.journals.cz