Evaluation of Algorithm Performance for Simulated Square and Non-Square Logistic Assignment Problems
SELMAIR / HAMZEHI / MEIER
The optimal allocation of transportation tasks to a fleet of vehicles, especially for large-scale systems of more than 20 Autonomous Mobile Robots (AMRs), remains a major challenge in logistics. Optimal in this context refers to two criteria: how close a result is to the optimal objective value and the shortest possible computational time. Operations research has provided different methods that can be applied to solve this assignment problem. Our literature review has revealed six commonly applied methods to solve this problem. In this paper, we compared three optimal methods (Integer Linear Programming (ILP), Hungarian Method (HM) and the Jonker Volgenant Castanon (JVC) algorithm) to three three heuristic methods (Greedy Search (GS) algorithm, Vogel's Approximation Method (VAM) and VAM-nq, for non-quadratic matrices). The latter group generally yield results faster, but were not developed to provide optimal results in terms of the optimal objective value. Every method was applied to 20.000 randomised samples of matrices, which differed in scale and configuration, in simulation experiments in order to determine the results' proximity to the optimal solution as well as their computational time. The simulation results demonstrate that all methods vary in their time needed to solve the assignment problem scenarios as well as in the respective quality of the solution. Based on these results yielded by computing quadratic and non-quadratic matrices of different scales, we have concluded that the JVC is deemed to be the best method for solving quadratic and non-quadratic assignment problems with optimal precision. However, if performance in terms of computational time is prioritised for large non-quadratic matrices (50×300 and larger), the Vogel's Approximation Method for non-quadratic Matrices (VAM-nq) generates faster approximated solutions.
Improved Decentral Task Allocation for AGV Systems based on Karis Pro
SELMAIR / MEIER
In this paper, we extended an existing decentralised method for allocating tasks to AGVs, by additionally considering vehicles which already are assigned to a task. This was achieved by also taking into account the opportunity costs arising from a vehicle passing a current task to another vehicle and subsequently accepting a new task. This loosened restriction is enabling the vehicle fleet for a higher flexibility, which can be used for improving the efficiency of the overall system. By means of simulation, our findings confirm the notion that our extended method – namely Karis Pro+ (KP+) – leads to lower traffic density and higher flexibility, both of which are important KPIs for largescale transport vehicle systems.
Enhancing Charging & Parking Processes of AGV Systems:
Progressive Theoretical Considerations
SELMAIR / MAURER
This paper presents our work in progress for the development of an efficient charging & parking strategy. Our research aim is to develop a strategy that not only provides an efficient approach to charging AGV batteries, but also reduces traffic density in a highly utilised large-scale AGV system. Alongside the current state-of-the-art solution, three new allocation methods are introduced: Trivial+, Pearl Chain and a method based on the Generalised Assignment Problem (GAP). These four methods vary in their scope, in terms of number of vehicles considered, when calculating a decision for a specific vehicle. Furthermore, two types of availability rules for vehicles are introduced and evaluated. Their combination with the allocation methods lay the foundation for future research. All allocation methods and availability rules are explained in detail and this is followed by a summary of the expected outcomes.
Efficient Task Prioritisation for Autonomous Transport Systems
SELMAIR / PANKRATZ / MEIER
The efficient distribution of scarce resources has been a challenge in many different fields of research. This paper focuses on the area of operations research, more specifically, Automated Guided Vehicles intended for pickup and delivery tasks. In time delivery in general and flexibility in particular are important KPIs for such systems. In order to meet in time requirements and maximising flexibility, three prioritisation methods embedded in a task allocation system for autonomous transport vehicles are introduced. A case study within the BMW Group aims to evaluate all three methods by means of simulation. The simulation results have revealed differences between the three methods regarding the quality of their solutions as well as their calculation performance. Here, the Flexible Prioritisation Window was found to be superior.
Towards ASP-based Scheduling for Industrial Transport Vehicles
FABRICIUS / DE BORTOLI / SELMAIR / REIP / STEINBAUER / GEBSER
The increasing number of robots and autonomous vehicles involved in logistics applications leads to new challenges to face for the community of Artificial Intelligence. Web-shop giants, like Amazon or Alibaba for instance, brought this problem to a new level, with huge warehouses and an huge number of orders to deliver with strict deadlines. Coordinating and scheduling such high quantity of tasks over a fleet of autonomous robots is a really complex problem: neither simple imperative greedy algorithms, which compromises over the quality of the solution, nor precise enumeration techniques, which compromises over the solving time, are no more feasible to tackle such problems. In this work, we use Answer Set Programming to tackle real-world logistics problems, involving both dynamic task assignment and planning, at the BMW Group and Incubed IT. Different strategies are tried, and compared to the original imperative approach.
Scheduling Charging Operations of Autonomous AGVs in Automotive In-house Logistics
SELMAIR / HAUERS / GUSTAFSSON-ENDE
Scheduling approaches for the charging of Automated Guided Vehicles (AGVs) are based on three key components: the timing of charging processes, the selection of a charging station and the duration of the charging process. Based on literature research introduced in this paper, two scheduling approaches have been studied: a rigid approach, based on state-of-the-art solutions, captures the optimal case for a single AGV. A flexible approach, particularly focusing on autonomous behaviour of AGVs, aims for an optimum for the whole AGV fleet. Therefore, the concept of auction-based task allocation is transferred. A closed-loop simulation compares both scheduling approaches for the application of automotive in-house logistics. The flexible approach shows a higher scheduling effectiveness, although influenced by the charging station allocation.
Solving non-quadratic Matrices in Assignment Problems
with an improved Version of Vogel's Approximation Method
SELMAIR / SWINAREW / MEIER / WANG
The efficient allocation of tasks to vehicles in a fleet of self-driving vehicles (SDV) becomes challenging for largescale systems (e.g. more than hundred vehicles). Operations research provides different methods that can be applied to solve such assignment problems. Integer Linear Programming (ILP), the Hungarian Method (HM) or Vogel’s Approximation Method (VAM) are frequently used in related literature (Paul 2018; Dinagar and Keerthivasan 2018; Nahar et al. 2018; Ahmed et al. 2016; Korukoglu and Ballı 2011; Balakrishnan 1990). The underlying paper proposes an adapted version of VAM which reaches better solutions for non-quadratic matrices, namely Vogel’s Approximation Method for non-quadratic Matrices (VAM-nq). Subsequently, VAM-nq is compared with ILP, HM and VAM by solving matrices of different sizes in computational experiments in order to determine the proximity to the optimal solution and the computation time. The experimental results demonstrated that both VAM and VAM-nq are five to ten times faster in computing results than HM and ILP across all tested matrix sizes. However, we proved that VAM is not able to generate optimal solutions in large quadratic matrices constantly (starting at approx. 15×15) or small non-quadratic matrices (starting at approx. 5×6). In fact, we show that VAM produces insufficient results especially for non-quadratic matrices. The result deviate further from the optimum if the matrix size increases. Our proposed VAM-nq is able to provide similar results as the original VAM for quadratic matrices, but delivers much better results in non-quadratic instances often reaching an optimum solution. This is especially important for practical use cases since quadratic matrices are rather rare.
Exploring Opportunities: Optimising Production Planning
by Factoring in Energy Procurement and Trading Options
SELMAIR / HANFELD / CLAUS / HERRMANN
Motivated by the increasing share of renewable energy in the markets for energy commodities, this study has evaluated the potential for optimising production planning by taking into account disposable options for procuring energy, in this case electricity. For this purpose, a material flow simulation study extended by an electricity price simulation has been executed to examine possible cost scenarios. Our findings support the notion of a potential for further research in new optimisation models involving energy procurement as well as energy trading options.
Job Shop Scheduling with flexible Energy Prices
SELMAIR / CLAUS / HERRMANN / TROST
The rising energy prices - particularly over the last decade - pose a new challenge for the manufacturing industry. Reactions to climate change, such as the advancement of renewable energies, raise the expectation of further price increases and variations. Regarding the manufacturing industry, production planning and controlling can have a significant influence on the in-plant energy consumption. In this paper, we develop a scheduling method as a linear optimization model with the objective to minimize energy costs in a job shop production system.
Social and Ecological Capabilities for a Sustainable Hierarchical Production Planning
TROST / CLAUS / HERRMANN / TEICH / SELMAIR
Production planning and production control mainly focus on optimising the entire production system of a company. On the basis of hierarchical planning as a suitable method for solving this task, this paper shows - besides the economic dimension taken into account so far - that there are also social and ecological effects which will have to be considered in the process of plan-ning. For this purpose, we would like to indicate here which social and ecological parameters can be or have already been taken into account for master production scheduling, for lot sizing and resource scheduling. As a result, an overview has been created which presents the existing concepts of sustainable production planning and production control as well as the existing deficits regarding the sustainability perspective.
Potential of Reducing the Total Energy Consumption
by Scheduling a Jobshop Production System
SELMAIR / HERRMANN / CLAUS / TEICH
This research paper has evaluated the potential of reducing energy consumption by scheduling jobshop production systems with machines using standby modes in free times. The initial introduction of the planning issue is followed by a description of the approach to assess the available potential. Subsequently, the research procedure by means of simulation, a detailed discussion of the results and a perspective on future research is given. Moreover, the notion that scheduling influences the energy consumption in jobshop production systems is supported. The presented simulation research also documents that there is no direct correlation between energy consumption and total lead time, although this was presumed usually. Finally, this paper provides a forecast for a possible optimisation model as well as an exemplary model with an energy-optimised schedule plan.
Automatisation of the SAP GUI via Scripting
SELMAIR / HERRMANN / HAMMER
The core product provided by the SAP AG is the software system called “Enterprise Resource Planning” or short ERP which can be used to support all business process in a company. This includes accounting, human resources and logistics as well as different industry-specific solutions. In order to ensure the functionality of this complex software system, it is imperative to handle the corresponding master data conscientiously and manage them continuously. The resulting work processes are mostly recurring and require a substantial amount of time in their execution. Resolving this issue was the subject of my master’s thesis at Siemens AG. The solution I provided by using SAP GUI Scripting increased the efficiency of several operating procedures and is a intensively utilised tool in different departments of Siemens AG in its Regensburg location. No literature except the API had existed before I started working on this topic. In the course of the thesis, a substantial amount of research has been carried out regarding the entire topic in order to analyse the functions and difficulties of this emergent SAP interface, and in order to be able to handle it properly.