TOPTW Metaheuristics

A collection of metaheuristic algorithms for solving the Team Orienteering Problem with Time Windows (TOPTW).

Problem Description

The Team Orienteering Problem with Time Windows (TOPTW) is an NP-hard combinatorial optimization problem that extends the classic Orienteering Problem (OP) and Team Orienteering Problem (TOP).

Problem Definition

Given:

• A depot node (start and end point)
• A set of n customer locations
• A fleet of m vehicles with time budget T_max
• Each customer i has:
  • Score/profit (p_i): reward for visiting
  • Time window [e_i, l_i]: earliest and latest arrival times
  • Service time (s_i): time spent at the location

Objective: Maximize total collected score while respecting constraints.

Constraints:

1. Each location can be visited at most once (across all vehicles)
2. All vehicles must start and end at the depot
3. Service must begin within the customer's time window (can wait if arriving early)
4. Total route time ≤ T_max for each vehicle

Mathematical Formulation

Maximize:  Σᵢ Σₖ pᵢ · xᵢₖ

Subject to:
  Σₖ xᵢₖ ≤ 1                    ∀i ∈ V\{0}     (visit at most once)
  Σⱼ x₀ⱼₖ = Σⱼ xⱼ₀ₖ = 1        ∀k ∈ K         (start/end at depot)
  aᵢ ≥ eᵢ                       ∀i visited     (respect time window)
  aᵢ ≤ lᵢ                       ∀i visited     (respect time window)
  route_timeₖ ≤ Tmax            ∀k ∈ K         (time budget)

Implemented Algorithms

Algorithm	Short Name	Implementation	Description
Genetic Algorithm	ga	Python	Population-based evolutionary search
Simulated Annealing	sa	C++	Temperature-based local search
Tabu Search	tabu	C++	Memory-based local search
GRASP	grasp	C++	Greedy randomized + local search
Ant Colony Optimization	aco	Python	Pheromone-guided construction
Particle Swarm Optimization	pso	Python	Swarm intelligence approach

See docs/ALGORITHMS.md for detailed documentation of each algorithm.

Installation

From source

git clone https://github.com/miladbarooni/TOPTW.git
cd TOPTW
pip install -e .

Requirements

pip install -r requirements.txt

Note: For C++ algorithms (SA, Tabu, GRASP), the pre-compiled .so libraries are included. If you need to recompile:

cd src/toptw/lib
g++ -shared -fPIC -O3 -o sa.so sa.cpp
g++ -shared -fPIC -O3 -o tabu.so tabu.cpp
g++ -shared -fPIC -O3 -o grasp.so grasp.cpp

Quick Start

Command Line

# Solve an instance with Genetic Algorithm
python -m toptw solve data/instances/c102.txt -a ga -t 60

# Solve with Simulated Annealing (verbose)
python -m toptw solve data/instances/c102.txt -a sa -v

# List available algorithms
python -m toptw list

# Get instance information
python -m toptw info data/instances/c102.txt

# Validate a solution
python -m toptw validate solution.txt data/instances/c102.txt

Python API

from toptw import load_instance, solve

# Load a problem instance
problem = load_instance("data/instances/c102.txt")
print(f"Customers: {problem.num_customers}")
print(f"Vehicles: {problem.num_vehicles}")
print(f"Optimal score: {problem.optimal_score}")

# Solve with default algorithm (GA)
solution = solve(problem, algorithm="ga", time_limit=60)
print(f"Score: {solution.total_score}")
print(f"Gap: {solution.calculate_gap():.2%}")

# Or use algorithm classes directly
from toptw.algorithms import GeneticAlgorithm

ga = GeneticAlgorithm(problem, population_size=100, generations=500)
solution = ga.solve(time_limit=60)
results = ga.get_results()
print(f"Best score: {results.best_score}")
print(f"Runtime: {results.runtime:.2f}s")

Benchmark Instances

The data/instances/ directory contains 34 standard benchmark instances:

• Solomon instances (c*, r*, rc*): 100 customers, various time window characteristics

  • c*: Clustered customers
  • r*: Random customer locations
  • rc*: Mixed clustered and random

• Cordeau instances (pr*): Larger instances up to 480 customers

Instance file format is documented in data/README.md.

Project Structure

toptw-metaheuristics/
├── src/toptw/              # Main package
│   ├── problem.py          # Problem definition, Node class
│   ├── solution.py         # Solution representation
│   ├── algorithms/         # Algorithm implementations
│   │   ├── genetic.py      # Genetic Algorithm
│   │   ├── simulated_annealing.py  # SA wrapper
│   │   ├── tabu_search.py  # Tabu Search wrapper
│   │   ├── grasp.py        # GRASP wrapper
│   │   ├── aco.py          # Ant Colony Optimization
│   │   └── pso.py          # Particle Swarm Optimization
│   ├── lib/                # Compiled C++ libraries
│   └── utils/              # I/O, visualization, metrics
├── data/instances/         # Benchmark instances
├── docs/                   # Documentation
├── examples/               # Usage examples
├── notebooks/              # Jupyter notebooks
└── tests/                  # Unit tests

Documentation

• ALGORITHMS.md - Detailed algorithm documentation
• PROBLEM.md - Problem formulation
• USAGE.md - Usage examples and tutorials

Contributing

Contributions are welcome! Please feel free to submit a Pull Request.

License

This project is licensed under the MIT License - see the LICENSE file for details.

References

1. Vansteenwegen, P., Souffriau, W., & Van Oudheusden, D. (2011). The orienteering problem: A survey. European Journal of Operational Research, 209(1), 1-10.

2. Righini, G., & Salani, M. (2009). Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming. Computers & Operations Research, 36(4), 1191-1203.

3. Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35(2), 254-265.