Weihnachtsmann rot

Challenge from 19. December

Slipping Rudi
In an earlier version of this challenge, 156 reindeer were scheduled to realise the original timetable. This was wrong: there are 168 reindeer needed to realise the original timetable.

We are very sorry for the inconvienence!

The additional time for this challenge ist 24h.

Author: Sarah Roth

Project: ECMath MI7 - Routing Structures and Periodic Timetabling

Challenge:

In order to secure on time delivery all over the world, right after their production in the Christmas Elve’s Workshop, the Christmas presents are brought to the warehouse Greenland Gifts. From there, the presents are distributed to the present warehouses on the different continents.

As every year, the shipment of presents is organised by the international company Running Rudi. Currently, Running Rudi employs 168 reindeer, among them Rudolf (called Rudi) and his friends Ren-Qing, Rashid, Raha, Riley, and Rolando. This year, the friends were lucky to be assigned together to the yellow line, which runs back and forth from the station Greenland Gifts to the station Lama Logistics.


PIC

Figure 1: Network with times stated in minutes.

The following timetable is realised by Running Rudi. The timetable contains the departure times (= arrival times) and the direction of travel. The timetable is repeated every 60 minutes.


PIC


A reindeer cart consists of six reindeer. It is assigned to a fixed line and pulls the same sleigh all day long. Thus, all of the 168 reindeer are occupied simultaneously.

Unfortunately, Rudi slipped during the touchdown at Greenland Gifts this morning. Besides having a crimson nose now, he also sprained his ankle. It is out of the question for Rudi to work on the next two days. Since Rudi’s friends are not able to pull the sleigh by themselves, the timetable gets mixed up completely.

Rachel, the manager at Running Rudi, tries to implement a new schedule for the remaining reindeer, such that the existing timetable (see above) can be adhered. In doing so, she allows the reindeer to switch in between lines at the termini. However, the change of six reindeer from a sleigh of one line to the sleigh of another line takes 15 minutes.

Rudi’s friends—who of course still want to work together in a cart—have some additional requests for the new schedule:

Ren-Qing, “I have never been in Europe. I want to go there.”

Riley, “And I want to deliver presents to my friends in Australia.”

Rolando, “In any case, I do not want to be on the road for more than 12 hours from our starting point at Greenlandic Gifts to the endpoint, which is at Greenland Gifts as well.”

What is the maximal number of reindeer carts that can be saved with a new schedule that still realises the timetable given above? Is there a route in this schedule that fulfils all the requests made by Rudi’s friends?


Artwork: Frauke Jansen

PDF download

Possible answers:

  1. There does not exist a schedule with less than 168 reindeer.

  2. At most one cart can be saved with a new schedule. However, this schedule realises only two requests.

  3. At most one cart can be saved with a new schedule. This schedule realises all of the requests.

  4. At most two carts can be saved with a new schedule. However, this schedule realises only one request.

  5. At most two carts can be saved with a new schedule. This schedule realises all of the requests.

  6. At most three carts can be saved with a new schedule. However, this schedule realises only one request.

  7. At most three carts can be saved with a new schedule. However, this schedule realises only two requests.

  8. At most four carts can be saved with a new schedule. However, this schedule realises only one request.

  9. At most four carts can be saved with a new schedule. However, this schedule realises only two requests.

  10. At most four carts can be saved with a new schedule. This schedule realises all of the requests.

You have to log in to be able to submit your answer.

Project relevance:

The project Routing structures and Periodic attends to develop optimal timetables for local public transport networks. The transport companies prefer timetables that use vehicles as efficient as possible. At the same time, requests of the employees need to be incorporated as well.