Project: Algebraic and Tropical Methods for Periodic Timetabling (MATH+ Incubator Project IN-A1)
Challenge:
Oh, how many children there are on Earth! And come Christmas, all of them write letters to Santa. In recent years, the elves had to build more and more post offices to sort all the letters. By now there are twelve of them scattered all over the North Pole: the main building, called NP, and eleven additional offices, numbered from 1 to 11.
Ralph, the elf, sighs. He and his little brother Steffan were instructed to get the next batch of letters from the post offices to the NP-building where they would be processed. Although they were given reindeers, riding through the snow for hours is still not a nice task. Ralph looks at the map that shows the post offices, the usable trails between them, and the corresponding travel times in minutes. Together with the map he was also given a list of the offices, specifying how many letters need to be picked up at each of them (see Fig. 1). “Each of our backpacks can hold exactly 143 letters. I am pretty sure we can do this!” Ralph claims. “But what would be the best way to go, to be done as quickly as possible?”
Figure 1: The map of the post offices. The circles are the numbered offices. The lines are the trails between them, with numbers indicating the time needed to ride the trail (in minutes). List of the post offices with the number of letters that have to be picked up there.
Ralph and Steffan wish to finish their task as soon as possible. The task starts when the two elves leave the NP-building, and it is done when both elves have returned to the NP-building, having collected all of the letters. They leave at the same time. Every time one of them reaches a post office, he either picks up all of the letters there or leaves all of them in the office. Of course, to pick up letters they need to have sufficient space in their backpack. Being enthusiastic sightseers, neither Ralph nor Steffan want to visit the same post office twice (except for the NP-building, to which they return only at the very end). Ralph, who is stronger, will take the longer route.
The two elves think about their task for a while, but are not able to find the best routes to take. Thankfully, their friend Petra, who is very good at math, passes by and is able to help them. She quickly finds the best tours for each of them so that the elves' task will be completed within as little time as possible. “This way,” she says, “Ralph will be back after 3 hours and 24 minutes.”
Discussing Petra's solution, the elves say:
Which of the statements are true?
Artwork: Friederike Hofmann
PDF download
Possible answers:
Project relevance: The MATH+ Incubator Project Algebraic and Tropical Methods for Periodic Timetabling explores connections between the mathematical optimization of timetables in public transport and pure mathematics disciplines. Routing of passengers and vehicles is an important problem in public transport. The problem presented here is a so-called Capacitated Vehicle Routing Problem, which belongs to the class of NP-hard optimization problems. Until now, no efficient algorithm solving this kind of problems to optimality has been found, and it is an open Millenium Problem to prove whether such a method exists at all.