Ant Colony Optimization applied to the Traveling Santa Problem

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. Given the vast number of permutations of city-to-city legs, different payload drop-offs at each location, and the necessity of delivering gifts during the hours of darkness, to minimize energy expenditure, a heuristic-based optimization was applied. To design this schedule, the Traveling-Santa Ant-Colony Optimization (TSaP–ACO) framework 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 minimize aerodynamic work via a shrinking sleigh cross-sectional area depending on current payload, (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 Ant-Colony Optimization (ACO). In a 40-capital-city stress test, it cuts energy use by 89% and shortens tour length by 60%. Population-first routing emerges naturally from work minimization (50% served by leg 11 of 40). These results demonstrate that rolling-window, energy-aware ACO has potential applications in more realistic global delivery scenarios.

The classical Traveling Salesman Problem (TSP) asks for the shortest route that visits a set of locations once and returns to the start. Although deceptively simple, it is NP-hard and underpins many real-world logistics tasks [1]. The related Traveling Santa Problem (TSaP) revisits this puzzle with a twist: rather than just minimizing the distance traveled, Santa must deliver gifts worldwide only during local hours of darkness to maintain his air of mystery and anonymity. Each destination has a strict night-time window that varies with latitude and longitude, making the feasibility of a delivery route depend on timing relative to the Earth's rotation. Furthermore, the necessity for a high-efficiency, energy-saving route adds complexity, leading to constraints on flight speed (to minimize aerodynamic drag) and drop-off schedules that maximise early present deliveries (lowering payload). These rolling darkness windows and other constraints convert the purely spatial problem of the TSP into a spatio-temporal routing challenge for the TSaP; distance-only optimizations inevitably lead to unacceptable daylight deliveries and fail to minimize energy use.

Time-window routing is important in transport and logistics across many areas, such as agriculture [2], healthcare [3], and waste collection [4, 5]. As such, this problem has been studied for decades [6], but prior studies typically assume fixed or regionally synchronized windows. However, global delivery schedules are sometimes restricted to sending or receiving goods during typical local working hours. Hence, determining optimal delivery routes that explicitly incorporate a moving delivery time window is important. To meet the net-zero goals of governments around the world, “green” effective route-finding logistics now optimize distance, speed, and load to minimize energy consumption and emissions [7, 8]. Therefore, handling both timing and energy constraints calls for a flexible approach.

Early exact solvers and heuristics for the TSP laid essential groundwork [1]. Incorporating service intervals produces the Vehicle Routing Problem with Time Windows (VRPTW) [9], first formalized by Solomon [6]. Exact branch-and-bound methods solve small VRPTW problems, but meta-heuristics dominate at realistic scales [10, 11]. The majority of the VRPTW research assumes time windows on a single global clock; the rolling night-time constraint of TSaP is largely unexplored. Approaches to NP-hard routing such as the Traveling Santa Problem typically include meta-heuristics like evolutionary algorithms [12] and tabu search [13, 14], deep learning methods such as reinforcement learning [15], and hybrid approaches that combine multiple techniques [16]. These methods aim to quickly find near-optimal solutions to problems that are computationally too complex for exact algorithms to solve.

General-purpose meta-heuristics, genetic algorithms, simulated annealing, and others offer robust VRPTW solutions [17]. Among swarm techniques, Ant-Colony Optimization (ACO) is notable for its distributed search and positive feedback via pheromone trails [18]. The Multiple Ant Colony System extended ACO to VRPTW by separating routing and scheduling colonies [19], yet still assumed synchronous time windows. In the modern scientific literature, there are numerous examples of applying the ACO to vehicle routing problems [20–23].

A key advantage of ACO is its ability to naturally incorporate dynamic decision-making into the construction of a tour. Compared to standard population-based methods such as genetic algorithms, which rely on recombination of complete candidate solutions, ACO incrementally builds routes and can have feasibility checks, such as compliance with darkness windows at each decision step. This is particularly important for the TSaP, where temporal feasibility is not fixed but changes continuously with the Earth's rotation, requiring route construction to remain adaptive rather than globally pre-defined. Pheromone updates provide an efficient mechanism for determining both the spatial and temporal solution quality, allowing ants to implicitly learn favorable trade-offs among distance, timing, and energy expenditure.

In contrast to methods that require explicit scheduling layers or post-hoc repair mechanisms, ACO offers a unified framework in which routing, timing, and load-dependent cost considerations can be jointly optimized during solution construction. These properties make it particularly well-suited to the Traveling Santa Problem, where feasibility, energy efficiency, and temporal alignment are tightly coupled. Hence, the ACO was chosen as a potential approach to the Traveling Santa Problem, which is the focus of this study. Only a handful of novelty projects have addressed the TSaP directly, such as Strutz [24], which, on a million-node Christmas tour, minimized distance only, ignoring night-time feasibility. No prior study jointly addresses (i) worldwide darkness windows, (ii) load-dependent energy expenditure, and (iii) a single-vehicle schedule.

This brief research report presents a preliminary ACO framework that constructs night-feasible, energy-aware Santa Claus delivery routes that visit capital cities across the globe. The main unique contributions are: (i) integration of rolling-darkness windows into pheromone-guided search; (ii) a work-based cost function that scales with sleigh load and speed; and (iii) an adaptive cruise-speed model reflecting realistic travel times. The Materials and Methods section formalizes the TSaP and details the ACO framework, including its implementation. The Results section critiques the performance of preliminary optimized routes, explores convergence behavior, and quantifies energy savings. The discussion section further highlights real-world applications of this technique and the advances needed to extend its use to more complex delivery systems. Possible alternative algorithms beyond the ACO are also discussed.

Formalizing the problem

Santa's delivery task can be expressed as vertices, labeled as V = {0, 1,..., N, 0}, where vertex 0 represents Santa's base at the North Pole. and each i >0 is a delivery location. To simplify the problem, each vertex corresponds to a world capital city. Each of these is characterized by geographic coordinates (ϕ i, λ i) expressed in degrees, a population P i, and a sunrise and sunset, in local time, [ t i d u s k, t i d a w n ], defined on 24–25 December 2025. The night-time windows were shortened by a 15-min buffer. To reduce the computational cost of the problem to a level that can be computed on a laptop, the number of cities selected was capped at 40 (one-fifth of all world capitals) for this scoping study. For low numbers of cities ≤ 30, the number of iterations required to find a viable night-time-only delivery route initially increased exponentially with the number of cities.

A tour (π) is an ordered list of edges that: (i) starts and ends at 0, (ii) visits every city exactly once, and (iii) reaches each city during its darkness window. The Traveling Santa Problem seeks the tour (π) that minimizes energy expenditure subject to the feasibility rules stated above.

Classic Ant-Colony Optimization

The power of biological systems in addressing path-finding problems is no secret, with well-popularized systems utilizing slime mold-inspired algorithms [25]. With a similar basic philosophy, the ACO framework [26] optimizes a route by simulating tours of a population of artificial ants that iteratively extend partial paths. These digital ants make their decisions much like they do in nature, by following pheromones left previously by other ants, while maintaining a degree of exploration. This is incorporated into the algorithm during the construction of the tour. At the construction step at time t, an individual ant (k) is located at a city (i) with a set N i (k) of yet-unvisited cities. The probability of this ant choosing the next city j is calculated as

Here, τ ij (t) is the pheromone level on path (i, j) at time t and η ij = 1/ J π is the heuristic, using the inverse of the effective cost function for that part of the journey, J π. The α and β are powers (>0) that weight the influence of the pheromone against heuristic information. In the zeroth iteration, equal pheromone levels are applied to all paths, a certain number of ants set out on their journeys, and complete their tours.

In the next iteration, the ant pheromone levels along each possible path are updated to weight the choices of the next set of ants, such that more favorable paths are chosen. This is achieved with two updates.

(1) Uniform evaporation reduces every trail by a factor (1−ρ), where ρ∈(0, 1) is the evaporation rate.

(2) Deposit adds new pheromone in proportion to tour quality.

Combined, these two effects modify the pheromone level as shown in Equation 2 as

with

Here, J k is the total “cost” incurred during ant k 's tour (Equation 4) and Q is a user-defined deposit factor. The best tour found so far receives an extra reinforcement pass, biasing future ants toward high-quality edges. The level at which to weigh preferential edges with pheromone is a delicate balance between following the wisdom gained by earlier ants and allowing further exploration.

Traveling-Santa implementation

To evaluate a tour, two cost components were introduced into the heuristic and are depicted in Figure 1:

(1) Aerodynamic work W ij incurred while traveling from city i to city j

(2) A daylight penalty Ω that activates whenever the sleigh lands in daylight. This is done by introducing an indicator variable

The constant Ω = 2.1 × 10 100 J was chosen to outweigh any plausible work term, making daylight arrivals hideously unattractive. The total effective tour “energy” is therefore defined as

Dynamic cruise speeds

Each ant begins iteration 0 with a default cruise speed v ̄ default = 11, 500 km h −1, which was chosen as a sufficient value to complete a naïve, distance-only world tour in 24 h. At departure time t dep (in UTC), before committing to an edge (i, j), the algorithm checks whether the earliest possible arrival under this speed would violate the local darkness window at city j. The arrival time is computed as

If t arr lies within the hours of darkness at destination j, the ant may proceed as is. However, if t arr lies before dusk or after dawn, a feasible cruise speed that just meets the nearest boundary is computed as

To keep the model physically plausible, speeds are restricted to v min = 10 km h −1 and v max = 15, 000 km h −1. An object will burn up in the atmosphere due to extreme heating from air compression and friction at supersonic speeds, with meteors often vaporizing at 24, 000km h −1 [27]. Therefore, the sleigh's maximum velocity was chosen to be sufficiently below this limit. While even slower speeds above 2, 400km h −1 can ignite flammable materials like clothing, Santa cannot complete his delivery schedule at such low speeds, so it is assumed that his sleigh and reindeer possess some advanced heat shield. If the required speed exceeds v max or the remaining darkness window is negative, the edge is marked infeasible and receives a costly penalty in the heuristic.

Every 1% of iterations, v default is further refined, since from an aerodynamic work perspective, slower speeds are preferable. The program calculates v avg − the mean cruise speed of the current best tour − and a smoothing update is then applied as v ̄ new = 0. 1 v avg + 0. 9 v ̄ default. This v ̄ new as the reduced default speed is adopted only if that tour remains fully night-feasible. This feedback loop tightens travel-time estimates without destabilizing pheromone learning.

Aerodynamic work and payload-driven cross-section

Like in many simplified physics calculations, here Santa's sleigh is modeled as a perfect sphere. The sleigh's energy consumption while traveling between cities (i, j) is modeled as aerodynamic work using the formula:

where ρ = 1.225kg m −3 is the density of air at sea level, d ij is the geodesic distance in kilometers, and v ij (t) is the cruise speed selected by the dynamic-speed module, described earlier. The cross-sectional area of Santa's sleigh, A (t), decreases as presents are delivered, reflecting a decreasing payload. As presents are delivered, his sack's cross-sectional area decreases according to the equation

The P k / P tot is the fraction of gifts delivered upon visiting a location. The constant term (0.01m 2) prevents the area from collapsing to zero after the final present has been delivered. This work term feeds directly into the ACO heuristic through Equation 4, biasing ants toward energy-efficient segments. It encourages low-velocity routes that serve high-population cities early in the journey, rapidly reducing the payload size and, hence, aerodynamic drag.

Adaptive exploration

The degree of ant exploration balances the exploitation of strong pheromone trails with occasional exploration of random moves. A “ε-greedy” policy selects a random feasible city with probability ε r or chooses the city with the highest transition probability (Equation 1) otherwise. The pheromone decay schedule maintains exploration early on while encouraging exploitation later [3]. The exploration probability begins at ε 0 = 0.45 and decays as the number of iterations increases. A baseline value of ε min = 0.05 makes sure that even during later iterations, there is still a chance for some exploration, rather than just following the pheromone trails. To ensure that the exploration probability first meets ε min exactly at the final iteration R, the per-step decay factor, d tuned was set to

Rogue-ant re-evaluation

The darkness constraint makes the cost surface direction-sensitive; a perfectly feasible tour East-to-West may incur heavy daylight penalties when traveling West-to-East and vice versa. To discover this, each completed route is subjected to a rogue-ant check. Once an ant finishes its forward tour π fwd a “rogue” copy instantly computes the reversed sequence π rev = (0, v N, …, v 1, 0). Both directions are simulated with the same departure time, calculating energies J (π fwd) and J (π rev) using Equation 4. The direction with the lower cost is retained for pheromone deposit, while the more expensive one is discarded.

Because reversal costs only O (N) time per ant, the extra computational time is negligible relative to the full tour construction. However, the inclusion of the rogue ant was found to lead to a more rapid reduction in daylight penalties in early iterations of pilot tests. Intuitively, the additional “look-behind” step widens the search neighborhood without requiring new construction heuristics. It is especially valuable when night windows are long in one hemisphere and short in the other − a pattern that naturally skews edge desirability by direction.

Ant colony size

Initial smaller-scale calculations showed that although the overall ability for the TSaP-ACO to find a low-energy viable night-time only route was independent of the number of ants chosen, more rapid convergence was observed when the number of ants was set to around 35% of the number of cities, in broad agreement with the literature [28]. Therefore, 14 ants were chosen.

Objective and fitness functions

In this study, the objective function of the TSaP is to minimize the total effective energy cost of the delivery route while ensuring arrivals occur during the local darkness window. For each leg i → j the base cost is estimated from the aerodynamic work required for travel. This cost is then modified with a small reward for arrivals during darkness and a large penalty for daylight arrivals. This effective cost is used directly as the fitness function in the ACO framework. The heuristic term guiding city selection is defined in Equation 3, meaning routes with lower effective cost correspond to higher fitness. They are therefore more likely to be selected and reinforced through pheromone updates. The main tuned parameters in the algorithm are the pheromone influence α, heuristic influence β, evaporation rate ρ, pheromone deposit factor Q, pheromone bounds, number of ants, and the exploration parameter ϵ.

Model parameters summary

The overall model parameters used in the presented calculations are given in the list below:

Number of iterations, R = 60,000

Colony size, m = 14

Pheromone bias, α = 3

Heuristic bias, β = 2

Deposit factor, Q = 1.0

Pheromone limits, τ min = 0.1, τ max = 10

Exploration schedule, ϵ = 0.45 ↘ 0.05

Cruise-speed bounds, v min = 10 km h −1, v max = 15,000 km h −1

Daylight penalty, Ω = 2.1 × 10 100 J

Comparative analysis of traditional ACO vs. TSaP

The performance of the full TSaP-ACO approach described in Section 2 was measured against the traditional distance-only ACO approach. The convergence behavior and final energy outcomes of the two algorithms were compared across varying subsets of world capital cities (N = 15, 30, 45) during a 3000-iteration testing phase.

Convergence was measured by plotting the total energy expenditure of a route (Equation 4) as a function of the number of iterations. Both approaches appear to converge in approximately 500 iterations for N = 15, with incremental improvements becoming negligible thereafter. Notably, the TSaP-ACO achieves lower final energies sooner than the distance-only method, as expected, demonstrating its ability to account for additional constraints such as aerodynamic drag and rolling-darkness windows.

The total energy expenditure was calculated for the traditional distance-only ACO and the full TSaP-ACO approach over 15 trials. The full TSaP-ACO demonstrated not only a lower median energy expenditure but also a narrower distribution.

Convergence curves reveal how each algorithm handles increasing spatial and temporal complexity. For the smallest instance (N = 15) the trajectories of the distance-only and full TSaP-ACO heuristics are almost identical until roughly iteration 400. After that point, the full model edges ahead by a few percent and both methods stabilize before iteration 1,000.

A different story is told for N = 30. Here, the two curves diverge much earlier, crossing at around iteration 800, and the distance-only run continues to exhibit low-amplitude oscillations well past iteration 2,500. At the same time, the full TSaP-ACO has already stabilized at a lower energy by around 1,200 iterations. These results suggest that the richer pheromone landscape created by the constraints helps the ants to identify high-quality edges sooner, and that this advantage grows with the number of cities.

Large-scale validation: 40-capital instance

A final stress-test was run on a set of N = 40 national capitals drawn from all inhabited continents except Antarctica. To perform a statistical analysis, the optimization was run ten times independently. Figure 2 overlays tour length and total work on a common timeline. Distinct “stairs” are visible, each marking the discovery of a more efficient valid tour. Over the run, the objective falls from 8.08 ± 0.81 × 10 14 J to 8.86 ± 0.58 × 10 13 J, (errors quoted as standard deviations over ten measurements), while the tour length shrinks by 60% on average. It is worth noting here that a valid near-optimal tour length is found after 35,000 iterations. However, after that point, energy expenditure continues to fall sharply, further emphasizing that a route's energy efficiency is not determined solely by length. This fact is also highlighted by the distance-only ACO optimization results, displayed by the dashed lines in Figure 2. Here, it is seen that although the tour length initially converges more rapidly than in the full TSaP-ACO results, the total work remains high. The work only falls from 6.65 ± 0.73 × 10 14 J to 3.06 ± 0.47 × 10 14 J, with the standard deviation remaining high.

The best delivery route is shown in Figure 3. It covers 99, 286 km in 32.86 hours with zero daylight violations. In general, the route tracks East-West, following the Earth's rotation, with some exceptions that appear to facilitate early visits to high-population cities.

An alternative way to visualize the journey is depicted in Figure 4. Here, time runs along the horizontal axis and the index of each stop is on the vertical axis. The night-time windows of each considered capital city are shown by the gray rectangles. Santa's route is shown by the black line and reveals a near-diagonal progression across the gray bars. This demonstrates that the darkness windows line up in a rough chronological order as the leg index increases. It is also worth noting that at the start of Santa's route, he arrives in the early evening, whereas after this he seems to progress into the late night. He begins rounding out his tour in North America, with the final stop in Oslo just before sunrise.

Load, speed and work distribution

By tracking the per-leg energy expenditure along this route, it was found that the first 10 delivery stops account for the majority of the energy expenditure. This is as expected, as the sack of presents is largest at the beginning of the journey and subject to larger aerodynamic drag. Further analysis of the route confirms the expected “heaviest-first” delivery policy: 50% of the entire population is served by leg 11 of 40. This is beneficial because, when delivering to larger-population cities first, Santa's sleigh will have a smaller cross-sectional area and therefore experience less aerodynamic drag. This further highlights the goal of minimizing energy expenditure rather than distance traveled.

Cruise speeds settle on a tuned ceiling of ≈3, 800 kmh −1 with a small reduction for the first few legs, ≈1, 000 kmh −1. The slowest first leg was found such that arrival in Tokyo (the first stop) happened just as the sun was setting.

The present calculations represent a paradigm shift toward timing rather than geography in the modern “green” Traveling-Santa landscape. Placing rolling-darkness windows directly inside the pheromone heuristic removed all daylight violations without adding any holding patterns. In practical terms, the sleigh never wastes fuel while “circling till nightfall”, a weakness that distance-only heuristics possess.

Energy-aware routing delivers a second, possibly more useful benefit. When aerodynamic work, payload decay, and leg-specific cruise-speed tuning are jointly optimized, total work falls significantly while the geometric tour length is cut by two-thirds. These gains are because the model continually trades a small increase in trip time for a larger reduction in drag (∝ v 2). The algorithm then uses the saved energy to better align with the moving darkness band due to Earth's rotation.

Despite these successes, Figure 4 indicates that the current solution does not represent a true optimal tour in terms of energy minimization. A better solution would fill a larger portion of each city's darkness window, indicating that Santa is traveling more slowly and thus expending less energy. The presence of underutilized time windows indicates potential inefficiencies, likely stemming from applying a constant default speed across all legs of the journey, changing only when circumstances demand.

To address this, a future study could extend the existing adaptive speed model to dynamically calculate optimal cruise speeds for each leg of the journey. Tailoring speeds to individual legs would facilitate a more efficient distribution of travel times, maximizing the utilization of available darkness windows, thereby reducing overall aerodynamic work and improving energy performance.

Scalability to larger numbers of cities shows promise. Although for small numbers of cities the computational cost initially grows exponentially, the 40-node journey required only 1.67 times as many iterations as the 30-node case to reach a convergence plateau. This supports the idea that richer pheromone landscapes highlight valuable edges more quickly. Unfortunately, the calculation required to explore routes for the full 195-capital-city delivery was beyond the computational scope of the laptop computer used for this study. However, access to larger computer clusters would resolve this issue. One improvement to scalability would be to use a GPU to run the individual ants in parallel, which, if well-designed, will in turn make the algorithm much faster, allowing even more cities to be added to the framework with relative ease.

The framework adopts a useful heaviest-first strategy: half the population is served by leg 11. Deliveries to high-population hubs naturally occur early, rapidly reducing sack size and diminishing drag, thereby enhancing energy efficiency. Finally, the rogue-ant reversal proves cost-effective. A single, O (N) reverse-tour check per ant slashes early daylight penalties. It sharpens pheromone clusters along the dominant Europe-Americas corridor, adding little computational cost yet expanding the search neighborhood.

This study has demonstrated the applicability of the ACO Algorithm to the Traveling Santa Problem. Although the TSaP is niche, the overall aims of Santa's delivery route have strong synergies with common vehicle routing problems. It is a single-vehicle delivery schedule in which multiple cities must be serviced within strict dynamic time windows while minimizing energy expenditure with a variable payload. Viable night-time-only delivery routes were found for a 40-city itinerary, although scalability to larger numbers of cities is challenging without further computational resources.

The ACO algorithm was applied here based on the experience of the authors with this method, along with the numerous previous examples of it being successfully applied to discrete vehicle routing problems [20–23]. However, the ACO does have some well-documented downfalls [29]. As described in Section 2, the ACO relies on generating a large number of randomized paths and, as demonstrated in Figure 2, finding a globally optimized route within the rigid delivery windows requires a significant run-time, despite the flexibility afforded by the adaptive cruise speeds. As with all implementations of the ACO, there was a risk of converging prematurely on suboptimal routes if the pheromone/exploration weighting was not correctly set, requiring careful consideration and adaptation during set-up.

Other tried-and-tested algorithms applicable to vehicle routing optimization and the Traveling Salesman Problems do exist [30] and could outperform ACO in several areas when applied to the TSaP. The Discrete Marine Predators Algorithm has previously been applied to the classical symmetric TSP [31] and has also been used to develop a more unusual thermal-aware routing scheme for wireless body area networks, demonstrating its applicability beyond simple distance optimization [32]. Marine Predators-based approaches are more robust in avoiding local optima than the ACO, because they leverage a combination of Lévy flights (long, random, unpredictable jumps) to explore the broader search space, and Brownian motion for more localized refinements [33]. They are also effective in multi-objective optimizations and could therefore be useful for more complex TSaP constructions than those currently presented, in which energy expenditure and delivery time could be minimized concurrently.

Furthermore, compact sine-cosine algorithm approaches have successfully tackled vehicle routing problems with time windows [34, 35]. These approaches update a probabilistic model using sine and cosine trigonometric functions to fluctuate between exploration (broad search) and exploitation (fine-tuning) [36]. These methods typically require less memory and computation time than the ACO because they only store and update a probability vector rather than tracking large numbers of individual paths − a property that would be highly advantageous when attempting to optimize a delivery schedule incorporating more cities.

Game theory-based approaches have previously been applied to route planning in dynamic road networks [37, 38], although the majority of the literature focuses on multi-vehicle systems, unlike the system examined in the present study. In recent years, researchers have explored a hybrid game theory/ACO approach, in which game theory is employed to develop a more strategic and informed selection of the initial population [39]. Intelligently choosing a strong initial delivery route would partially mitigate the downfalls of the ACO mentioned above.

The tunicate swarm algorithm also shows promise for high-dimensional optimization problems [40], especially for dynamic problems where random factors can interfere with scheduling decisions and execution [41]. Such random factors would likely need to be considered in a real-world routing problem, but lie beyond the scope of the simplified TSaP picture presented here.

Clearly, scalability to a very large number of delivery locations is a key criterion for the TSaP, and we encourage a comparative analysis of the convergence behavior of the various algorithms listed above in a future study. The compact sine cosine algorithm approach shows significant promise for extension to larger numbers of delivery locations.