Scientific Program > Talks by Speaker > Deineko Vladimir

We consider a 2-period-balanced-TSP, where n customers to be visited in two days: some of them have to be visited each day, i.e. twice within these two days. An additional constraint demands that the number of customers visited each day should be the same (we assume here that the number of customers is even).

We generalise one of the well known polynomially solvable cases of the TSP to the case of the 2-period-balaced-TSP. We describe also a tool for generating benchmark test problems that can be used for testing heuristics for this NP-hard problem. One of earlier suggested heuristics is used to empirically evaluate the usefulness of this type of benchmark problems.