SOLUTION OF TRAVELLING SALESMAN PROBLEM FOR WHOLESALE OUTLAYS CONSIDERING REPEATED VISITATION OF CERTAIN SALES OUTLETS

Nataliia Matsiuk

Abstract


This paper presents the solving of the travelling salesman problem with repeated visitation of several outlets. The genetic algorithm was used as a technique for the finding the shortest route in the case of visiting every destination point. The three cases are described in the present research: the solving of the Euclidean travelling salesman problem, the solving of the travelling salesman problem considering the region transportation network and the solving of the travelling salesman problem with repeated visitation of some sales outlets. The solving algorithm which involves partitioning the route into sections without repeated visits to sales outlets has been proposed. Obtained results were combined into one which was considered as optimized for a given route. As a result of our investigation we have proposed the optimized routes that are up to 29% shorter than the actual ones used by the wholesale trade enterprises. As we can see this methodology provides a significant reduction of the transportation expenses of such organizations.


Keywords


travelling salesman problem, genetic algorithm, near optimal route, wholesale outlays

Full Text:

PDF

References


Bi, S., Dong, X., & Ma, Y. (2012). The Design and Analysis of TSP Problem Based on Genetic Algorithm and Ant Colony Algorithm. International Journal of Education and Management Engineering, 2(9), 56-60.

Davendra, D. (Ed.). (2010). Travelling Salesman Problem, Theory and Applications. InTech. doi:10.5772/547

Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Reading, MA: Addison-Wesley.

Goodman, S. E., & Hedetniemi, S. T. (1977). Introduction to the design and analysis of algorithms. McGraw-Hill.

Holland, J. H. (1992). Adaptation in Natural and Artificial Systems. An Introductionary Analysis With Application to Biology? Control and Artificial Intelligence. Cambridge, MA, USA: MIT Press.

Kouki, Z., Chaar, B. F., & Ksouri, M. (2009). TSP based Evolutionary optimization approach for the Vehicle Routing Problem. 2nd Mediterranean Conference on Intelligent Systems and Automation (pp. 373-376). Melville, N.Y.: American Institute of Physics.

Nilsson, C. (2003). Heuristics for the Traveling Salesman Problem. Retrieved from Technical University Koshice: http://web.tuke.sk/fei-cit/butka/hop/htsp.pdf

Zhong, W. (2003). Using Traveling Salesman Problem Algorithms to Determine Multiple Sequence Alignment Orders. Athens.


Refbacks

  • There are currently no refbacks.