|
Click on a theme or a project in the table below for more information.
Project leader:
Dr. Peter A.N. Bosman (CWI)
Consortium:
CWI, TU/e, UT, UU
Industrial partners (non-exhaustive):
NS Reizigers, Microsoft Research, KLM, Schiphol, Ortec, Rüttchen
Total FTE: 10.8 (heads: faculty: 27, PhD: 6)
Key BRICKS publications:
| • |
Fioole, Kroon, Maróti, Schrijver: "A rolling stock circulation model for combining and splitting of passenger trains" In: European Journal of Operational Research 174(2), 2006, 1281-1297
|
| • |
Van Leeuwen: "Better Approximation Schemes for Disk Graphs " In: Arge, Freivalds. (eds.) Algorithm Theory - SWAT 2006, 10th Scandinavian Workshop on Algorithm Theory, Riga, Latvia, July 6-8, 2006, Proceedings, LNCS 4059, Springer-Verlag, Berlin, 2006, pp. 316-327
|
| • |
Sitters, Stougie: "The generalized two-server problem" In: Journal of the ACM 53, 2006, 1-22
|
| • |
Brueggemann, Hurink, Kern: "Quality of move-optimal schedules for minimizing total weighted completion time" In: OR Letters 34, 2006, 583-590
|
| • |
Bosman, La Poutré: "Computationally intelligent online dynamic vehicle routing by explicit load prediction in an evolutionary algorithm" In: Parallel Problem Solving from Nature - PPSN IX, pages 312-321, Springer-Verlag, Berlin, 2006
|
|
Project IS3: Decision Support Systems for Logistic Networks and Supply Chain Optimization
In several sectors of society, we are faced with problems that can
be modelled as problems on networks. Examples are: routing of
trains in station areas, design of telecommunication networks,
design of wireless networks, scheduling of aircraft crew, assigning
airport gates, workflow scheduling, timetabling, and management of
supply chains. In some cases the network structure is given, such
as the tracks in a railway station, and sometimes it is not, such
as in the design of computer and telecommunication networks. In
designing networks and in determining the flow in the network one
needs to take several capacity, legal, and topological constraints
into account. It is also essential to develop an appropriate
measure of what we mean by a good design.
Research in the theme BRICKS-IS3 focuses on developing methods and
algorithms for such problems using tools and techniques in
particular from operations research, integer and linear
programming, graph theory, learning, evolutionary computing, and
agent-based computational economics.
Industrial cooperation
In cooperation with NS Reizigers work has been done on rolling
stock planning, that is, the planning of how many locomotives and
passenger carriages are needed and how to use them for trains. The
models resulting from this work, together with work by Schrijver on
various optimization problems at the Dutch railways, have been used
when developing the new timetables and trajectories of the
railways.
Jules van Kempen, a MSc student, has under the supervision
of Aardal worked for a large car dealer, Rüttchen b.v.,
in Breda to develop an on-line planning system of their car repairs
and maintenance activities. Van den Akker, Hoogeveen, and Diepen
have developed a bus and gate planning system together with
Schiphol airport.
Highlights 2004-2006
Research highlights
Bruggeman, Hurink, and Kern have examined the quality of local
optima for several neighborhood structures for some scheduling
problems leading to worst case performance guarantees for local
search. Furthermore, for the same scheduling problems large-scale
neighborhood structures are developed. The group in Twente also
investigate the impact of the presence of adjacency requirements
for resources on scheduling models, and exact algorithms for
solving Steiner tree problems occurring in for instance chip
design. They have shown that the problem for k terminals can be
solved in roughly O(2k) steps. The best known previous bound (since
1970) was O(3k).
Van den Broek, Hurkens, and Woeginger, have
developed a decision support tool for a timetabling problem
occurring at the Department of Industrial Design at Eindhoven
University of Technology. Students are submitting a list of
preferred courses to the academic office and they have to produce a
plan for each student consisting of non-overlapping classes. The
same group is also working with the Dutch Railways to produce shunt
plans.
Bosman, and La Poutré are investigating how to
perform optimization for problems that are dynamic and need to be
solved on-line, such as inventory management and vehicle routing.
One of the focal points is how to take into account future
consequences of current actions. They use learning methods to
forecast future events, taking into account decisions taken earlier
when making such predictions.
Van Leeuwen gave approximation
schemes on unit disk graphs for several relevant problems,
including the problem of finding minimum-sized communication
backbones and finding maximum-sized sets of non-interfering
devices. The approach for the latter problem was recently
generalized to disk graphs induced by arbitrary disks, while the
former problem on general disk graphs remains the subject of
ongoing and future research.
Future work 2007-2009
An important issue in logistics is better forecasting. We will also
further develop a learning-based framework and software to problems
from the literature, specifically inventory management. We aim at
continuing the work on scheduling problems where there are adjacent
requirements on the resources, and on game theoretic concepts which
may play a role in sharing additional revenue which results from
cooperation within a supply chain. We also aim at studying
telecommunication problems in future telecom networks.
IS3 Researchers funded by BRICKS
- Prof.dr. A. Schrijver (CWI)
- Prof.dr.ir. K.I. Aardal (CWI)
- Dr.ir. J.M. van den Akker (UU)
- Dr. H.L. Bodlaender (UU)
- Dr. S.M. Bohte (CWI)
- Dr. P. Bosman (CWI)
- Dr. H.J. Broersma (UT)
- Dr. N.P. Dellaert (TU/e)
- Dr. H.J. Driessen (UT)
- Prof.dr. A.M.H. Gerards (CWI)
- Dr. J.A. Hoogeveen (UU)
- Dr. J.L. Hurink (UT)
- Dr. C.A.J. Hurkens (TU/e)
- Dr. W. Kern (UT)
- Prof.dr. A.G. de Kok (TU/e)
- Prof.dr.ir. J.A. La Poutré (CWI)
- Dr. M. Laurent (CWI)
- Prof.dr. J. van Leeuwen (UU)
- Dr. D. Paulusma (UT)
- Dr. R. Pendavingh (TU/e)
- A.G. Steenbeek (CWI)
- Dr. L. Stougie (TU/e)
- Prof.dr. G.J. Woeginger (TU/e)
- Drs. E.J. van Leeuwen (CWI)
- Ir. J.J. Paulus (UT)
- Drs. G. Diepen (UU)
- Drs. S. Ju (TU/e)
- Ir. J.J.J. van den Broek (TU/e)
For more information, please refer to the publications and posters of this project.
|
