On solvable cases of the 2-period-balanced-TSP and benchmark test problems
Vladimir Deineko  1@  
1 : Warwick Business School  (WBS)  -  Website
Warwick Business School The University of Warwick Coventry CV4 7AL, UK -  United Kingdom

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.

Online user: 1 RSS Feed