Heuristics for a generalization of TSP in the context of PCB assembly

Abstract

Traveling Salesman Problem (TSP) is one of the most well-known NP-Hard combinatorial optimization problems. Adding new constraints to the problem yields different generalizations to the problem and each new generalization forms the basis of a new research area. In this study, we propose new techniques for a generalization of the TSP. In this problem, the cost of traveling between two cities does not only depend on the distance between these cities, but also on the visiting sequence. We analyzed the problem under different conditions; the first and last points (nodes) are set fixed or they are free and for solving the problem we propose several heuristics. After analyzing constructive heuristics, improvement heuristics are applied. As improvement heuristics, we implemented pair-wise exchange procedure (PEP) and record-to-record travel with local exchange moves (RTRLEM). Comparison of these approaches together with their parameter fine tuning are given.