Source-linked AI summary
An Ant Colony System for the Team Orienteering Problem with Time Windows
Roberto Montemanni, Luca Maria Gambardella
TL;DR
The Team Orienteering Problem with Time Windows models profitable routes that must respect customer service intervals, a constraint relevant to applications such as fuel delivery. The paper combines a hierarchical problem model with Ant Colony System search; on literature benchmarks, the method retrieves known solutions and improves lower bounds, though its scope excludes related problems with additional capacity and departure-time constraints.
Problem
TOPTW adds customer time-window constraints to team orienteering, making routing applications such as home fuel delivery more realistic; the introduction notes limited prior TOPTW contributions.
Source: §1 · p. 2Method
The proposed Ant Colony System uses a hierarchical generalization of TOPTW and a giant-tour representation with local search exchanging customer subchains.
Source: §3.3 · p. 6, §3.5 · p. 8, §5 · p. 18Results
ACS retrieved the best known solutions for all Solomon instances and improved 24 of 27 lower bounds without proven optima, supporting practical effectiveness on literature benchmarks.
Source: §4.1.2 · p. 10, §5 · p. 18Takeaways & Limitations
The hierarchical strategy is reported to pay on harder instances, where computation times rise but many previously unknown best solutions are retrieved.
Source: §4.1.2 · p. 10The method was not designed for capacity and maximum-tour-length constraints, and optimizing depot departure times would require redesigning construction and local search.
Source: §4.2.1 · p. 13
Abstract
from arXiv · showhide
This paper discusses a heuristic approach for Team Orienteering Problems with Time Windows. The method we propose takes advantage of a solution model based on a hierarchic generalization of the original problem, which is combined with an Ant Colony System algorithm. Computational results on benchmark instances previously adopted in the literature suggest that the algorithm we propose is effective in practice.
1 Introduction
The introduction frames the Team Orienteering Problem as a scored routing problem generalized to teams, with time windows adding practical constraints. It motivates heuristic approaches and positions the paper among limited prior work on the time-window variant.
1 Introduction
- TOP generalizes the Orienteering Problem to teams that maximize cumulative score while visiting each point at most once.Its paths can be viewed as tours, linking the problem to Vehicle Routing Problems with Profits.Source: §1 · pp. 1–2
- TOP models applications including multi-vehicle fuel delivery, college football recruiting, pickup or delivery services, and technician scheduling.The cited examples span routing and non-routing contexts.Source: §1 · p. 2
- Because TOP is NP-hard, research has focused mainly on heuristics and metaheuristics, while relatively few exact TOP algorithms are cited.The introduction names greedy, stochastic, tabu-search, variable-neighborhood, and ant-colony approaches, alongside column-generation and branch-and-price exact methods.Source: §1 · p. 2
- Time windows require visits to start within each location’s predefined interval and can make applications such as home fuel delivery more realistic.For TOPTW, the introduction identifies two prior metaheuristic contributions.Source: §1 · p. 2
2 The Team Orienteering Problem with Time Windows
TOPTW seeks profitable, time-feasible paths through a weighted network. Its formulation selects mutually non-overlapping routes from a common origin to destination while enforcing visit and timing constraints.
2 The Team Orienteering Problem with Time Windows
- TOPTW is defined on a complete undirected graph whose edges encode travel times and whose nodes carry profits, time windows, and service times.Nodes 1 and n are the path endpoints; the model seeks m elementary paths that share only those endpoints.Source: §2 · p. 3
- Binary arc variables encode route membership and integer variables encode visit times, with constraints enforcing time propagation and feasible arrival windows.The time variables correspond to arrival times for visited customers; the formulation also defines their domains.Source: §2 · pp. 3–4
- The objective maximizes collected prize while each customer is visited at most once and the paths have a feasible structure.The special case m = 1 corresponds to the Orienteering Problem with Time Windows.Source: §2 · p. 4
3 An Ant Colony System for the TOPTW
The method embeds TOPTW in a hierarchical multi-tour problem and combines an Ant Colony System with a giant-tour representation and specialized local search.
3.1 Ant Colony System
- ACS uses multiple ant-like agents and memory of prior choices to guide construction, with pheromone trails supporting exploration and exploitation through positive feedback.Following a trail reinforces it, making it more attractive to later ants.Source: §3.1 · p. 4
3.2 The Hierarchic Team Orienteering Problem with Time Windows
- HTOPTW optimizes ordered, non-overlapping tours hierarchically; with integer prizes, the first m tours solve TOPTW while later tours cover feasible customers left out.Maintaining useful fragments in these extra tours supports local-search exchanges and insertions that can improve the first m tours, at the cost of optimizing tours outside TOPTW’s objective.Source: §3.2 · p. 5
3.3 Solution model
- The giant-tour model merges the endpoints into a depot and duplicates it, resetting tour duration at each copy; this also facilitates generic local search.A feasible solution visits every node exactly once in the transformed representation.Source: §3.3 · p. 6
3.4 Construction phase
- Each ant constructs a feasible HTOPTW solution by repeatedly selecting an unvisited node feasible under its time window, with construction cost O(|V|^2).Choices combine pheromone memory with a desirability measure favoring high-prize, nearby customers whose time windows are suitably used.Source: §3.4 · pp. 6–7
- Only the best-so-far solution deposits pheromone on its route, while ants decrease pheromone on traversed arcs to encourage variety.The best-route reinforcement is controlled by ρ; the local decrease uses ψ and the initial trail value τ0.Source: §3.4 · p. 7
3.5 Local search
- The local search applies CROSS exchanges to customer subchains of a giant tour, increasing their maximum length when recent ant generations find no improvement.The authors note that this inversion-free search suits time-window problems, while other, possibly simpler, schemes may suit problems without time windows or with very wide windows.Source: §3.5 · p. 8
4 Computational experiments
The experiments evaluate ACS on OPTW and TOPTW benchmark instances, with strong results on Solomon OPTW instances and additional results across multiple vehicle counts. Performance varied by instance class, including weaker results on wide-window Cordeau instances.
4 Computational experiments
- The broader experiments were divided between OPTW and TOPTW, with TOPTW runs using 2–4 vehicles and excluding Solomon instances with 50 nodes.Each run had a 3600-second limit, and reported statistics were collected over five runs per instance.Source: §4 · pp. 8–9, §4.1.2 · p. 9, §4.2.1 · p. 13
4.1.1 Benchmarks
- The OPTW tests used reference benchmarks from Righini and Salani and Mansini et al., comprising Solomon-derived and Cordeau-derived instance classes.The Solomon-derived set included 29 instances with 50 nodes and 48 with 100 nodes; the Cordeau-derived set had 20 instances and up to 288 customers.Source: §4.1 · p. 9, §4.1.1 · p. 9
4.1.2 Experimental results
- ACS matched the best-known solutions on all Solomon instances and improved 24 lower bounds across 27 instances without proven optima, while dominating GVNS in solution quality and generally running faster.Optimal solutions were found in every run for most Solomon problems; the GVNS machine was reported to be approximately 10% faster than the authors’ machine.Source: §4.1.2 · pp. 9–10
- On Cordeau instances, wide time windows and a local search specialized for narrow windows were identified as likely reasons for weaker performance; the method also did not scale particularly well on large instances.The authors attribute the scaling drawback to the time-consuming construction phase typical of Ant Colony System algorithms.Source: §4.1.2 · p. 10
- On Cordeau instances, ACS did not solve 3 of 8 known-optimum problems to optimality, improved two previously known lower bounds, and provided first documented lower bounds for ten others.No GVNS comparison was possible because Mansini et al. reported no Cordeau results.Source: §4.1.2 · p. 10
4.2.1 Benchmarks
- For the most difficult TOP instances—about 5% of the dataset—ACS solutions were up to 5% worse than Ke et al.’s ACO results, although ACS quickly converged to optimal values for most problems.The hierarchy and fragment-exchange design is optimized for time windows, adding complexity when those windows are absent.Source: §4.2.1 · pp. 12–13
4.2.2 Experimental results
- Across TOPTW tests with 2–4 vehicles, the authors considered ACS suitable for multiple vehicles, but no upper bounds were available to estimate absolute solution quality.Crosschecking the tables showed that each additional vehicle contributed increasingly marginally as m increased.Source: §4.2.2 · p. 13, §4.2.1 · p. 13, Table 2 · pp. 14–15
- On some TOPTW problems, especially Cordeau pr* instances, the best solution arrived near the 3600-second limit, suggesting longer runs might have improved results.The authors also report high variation in computation times for these instances.Source: §4.1.2 · p. 10, §4.2.2 · pp. 13–14
5 Conclusions
The paper presents an Ant Colony System algorithm for the Team Orienteering Problem with Time Windows, using a hierarchic generalization of the original problem. Benchmark results support the algorithm’s practical effectiveness.
5 Conclusions
- The proposed algorithm applies the Ant Colony System paradigm to the Team Orienteering Problem with Time Windows.Source: §5 · p. 18
- Its solution method uses a hierarchic generalization of the original Team Orienteering Problem.Source: §5 · p. 18
- Experiments on benchmark instances previously used in the literature support the algorithm’s practical effectiveness.Source: §5 · p. 18