Skip to content

10 Santa’s Snowflake-powered Snowmobiles

© Frauke Jansen, MATH+

Authors: Niels Lindner (ZIB), Fabian Löbel (ZIB), Berenike Masing (ZIB)
Project: Electric Bus Scheduling (Research Campus MODAL)

Because of the server issues, there will be a time bonus of 48 hours for this challenge.

Challenge

Each year, the preparation of Christmas gifts is a mammoth task for Santa and his elves. Not only the production of the presents, but also the logistics behind it pose a real challenge: there are different manufacturing steps and the needed components have to be transported to the correct locations on time. Since the task takes multiple days, Santa has been using the well-established system of reindeer sleds on the street network at the north pole up until now: each hour the same sled performed the same trip at the same departure and arrival times. The usual street network and the corresponding timetable can be found in Figure 1.

This year, however, everything is different: the reindeer do not want to do all this exhausting work anymore and have mutually decided to go on indefinite strike. Santa has to react immediately: the timetable for the sleds cannot be changed on such short notice, since the production process at each station is exactly adjusted to it. Luckily, Santa manages to procure environmentally friendly snowmobiles to replace the reindeers. They run as fast as the reindeers and can therefore keep the same travel times between stations as indicated in Figure 1. Just like the reindeer sleds, they can only use the indicated roads; their travel times are independent of the travel direction.

“This works out perfectly!”, decides Santa. “It means that the timetable can be covered with six snowmobiles just as usual.” The vehicles should travel through the network along circles, as the timetable is supposed to repeat itself after each hour. Each trip should be covered by exactly one circle, and no circle should contain a trip more than once. The vehicles can use the streets freely; in particular, they are allowed to return on the same road as they arrived. After arriving at a station, they can either wait or depart immediately. Concretely, Santa constructed the vehicle schedule depicted in Figure 2.

Just when he was about to order the six snowmobiles, Rudolf the reindeer knocks on Santa’s door. On taking a look at the vehicle schedule, Rudolf starts laughing out loud. He explains to the confused Santa that he has forgotten about one crucial detail: the snowmobiles have a special engine, powered by snowflakes. Each vehicle is equipped with a bucket which can hold up to 500 snowflakes. However, the engine consumes 10 snowflakes per minute, which means that each snowmobile can run only for 50 minutes without breaks. The buckets can be refilled at each station, but this takes 5 minutes each time. As a result, the vehicles cannot be operated as planned, as some of the vehicle routes are scheduled to run for up to 110 minutes without breaks. However, if they simply refueled at some station within Santa’s plan, they would miss their next departure and delay the entire process; the whole gift production would be disrupted! There is no getting around it—Santa has to re-plan the circles on which the snowmobiles have to operate. If worst comes to worst, Santa might have to buy even more than 6 snowmobiles in order to cover all trips…

Question: What is the minimum number of snowmobiles needed to realize all trips 1 to 8 in the schedule from Figure 1?

Figure 1: Street network and timetable.

Figure 2: Santa’s Vehicle Schedule:

The blue circle serves Trips 7 and 8 in turns, one circulation takes 60 minutes. Consequently, the blue cycle needs exactly one vehicle in a periodic setting of 60 minutes. The corresponding vehicle departs immediately after each arrival without taking any breaks.

The green circle consists of Trip 1, followed by a wait of 10 minutes at the chocolate factory, Trip 5 (20 minutes), an empty run to the cinnamon depot (55 minutes), Trip 2 (35 minutes), an empty run to the cocoa depot and finally waiting for departure of Trip 1 (20 minutes). Consequently, travelling along the green circle takes 180 minutes in total, which means that 3 vehicles are needed.

On the red circle vehicles travel for exactly 120 minutes. For hourly departures, this corresponds to exactly 2 vehicles. Due to the pure travel time of exactly 55 minutes from the wrapping station to the cinnamon depot, a vehicle departing at the former at minute 55 manages to arrive at the latter at minute 50 exactly. Along this circle, the vehicles only have one break of 10 minutes at the gingerbread factory.

Possible answers:

  1.  1
  2.  2
  3.  3
  4.  4
  5.  5
  6.  6
  7.  7
  8.  8
  9.  9
  10.  10

Project reference:

The MobilityLab at the Zuse Institute Berlin researches how to improve operation, organisation, and passenger convenience of public transport with the help of Mathematics. As part of the Research Campus MODAL, the project Electric Bus Scheduling addresses the problem of scheduling routes for battery-powered buses. The greatest challenge when replacing diesel-fuelled buses by electric ones is that today’s battery capacities are not sufficient for the typical distances that diesel buses accumulate over a day. Thus, the charging of the batteries has to be taken into account when planning vehicle schedules.