TeleTruck:
A Holonic Fleet Management System

Hans­Jürgen Bürckert, Klaus Fischer, Gero Vierke

German Research Center for Artificial Intelligence (DFKI GmbH)
Stuhlsatzenhausweg 3, D­66123 Saarbrücken
{hjb,kuf,vierke}@dfki.de

Abstract

In this paper we describe TeleTruck, a multiagent dispatching system that was developed in close cooperation with a forwarding company and that is capable of handling real­world requirements like dynamics and uncertainty. The main idea underlying the TeleTruck approach is the usage of holonic agents, i.e. agents composed of subagents that act in a corporated way. We describe the implementation in detail and point out the advantages of the holonic paradigm.

1 Introduction

Order dispatching in a haulage company is known as a rather complex problem that attracted researchers from operations research (OR) as well as from multiagent systems (MAS) [ Desrochers et al., 1992; Sandholm, 1993; Fischer and Kuhn, 1993 ] . Up to now, there are no approaches which are able to deal with the dynamic and uncertain nature of transportation orders. Hence, no general software solution for transportation companies is available.

Often transportation companies do not use any dispatch software at all but schedule transportation orders by hand, distribute the cargo among their vehicle fleet, and calculate the routes in an ad hoc manner only ``optimised'' by the experience of their stressed dispatch officers. Therefore, transportation companies have a high potential for rationalisation and optimisation. Because of this demand and its natural distribution the dispatch problem is a highly promising area for distributed AI technology.

In this paper we describe our approach taken in the TeleTruck system. TeleTruck is an extended reimplementation of the MAS­MARS system [ Fischer et al., 1996 ] , which is a research prototype for transportation scheduling. MAS­MARS implements an abstract, simplified version of the dispatch problem. The agents of MAS­MARS represent homogeneous trucks. They negotiate on incoming orders and optimise the distribution and execution of these orders according to an abstract cost measure. The TeleTruck system is an application prototype developed in close collaboration with a forwarding company. It schedules realistic orders using heterogeneous agents modelling different forms of vehicles. A central idea underlying the TeleTruck approach is to model the basic physical objects (drivers, trucks, trailers, containers) of the transportation domain explicitly by basic agents. These agents have to join together and form holonic agents that act in a corporated way. These composed agents represent the physical transportation entities (e.g., road trains or articulated vehicles together with their drivers) which are able to execute the orders.

In the next section we discuss the application domain in more detail. Section 3 presents some basics of holonic MAS. In Section 4 we describe the modelling of the domain, the architecture of TeleTruck, and, finally, its implementation.

2 Fleet Scheduling

The task of a dispatch officer in a forwarding company is to schedule a fleet of vehicles and their drivers such that all incoming and accepted transportation orders will be performed with minimal costs and maximal profit. The dispatch officer should guarantee as far as possible that the available transport vehicles are used with balanced loads, with minimal routes and time for the tasks at hand---of course under the constraints that all customer requirements are fulfilled optimally.

The dispatch officer has to consider both the company's own vehicles and those of subcontractors and partners. The vehicle fleet may consist of trucks, road trains, and articulated vehicles of different sizes and types. Trucks and trailers may have fixed or exchangeable loading space. Containers or swap bodies may again be owned by the forwarder, his partners, or even the customers. The drivers have to be scheduled by the dispatch officer according to their free driving times (limited by their contracts or by laws). Amount and type of cargo, different types of time windows (delivery or pick up times, opening times, etc.), consignor and consignee are the features of the transportation orders that have to be taken into account by the dispatch officer.

From an abstract point of view two types of transportation settings can be distinguished: The general one where orders are to be transported between any two places is called the pick­up­and­delivery­problem and the restricted setting where the cargo has to be delivered to different points from a single depot or vice versa is known as vehicle­routing­problem.

In an idealised form the vehicle­routing­problem is a fruitful benchmark for operations research [ Desrochers et al., 1992 ] . We adopted these benchmarks for multiagent systems to explore the distributed problem solving capabilities of cooperative agents and to compare it with the OR solutions. It turned out that the solutions obtained by MAS can compete with the OR solutions [ Fischer et al., 1996 ] . The general idea of a MAS solution for these scheduling problems is to model each truck by an agent that has the capability to compute a route for executing a subset of the orders. By successively announcing the tasks to the truck agents via the contract net protocol, an initial solution is obtained. In general, this solution is suboptimal. It can be improved by coordinated exchange of orders among the trucks [ Bachem et al., 1992; Fischer et al., 1996 ] . In every day business of transportation companies the idealised setting of the benchmark has to be extended: New orders arrive during the execution of the orders and have to be incorporated into existing plans quickly. The information which is available may be incomplete or even wrong. The plans are not totally reliable since the time that is needed for loading a truck or driving from one customer to the next depends on factors that are not under control of the dispatch officer. Therefore, a truck can be delayed such that its plan is no longer feasible and it is necessary to replan. These uncertainties and dynamics handicap central OR algorithms which would always have to be restarted when a plan has to be modified or adapted. The MAS approach allows for local improvement of tour plans and the handling of inconsistent and fuzzy knowledge. It is thus able to cope with the dynamic setting.

Nevertheless, it turned out that modelling just the vehicle as autonomous agent was not yet appropriate. In reality truck, trailer or semi­trailer, loading space, and driver form a transportation entity which is not fixed but may change during order execution: trucks meet and exchange trailers, containers are left at the customers or a truck may be temporarily staffed with two drivers. The simplifying abstraction does not allow to distinguish all these cases.

We therefore decided to represent each of these components as agents as well, which have to find their ``partners'' and form composed agents representing complete transportation entities that are able to handle the orders at hand. This resulted in a concept which we would like to call a holonic MAS.

3 Holonic MAS

The word ``holon'' [ Koestler, 1989 ] is derived from the Greek holos (whole), where the suffix means particle or part. A holon is a natural or artificial structure that is stable and coherent and that consists of several holons as substructures. Koestler's observation is that most entities (in biology as well as in sociology) exhibit a holonic structure. For example a human being consists of organs that consist of cells that can be further decomposed. The second interesting insight is that no natural structure is either `whole' or `part' in an absolute sense. Depending on the point of view a holon is a complex whole that consists of substructures as well as a dependent part of a larger entity.

These ideas are certainly not unfamiliar to the multiagent community since Marvin Minsky proposed his vision of the mind as a society of agents in [ Minsky, 1985 ] and tried to show how human intelligence could evolve from the neuronal structures of the brain. His approach was to show how complex cognitive tasks can be decomposed into simpler ones that can then be performed by simple, non­intelligent computational structures called agents. Minsky's main message is that the human mind consists of less intelligent structures, which in turn consist of simple parts that are not intelligent at all.

In a MAS holonic structures occur when agents not only cooperate loosely but have to be composed in order to perform their tasks. That means autonomous agents join others and form holons without loosing their autonomy completely but keeping the freedom to leave the holon again and act autonomously or rearrange themselves as new holons. According to this view we call an agent holonic or a holon if it consists of subagents, which can decompose and rearrange themselves and which may again be holonic. The ``leaves'' of a holonic MAS are autonomous agents that are stable over time and cannot be decomposed further into subagents [1] . We will assume one subagent of a holon to be distinguished as the representative or head, that will represent the holon to the rest of the agent society according to all kinds of interactivity.

The competences of the head of a holon range from pure administrative tasks to the authority to issue directives to the other agents. The minimum task a representative must implement is the interaction with the rest of the agent society, such that the behaviour of the holon is consistent. Furthermore, the head can be equipped with the authority to allocate resources to the other agents in the holon, to plan and negotiate for the holon on the basis of its subagents' plans and goals, or even to remove parts from the holon or to incorporate new parts.


resources
components            		 driving
time
motor
chassis		 loading
space
driver X      
truck with   loading space  
 		  
X		  
X		  
X
truck without   loading space  
X
X
truck tractor   X    
trailer     X X
semi-trailer     X X
chassis     X  
container
  /swap body		      
X
Figure 1: Components and Resources in TeleTruck


There is no universal method to determine the head. It may be elected from the agents forming the holon; a new agent may be created just for the lifetime of the holon to represent it; or, as in our setting, special agents are designed, that coordinate the formation of holons and establish themselves as heads of these holons.

4 The Implementation

In this section we provide a brief overview of the TeleTruck system. For more details see [ Bürckert et al., 1998b ] and the comprehensive system description in [ Bürckert et al., 1998a ] . After a presentation of the domain modelling we consider the system's architecture with the different modules and their interaction. Subsequently we focus on the core of TeleTruck, its holonic agent society, and the details of its planning procedure.

Modelling the Domain

In the transportation domain there are a number of components like driver, truck, trailer, container, and chassis which have special properties that restrict their usability, e.g. the storage capacity of a container, the possibility of loading a truck from its side or from the back, or even a driver who does not speak French and thus should not be sent to France. However, we identified four basic resources that are offered by different components and that are necessary for the execution of transportation tasks: loading space, chassis, motor component, and driving time of the driver. Some of these components occur already in different fixed combinations (trucks with chassis, trucks with loading space, trailers with loading space). For a detailed listing of the components and the resources they supply see Figure 1.

We developed an object­oriented data and process model of the domain, where each of the physically indivisible components are modelled as objects offering the services of administrating its resources.

According to the inherent distribution of the problem we chose to go further in order to achieve an incremental and dynamic scheduling procedure with stepwise approximation of globally optimised plans through local optimisation coupled with cooperative re­distribution of orders. We agentified the components and equipped them with local goals, plans, and the capabilities to communicate, cooperate, and form holons in a multiagent setting [2]. For such holonic MAS we have different ways of organising the formation and representation of the holons. The different types of component agents have to unite in order to form a transportation entity, the holon, that is able to plan and execute the transportation task for those orders it applied for. Concerning the representation of the holon at a first glance the motor component seems to be a static part during planning and execution and hence would be the natural candidate for the head of the holon. However, the motor component may be exchanged while the holon and its plan continue to exist. The same holds for each of the other components.

Since all physical components can be exchanged during the life time of a holon we decided to introduce a representative component as head of the holon that is able to coordinate the formation of the holon and its potential reconfigurations. The resources of the head are the planning and coordination capabilities.

The Systems Architecture

Figure 2 gives an overview on the modules that form the TeleTruck system. The trucks of our forwarding partners have been equipped with on­board computers that contain a communication facility and a global positioning system (GPS) which allows to determine the position of the truck precisely. Incoming GPS information and messages from the driver are stored in an SQL­database. The core of the setting is the multiagent system that contains the representation of the transportation components and is responsible for the composition of the components to vehicle holons and the planning of transportation orders as well as replanning on the basis of the online information. The route planning is aided by a commercial routing module that provides the distance and driving time between any two cities on the reference map. It is left to future work to incorporate on­line traffic information to refine the statistical data of the distance system. The user interface of TeleTruck allows for visualisation of the map and the truck positions and for all kind of interaction. The dispatch officer can input and update orders by hand or from the database, he can pre­schedule orders by hand, look up the computed plans and configurations of the transportation entities and can modify plans and configurations by hand.


Figure 2: The TeleTruck Architecture


The Multiagent Society

The multiagent system consists of an agent for each physical component of the forwarding company. The agents administrate the resources the components supply and have their own plans and goals. In addition Plan'n'Execute Units (PnEUs) will play the roles of heads of holons, and are equipped with planning and coordination abilities. They coordinate the formation of the holons, which represent the transportation entities, and plan the vehicles' routes. The PnEU also represents the vehicle to the outside and is authorised to reconfigure it. Each vehicle holon that has at least one task to do is headed by a PnEU. Additionally, there is exactly one idle PnEU with an empty plan that coordinates the formation of a new holon from idle components if needed. The whole society can be seen as a holon as well since there is a hierarchical relationship between the PnEUs and a further agent, the company agent that represents the society to the user (or---in a future extension---to other forwarding agents). The company agent is also responsible for the control of the optimisation process (cf. below).

Holonic Planning

For the route planning and allocation of resources in the TeleTruck system two cooperation protocols are used: Firstly, a simple resource requesting protocol that consists of a request message and an answer, and secondly, the extended contract net protocol (ECNP) [ Fischer and Kuhn, 1993 ] , an extension of the classic protocol [ Davis and Smith, 1983 ] that allows to distribute a task to several contractors by iteratively collecting bids. Whenever a new task becomes known the company agent announces it via ECNP to the PnEUs, which request resources from their components and decide whether the resources are sufficient to fulfil the task or not. If they are sufficient, the PnEU computes a plan, calculates its costs, and bids for the task. If the resources supplied by the components that are already member of the holon are not sufficient---which is trivially the case for the idle PnEU---the task together with the list of missing resources and a set of constraints that the order or the other members of the holon induce is announced to those agents which could supply such resources. These agents calculate which of their resources they actually can supply and again announce the task and the still missing resources. This is iterated until all the needed resources are collected. The task of collecting the needed resources is not totally left to the PnEU because the components have local knowledge about how they can be combined, e.g. if a driver always drives the same truck it is local knowledge of the components and not of the PnEU.

Example: Holonic Resource Allocation


Figure 3: Holonic Planning


Figure 3 illustrates a company agent announcing a new transportation task to two vehicle holons and the idle PnEU. The complete vehicle holon on the left hand side cannot incorporate any further components. Hence, the head requests the necessary resources from its components and, if these resources are sufficient, it calculates the costs for the execution of the task. The second vehicle holon could integrate one further component. In a first step, however, its head tries to plan the task using only the resources of the components, the holon already has incorporated. If the resources are not sufficient, the head tries to collect the missing resources by performing an ECNP with idle components that supply such resources---in this case the idle trailer. The idle PnEU, which has not yet any resources at all, first of all performs an ECNP with those idle components that offer loading space; in the example a truck and a trailer. The trailer supplies loading space and chassis, therefore, it needs a motor supplying component. Hence, it announces the task to the truck. The truck which received two different announcements for the same task---one by the trailer and one by the PnEU directly---can bid in both protocols since it can be sure that only one of the protocols will be successful. Therefore, the truck agent looks for a driver, computes the costs for the two different announcements, and gives a bid both to the PnEU and to the trailer. Obviously, the costs for executing the task with a vehicle that consists of a driver and a truck are less than the costs of executing the same task with the same truck and driver and, in addition, a trailer. Therefore, the idle PnEU will pass the bid of the truck to the company agent. If the task is granted to the idle PnEU, the PnEU merges with the components to a vehicle holon and a new PnEU will be created for further bidding cycles. Whenever the plan of a holon is finished the components separate and the PnEU terminates.

The Optimisation

In the MAS­MARS system the simulated trading algorithm [ Bachem et al., 1992 ] was used to improve the suboptimal initial solution stepwise towards globally optimised plans [ Fischer et al., 1996 ]. Simulated trading is a randomised algorithm that realises a market mechanism where the vehicles optimise their plans by successively selling and buying tasks. The trading goes over several rounds. Each round consists of a number of decision cycles. In each cycle the truck agents submit one offer to sell or buy a task. At the end of each round the company agent tries to match the sell and buy offers of the trucks such that the costs of the global solution decrease. This implements a kind of hill­climbing algorithm. Like in simulated annealing a derivation that decreases from round to round can be specified such that in early rounds the company agent is willing to accept a worsening of the global solution which is helpful to leave local maxima in the solution space. Nevertheless, maxima that are left are saved, such that, when the algorithm terminates before a better solution is found, the best solution hitherto is returned. Hence, simulated trading is an interruptible anytime algorithm.

In order to allow the optimisation not only of the plans but also of the combination of components we extended the simulated trading procedure. It might be the case that a good route plan is not efficient because the allocation of resources to the plan is bad, e.g. a big truck is not full while a smaller truck could need some extra capacity to improve its own plan. We divided a trading round into three phases. The first phase consists of order trading cycles as explained above; in the middle phase the holons can submit offers to exchange components. The third phase is, like the first phase, an order trading phase. After the third phase is finished the company agent matches the sell and buy and component exchange offers. This final trading phase is needed to decide whether the exchange of components in the middle phase actually lead to an improvement of the global resource allocation.

5 Conclusion and Outlook

We have described the TeleTruck approach to dispatch problems. Its main characteristics are that we use a multiagent approach instead of common OR techniques, that our agents rather directly reflect the physical objects of the transportation domain, and that they are holonic agents. Our approach has the advantage that TeleTruck is an incremental, dynamic, anytime algorithm. It is an anytime algorithm in the sense that it starts with an initial suboptimal schedule and improves the solution through every negotiation cycle. It is incremental as it includes the orders step by step and it is dynamic since it can take into account both new incoming orders and changes of former orders or the already scheduled plans during its optimisation cycles. Therefore, TeleTruck also supports monitoring of the schedule during execution and allows for online re­planning when changes take place.

Compared to other software supporting order dispatching, it had been shown earlier [ Fischer et al., 1996 ] , that the MAS­MARS/TeleTruck approach can easily compete with traditional OR algorithms. The features of TeleTruck mentioned above, however, allow for much wider usage and better assistance of dispatch officers. An intensive field trial has to demonstrate also its practical superiority.

The holonic structure of our agent society has several advantages:

TeleTruck is an application prototype. All modules as described above are prototypically integrated. They are currently running in a test version, in order to determine, in close collaboration with our partner's dispatch officers, adaption requirements for a future pilot system. Especially the global optimisation process through simulated trading needs further adaption concerning cost functions etc. in order to compete with experience of the dispatchers on hand made plans. Nevertheless, already our initial plans, although just locally optimised approved to be useful at least for generating hypothetical scenarios.

TeleTruck is an open system in the sense that other modes of transport (be it by railway, ship or plane) can be taken into account easily. In the same way as different road hauliers can cooperate horizontally other carriers can be integrated together with their subagents (trains, waggons, ships etc.) modelling their modes of transport. We are currently extending our approach towards such intermodal transport chains.

Our general vision for the future of freight haulage in Europe involves a close interaction between the Trans­European Network (TEN) of transportation and the Trans­European Network of telecommunications, in such a way that haulage via multiple modes of transportation is supported by AI technology and Telematics. Loading units derived from transport orders are assigned to loading spaces, transport units, transport modes etc. They are hauled between different locations, possibly undergoing several transshipments. Parallel to this flow of physical objects through the transport TEN, a flow of virtual objects through the telecommunications TEN will occur. Intelligent agents accompany the loading units like virtual analogs through the telecommunication TEN and, coupled with other intelligent agents (the virtual analogs of the trucks, trains etc.), they determine an optimal path for the corresponding physical object through the transport TEN. Just as the physical loading unit may change the physical transport unit, or may be loaded or unloaded at a terminal or a loading dock, so its virtual analog may alter the virtual transport unit or may move from or to the server of the terminal or the loading dock (i.e., the virtual analog of that physical location).

Acknowledgements

Andreas Gerber, Stefan Denne, and Volker Rückel supported the implementation of TeleTruck. The authors are indebted to CPN GmbH, Konz GmbH & Co. KG, PTV GmbH, and Simac Systems bv for their support in problem specification and for supplying electronic maps and telecommunication systems. TeleTruck has been funded by INTERREG II­programme Saarland/Lothringen/Pfalz of the European Commission.

References

[ Bachem et al., 1992 ] A. Bachem, W. Hochstättler, and M. Malich. Simulated Trading: A New Approach For Solving Vehicle Routing Problems. Technical Report 92.125, Mathematisches Institut der Universität zu Köln, Dezember 1992.

[ Bürckert et al., 1998a ] H.­J. Bürckert, K. Fischer, and G. Vierke. The TeleTruck System. Research Report, DFKI, 1998. to appear.

[ Bürckert et al., 1998b ] H.­J. Bürckert, K. Fischer, and G. Vierke. Transportation scheduling with holonic mas -- the teletruck approach. In Proceedings of the Third International Conference on Practical Applications of Intelligent Agents and Multiagents (PAAM'98), 1998. to appear.

[ Davis and Smith, 1983 ] R. Davis and R. G. Smith. Negotiation as a metaphor for distributed problem solving. Artificial Intelligence, 20:63 -- 109, 1983.

[ Desrochers et al., 1992 ] M. Desrochers, J. Desrosiers, and M. Solomon. A new optimization algorithm for the vehicle routing problem with time windows. Operations Research, 40(2), 1992.

[ Fischer and Kuhn, 1993 ] K. Fischer and N. Kuhn. A DAI Approach to Modeling the Transportation Domain. Research Report RR­93­25, DFKI, 1993.

[ Fischer et al., 1996 ] K. Fischer, J. P. Müller, and M. Pischel. Cooperative transportation scheduling: an application domain for DAI. Journal of Applied Artificial Intelligence. Special issue on Intelligent Agents, 10(1), 1996.

[ Gerber and Jung, 1998 ] C. Gerber and C. G. Jung. Holonic Structures for Bounded Optimal Agent Societies. Technical Memo, DFKI, 1998. to appear.

[ Koestler, 1989 ] A. Koestler. The Ghost in the Machine. Arkana Books, 1989.

[ Minsky, 1985 ] M. Minsky. The Society of Mind. Simon and Schuster, New York, 1985.

[ Sandholm, 1993 ] T. W. Sandholm. An implementation of the contract net protocol based on marginal cost calculations. In Proceedings of the 12th International Workshop on Distributed Artificial Intelligence, pages 295&endash;308, Hidden Valley, Pennsylvania, May 1993.

[ Smolka, 1995 ] G. Smolka. The Oz programming model. In J. van Leeuwen, editor, Computer Science Today, volume 1000 of Lecture Notes in Computer Science. Springer­Verlag, Berlin, 1995.

Footnotes

[1] Nevertheless, it is possible to find holonic structures in the sense of Koestler in these agents' architecture [Gerber and Jung, 1998].
(back to text)

[2] This did not result in lower efficiency, as the core of TeleTruck has been implemented in Oz [Smolka, 1995] a modern concurrent language that allows to model hun­ dreds of computational threads with small overhead.
(back to text)

converted from PostScript by
Paolo.Petta@ofai.at

Last modified: Thu Mar 19 18:39:58 GMT 1998