THE TRAVELLING SALESMAN PROBLEM IN THE ENGINEERING EDUCATION PROGRAMMING CURRICULUM

Authors

  • Yevgeny Gayev National Aviation University
  • Vadim Kalmikov National Aviation University

DOI:

https://doi.org/10.18372/2306-1472.72.11989

Keywords:

combinatorics, discovery based learning methodology, logistics, optimization, programming, programming education, TSP (Traveling Salesman Problem)

Abstract

Objective: To make students familiar with the famous Traveling Salesman Problem (TSP) and suggest the latter to become a common exercise in engineering programming curriculum provided the students master computer science in the easy programming environment MATLAB. Methods: easy programming in MATLAB makes true such modern educational approach as “discovery based” methodology. Results: a MATLAB TSP-program oriented to Ukrainian map is suggested that allows to pictorially demonstrate the process of optimal route search with an option to decelerate or accelerate the demonstration. The program is guessed to be useful both for learning the TSP as one of fundamental logistics problems and as an intriguing programming curriculum excersize. Several sub-programs according to key stone Computer Science Curriculum have also been suggested. This lies in line with recent “discovery based” learning methodology. Discussion: we explain how to create this program for visual discrete optimization, suggest required subprograms belonging to key stone programming algorithms including rather modern graphical user interface (GUI), how to use this MATLAB TSP-program for demonstration the drastical grows of solution time required. Conclusions: easy programming being realized in MATLAB makes dificult curriculum problems attractive to students; it focuses them to main problem’ features, laws and algorithms implementing the “discovery based” methodology in such a way.

Author Biographies

Yevgeny Gayev, National Aviation University

Doctor of Engineering. Professor.

Professor on Aircraft Control Systems Department, National Aviation University, Kyiv, Ukraine.

Education: Kharkiv State University, Kharkiv, Ukraine (1971).

Research area: fluid mechanics and thermal physics, boundary layer theory, mathematics, computer science, history of science.

Vadim Kalmikov, National Aviation University

Student.

Aircraft Control Systems Department, National Aviation University, Kyiv, Ukraine.

Research area: computer science, aerodynamics.

References

Azarskov V.M., Gayev Ye.A. (2014) Suchasne programuvannya [Modern programming, p. 1. Кyiv: NAU. – 256 p.]. (in Ukrainian)

Gayev E.O., Azarskov V.М. (2016) Suchasne programuvannya [Modern Programming, p. 2. Кyiv: NAU. – 197 p.]. (in Ukrainian)

Azarskov V.М., Gayev E.A. (2015) Programmirovanie intensifitsiruet ovladenie nauk studentami [Programming intensifies mastering sciences by students]. Materiali XIY Mizhnarodnoji Konferencii [Materials ХІY International Conference «Industrial hydraulics and pneumatics»], Sumy, pp. 28 -29. (in Russian)

Gayev E.A., Martych. M., Tarak G. (2015) Programmy modelirovaniya sluchainykh yavlenii dlya izucheniya programmirovaniya i matematiki [Programs for modeling random phenomena for learning programming and mathematics]. Information Technologies in Education, 2015, № 23, p. 30-42. (http://ite.kspu.edu/webfm_send/829) (in Russian)

Gayev E.A., Rozhok О., Ovcharchin N. (2014) Zvuk ta muzyka v kursi prohramuvannia [Sound and music in the course of programming]. Software Engineering, 2014, № 3(19), pp. 41 - 48. (in Ukrainian)

https://en.wikipedia.org/wiki/List_of_educatio nal_programming_languages

Discovery-Based Learning. https://en. wikipedia.org/wiki/Discovery_learning.

Entdeckendes Lernen. https://de. wikipedia.org/ wiki/Entdeckendes_Lernen. (in German)

An algorithmic programming language developed within Russian Buran space project. https://en.wikipedia.org/wiki/DRAKON

Computer Science Curriculum 2008. IEEE Computer Society. http://www.acm.org//education /curricula/ComputerScience2008.pdf

A full and modern overview of the Travelling Salesman Problem (TSP). https://en.wikipedia.org/wiki/Travelling_salesman_problem

Golovnev A.G. (2012) Priblizhennye algoritmy resheniya perestanovochnykh zadach.. Diss. magistra. [Approximation algorithms for solving commuting problems]. - Master degree Thesis, SPb.: Academic Educ.-Sci. Nanotechnology Center of RAS. - 25 p. (in Russian)

Mudrov V.I. (1969) Zadacha o kommivoyazhere. [The problem of the traveling salesman.]. Moscow: "Znanie", 62 p. (in Russian)

An overview of GPS technique. https:// en.wikipedia.org/wiki/GPS_navigation_device

TSP overview in German. https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden.

Published

01-11-2017

How to Cite

Gayev, Y., & Kalmikov, V. (2017). THE TRAVELLING SALESMAN PROBLEM IN THE ENGINEERING EDUCATION PROGRAMMING CURRICULUM. Proceedings of National Aviation University, 72(3), 91–98. https://doi.org/10.18372/2306-1472.72.11989

Issue

Section

PROFESSIONAL EDUCATION