O ABORDARE PRIVIND REZOLVAREA PROBLEMEI COMIS-VOIAJORULUI CU AJUTORUL METODEI POTENŢIALELOR

Dmitri TERZI

Abstract


Solutia aproximativă a problemei comis-voiajorului se realizează prin modificarea metodei potențialelor de rezol­vare a problemei de transport. O condiție necesară se utilizează pentru a verifica optimalitatea soluţiei. În procesul de rezolvare, matricea costurilor este convertită pentru a elimina călătoriile nedorite de la un punct la altul.

 

SOLUTION APPROACH TRAVELING SALESMAN  PROBLEM

USING THE METHOD OF POTENTIALS

Approximate solution of the traveling salesman problem is carried out by modifying the potential method to solve the transport problem and using the necessary optimality condition. In the process solutions, the cost matrix is converted to eliminate unwanted journeys from one point to another.


Keywords


traveling salesman problem, potential method, necessary solution optimality condition, transformation of cost matrix.

Full Text:

PDF

References


ГОЛЬШТЕЙН, Е.Г., ЮДИН, Д.Б. Задачи линейного программирования транспортного типа. Mосква: Science, 1969.

REINGOLD, E.M., NIEVERGELT, J., DEO, N. Combinatorial algorithms. Theory and practice. Prentice-Hall, Inc., Englewood Cliffs, New Jersey 07632, 1977.

PAPADIMITRIOU, Ch.H., STEIGLITZ, K. Combionatorial optimization: Algorithms and Complexity. Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1982.

Traveling Salesman Problem, Theory and Applications. Edited by Donald Davendra, 2010.

TERZI, D. Realizarea metodei Branch and Bound pentru rezolvarea problemelor de programare discretă. În: Materia¬lele Conferinţei ştiinţifice internationale jubiliare „Paradigme moderne în dezvoltarea economiei naţionale şi mon¬diale”. Chişinău, 2018.


Refbacks

  • There are currently no refbacks.