CETSPST Reproducibility Package

This folder contains the source code, test instances, detailed instance-level results, and a Jupyter example for the manuscript On the service time in the close-enough traveling salesman problem. The study considers a close-enough traveling salesman setting with service time, where a target can be served while the traveler moves inside its neighborhood.

Repository Contents

• cetspst/ contains the source code for the proposed method.
• Instance/ contains all test instances used in the computational experiments.
• Solution/ contains the detailed solution obtained for each instance and parameter setting.
• Jupyter/Solve_CETSPST.ipynb provides a runnable example that generates an instance, solves it, plots the resulting route, and reports its completion time and travel distance.

Requirements

The Jupyter example was created with Python 3.12.3. It requires Jupyter, Gurobi with a valid license, and the Python packages used by the source code, including gurobipy, numpy, scipy, matplotlib, networkx, shapely, geopy, geojson, requests, and guid.

Running the Jupyter Example

Start Jupyter from the Jupyter directory so that the relative import paths in the notebook are resolved correctly.

cd public/Jupyter
jupyter notebook Solve_CETSPST.ipynb

Run the notebook cells in order. The example generates 10 circular neighborhoods in a square area, solves the resulting CETSPST instance for 150 iterations, plots the route, and displays the total completion time and travel distance. Because the solution method contains randomized components, results may vary between runs.

The serviceMode argument selects one of the four service modes studied in the manuscript:

• AccuOverlap corresponds to STAP-IM.
• AccuNonOverlap corresponds to STAP-IS.
• ContOverlap corresponds to STAP-CM.
• ContNonOverlap corresponds to STAP-CS.

Numerical Data Format

All files in Instance/ and Solution/ are plain text files. Fields in the same line are separated by tab characters.

Instance Format

Each instance file describes the neighborhood setting, the depot location, and the target coordinates.

<shape>	<radius>
<depot_x>	<depot_y>
<target_1_x>	<target_1_y>
<target_2_x>	<target_2_y>
...
<target_N_x>	<target_N_y>

The first line gives the neighborhood shape and radius. The shape is either Circle or Flat.

The second line gives the depot coordinate. In the current data, the depot is located at (0, 0).

Each remaining line gives one target coordinate. The target index is determined by the row order, starting from 1.

Example:

Circle	300
0	0
-129	-686
-113	331
419	274

Solution Format

Each solution file describes the total route length, the total completion time, and the ordered path segments of the solution.

<total_distance>	<total_time>
<x_1>	<y_1>	<x_2>	<y_2>	<time>	<serve>
<x_2>	<y_2>	<x_3>	<y_3>	<time>	<serve>
...

The first line gives the total travel distance and the total completion time. Numerical values in solution files are reported with two decimal places.

Each remaining line gives one path segment. The segment starts from (x_1, y_1) and ends at (x_2, y_2). The value time is the travel and service time assigned to that segment.

The field serve lists the targets served on that segment. Target indices are separated by commas and enclosed in parentheses. If no target is served on a segment, the field is written as ().

Example:

3923.08	158.43
0.00	0.00	-147.97	549.33	22.76	()
-147.97	549.33	-130.18	569.46	1.07	(9)
-130.18	569.46	-48.13	662.34	6.46	(9)