eunite

research

applications

knowledge transfer

e-archives



Using a multi-agent approach to optimise the train coupling and sharing system

Submitted by Josefa Z. Hernandez 27.11.2001, IBA B

Problem

The problem consists of scheduling a given set of transportation tasks in a railway network reducing the cost. Each task is specified as a tuple consisting of the origin and the destination node; the earliest possible departure time, the latest allowable arrival time and an additional time stamp indicating when the task is announced to the system. To reduce the track allocation cost and to increase the capacity of tracks, different modules are coupled together and uncoupled. This allows the joint use of the train paths by the formed module-sets for the track allocation price near by one module.

Solution

In the Institute of Transport, Railway Construction and Operation, at the University of Hannover, a multi-agent system approach has been used for the innovative train coupling and sharing system (TCS). It has been used an incremental planning approach that takes incomplete task specifications into account and uses the contract-net protocol to obtain a initial plan. Then, a post-optimisation of the initial solution is achieved by means of the simulated trading protocol. The plan execution-monitoring unit of the agent, which dynamically reacts to external events and which can initiate a revision of the actual plan of the agent, draws the link between the agents planning unit and the external world.

The agents in the TCS/MAS-system are based on the architecture for the integration of reactive behaviour and rational planning (InteRRaP), which was developed at the DFKI. The goal of this kind of architecture is the combination of reactive and planned performance. Agent architecture with these kinds of attributes is also called "hybrid architecture". These kinds of agents can carry out simple actions on demand (reactive behaviour), plan complex actions on the basis of their base knowledge alone (planned behaviour) and co-operate with other agents (co-operative behaviour).

Status and results

In the current version of the system, an abstracted map of the German railroad network with approximately 250 nodes and 350 links has been used. In the simulation process, the results of three different optimisation levels were compared. The first one, without optimisation (without coupling and sharing process) and then with minimal sharing length requirement (100 and 200 km). The results were better when it was permitted coupled and sharing with the minimal sharing length, since this minimal sharing length prevents same unions to commit them to sharing partners with low cost-saving potential (i.e. with only a short common path) to early. These early commitments, made in the case where the minimal sharing length exits, make impossible for the units to benefit from better sharing peers that occur later within the integration process because they cannot satisfy the additional constraints and thus have to reject route sharing.

Adaptivity and portability

The main idea of multi-agent system is to generate approximate solutions to very complex problems by distributing then to autonomous problem solvers (agents). These agents would be able to solve local problems by themselves. By integrating the agents in a communication environment, they are able to find a solution for the whole problem in co-operating with each other. These autonomous problem solvers can be used in a lot of problems and can be reused for other problems of scheduling.

More information

J. Bocker et al. European Journal of Operational Research 134 (2001) 242-252

technical reports & case studies

executive summaries

scientific papers

tutorials

bibliography

e-dictionary

search eunite with

google



  home