Labor Parallele und Verteilte Systeme
Refine
Year of publication
Document Type
- conference proceeding (article) (16)
- Part of a Book (7)
- Article (3)
- Book (1)
Is part of the Bibliography
- no (27)
Keywords
- Higher-Order Components (3)
- Concurrent computing (2)
- CoreGRID Component Model (GCM) & Fractal (2)
- Java (2)
- Web Services (2)
- AI (1)
- Adaptable Code (1)
- Ant Colony Optimization (1)
- Application Code (1)
- Biological system modeling (1)
Institute
Begutachtungsstatus
- peer-reviewed (10)
Control and Automation of services of the urban infrastructure offered to citizens and tourists are elementary parts of a smart city. But both rely on a stable supply of data from sensors spread across the whole city, e. g., the fill level sensors of waste bins needed for a waste management tool which we developed in a collaboration with the Regensburg city council for the on-demand collection of waste bins. Europe has a lot of historic cities like Regensburg with narrow streets and huge building walls, some made from granite and fieldstones, which often represents an insurmountable obstacle to wireless data transmission. The reduction of the road traffic volume poses an additional challenge for city planners. By means of networked planning and simulation software, the situation, state and efficiency of citywide logistic services can be monitored and optimized. In the course of such optimizations, we propose the combination of digital and logistic services. As an example, we show that monitoring state information, such as the waste bin fill levels, can be accomplished using the same vehicles and the same planning software, that is used for luggage transportation. Moreover, we describe how we adapted a solver for a variant of the TSP, namely the prize-collecting traveling salesman, to optimize the route planning dynamically.
In the realm of parallel computing, optimization plays a pivotal role in achieving efficient and scalable solutions. In this work, we present the parallelization of a hybrid genetic search for solving the Capacitated Vehicle Routing Problem with Pickup and Delivery (CVRPPD).It leverages the synergy between genetic algorithms and parallel computing to address the complex optimization problem. This hybrid algorithm combines a customized version of local search with a genetic algorithm to compute an effective solution. Our implementation makes use of the Message Passing Interface (MPI) for data distribution and parallel execution. In addition, we run multi-threaded processes on NVIDIA graphical processors using the CUDA technology, which further increases the computation speed and consequently minimizes the runtime. Parallelization also allows the best-improvement strategy to be used instead of the rst-improvement strategy while maintaining the same runtime. We store the resulting routes in a bus route database which we created as the basis of an extensive library of optimal routes for our specifc use case of optimizing bus routes in a rural area. The experimental results on real road data show that the parallel implementation of the Hybrid Genetic Search (HGS) achieves significant improvements in runtime over the sequential implementation above a certain problem size. We believe that our implementation of the parallel hybrid genetic search method can have a great in influence on optimization strategies in parallel computing and can also be applied to other subproblems of the VRP.
In this paper, we present a new approach to determine the estimated time of arrival (ETA) for bus routes using (Deep) Graph Convolutional Networks (DGCNs). In addition we use the same DGCN to detect detours within a route. In our application, a classification of routes and their underlying graph structure is performed using Graph Learning. Our model leads to a fast prediction and avoids solving the vehicle routing problem (VRP) through expensive computations. Moreover, we describe how to predict travel time for all routes using the same DGCN Model. This method makes it possible not to use a more computationally intensive approximation algorithm when determining long travel times with many intermediate stops, but to use our network for an early estimate of the quality of a route. Long travel times, in our case result from the use of a call-bus system, which must distribute many passengers among several vehicles and can take them to places without a regular stop. For a case study, the rural town of Roding in Bavaria is used. Our training data for this area results from an approximation algorithm that we implemented to optimize routes, and to generate an archive of routes of varying quality simultaneously.
While high-level software components simplify the programming of grid applications and Web services increase their interoperability, developing such components and configuring the interconnecting services is a demanding task. In this paper, we consider the combination of Higher-Order Components (HOCs) with the Fractal component model and the ProActive library.
HOCs are parallel programming components, made accessible on the grid via Web services that use a special class loader enabling code mobility: executable code can be uploaded to a HOC, allowing one to customize the HOC. Fractal simplifies the composition of components and the ProActive library offers a generator for automatically creating Web services from components composed with Fractal, as long as all the parameters of these services have primitive types.
Taking all the advantages of HOCs, ProActive and Fractal together, the obvious conclusion is that composing HOCs using Fractal and automatically exposing them as Web services on the grid via ProActive minimizes the required efforts for building complex grid systems. In this context, we solved the problem of exchanging code-carrying parameters in automatically generated Web services by integrating the HOC class loading mechanism into the ProActive library.
In this paper, we present a new Hybrid Genetic Search (HGS) algorithm for solving the Capacitated Vehicle Routing Problem for Pickup and Delivery (CVRPPD) as it is required for public transport in rural areas. One of the biggest peculiarities here is that a large area has to be covered with as few vehicles as possible. The basic idea of this algorithm is based on a more general version of HGS, which we adopted to solve the CVRPPD in rural areas. It also implements improvements that lead to the acceleration of the algorithm and, thereby, to a faster generation of a fastest route. We tested the algorithm on real road data from Roding, a rural district in Bavaria, Germany. Moreover, we designed an API for converting data from the Openrouteservice, so that our algorithm can be applied on real world examples as well.
Recent advances in the development of smart homes have led to the availability of a wide variety of devices providing a high level of convenience via gesture and speech control or fully automated operation. Many smart home appliances also address the aspects of safety and electricity savings by automatically powering themselves off after not being used for a while. However, many devices remain in a typical household that are not themselves "smart", or are not primarily electric (such as heating systems). We address the savings aspect by identifying processes involving the use of multiple devices in the electrical flow data, as captured by a smart meter in a modern household, rather than focusing on a single appliance. Therefore, we introduce a novel approach to usage pattern analysis based on the idea that a pattern of device usages as a result of a resident's 'routine' (such as making breakfast) can be interpreted similarly to a natural language 'sentence'; Natural Language Processing (NLP) algorithms can then be used for interpreting the residents' behavior. We introduce the notion of bag-of-devices (BoD), derived from the bag-of-words model used in document classification. In an experiment, we show how we use this model to infer predictions about the inhabitants from device usage, such as the resident leaving for the day or just to fetch the newspaper.
In this paper a new method for placing bus stops is presented. The method is suitable for permanently installed new bus stops and temporarily chosen collection points for call busses as well. Moreover, our implementation of the Voronoi algorithm chooses new locations for bus stops in such a way that more bus stops are set in densely populated areas and less in less populated areas. To achieve this goal, a corresponding weighting is applied to each possible placement point, based on the number of inhabitants around this point and the points of interest, such as medical centers and department stores around this point. Using the area of Roding, a small town in Bavaria, for a case study, we show that our method is especially suitable for for rural areas, where there are few multi-family houses or apartment blocks and the area is not densely populated.
Computer-based Improvements of waste collection and public transport procedures are often a part of smart city initiatives. When we envision an ideal bus network, it will primarily connect the most crowded bus stops. Similarly, an ideal waste collection vehicle will arrive at every container exactly at the time when it is fully loaded. Beyond doubt, this will reduce traffic and support environmentally friendly intentions like waste separation, as it will make more containers manageable. A difficulty of putting that vision into practice is that vehicles cannot always be where they are needed. Knowing the best time for arriving at a position is not insufficient for finding the optimal route. Therefore, we compare four different approaches to optimized routing: Regensburg, Christchurch, Malaysia, and Bangalore. Our analysis shows that the best schedules result from adapting field-tested routes frequently based on sensor measurements and route optimizing computations.
In recent years, mobility solutions have experienced a significant upswing. Consequently, it has increased the importance of forecasting the number of passengers and determining the associated demand for vehicles. We analyze all bus routes in a rural area in contrast to other work that predicts just a single bus route. Some differences in bus routes in rural areas compared to cities are highlighted and substantiated by a case study data using Roding, a town in the rural district of Cham in northern Bavaria, as an example. Data collected and we selected a random forest model that lets us determine the passenger demand, bus line effectiveness, or general user behavior. The prediction accuracy of the selected model is currently 87%. The collected data helps to build new mobility-as-a-service solutions, such as on-call buses or dynamic route optimizations, as we show with our simulation.
We tackle the problem that collecting all the waste of modern cities within the scheduled time spans becomes increasingly challenging, while the waste collection team is not supplemented accordingly in many places, e.g. by more staff or vehicles. Separating waste has become natural for urban populations, as recycling is ecologically necessary. However, the separation also leads to a continuously increasing number of containers which are logistically unmanageable without computer-aided collection scheduling. Regensburg recently introduced a new program for the collection of biological waste, which extends the private collection of such waste by a few hundred public biological waste containers. Computer support was pretty basic so far, i.e. the collection times were recorded and the routes were sporadically rescheduled manually in an Excel sheet. We show that much shorter waste collection routes can be found automatically using a dynamic version of the classic Ant Colony Optimization (ACO) algorithm for shortening the collection routes. Moreover, we sketch an loT (lnternet-of-Things) approach to "lntelligent Waste Containers" which we equip with ultrasonic sensors monitoring the fill levels, which allows us to skip poorly used containers during the collection and reposition them on demand. By means of a computer simulation with online visualization, we illustrate that our optimized and dynamically adapted collection routes lead to significant time savings. Indeed, more than twice the number of currently used containers can be collected within the same time. We also report about the first experiments that we conducted with real sensors. The presented work is the result of a cooperation between four contributing parties: 1) Technical University of Regensburg (OTH); 2) Ara Institute of Canterbury; 3) Regensburg's Governmental Department of Waste Management; and 4) an industry partner (kpit.com). We compare the outcome of our project with related work and we sketch some future perspectives and ideas for transforming Regensburg into an even more automatized, environmentally friendly "smart city".