SoSe18: Mathematical Aspects of Public Transportation Networks

10.10.2018: <a href="http://www.zib.de/lindner/MAPTN_2018/K2L.pdf">Solutions to the second exam.</a>09.10.2018: <a href="http://www.zib.de/lindner/MAPTN_2018/K2R.pdf">Results of the second exam. </a>26.09.2018: <a href="http://www.zib.de/lindner/MAPTN_2018/K1L.pdf">Solutions to the first exam are online.</a>07.08.2018: <a href="http://www.zib.de/lindner/MAPTN_2018/K1R.pdf">Results of the first exam are online</a>. 12.07.2018: No tutorial (excursion).25.06.2018: No lecture. The lecture takes place on Thursday instead of the tutorial.18.06.2018: The lecture takes place in the ZIB meeting room 3028. 29.05.2018: Added slides of May 28, with some modifications in the cycle spaces part. Update: Exercise 2b in Problem Set 6 should end with "in its last columns", not with "in its last rows".15.05.2018: Slides update: Renamed LCSPP to LCSWP (replacing "path" by "walk").08.05.2018: There will be no tutorial on May 10 and no lecture on May 21. Problem Set 4 is due on May 22 (Tuesday).19.04.2018: The tutorial on April 26 as been shifted to 16-18 and will take place in the ZIB seminar room.19.04.2018: Slides update: Corrected a mistake in Improved Hierholzer's Algorithm. 16.04.2018: The tutorial sessions have been shifted to Thursdays, 12-14. The tutorial on April 19 will take place in the ZIB lecture hall. <h3>Problem sets:</h3><ol><li><a href="http://www.zib.de/lindner/MAPTN_2018/P1.pdf">Problem set 1</a> (due on April 23, <a href="http://www.zib.de/lindner/MAPTN_2018/BerlinU.csv">Berlin U-Bahn network</a>, <a href="http://www.zib.de/lindner/MAPTN_2018/P1E3.py">short solution to Exercise 3</a>, <a href="http://www.zib.de/lindner/MAPTN_2018/P1E3-extended.py">extended solution</a>)</li><li><a href="http://www.zib.de/lindner/MAPTN_2018/P2.pdf">Problem set 2</a> (due on May 1, <a href="http://www.zib.de/lindner/MAPTN_2018/NuernbergU.csv">Nürnberg U-Bahn network</a>)</li><li><a href="http://www.zib.de/lindner/MAPTN_2018/P3.pdf">Problem set 3</a> (due on May 7)</li><li><a href="http://www.zib.de/lindner/MAPTN_2018/P4.pdf">Problem set 4</a> (due on May 22, <a href="http://www.zib.de/lindner/MAPTN_2018/connections.csv">connections.csv</a>, <a href="http://www.zib.de/lindner/MAPTN_2018/P4E2.py">code for Exercise 2</a>)</li><li><a href="http://www.zib.de/lindner/MAPTN_2018/P5.pdf">Problem set 5</a> (due on May 28)</li><li><a href="http://www.zib.de/lindner/MAPTN_2018/P6.pdf">Problem set 6</a> (due on June 4)</li><li><a href="http://www.zib.de/lindner/MAPTN_2018/P7.pdf">Problem set 7</a> (due on June 11, <a href="http://www.zib.de/lindner/MAPTN_2018/wien.zip">wien.zip</a>)</li><li><a href="http://www.zib.de/lindner/MAPTN_2018/P8.pdf">Problem set 8</a> (due on June 18, <a href="http://www.zib.de/lindner/MAPTN_2018/P7E1.py">code for Exercise 1</a>, <a href="http://www.zib.de/lindner/MAPTN_2018/P7E2.py">code for Exercise 2</a>)</li><li><a href="http://www.zib.de/lindner/MAPTN_2018/P9.pdf">Problem set 9</a> (due on June 25, <a href="http://www.zib.de/lindner/MAPTN_2018/P9E2.py">matrix minor random sampling code</a>)</li><li><a href="http://www.zib.de/lindner/MAPTN_2018/P10.pdf">Problem set 10</a> (due on July 9)</li><li><a href="http://www.zib.de/lindner/MAPTN_2018/TE.pdf">Test exam</a> (discussed on July 16)</li></ol>You may work in groups of two. Problem sets should reach me no later than on the indicated day, either on paper or by e-mail.  The aim of this lecture is to present some interesting and easy-to-understand problems around public transportation networks and to explain mathematical concepts behind them. Although most of the mathematics is rather intuitive, we will also touch a few research-level topics. Chapter 1: S-Bahn-Challenge (<a href="http://www.zib.de/lindner/MAPTN_2018/L1.pdf">Lecture 1</a>, <a href="http://www.zib.de/lindner/MAPTN_2018/L2.pdf">Lecture 2</a> and <a href="http://www.zib.de/lindner/MAPTN_2018/S-Bahn-Challenge_MathInside.pdf">talk for high school students</a>)<ol><li>Walks in graphs</li><li>The Chinese Postman Problem</li><li>The Traveling Salesman Problem</li><li>Generalized Routing Problems</li><li>Public Transportation Networks</li></ol>Chapter 2: Shortest Routes in Public Transportation Networks (<a href="http://www.zib.de/lindner/MAPTN_2018/L3.pdf">Lecture 3</a>, <a href="http://www.zib.de/lindner/MAPTN_2018/L4.pdf">Lecture 4</a>, <a href="http://www.zib.de/lindner/MAPTN_2018/L5.pdf">Lecture 5</a>)<ol><li>Overview</li><li>Graph Methods</li><li>Advanced Methods</li><li>Multi-Modal Routing</li></ol>Chapter 3: Periodic Timetabling (<a href="http://www.zib.de/lindner/MAPTN_2018/L6.pdf">Lecture 6</a>, <a href="http://www.zib.de/lindner/MAPTN_2018/L7.pdf">Lecture 7</a>, <a href="http://www.zib.de/lindner/MAPTN_2018/L8.pdf">Lecture 8</a>)<ol><li>Overview (introducing PESP and its complexity)</li><li>Cycle Spaces</li><li>Cycles in Periodic Timetabling</li><li>Modulo Network Simplex</li><li>Further Topics</li></ol>Chapter 4: Vehicle Scheduling (<a href="http://www.zib.de/lindner/MAPTN_2018/L9.pdf">Lecture 9</a>)<ol><li>Periodic Vehicle Scheduling</li><li>Aperiodic Vehicle Scheduling</li><li>Railway Stock Rotation Planning</li></ol>Chapter 5: Line Planning (<a href="http://www.zib.de/lindner/MAPTN_2018/L10.pdf">Lecture 10</a>, <a href="http://www.zib.de/lindner/MAPTN_2018/L11.pdf">Lecture 11</a>)<ol><li>Overview</li><li>Passenger-oriented Models</li><li>Steiner Connectivity</li></ol>Chapter 6: Metro Map Drawing (<a href="http://www.zib.de/lindner/MAPTN_2018/L12.pdf">Lecture 12</a>)<ol><li>Metro Maps</li><li>Planar Graphs</li><li>Octilinear Layout Computation</li></ol> <table style="width: 464px; height: 58px;" border="0"><tbody><tr><td> </td><td>Time</td><td>Location</td></tr><tr><td>Lecture</td><td>Mon 14-16</td><td><a title="ZIB" href="http://www.zib.de/contact">ZIB</a> 2006 (Seminarraum Rundbau)</td></tr><tr><td>Tutorial</td><td>Thu 12-14</td><td><a title="ZIB" href="http://www.zib.de/contact">ZIB</a> 2006 (Seminarraum Rundbau)</td></tr></tbody></table> Exams (written, 60 minutes, be on time):<ul><li>August 7, 10am, ZIB seminar room 2006</li><li>October 8, 10am, ZIB seminar room 2006</li></ul>You are allowed to bring one A4 sheet with notes. First lecture: April 16.First tutorial: April 19.The tutorial on April 26 has been shifted to 16-18.There will be a lecture on April 30.There is no tutorial on May 10 and no lecture on May 21.The lecture on June 18 takes place in the ZIB meeting room 3028.No lecture on June 25 (Visit of the Scientific Advisory Board).No tutorial on July 12 and on July 19. There are no formal requirements, the course will try to be self-contained.However, you could take a look at the parallel <a href="http://www.zib.de/node/3501">lecture Optimization III</a> and the <a href="http://www.zib.de/node/3446">seminar on shortest paths</a>. <table style="width: 456px; height: 40px;" border="0"><tbody><tr><td>Name</td><td>Room</td><td>E-Mail</td><td>Office hours</td></tr><tr><td><a href="http://www.zib.de/lindner">Dr. Niels Lindner</a></td><td><a title="ZIB" href="http://www.zib.de/contact">ZIB</a> 3007</td><td>lindner@zib.de</td><td>by appointment</td></tr></tbody></table>