Ant Colony Optimisation applied to the Travelling Santa Problem
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914214821494784 |
|---|---|
| author | Fisher, Elliot Smith, Robin |
| author_facet | Fisher, Elliot Smith, Robin |
| contents | The hypothetical global delivery schedule of Santa Claus must follow strict rolling night-time windows that vary with the Earth's rotation and obey an energy budget that depends on payload size and cruising speed. To design this schedule, the Travelling-Santa Ant-Colony Optimisation framework (TSaP-ACO) was developed. This heuristic framework constructs potential routes via a population of artificial ants that iteratively extend partial paths. Ants make their decisions much like they do in nature, following pheromones left by other ants, but with a degree of permitted exploration. This approach: (i) embeds local darkness feasibility directly into the pheromone heuristic, (ii) seeks to minimise aerodynamic work via a shrinking sleigh cross sectional area, (iii) uses a low-cost "rogue-ant" reversal to capture direction-sensitive time-zones, and (iv) tunes leg-specific cruise speeds on the fly. On benchmark sets of 15 and 30 capital cities, the TSaP-ACO eliminates all daylight violations and reduces total work by up to 10% compared to a distance-only ACO. In a 40-capital-city stress test, it cuts energy use by 88%, and shortens tour length by around 67%. Population-first routing emerges naturally from work minimisation (50% served by leg 11 of 40). These results demonstrate that rolling-window, energy-aware ACO has potential applications more realistic global delivery scenarios. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_19627 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Ant Colony Optimisation applied to the Travelling Santa Problem Fisher, Elliot Smith, Robin Applications I.2.8; J.0 The hypothetical global delivery schedule of Santa Claus must follow strict rolling night-time windows that vary with the Earth's rotation and obey an energy budget that depends on payload size and cruising speed. To design this schedule, the Travelling-Santa Ant-Colony Optimisation framework (TSaP-ACO) was developed. This heuristic framework constructs potential routes via a population of artificial ants that iteratively extend partial paths. Ants make their decisions much like they do in nature, following pheromones left by other ants, but with a degree of permitted exploration. This approach: (i) embeds local darkness feasibility directly into the pheromone heuristic, (ii) seeks to minimise aerodynamic work via a shrinking sleigh cross sectional area, (iii) uses a low-cost "rogue-ant" reversal to capture direction-sensitive time-zones, and (iv) tunes leg-specific cruise speeds on the fly. On benchmark sets of 15 and 30 capital cities, the TSaP-ACO eliminates all daylight violations and reduces total work by up to 10% compared to a distance-only ACO. In a 40-capital-city stress test, it cuts energy use by 88%, and shortens tour length by around 67%. Population-first routing emerges naturally from work minimisation (50% served by leg 11 of 40). These results demonstrate that rolling-window, energy-aware ACO has potential applications more realistic global delivery scenarios. |
| title | Ant Colony Optimisation applied to the Travelling Santa Problem |
| topic | Applications I.2.8; J.0 |
| url | https://arxiv.org/abs/2512.19627 |