Onderzoek met M-Industries: Het optimaliseren van het aantal rekken per uur door een anodiseerstraat

M-Industries BV is een software startup in Delft. Wij verkopen maatwerksoftware op basis van een inhouse ontwikkeld model driven, web based platform. De kern van dit platform wordt gevormd door een unieke datamodelleertaal. Daarmee zijn we in staat voor de volle 100% model driven te werken. Wij werken op dit moment met 5 mensen, waarvan 4 fulltime aan het programmeren zijn. Wij richten ons op de industrieele markt en hebben de wereldleider op het gebied van aluminiumextrusie als launching customer.

Wij zijn op zoek naar een student die de scheduling van een anodiseerstraat wil optimaliseren. In een anodiseerstraat staan meerdere baden van 7 meter breed achter elkaar opgesteld, elk met zijn eigen chemische/elektrische functie. Om bepaalde materiaaleigenschappen te bereiken moeten producten op rekken worden bevestigd en een bepaalde volgorde van behandelingen in die straat ondergaan. Het transport van de rekken van het ene naar het andere bad gebeurt met enkele kranen. De software die op dit moment de lijn aanstuurt plant ad hoc; het kijkt naar de huidige status van de straat, en plant op basis daarvan de volgende actie. Omdat het systeem niet genoeg vooruit denkt, wordt niet de maximale capaciteit van de straat benut. De nieuwe software moet voor een shift lang (8 uur) vooruit kunnen plannen om zodoende meer rekken per uur te kunnen verwerken. Er moet een optimalisatie algoritme ontwikkeld worden dat via webservices (XML of mogelijk JSON) zijn data binnen krijgt en de planning oplevert. De oplossing moet worden gerealiseerd in dot net of node.js.

Plan repair in multi-agent route planning

In multi-agent route planning, agents (vehicles) coordinate their movements by reserving time slots on sections of the infrastructure. These reservations ensure that no part of the infrastructure contains more vehicles than desirable, while also providing the agents with predictable travel times. In case unexpected incidents disrupt the execution of the route plans, however, collisions or deadlocks could occur. What can we do to ensure that each agent reaches its destination in a timely manner?

In this project, you will devise and implement algorithms for plan repair. Existing methods focus on changing only the timing of plans, but these are sub-optimal, and only applicable to a restricted set of incidents. You will therefore explore the possibilities of re-routing in order tackle more types of incidents, and to improve on the exisiting methods when both are applicable.

Selfish routers on smart infrastructures

Two types of agents in the daily traffic problem are the vehicles that make use of the infrastructure, and those who manage it (typically the authorities). The goals of these agents are neither exactly opposed nor perfectly aligned: agents driving vehicles usually want to reach their destination in the minimum time, whereas traffic managers want to minimize the congestion on the infrastructure as a whole.

So far, research into the traffic problem has focused on one but not both of these perspectives: either the problem is to find a shortest-time route for a single vehicle, possibly taking congestion and the planned movements of others into account, or to manage the infrastructure resources (e.g. by altering the timing of traffic lights) gives some assumed default behavior of (flows of) vehicles. We believe it is time for an approach to the traffic problem that integrates both perspectives.

The traffic problem can be viewed as a non-cooperative game in which the players are the traffic manager(s) and the infrastructure users. Your assignment will be:

• To model the traffic problem and the non-cooperative traffic game
• To come up with strategies for all types of agents
• Mechanism design: To investigate whether it is possible to change the rules of the game (e.g. by introducing road pricing) in such a way that the global behavior of the system, resulting from the actions of utility-maximizing agents, is improved.

In our research group, you will be working alongside experts in multi-agent route planning, planning and scheduling, and mechanism design, and you can benefit from our contacts with partners in industry.

Coordination between least-commitment planning agents at APM terminals

APM operates a terminal for the transshipment of containers between sea-going vessels and inland transportation modes such as trucks, trains, and barges. The operations of a container terminal involve loading containers off ships, positioning the containers around the terminal, deciding if and how to stack containers on top of each other and getting containers ready for pickup by e.g. a truck. A challenge is posed by reefer containers (i.e., containers that have to be kept cool), because these need to be hooked up to electricity. The problem we consider is to try to improve the efficiency of the operations of the APM terminal.

One way of achieving improved efficiency is through operational (i.e., short-term) planning. One challenge in making a plan for all of the parties involved (e.g. terminal operator, trucking company or shipping company) is that they depend on the time in each other's plan: a truck needs to know when a container can be picked up, while the terminal operator needs to know when the container should be placed at a pickup location, but also when it can be retrieved from the ship. A least-commitment approach to planning will defer decisions about e.g. timing and sequencing of actions until the last moment, when more accurate information is available. Coordination between parties should be achieved by flows of increasingly accurate information, and should ensure that the plan refinement processes of each of the agents converge to a stable global plan.

Prediction of material malfunctions in trains

Modern trains are equipped with a lot of ICT supplies. This makes it possible to obtain sensor data, which can be used for data-mining. In this masters project the goal is to find, within this sensor data, indicators for (soon to be) malfunctioning material. These indicators can then be used to give advice regarding which parts of the train should be inspected and/or repaired.

This thesis consists of two parts:

• Construct, using patterns in the sensor data and repair history, a decision model which shows what parts of the train should be inspected.
• Refine the constructed model in order to use it for prediction of how long it will take before a part will malfunction.

Quality personal transport for elderly and disabled people

Currently the quality of personal transport for elderly and disabled people is very low. The main reason is the heavy competition for the three-year long contracts with governmental institutions. What if people can choose their preferred company per ride? What if people can choose between different pick-up times for their transport?

In this project you will test multiple methods for assigning transportation jobs to taxi companies, such that the preferences and quality for the end-users increases without increasing the costs for the government too much.

City logistics

Cities do not like trucks in their city center, but still their stores need supplies. Many cities therefore have strict rules for when trucks are allowed in the city center. These rules are different for every city, but still often such that one truck of a chain of stores cannot visit multiple cities at the same day. Can we help the national government to set-up a game such that cities and trucking companies are encouraged to coordinate their schedules?

For this project you will study the interesting field of mechanism design. To get to know more about the application, we will bring you into contact with researchers from the Erasmus university who are studying many other aspects of city logistics as well.

Planning in the harbor

In the harbor in Rotterdam, every day many barges need to visit a number of the terminals. Sometimes they need to wait a long time before they are served. What can we do to coordinate the loading and unloading of barges at the different terminals better to reduce the total time barges spend waiting for their turn?

For this project you will study the interesting field of mechanism design. To get to know more about the application, we will bring you into contact with researchers from the Erasmus university who are studying many other aspects of the process in the harbor as well.

Barge/lock scheduling

When barges sail from Roterdam harbor to Germany they need to pass a number of locks. Such locks open about every half an hour, so if a ship just missed an opening, it has a delay. Also a lock has a limited capacity, so if someone arrives at the lock just ahead of you, you also have to wait. Because of this, many barges sail at maximum speed to try to catch the current opening. Often they fail anyway, because they do not know the current situation at the lock.

In this project you will test multiple methods for assigning slots in an opening to barges in advance. This assignment should be fair, and it should reduce the urge of shippers to sail at the (costly) maximum speed, while maintaining (or even improving) the average throughput of ships over our rivers.

Preferences in temporal planning

At airports many processes such as the arrival and departure of planes and the use of gates need to be coordinated in time. Several parties have different preferences concerning the resulting schedules.

In this project you will develop a (search) algorithm to solve the temporal planning problem with preferences. Some of the techniques from the Satisfiability master course can be used to develop this temporal solver. Currently already one Master student is working on this project to give you a good head start.

(Cooperative) multiagent planning competition

Many existing competitions or problem settings include a multiagent planning component: in Robo Rescue robots need to coordinate their plans to get people safely out of hazardous environments. In the Trading Agent Competition and especially the supply chain management game, the activities of different organizations involved in getting products to the customers need to be coordinated. Finally, in the DARPA Coordinators program, the problem setting is to provide automated decision support for military field units. For each of these settings different algorithms are used. This project is an investigation of these settings and about a comparison, and possibly improvement of the existing approaches.

Part of the research assignment could be to set-up a competition for such cooperative multiagent planning problems and/or participate in one the competitions mentioned above.

Other topics related to multi-agent systems

Within the Algorithmics group we also study some other topics that do not directly deal with multi-agent systems and transportation. In consultation with the mentioned supervisor, you can also work on one of the following topics:

• continue on the paper you wrote for the CABS seminar
• game-theoretical multiagent planning
• dealing with resource conflicts
• task allocation
• dealing with incidents
• satisfiability

These projects all have a practical side, but can also be extended with a theoretical counter part. The project will be adapted to your own interests and abilities.

More information

• Cees Witteveen 015 - 278 2521 C.Witteveen at tudelft.nl
• Mathijs de Weerdt 015 - 278 4516 M.M.deWeerdt at tudelft.nl
• Tomas Klos 015 - 278 3895 t.b.klos at tudelft.nl

If you are currently not studying in Delft, but if you'd like to study here, please read and act according to the formal guidelines found on the webpage of the Delft University.