Skip to main content


Clustered Generalized Traveling Salesman Problem

Given a list of cities, suppose the cities are partitioned into mutually exclusive clusters, and each cluster is further partitioned into mutually exclusive sets of nodes called subclusters. Then the Clustered Generalized Traveling Salesman Problem (CGTSP) is the problem of finding the shortest cycle that satisfied the following:

(1) the cycle visits exactly one node per subcluster, and,
(2) within each cluster, all of the visited nodes are visited consecutively.

For a detailed study of CGTSP see:

Benchmark set:

STSP Solver
Random CGTSP instances
The instances of the benchmark set consist of randomly generated vertices in a 1000 × 1000 2D Euclidean space. We use the generic name “rnd<NC>-<NS>-<NV >n", where Nis the number of clusters, NS is the number of subclusters in each cluster, and NV is the number of vertices in each cluster. For each size, we have generated problems with high, low or even numbers for NCNS and NV relative to one another to extract the differences that arise from various combinations. 

CGTSP Instances inspired by ASRS
A number of item locations are generated in a warehouse that is assumed to be square. Each item may be associated with multiple item locations. A robot collects the items in the warehouse is given a list of orders and due to stacking restrictions, it must finish collecting one order, before moving on to the next order. Finally, the robot should deliver the collected items to a specific point (the initial point) in the warehouse. This problem may be modelled as a CGTSP and this benchmark set is a collection of CGTSP instances associated with this problem.

Consider a warehouse where the stored items are in thetwo categories of high-demand and low-demand items, consisting of 20% and 80% of total items respectively. We randomly generate orders for which we presume that there is a 80% chance that a randomly selected item in an order is marked as a high-demand item. Furthermore, there are 400 possible storage locations in the warehouse, and each item may be stored at multiple locations. The ASRS test instances are labeled as “ASRS_i<A>r<L>_<I><type>", where is the total number of available items in the warehouse, is the number of locations where each item is stored, and is the total number of items in all orders. It is clear that the size of the problem is L×I. The type of the instance determined whether the locations of all items is randomly selected in the warehouse (type rnd), or if there is at least one location for all high-demand items near the I/O conveyor (type alt). 

CGTSP Instances inspired by Drone delivery systems
We have used GTSPLIB instances to generate CGTSP instances corresponding to the drone-assisted parcel delivery service (PDS) and compare the impact of the different number of drones. In the GTSPLIB library the nodes of the selected TSPLIB test instances are divided into regions (clusters of close-by nodes) by a simple clustering procedure that clusters nodes that are close to each other. If the size of any particular cluster is larger than the number of drones plus one, we further subdivide the cluster into subclusters where the truck only visits one of the nodes from each subcluster, and the drones visit the rest of the nodes. We assume that loaded drones and empty drones are 50% and 100% faster than the truck respectively. We also presume that one unit of distance traveled by truck corresponds to one unit of time. As a measure of improvements made by adding the drones, we compare the time values to the case where the drones are not employed. It is interesting to note that if we employ zero drones, the problem is equivalent to a CTSP. Furthermore, if there are enough drones in each step to cover an entire cluster, then the problem reduces to a GTSP.