SOLUTION OF TRAVELING SALESMAN PROBLEM USING RELATIONAL DATABASE SYSTEMS

MEŠINA, M.; ROLLER, D.; LAMPASONA, C.

Abstract

For a given set of points (j=1,…, N) and a given Distances-Matrix with elements Djk the shortest way of visiting all the cities (points) and returning to your starting point should be found. Relational databases allow creating all possible sequences of points and calculating the corresponding path’s lengths very easily. Since there are (N-1)! possible paths, this approach can only be used for a low N (approximately N≤11). The aim of this paper is to show, how this limit can be shifted to a greater N. The suggested proceeding can be used for accurate and approximate solutions of the task. The proposed approach can also be implemented in a program, without using the database systems. The solution is presented using MS-Access.

Coresponding author e-mail: marian[dot]mesina[at]informatik[dot]uni-stuttgart[dot]de

Session: Process Optimisation