DELIVER

Distributed Coordination for Perpetual Planning

(duration: 01-2010 - 12-2012 /// funding: Eureka)

Project summary

Current ICT systems used in the logistics industry make use of a priori planning: schedules are made days, or even weeks in advance. Such systems are incapable of adapting to disturbances, changes or delays. Mobile services (repair, security), home delivery services and courier services are estimated to suffer a 20% inefficiency because of this. Not to mention the unhappy customers, who do not appreciate delays.

The DELIVER project seeks to research, design and develop perpetual planning software for the logistics industry, which is capable of changing the plan when that is necessary. This requires a much stronger interaction with the "real world" than in a priori planning. The actual status of all entities and actors has to be monitored in order to identify disturbances and to facilitate coordination.

Naturally, incidents happen in every part of the process: drivers get sick, trucks break down, traffic jams occur, urgent tasks come up. From the perspective of an a priori planning system, these unavoidable events are all treated as "incidents that disturb the optimal solution" or "noise that must be filtered out". In a continuous planning system, events would be really treated as events rather than "incidents" or "noise", and truck drivers would never be "behind schedule" because the schedule itself evolves on-the-fly.

Contribution Almende

Almende is the project partner which offers the most experience with applied ICT research. Where the university partners offer fundamental research, and Trigion tests the product in a real-life environment, Almende acts as the link between the two.

The challenge the project members have to face, is to design software that can compute plans based on incomplete information. Although existing algorithms do not have this capability, they do have their merits, and so the project will use different algorithms in parallel.

* bio-inspired optimization algorithms support dynamically changing requirements, multi-objective problems and fuzzy constraints.
* traditional OR techniques perform very well on smaller but completely identified problems.
* approximate algorithms generate acceptable solutions in a "time-efficient" manner and do not make strong assumptions regarding the problem they solve.

Based on two ideas, multi-agent systems and coordinated parallel algorithms, we propose to create an agent-based planning system as visualized below. The planning system consists of three logical layers: representation, coordination and algorithms.

Partial solutions, as created by the algorithms, are evaluated based on evolving criteria learnt from the past. However, plans cannot be adjusted continuously, and so a balance needs to be sought between optimality and stability.

Finally, the system will be able to learn which algorithms eventually perform better or quicker on which types of problems, i.e. on which patterns of incoming events, and how these algorithms can be coordinated in a more efficient manner.

Links

The DELIVER project website

Partners