The Traveling Salesman Problem with positional consistency constraints

The Traveling Salesman Problem with positional consistency constraints is defined in a complete graph with n nodes, where node 1 is the depot and the other nodes are clients. We consider m vehicles, which have to perform one route each. Each client has to be served by one or several vehicles, and we know a priori which vehicles must serve each client. If two vehicles serve the same client, that client must appear in the same relative position in both routes.

The following parameters are given as input:

• The number of nodes, n.

• The number of routes, m.

• The vector with the number of nodes in each route, N.

• The vector that indicates which nodes require consistency, RC.

• The cost matrix, C.

• The matrix that indicates if a node i is in a route l, S.

The parameters appear in this order in each test instance.

Several test instances for the CTSP are available for download.

The first three folders contain the test instances used to compare the ILP formulations proposed by

Gouveia, L., Paias, A., & Ponte, M. (2023). The travelling salesman problem with positional consistency constraints: An Application to healthcare services. European Journal of Operational Research, 308(3), 960-989.

The test instances from the consistency configuration tests appear in the form  "mat_nroutes_prop_var.txt", where mat is the cost matrix, nroutes is the number of routes, prop is the proportion of consistent nodes (12_5=12.5% and 25=25%), and var is the variant. For example, instance "med32_5_12_5_v1.txt" uses matrix med32, has 5 routes, 12.5% consistent nodes and is from variant v1. All the other test instances appear in the form "mat_m_prop.txt".

• Preliminary tests

https://drive.google.com/drive/folders/1T84axoqeg9dAoQLSBHZdiggrx5H90J9-?usp=sharing

• Healthcare application tests

https://drive.google.com/drive/folders/1cpMDXOKkR1S3io8bSMw0bsogOICIFku_?usp=sharing

• Consistency configuration tests

https://drive.google.com/drive/folders/14zn8bsQ5n8zOyq3Y9f6_TRoYpRI26wJd?usp=sharing

Some larger instances were generated to assess a matheuristic for the CTSP. These appear in the form "matmnroutesvvar.txt", where mat is the cost matrix, nroutes is the number of routes and var is the variant. For example, instance "pr144m10v5.txt" uses cost matrix pr144, has 10 routes and has the consistent nodes distributed according to variant v5.

• Matheuristic instances

https://drive.google.com/drive/folders/1nFDWV9ThhG7GaxAgQz7KRRTbzn0Bgrjw?usp=drive_link