Designing Express Networks with Multi-Agent Modelling

Abstract

The ORTEC Consulting Group (OCG) advises express service providers on efficient network design. A part of the challenge to this design is the hub location problem (HLP). The HLP consists of selecting optimal locations for large sorting centres (hubs) from a range of smaller sorting centres (depots) to which the rest of these depots can connect. The resulting network aims to transport parcels in the most cost effective manner achievable. The OCG is interested in multi-agent modelling technique as a new approach to the HLP, since this technique provides a natural way of modelling complexity that arises from interacting nodes. Literature showed no research on solving the HLP from a multi-agent systems (MAS) perspective. This thesis aims to fill this gap. With the main research goal being "Designing a model that can solve the hub location problem for express networks with use of multi-agent modelling", the model was designed using the Prometheus methodology. The model uses information on the volume distributions of a set of fixed depots to determine optimal hub locations from these depots. Simultaneously, the model ensures that parcels can be sent from any location and will be delivered within the set service time. Optimal hub locations in this sense means that the total network cost consisting of hub cost and transport cost is as low as possible. The inputs of the designed model are the depot locations, their volume distributions, the driving times between nodes, hub cost and transport cost. The outputs are the network cost, the number of hubs, the locations of these hubs and the routes of all the different parcels. The designed MAS consists of three main phases. Phase 1 is responsible for creating hubs based on volume distributions. Hubs are placed in regions that have a lot of parcels to be transported between them. Phase 2 creates routes via the hubs that resulted from Phase 1. Although the most efficient routes are calculated, the main focus of this phase is to create routes for every parcel in the first place. During Phase 3 the main focus is cost reduction through reducing air transport cost, reducing road transport cost and reducing hub cost. In addition, part of this design is implemented into a proof of concept using the JACK Agent Language (a Java based language) to show the added value of multi-agent modelling. This proof of concept, Preliminary Organisation of Hub Location Tool (POHST), contains the implementation of the first part of Phase 1. Hence, it creates hubs based on the volume distribution. A graphical user interface is added to turn POHST into an easily accessible tool. This tool is applied to two datasets to demonstrate its use in the preliminary phase of network research aiding in data gathering and the generation of initial hub configurations. Experts of the OCG confirmed the usefulness of POHST as strategic analysis tool. In addition, the type of model outputs did not allow for thorough integral testing of the tool, although other verification methods showed that the tool behaved as intended by the model design. Due to the lack of quantitative output, the tool could not be validated using traditional methods. Instead, the same experts were asked to validate the model. Although they had quite a few recommendations for further improvement of the tool, there was a consensus on its validity. The design process revealed interesting benefits and drawbacks of using the agent paradigm to solve the HLP. The source of much of the complexity of the HLP is the interaction between nodes. One of the major advantages of using the agent paradigm is that it provides a natural way of modelling such interactions. Furthermore, the scalability of agent models is an attractive feature. When a few types of agents have been designed, an unlimited amount of such agents can be used when applying the model, scaling along with the inserted data. Next, the research shows the benefit of agents adapting to local circumstances. By locally looking around for inefficiencies agents are capable to enhance the solution with limited data. Another advantage of using agents is the detailed level of statistics gathering it enables. Every agent decision can be tracked. Consequently, an agent model does not only produce an outcome, it can also show how and why this outcome evolved as it did. The major challenge of using agents to solve the HLP is the difficulty of making local decisions that might impact the entire infrastructure. To be absolutely sure that a local change will lead to lower network cost, all possible consequences are checked and valued for their change in cost. This process can lead to a vast amount of communication, because the agents are practically considering global data. Thus, undermining the multi-agent modelling values of local data views. Although this risk exists in the presented model, it does not prove that it is impossible to achieve a design that reaches a global optimum using strictly local information. However, it is the greatest challenge that the HLP poses to the use of multi-agent modelling. In conclusion, it can be said that this research has proved the potential of using MAS to solve the HLP. It is also certain that many interesting properties of agents can be further investigated. Subsequently, these models could add great value to compete with and possibly even defeat current HLP models.