<p><strong><strong>10.10.2018: </strong></strong><a href="http://www.zib.de/lindner/MAPTN_2018/K2L.pdf">Solutions to the second exam.</a></p><p><strong><strong>09.10.2018: </strong></strong><a href="http://www.zib.de/lindner/MAPTN_2018/K2R.pdf">Results of the second exam. </a></p><p><strong><strong>26.09.2018: </strong></strong><a href="http://www.zib.de/lindner/MAPTN_2018/K1L.pdf">Solutions to the first exam are online<strong><strong>.</strong></strong></a></p><p><strong><strong>07.08.2018: </strong></strong><a href="http://www.zib.de/lindner/MAPTN_2018/K1R.pdf">Results of the first exam are online</a>.<strong><strong><br /></strong></strong></p><p><strong><strong>12.07.2018: No tutorial</strong></strong> (excursion).</p><p><strong><strong>25.06.2018: No lecture</strong></strong>. The lecture takes place on Thursday instead of the tutorial.</p><p><strong><strong>18.06.2018: </strong></strong>The <strong>lecture</strong> takes place in the ZIB meeting room<strong><strong> 3028. </strong></strong></p><p><strong><strong>29.05.2018:</strong></strong> Added slides of May 28, with some modifications in the cycle spaces part. <strong>Update:</strong> Exercise 2b in Problem Set 6 should end with "in its last columns", not with "in its last rows".</p><p><strong><strong>15.05.2018: </strong></strong>Slides update: Renamed LCSPP to LCSWP (replacing "path" by "walk").</p><p><strong><strong>08.05.2018: </strong></strong>There will be <strong>no tutorial on May 10</strong> and <strong>no lecture on May 21</strong>. Problem Set 4 is due on May 22 (Tuesday).</p><p><strong><strong>19.04.2018: </strong></strong>The <strong>tutorial on April 26</strong> as been shifted to <strong>16-18</strong> and will take place in the ZIB seminar room.</p><p><strong>19.04.2018: </strong>Slides update: Corrected a mistake in Improved Hierholzer's Algorithm.<strong><br /></strong></p><p><strong>16.04.2018:</strong> The tutorial sessions have been shifted to Thursdays, 12-14. The tutorial on April 19 will take place in the ZIB lecture hall.</p><p> </p><h3><strong>Problem sets:</strong></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><p>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.</p><p> </p>
<p>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.</p><p> </p><p>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>)</p><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><p>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>)</p><ol><li>Overview</li><li>Graph Methods</li><li>Advanced Methods</li><li>Multi-Modal Routing</li></ol><p>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>)</p><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><p>Chapter 4: Vehicle Scheduling (<a href="http://www.zib.de/lindner/MAPTN_2018/L9.pdf">Lecture 9</a>)</p><ol><li>Periodic Vehicle Scheduling</li><li>Aperiodic Vehicle Scheduling</li><li>Railway Stock Rotation Planning</li></ol><p>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>)</p><ol><li>Overview</li><li>Passenger-oriented Models</li><li>Steiner Connectivity</li></ol><p>Chapter 6: Metro Map Drawing (<a href="http://www.zib.de/lindner/MAPTN_2018/L12.pdf">Lecture 12</a>)</p><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><strong>Time</strong></td><td><strong>Location</strong></td></tr><tr><td><strong>Lecture</strong></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><strong>Tutorial</strong></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><p> </p><p><strong>Exams </strong>(written, 60 minutes, be on time)<strong>:</strong></p><ul><li>August 7, 10am, ZIB seminar room 2006</li><li>October 8, 10am, ZIB seminar room 2006</li></ul><p>You are allowed to bring one A4 sheet with notes.</p><p> </p><p>First lecture: April 16.</p><p>First tutorial: April 19.</p><p>The tutorial on April 26 has been shifted to 16-18.</p><p>There will be a lecture on April 30.</p><p>There is no tutorial on May 10 and no lecture on May 21.</p><p>The lecture on June 18 takes place in the ZIB meeting room 3028.</p><p>No lecture on June 25 (Visit of the Scientific Advisory Board).</p><p>No tutorial on July 12 and on July 19.</p>
<p>There are no formal requirements, the course will try to be self-contained.</p><p>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>.</p>
<table style="width: 456px; height: 40px;" border="0"><tbody><tr><td><strong>Name</strong></td><td><strong>Room</strong></td><td><strong>E-Mail</strong></td><td><strong>Office hours</strong></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>