Abstract The division of road network into sub-networks prior to the simulation (i.e., static division) is a common part of distributed or parallel road traffic simulation. Its quality has significant impact of the speed of the entire simulation, but the mutual comparison of the division methods is difficult, as their descriptions contain inconsistent tests. Hence, in this paper, a benchmark for static road network division methods is presented. It is based on performing divisions of road networks with various sizes and observing multiple parameters of the sub-networks and their computation time. These values are summarized into scores utilizable for direct comparison of the division methods. The description of a publicly available tool enabling actual performance of the benchmark—ROad Network DIvision BEnchmark Tool or RONDIBET—is also provided. The tool was also used to demonstrate the functioning of the benchmark in a case study on three different division methods.

In this paper, a novel method for efficient division of road traffic network - the Multi-Level All-Possibilities-based Division (MLAPoD) - is described. Since a road traffic network is basically a graph, it is based on the standard multi-level graph partitioning. For the initial partitioning phase, it generates all possible assignments of graph nodes and assesses the quality of corresponding road traffic network divisions using a multi-objective fitness function. The obvious issue of a huge number of all possible assignments is solved by using sufficient number of graph coarsening steps to make the number of graph nodes feasible. The performed tests indicates that the MLAPoD method produces road traffic network divisions of the same or higher quality in comparison to our older division method and is significantly faster. It also outperforms a third-party division method in an important feature of the road traffic network division.

In this paper, we describe a library for Java, which enables easy usage of a genetic algorithm in a project. The library - Genetic Algorithm Library for Java (GAL4J) - contains multiple utilizable variants of individual parts of the genetic algorithm and also enables parallel computation of the fitness values of the individuals. The usability of the library was demonstrated on two classical problems. The speed of the GAL4J genetic algorithm using sequential and parallel fitness function calculation was investigated. The GAL4J was also compared to two existing GA libraries of third parties.

This paper compares sequential and parallel Java and C++ implementations of the B algorithm, a relatively new algorithm for user-equilibrium (UE) (road) traffic assignment (TA). All the versions were implemented in an optimized way while using best practices in both languages. Their performances were thoroughly tested using multiple large real road traffic networks. The tests showed that the C++ version is indeed faster in most cases, but only by 8.54 % on average.

In this paper, a method for road traffic network division for distributed and/or parallel road traffic simulation is described. Similarly to its former version, it employs multi-level graph partitioning scheme with graph coarsening, where a genetic algorithm is used for initial partitioning. The version of the method described in this paper (Improved Dividing Genetic Algorithm with Graph Coarsening and Improved Refining - IDGA-GC-IR) incorporates improved refining phase. In order to investigate its performance, it was compared to a third-party division method using testing on five road traffic networks. The tests showed that the IDGA-GC-IR method outperforms the compared third-party method in some important aspects of the division (e.g., number of divided traffic lanes), but is significantly slower.

The testing is an integral part of the software development.At the same time, the manual creation of individu-al test cases is a lengthy and error-prone process.Hence, an intensive research on automated test generation methods is ongoing for more than twenty years.There are many vastly dif-ferent approaches, which can be considered automated test case generation.However, a common feature is the generation of the data for the test cases.Ultimately, the test data decide the prog-ram branching and can be used on any testing level, starting with the unit tests and ending with the tests focused on the behavior of the entire application.The test data are also mostly independent on any specific technology, such as programming language or paradigm.This paper is a survey of existing litera-ture of the last two decades that deals with test data generation or with tests based on it.This survey is not a systematic literature review and it does not try to answer specific scientific questions formulated in advance.Its purpose is to map and categorize the existing methods and to summarize their common features.Such a survey can be helpful for any teams developing their methods for test data generation as it can be a starting point for the exploration of related work.

Road traffic simulation is one of the useful tools, which can help to cope with steadily increasing intensity of road traffic. A distributed or parallel computing environment can significantly speedup the simulation execution, but the road traffic network division is usually required. There are many existing methods for road traffic network division based on various approaches. However, there is a lack of surveys mapping these methods. For this reason, this paper is a survey of existing methods for road traffic network division published in last two decades. It is not a systematic review, as it does not try to answer specific scientific questions. Its purpose is to map and categorize the existing methods for road traffic network division and to summarize their common features. Such a survey can be useful as a good starting point for the related work exploration for any teams or individuals dealing with road traffic network division and distributed or parallel road traffic simulation.

In this paper, we describe the method for the Road Traffic Network Division for Dynamic Network Loading (RTND-DNL), which is based on our formerly developed Imp-roved Dividing Genetic Algorithm with Graph Coarsening and Refining (IDGA-GC-R) method. The IDGA-GC-R method was originally designed for a detailed distributed road traffic simulation. Hence, some modifications were necessary to meet slightly different requirements of the dynamic network loading. However, the RTND-DNL method still employs a genetic algorithm, a graph coarsening, and a refining. The description of the RTND-DNL method along with its testing is the main contribution of this paper.

This paper deals with a methodology for a complex testing and assessing the communication protocols for the distributed simulation of road traffic. The methodology enables to explore the dependency of the performance of communication protocols on various features of the distributed simulation. It is also possible to assess the particular communication protocols with an overall score, which can be used for direct comparison of the protocols. The methodology was successfully tested on several communication protocols for distributed simulation of road traffic, which we developed. The description of the methodology and a demonstration of its functioning on a case study with the developed communication protocols is the main contribution of this paper.

This paper describes in detail the Complex Object Generation (COG) algorithm, which is a semi-automated algorithm for the generation of instances of classes (i.e., objects) with a complex inner structure for Java and similar languages designed for black-box testing (i.e., without available source code).The algorithm was developed and tested as a stand-alone algorithm and can be used as such (e.g., during unit testing).However, we plan to use it to generate the parameter values of generated method invocations, which is a vital part of our interface-based regression testing of software components.

In this paper, an improved method for road traffic network division for distributed road traffic simulation is described and compared to its former version. The method is based on the multi-level graph partitioning and the improved dividing genetic algorithm. In comparison to its former version, the improved version uses a slightly different fitness function and employs refining for further improvement of the yielded road traffic network division. The improved division method was thoroughly tested together with its former version. The tests showed that the improved division method yields better results for real irregular road traffic networks.

A detailed computer simulation is an important tool for the managing of road traffic. Since it can be very time consuming, it is often performed in a distributed computing environment. The simulated road traffic network is then divided into sub-networks simulated by processes on the nodes of the distributed computer. The inter-process communication necessary for the vehicle transfer and the synchronization can then significantly influence the performance of the distributed road traffic simulation. In this paper, two efficient communication protocols for distributed road traffic simulation, which we developed during our previous research, are compared. These protocols - the Long Step (LS) protocol and the Long Step Binary (LSB) protocol - reduce the inter-process communication using an aggregate message transfer and/or a lossy data compression. Semi-centralized, centralized, and distributed variants of both protocols were thoroughly tested and compared to a reference communication protocol representing a common protocol of distributed road traffic simulators. The tests indicate significant savings of the number of transferred messages and, more importantly, of the total computation time.

In this paper, we describe a fair comparison of the performance of a microscopic road traffic simulation performed on a GPU and on a CPU. The aim of our work is to determine the speedup, which can be achieved if the GPU is used for the same simulation instead of the (multi-core) CPU. A microscopic road traffic simulator capable of running on both platforms was created for this purpose with the aim to make the GPU-based and the CPU-based simulations as similar as possible. The performances of both the GPU-based and the CPU-based simulations were tested using two different road traffic models (a car-following model and a cellular automaton model), four road traffic networks (regular square grids of crossroads) of different sizes, and three different hardware configurations. The maximal achieved speedup using the GPU instead of the multi-core CPU for the cellular automaton model was 12.4. For the car-following model, the maximal achieved speedup was 10.7.

In high-level object languages, such as Java, a problem of unnecessary duplicates of instances can easily appear.Although there can be a valid reason for maintaining several clones of the same data in the memory, often it indicates that the application can be refactored into a more efficient one.Unnecessary instances consume memory, but in case of Java applications can also have a significant impact on the application performance, as they might prolong the time needed for the garbage collection.In this paper, we are presenting a method and a tool that allows detecting duplicity in the heap dump of a Java application, based on the shallow and deep object comparison.The tool allows to identify the problematic instances in the memory and thus helps programmers to create a better application.On several case studies, we also demonstrate that the duplicates appear not only in the student projects and similar programs that often suffer from poor maintenance but also in commonly available Java tools and frameworks.

In this paper, we describe the deep object comparison (DOC) algorithm, which is used for comparison of general objects in Java programming language based on their internal structures and values of primitive attributes.The DOC algorithm was designed to be utilized in our interface-based regression testing of software components, which enables to uncover subtle changes of the behavior of a component-based application under test with a newly installed version of a software component in comparison to its behavior with an old version of this component.

In this paper, an efficient method for road traffic network division is described. The method is based on the dividing genetic algorithm and utilizes graph coarsening to improve its results. The main idea is to coarse the original road traffic network to obtain a smaller (i.e., coarser) network. This coarser network can be optimally divided and this division can be projected to the original network. Using the coarsening (based on geographical positions of the crossroads), the division method is faster and yields better road traffic network divisions. This is demonstrated directly on a distributed road traffic simulation, for which the division of road traffic network is performed.

The component-based software development enables to construct applications from reusable components providing particular functionalities and simplifies application evolution. To ensure the correct functioning of a given component-based application and its preservation across evolution steps, it is necessary to test not only the functional properties of the individual components but also the correctness of their mutual interactions and cooperation. This is complicated by the fact that third-party components often come without source code and/or documentation of functional and interaction properties. In this paper, we describe an approach for performing rigorous semi-automated testing of software components with unavailable source code. Utilizing an automated analysis of the component interfaces, scenarios invoking methods with generated parameter values are created. When they are performed on a stable application version and their runtime effects (component interactions) are recorded, the resulting scenarios with recorded effects can be used for accurate regression testing of newly installed versions of selected components. Our experiences with a prototype implementation show that the approach has acceptable demands on manual work and computational resources.

In this paper, a hybrid approach for the parallelization of a genetic algorithm for a distributed/parallel computing environment is described. The genetic algorithm is the main part of the method for the division of road traffic networks for distributed road traffic simulations. The hybrid approach is based on the commonly used island model for the parallelization of genetic algorithms and the parallelization of individual steps of genetic algorithms. The island model is used among the processes residing on different nodes of the distributed/parallel computer. The step parallelization is used among the threads of a single process. The thorough tests of the hybrid approach investigating its speedup and the achieved road traffic network division were performed. Their description and results are also part of this paper.

In this paper, a distributed/parallel genetic algorithm for the optimization of the parameters settings (e.g., the number of generations, the type of selection, etc.) of a genetic algorithm for the road traffic network division is described. Using this approach, new settings of the parameters of the dividing genetic algorithm were obtained. With these parameters, the dividing genetic algorithm yields better road traffic networks divisions than with the original parameters, which were set based on a preliminary testing. The distributed/parallel optimizing genetic algorithm is described in detail as well as its results and the following testing of the dividing genetic algorithm.

In this paper, the optimization of a genetic algorithm for the road traffic network division using the graph coarsening is discussed. Since each road traffic network is basically a graph, the main idea is to coarsen a large road traffic network to obtain a smaller (i.e., coarser) network. This smaller road traffic network can be then divided into required number of sub-networks using our division method based on a genetic algorithm. The division of the coarser network can be then projected to the original road traffic network. The coarsening algorithm, which utilizes the geographical coordinates of the crossroads (i.e., nodes of the graph) is described in detail and tested.

In this paper, we explore the features of the sparsely synchronized parallel genetic algorithm for the road traffic network division. The algorithm is an alternative to a commonly used island model for the parallelization of the genetic algorithms. The algorithm employs the parallelization of particular phases of the genetic algorithm (fitness values calculation, crossover, etc.). However, the threads of the genetic algorithm are not synchronized in every generation, but rather only once per several generations or even not at all. The lack of the synchronization leads to the inconsistencies in the shared memory, which does not have to be a problem considering the stochastic nature of the genetic algorithms. The investigation of the features and usability of the sparse synchronization of the parallel genetic algorithm (with application for the road traffic network division) is the main theme of this paper.

In this paper, the analysis of the fitness function of a genetic algorithm is discussed. This genetic algorithm is used by a method for the road traffic network division. The division of the road traffic network into a number of sub-networks is a part of necessary preparations for a distributed road traffic simulation. The fitness function consists of two parts reflecting two important issues of the road traffic network division - the load-balancing of the resulting sub-networks and the minimization of the number of divided traffic lanes. During the optimization and refactoring of the division method, it was discovered that the fitness function of the genetic algorithm is flawed, but gives better results than a new (repaired) fitness function. Hence, the working of the original fitness function was analyzed and the new fitness function was adjusted to give similar or better results than the original fitness function.

In this paper, we describe the possibilities of the parallelization of the genetic algorithm for road traffic network division for a distributed/parallel computing environment. This genetic algorithm, which we developed, is utilized for division of road traffic networks for distributed road traffic simulation. The parallelization of the genetic algorithm is not based on the commonly used island model. Instead, the particular steps of the genetic algorithm are performed concurrently. The analysis of the inter-process communication of the described distributed/ parallel genetic algorithm in dependency on the number of working threads and/or working processes is also part of the paper. The parallelization is utilizable also in different problem domains.

This paper deals with optimization of a genetic algorithm for road traffic network division for distributed road traffic simulation which we developed. Two approaches for finding of optimal setting of the genetic algorithm are considered an optimizing genetic algorithm and a systematic testing of possible settings. Since both approaches are expected to be extremely computation-consuming their distributed versions are proposed and a feasibility study is evaluated.

This paper deals with road traffic simulation performed on a cluster of computers with multi-core processors. Two versions of the simulation are compared - the distributed version and the parallel/distributed version. The distributed version utilizes a number of single threaded simulation processes. The number of processes corresponds to the total number of processor cores of the cluster. The parallel/distributed version utilizes a lower number of multithreaded processes. The number of processes corresponds to the number of computers of the cluster and the number of threads per process corresponds to the number of processor cores of each computer of the cluster. The parallel/distributed version minimizes the inter-process communication using the shared address space of particular threads in one simulation process. Hence, it is significantly faster than its pure distributed counterpart.