日時：2013年11月18日（月）13:30-16:00
場所：九州大学 伊都キャンパス 数理学研究教育棟／マス・フォア・インダストリ研究所3F 中セミナー室7
講演者：Ralf Borndörfer (Zuse Institute Berlin)
参考URL：
http://www.imi.kyushu-u.ac.jp/seminars/view/1211
http://www.imi.kyushu-u.ac.jp/seminars/view/1212

13:30-14:30
Title: Optimization in Traffic and Transport
Speaker: Ralf Borndörfer (Zuse Institute Berlin)
Abstract:
The mathematical treatment of planning problems in public transit, 
air, and rail traffic has made enormous advances in the last decade. 
Classical problems of vehicle and crew scheduling can nowadays be 
solved on a routine basis and for large scenarios using combinatorial 
optimization methods. This is not yet the case for problems that 
pertain to the design of public transit networks, and for problems of 
operations control that address the implementation of a schedule in 
the presence of disturbances. The talk surveys the state-of-the-art 
and some exciting developments in the area, and it addresses major 
challenges for the future.

15:00-16:00
Title: Configuration Models in Transport Optimization
Speaker: Ralf Borndörfer (Zuse Institute Berlin)
Abstract:
Configurations are local solutions of network optimization problems 
that can be used to assemble an overall solution. They are used to 
express complex requirements, that would be hard to formulate using 
constraints, by means of a local and hence manageable enumeration of 
``feasible configurations''. This gives rise to an extended 
formulation involving additional configuration variables. Usually, 
one has to make choices between several possible configurations, such 
that configuration models are often of a set packing, partitioning, 
or covering type. Such a formulation is combinatorially clean and 
lends itself to column generation techniques. If the configurations 
capture a core aspect of the problem, such a model will be provably 
strong, if the configurations can be computed efficiently, it is 
algorithmically tractable. Typical examples of configuration models 
come up in transport optimization, where the integrated treatment of 
technical etc. constraints or the simultaneous solution of 
multi-stage models is a major challenge. Successful applications 
include railway track allocation, leading to path packing 
configuration models, railway rotation planning, resulting in 
hypergraph assignment and flow models, and depot management as well 
as line planning, leading to set partitioning type models. All of 
these models provide strong LP bounds and can be solved efficiently 
for large scale real-world problems. The talk surveys these results. 
It is based on joint work with Martin Grötschel, Olga Heismann, Heide 
Hoppmann, Marika Karbstein, Torsten Klug, Markus Reuther, Thomas 
Schlechte, Elmar Swarat, and Steffen Weider.

問合せ先：来嶋（B01）