Instances in the paper “A memetic algorithm for the travelling salesperson problem with hotel selection”

Four sets of instances have been developed in [1] for the TSPHS. All of these instances are generated based on well-known VRP and TSP benchmarks. We restate the procedures for generating the TSPHS instances corresponding to the first two sets. For a detailed description of the third and fourth set we refer to [1].

The first set of instances (SET 1) is created from six instances for the capacitated vehicle routing problem with time windows (CVRPTW) (c101, c201, r101, r201, rc101 and rc201) from [2], containing 100 customers each, and ten instances for the multi-depot vehicle routing problem with time windows (MDVRPTW) (pr01-pr10) from [3], containing between 48 and 288 customers.

In order to generate TSPHS instances from the CVRPTW instances, the depot is taken as the starting hotel, the time windows for the customers are ignored, the closing time of the depot is taken as the time budget for every trip, and five extra hotels are to be added at the locations of customers 1, 11, 21, 31 and 41. In addition, distances between any pair of locations are rounded down to one decimal position.

To generate TSPHS instances from the MDVRPTW instances, the starting hotel is first defined. Given the available depots and their coordinates in the original instances, the starting hotel has to be created at the centroid of the set of depots.

Then, the closing time of the first depot is taken as the time budget for every trip, five available extra hotels are added at the locations of customers 1, 11, 21, 31 and 41, the time windows were ignored for each customer, and the distances between any pair of locations are also rounded down to one decimal position.

The second set of instances (SET 2) contains smaller instances and is generated using the instances of SET 1 by considering only the first 10, 15, 30 and 40 customers. This leads to four groups of 16 instances each. For this set, only one extra hotel is added at the location of the first customer, instead of the five extra hotels added when creating SET 1. The instances c201, r201 and rc201 in SET 2 are excluded because those instances are easily solved using just a single-trip (TSP) tour. Therefore, SET 2 contains only instances.

 

Bibliography

[1] Vansteenwegen P, Souffriau W and Sörensen K (2011). The travelling salesperson problem with hotel selection. J. Opl. Res. Soc. 63: 207-217.
[2] Solomon MM (1987). Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints, Opns. Res. 35:254-265.
[3] Cordeau J-F, Laporte G and Mercier A (2001). A unified tabu search heuristic for vehicle routing problems with time windows. J. Opl. Res. Soc. 52: 928-936.

 

Instances in the paper “A memetic algorithm for the travelling salesperson problem with hotel selection”