BERLIN SUBWAYS – PERIODIC TIMETABLE OPTIMIZATION

영상

BERLIN SUBWAYS – PERIODIC TIMETABLE OPTIMIZATION

저작권

게시자

크레딧

A film by Prof. Dr. Rolf Möhring, Dr. Christian Liebchen and Dr. Sebastian Stiller.
Peter Brinkmann, Samy Khadem-Al-Charieh, Pia Busch
Eric Hansen
Nils Bleicher, Bernd Gonska
Kai-Uwe Schulenburg
Andrea Niessen
Torpedo, Reinhard Sydow
Stephan Fleischer, Samy Khadem-Al-Charieh
지원: 
DFG Research Center MATHEON

베를린의 지하철 시스템은 19개의 환승역을 가지고 있습니다. 어떻게 이 시스템 안의 사람들의 대기 시간을 최소화하는(물론 모든 안전요건을 갖춘) ‘주기를 갖는 시간표’를 계산하여 얻을 수 있을까요? 이는 매우 복잡한 문제로써 전통적으로 ‘부과업(subtask)’ 으로 쪼개는 방식을 이용하여 다루어져 왔습니다.

2005년 이 네트워크의 시간표는 베를린 공과대학(Technische Universität Berlin, TU Berlin)의 Matheon 연구소에 의해 계산되어 얻어졌습니다. 핵심은 조합 최적화(combinatorial optimization)의 최신 기술들입니다. 베를린의 대중교통 시스템은, 역을 점(vertex)으로 하고 두 역 사이를 변(edge)으로 하고 몇몇 제약조건을 갖는 그래프 모형으로 생각될 수 있습니다.

제약조건을 만족하는 모든 가능한 해 중에는 대기 시간과 열차 대수를 최소화 하는 최적의 해가 숨어 있습니다. 그러나 가능한 전체 해의 집합은 너무 크기 때문에, 가장 강력한 성능을 가진 컴퓨터를 이용해서도 모두 분석하기는 어렵습니다. 기발한 수학적 기술을 이용하여 대부분의 해를 제외시킬 수 있는 강력한 성능의 알고리즘을 만들어, 최적해가 존재하는 소구역에 집중할 수 있습니다. 

이 영상은 영어와 독일어로 제공되며, 우측의 “download link”를 클릭하여 다운받을 수 있습니다. 

관련 자료

영상 더 보기