Wyniki wyszukiwania - BazTech

1

Design and development of a road traffic redirection system

Bazan M., Janiczek T., Halawa K., Dudek R., Rudawski Ł.

Archives of Transport System Telematics

|

2017

|

Vol. 10, iss. 1

3--8

EN

Nowadays, the crucial issue of guidance systems based on a GPS signal is that they are not able to redirect road users, taking into account the current state of traffic (and the predicted state within the time of the travel) in the city. In this paper we present a three layer architecture of a computer system capable of redirecting users of an urban road system via routes with a lighter traffic load in order to reach their declared destination in the city. A basic layer is a multiprocessor calculation server running Dijkstra path search tasks, the middle layer - the one which is visible to the road user - is a replicable proxy server that collects route requests from road users. The third layer is a mobile application. The prototype of such a system was developed by the ArsNumerica Group. The crucial feature of the system is feedback from road users that allows us to adjust the whole Intelligent Transportation System in the city to changes in traffic flow at various road links introduced by the redirection process applied to many users. The performance test strategy to prove the efficiency of the architecture was carried out for the city of Wrocław.

2

Multithreaded enhancements of the Dijkstra algorithm for route optimization in urban networks

Bazan M., Ciskowski P., Dudek R., Halawa K., Janiczek T., Kozaczewski P., Rusiecki A.

Archives of Transport System Telematics

|

2016

|

Vol. 9, iss. 2

3--7

EN

In this paper, we present a case study, showing step by step, how to speed up Dijkstra’s method by parallelizing its computation and using different data structures. We compare basic algorithm with its bidirectional version and investigate two-and-multi-thread implementations based on Fibonacci heaps and regular priority queues. Experimental results obtained for artificially generated graphs as well as real-world road network data are presented and described.

3

Algorytmy harmonogramowania zsynchronizowanego przemieszczania wielu obiektów

Tarapata Z.

Badania Operacyjne i Decyzje

|

2008

|

nr 4

107-132

PL

W pracy przedstawiono algorytmy wyznaczania harmonogramu zsynchronizowanego przemieszczania wielu obiektów. Zdefiniowano problem harmonogramowania przemieszczania w postaci dwukryterialnego nieliniowego zadania optymalizacji. Omówiono sposób rozwiązania sformułowanego problemu dwukryterialnego poprzez poszukiwanie rozwiązania leksykograficznego. Podano dwa algorytmy harmonogramowania zsynchronizowanego przemieszczania wielu obiektów oraz opisano ich własności. Szczegółowo omówiono konieczne i wystarczające warunki umożliwiające otrzymanie rozwiązania optymalnego. Oszacowano złożoności obliczeniowe prezentowanych algorytmów oraz przedyskutowano ich własności. Zasadę działania algorytmów zilustrowano przykładami.

EN

The paper presents algorithms of determining a synchronized movement schedule of many objects. The author defines movement scheduling as a bicriterion nonlinear optimization problem. He also presents a method of solving the bicriterion problem which is based on finding a lexicographic solution. Two scheduling algorithms of synchronized movement and their properties are given. The first algorithm is based on the dynamic programming, the second one is based on the cost-profit analysis. The necessary and sufficient conditions for obtaining optimal solutions from the algorithms are discussed in detail. The author describes computational complexity and some properties of the algorithms. The idea of the algorithms is presented with a few examples.

4

Modele harmonogramowania zsynchronizowanego przemieszczania wielu obiektów

Tarapata Z.

Badania Operacyjne i Decyzje

|

2007

|

nr 2

83-1031

PL

W artykule przedstawiono problem wyznaczania harmonogramu zsynchronizowanego przemieszczania wielu obiektów, wykorzystywany w zagadnieniach: routingu w sieciach komputerowych, planowania przemieszczania mobilnych robotów, przetwarzania zadań w systemach równoległych (rozproszonych), sterowania ramionami wielu niezależnych robotów, planowania i synchronizacji przemieszczania wielu obiektów w symulacyjnych grach komputerowych (systemy typu CGF i SAF). Omówiono szereg modeli harmonogramowania przemieszczania. Zdefiniowano dwie grupy kryteriów istotnych z punktu widzenia oceny harmonogramu: kryteria związane z szybkością przemieszczania obiektów oraz z „równoległością” ich przemieszczania (w sensie położenia i czasu osiągnięcia pewnych punktów pośrednich). Skupiono się na sformułowaniu nieliniowego zadania harmonogramowania przemieszczania obiektów w celu minimalizacji sumy opóźnień w tzw. punktach wyrównania, przy pewnych dodatkowych ograniczeniach. Przedstawiono również dwa równorzędne sformułowania problemu w postaci dwukryterialnych zadań programowania matematycznego. Wykazano, że macierz współczynników ograniczeń w tych zadaniach jest całkowicie unimodularna, co umożliwia zastosowanie efektywnych algorytmów rozwiązywania zadań programowania liniowego, przy poszukiwaniu leksykograficznego rozwiązania problemu dwukryterialnego. Omówiono podobieństwa i różnice między sformułowanym problemem harmonogramowania, a klasycznym problemem szeregowania zadań przed liniami krytycznymi w celu minimalizacji maksymalnego opóźnienia zadań. Zdefiniowano wiele rozszerzeń omawianego problemu. Jako jedno z nich opisano problem planowania przemieszczania wielu obiektów zgodnie z pewnym wzorcem ugrupowania. Zarysowano sposoby rozwiązywania sformułowanych problemów harmonogramowania.

EN

The paper deals with the problem of determining movement schedule of many objects, used in many domains such as: routing in computer networks, movement planning of mobile robots, tasks processing in parallel or distributed computing systems, arms control of independent robots, planning and synchronization of the movement of many objects in computer simulation games (e.g. in Computer Generated Forces (CGF) systems or Semi-Automated Forces (SAF) systems). A lot of movement scheduling models are discussed. Two groups of criteria which are essential from the point of view of schedule estimation are described: a group connected with movement time of all objects and a group connected with “parallelization” of their movement (in the sense of location and times of reaching specified checkpoints). A nonlinear movement scheduling problem in order to minimize the sum of delays of all objects at checkpoints with some additional constraints is defined. Two equivalent formulations of two-criteria mathematical programming problems are also presented. It is proved that constraint coefficient matrices for both problems are totally unimodular and we can use effective algorithms for solving linear programming problems to find lexicographic solution of two-criteria problems. Similarities and differences between the defined problem and classical tasks scheduling problem before critical lines on parallel processors are discussed. Some extensions of the problem are presented. One of which is the scheduling movement problem of many objects according to a group pattern. Methods of solving formulated problems are indicated.

5

Military route planning in battlefield simulation: effectiveness problems and potential solutions

Tarapata Z.

Journal of Telecommunications and Information Technology

|

2003

|

nr 4

47-56

EN

Path searching is challenging problem in many domains such as simulation war games, robotics, military mission planning, computer generated forces (CGF), etc. Effectiveness problems in military route planning are related both with terrain modelling and path planning algorithms. These problems may be considered from the point of view of many criterions. It seems that two criterions are the most important: quality of terrain reflection in the terrain model and computational complexity of the on(off)-line path planning algorithm. The paper deals with two above indicated problems of route planning effectiveness. Comparison of approaches used in route planning is presented. The hybrid, terrain merging-based and partial path planning, approach for route planning in dynamically changed environment during simulation is described. It significantly increase effectiveness of route planning process. The computational complexity of the method is given and some discussion for using the method in the battlefield simulation is conducted. In order to estimate how many times faster we can compute problem for finding shortest path in network with n big squares (b-nodes) with relation to problem for finding shortest path in the network with V small squares (s-nodes) acceleration function is defined and optimized.