Author:

Abstract:

Multi-agent system (MAS) literature often assumes decentralized MAS to be especially suited for dynamic and large scale problems. This assumption is based on the decentralized nature of MAS that allows for partitioning of the problem space such that individual agents can autonomously solve parts of the problem. This enables agents to quickly respond to changes in the problem. There is, however, little scientific evidence to support this assumption. Additionally, the prevailing paradigm in operational research is the use of centralized algorithms. The main problem addressed in this dissertation is the lack of a systematic evaluation of decentralized MAS and centralized algorithms on dynamic and large scale logistics problems. The problem under consideration is the dynamic pickup-and-delivery problem with time windows (dynamic PDPTW). There are four requirements of such an evaluation. First, exact definitions of dynamism and scale are needed such that these properties can be varied independently. Second, a dataset of dynamic PDPTW instances with varying levels of dynamism and scale is required. Third, there is a need for a realistic and fair simulation platform that allows real-time simulation of dynamic PDPTW and supports centralized as well as decentralized algorithms. Fourth, representative centralized and decentralized implementations are required. Reproducibility is one of the main principles of the scientific method. Therefore, all components needed for a systematic evaluation should be made open source. A sub-problem also addressed in this dissertation is that of optimizing MAS. This dissertation comprises five major contributions. Dynamism, urgency, and scale are formally defined in the context of dynamic PDPTWs (contribution 1). Existing definitions of dynamism often mix the concept of dynamism with that of urgency. An empirical evaluation of our definitions of dynamism and urgency shows that the degree of dynamism is negatively correlated with operating costs while more urgent scenarios are correlated with significantly higher operating costs. This justifies the conceptual separation of dynamism and urgency. We further define scale as a multiplier applied to the number of vehicles and orders in a problem. These three formal definitions enable experiments that investigate the influence of one property on operational costs independently of other properties. Based on the formal definitions of dynamism, urgency, and scale, a benchmark dataset and problem instance generator of dynamic PDPTWs are constructed (contribution 2). The generated benchmark dataset allows systematic comparison of algorithms subject to varying problem properties. For performing real-time experiments, a new open-source logistics simulator, RinSim, is developed (contribution 3). The simulator has support for both decentralized MAS as well as centralized algorithms and supports the dataset with different levels of dynamism, urgency, and scale. Both the centralized as well as the decentralized interface of RinSim provide the same software limitations and hardware constraints, thereby providing a fair environment for comparing performance. A MAS based on the dynamic contract-net protocol (DynCNET) and a centralized tabu search algorithm, based on the OptaPlanner optimization library, are implemented. Using the measures, dataset, and RinSim, a systematic evaluation of these two implementations is conducted (contribution 4). This evaluation experiment is the first of its kind to compare the influence of dynamism, urgency, and scale on the performance of two classes of algorithms in such a systematic, thorough, and fair manner. The results of the comparison show that the solutions found by the centralized algorithm cost, on average, only 94.2% of the operating cost of the solutions found by the DynCNET MAS. This indicates that the centralized algorithms generally perform better compared to the MAS. However, for scenarios that are medium to very dynamic, very urgent, and medium to large scale, the average relative operating cost of the centralized algorithm is 112.3%, indicating that under these circumstances, the MAS performs better compared to the centralized algorithm. When assessing the performance of the algorithms individually per scenario property, there is not one algorithm that generally outperforms the other on that dimension. To investigate whether the performance of agents can be optimized, the use of hyper-heuristics, more specifically genetic programming (GP), for MAS development is investigated (contribution 5). The heuristic that is evolved by GP is used as agent bid function in the auction process of CNET. The results show that our hyper-heuristic outperforms a reference algorithm, based on OptaPlanner, in all scenarios. In addition, the decentralized hyper-heuristic approach even outperforms the centralized reference algorithm in most situations.