Search

Many real-world applications of the vehicle routing problem (VRP) are arising today, which range from physical resource planning to virtual resource management in the cloud computing domain. A common trait of these applications is usually the large scale size of problem instances, which require fast algorithms to generate solutions of acceptable quality. The basis for many VRP approaches is a heuristic which builds a candidate solution that may subsequently be improved by a local search procedure. Since there are many variants of the basic VRP model, specialised algorithms must be devised that take into account specific constraints and user-defined objective measures. Another factor is that the scheduling process may be carried out in dynamic conditions, where future information may be uncertain or unavailable or may be subject to change. When all of this is considered, there is a need for customised heuristics, devised for a specific problem variant, that could be used in highly dynamic environments. In this paper, we use genetic programming (GP) to evolve a suitable dispatching rule to build solutions for different objectives and classes of VRP problems, applicable in both dynamic and stochastic conditions. The results show great potential, since this method may be used for different problem classes and user-defined performance objectives.

A vehicle routing problem aims to determine a set of vehicle routes to deliver goods to the customers. Most of the variants of the problem consider static traffic conditions, while in the real world, travel times depend on the departure time. In this paper, a capacitated time-dependent vehicle routing problem is observed, which considers time-dependent travel times between the customers, and delivery with vehicles that have limited load capacity. To solve the problem, an iterative local search metaheuristic is applied that couples the ruin-recreate principle with the common local search procedures. Several scenarios were developed to analyze the impact of time- dependent travel times on the solution quality in terms of the total travel time and customer configuration.

Ovaj rad pokazuje proces izvođenja procjene putanje mreže temeljene na podacima spajanjem mobilnih i plivajućih podataka automobila (engl. Floating Car Data, FCD). Sve veća količina velikih, otvorenih skupova podataka o prometu omogućuje istraživačima da steknu nove uvide u prometnu mrežu. Iako su okarakterizirani kao nestrukturirani, otvoreni skupovi podataka sadrže obilje informacija. Chen i sur. navode da se procjena putanje može opisati kao problem zaključivanja skupa segmenata ceste koje je korisnik najvjerojatnije prešao u vremenima tijekom kojih izvorni podaci mobilnog telefona ne pružaju takve informacije. Uz raširenu upotrebu mobilnih telefona, postoji i istraživačka zajednica koja se usredotočuje na procjenu putanje korisnika iz oskudnih skupova podataka mobilne mreže.

S porastom lokacijskih usluga kojima se prikupljaju korisnički podaci, značajno su porasli stopa prikupljanja podataka i potrebna količina prostora za pohranu podataka. To je osobito slučaj u prometnim sustavima, gdje korisnici opremljeni uređajima za praćenje proizvode velike skupove povijesnih geoprostornih podataka. U ovom se radu fokusira na povijesne plutajuće podatke praćenja vozila (engl. Floating Car Data, FCD) dobivene s vozila opremljenih GNSS uređajima za praćenje. Korišteni skup podataka zabilježen je na cestovnoj mreži Hrvatske koristeći 4908 vozila tijekom petogodišnjeg razdoblja od 2009. do 2014. godine. To je rezultiralo sa 6,55 milijardi zapisa, s veličinom prostora pohrane od 320GB. Korišteni skup podataka može se smatrati „velikim“ u smislu količine i brzine prikupljanja podataka. S tako velikim brojem podataka pojavio se problem skalabilnosti: kako smanjiti količinu prometnih podataka bez gubitka kvalitete i kako učinkovito izvući podatke iz tako velikog skupa podataka (An i sur., 2016.) FCD se obično koriste za procjenu stanja prometa cestovne mreže, posebno zagušenja (Yang i sur., 2017., Erdelić i sur., 2021.). Metodologija korištena za smanjenje povijesnog skupa podataka podijeljena je u tri koraka (Erdelić i sur., 2021.). Prvo su petominutni profili brzine za svaki cestovni segment u digitalnoj cestovnoj karti izvedeni iz korištenog povijesnog FCD skupa podataka (Erdelić i sur., 2015.).

Motorway bottlenecks are commonly occurring in developed countries with increased commercial activities. As opposed to the traffic jam, the source of the bottleneck is often a result of a specific traffic situation like traffic accidents, sudden breaks, or bad road design. They could be described as a sudden capacity drop that creates congestion on the part of the motorway that propagates in the downstream flow. More formally, free flow (normal traffic flow) could be described with equation $q_{; ; in}; ; \approx q_{; ; out}; ; $, where $q_{; ; in}; ; $ represents upstream flow and $q_{; ; out}; ; $ represents downstream traffic flow on the observed part of the motorway. The bottleneck manifested through the decrease of the downstream traffic flow due to the congestion. There are two types of bottlenecks: recurrent and non-recurrent. The recurrent bottlenecks are caused due to the influence of daily commuters and transit traffic. At the same time, non-recurrent are often the result of traffic anomalies like traffic accidents or some unexpected events.

With the rise of location-based services that collect user data, the collection rate and needed data storage volume increased significantly. This is especially the case in traffic systems, where users equipped with tracking devices produce large historical geospatial datasets. In this paper, we focus on the historical Floating Car Data (FCD) produced by vehicles equipped with GNSS tracking devices. The used dataset was recorded on a road network of Croatia during a five-year period between 2009 and 2014 by 4908 vehicles. This resulted in 6.55 billion records, with a storage volume of 320 GB. The used dataset can be considered as big data in terms of volume and velocity. With such large volume location-based data, the scalability issues emerged: how to reduce the traffic data without the quality loss and how to efficiently data-mine such large dataset (An et al., 2016)? The FCD is commonly used for estimating road network traffic state, especially congestion (Yang et al., 2017, Erdelić et al., 2021). The methodology used to reduce the historical dataset is divided into three steps Erdelić et al., 2021). First, the five-minute speed profiles for each road segment in the digital road map were derived from the used historical FCD dataset (Erdelić et al., 2015). In total, 561071 speed profiles were computed in five-minute time buckets with an additional 1245708 average or free-flow speed values. This resulted in the reduction of traffic data from 320 GB of raw FCD data to 428.53 MB speed profiles with used floating-point precision. To validate the aggregated data quality, the real test drive was conducted in which the real travel times were compared to the travel times estimated with speed profiles. The speed profiles produced a relative average percentage error of 4.82%. To further decrease the traffic data volume, in the second step, the observed road network of Croatia was divided into a fishnet grid. Then, for each cell, the congestion index ci ϵ [0, 1] was determined based on all of the road segments' speed profiles within the cell. The computed congestion indices were coupled with the image processing morphological closing method to determine congestion zones. Such procedure can be considered as a spatial clustering of traffic data, where the result are zones that have a significant change in the traffic pattern. Lastly, the Monte Carlo simulation of routes within the congestion zones was coupled with temporal clustering to determine Travel Time Indexes (TTIs) within the zone. This resulted in 5 to 7 TTIs per zone, ranging from -4.65% to 31.66% in value, where negative values represent shorter travel time compared to the free-flow travel time, while positive values represent an increase in the travel time, mostly in rush hours where congestion occurs. The TTIs further decreased the dataset size to 2.38 MB, without the significant loss in travel time estimation as relative travel time percentage error to real driven test routes was 4.13%. This particular has an effect in offline applications that need to store whole traffic data in the memory, which is usually limited. The TTIs show a reduction of 99.44% in data volume compared to speed profiles without the notable quality loss, as the difference in mean relative percentage travel time error to SP is 0.69%.

Prijelazna matrica brzina novi je model prikazivanja prometnih podataka. U ovoj prezentaciji prikazano je kako se model može koristiti za detekciju sigurnosnih problema u na gradskim prometnicama i autocestama.

The rapid increase in the number of vehicles on the roads is attracting the attention of many researchers around the world. The consequences of the increased number of vehicles are numerous, firstly increased congestion and negative climate effects, and secondly, many countries and companies are encouraged to research traffic behavior and collect historical data from traffic sensors. Simulations are gaining a significant role in researching traffic characteristics, as not all scenarios are feasible in the reality. Observing traffic in simulation environments provides a significant number of parameters that can be obtained and analyzed. In this paper, we provide an overview of the process of creating traffic simulations in the SUMO simulator. In addition, we have managed to automate part of the process of preparing the simulation.

Tensor-based models emerged only recently in the field of traffic data analysis. They outperform other data models because they can simultaneously capture both spatial and temporal components of the observed traffic data. In this paper, the Non-negative Tensor Decomposition (NTD) the method is used to extract traffic patterns in the form of Speed Transition Matrices (STM). The traffic pattern anomaly is estimated using Kullback–Leibler Divergence (KLD) between the observed traffic patterns and the average traffic pattern. Anomalous traffic patterns are then clustered using Agglomerative Clustering (AC), regarding its temporal components. Experiments were conducted on the large sparse Floating Car Data (FCD) for the most relevant road segments in the City of Zagreb, Croatia. Results show that the method was able to detect and cluster the most anomalous spatiotemporal traffic patterns, representing the traffic on the observed road segments. Valuable traffic insights can be extracted by using the proposed method, including the location and the cause of traffic anomalies. Therefore, such traffic information can be used in routing applications and urban traffic planning.

The increased development of the urban areas consequently results in a larger number of vehicles on the road network, leading to traffic congestion, especially in the rush hours. Intelligent Transport Systems (ITS) solutions present the applications that can be useful in detecting and dealing with the problems that are related to congestion. This paper presents a method for traffic state estimation and anomaly detection on urban roads using the tensor decomposition method. The method is composed of several steps: (i) computation of the Speed Transition Matrices (STMs) for every observed transition on the observed traffic road network, (ii) dividing the observed area (the city) using the grid, (iii) composing the tensor for every cell in the grid, (iv) tensor decomposition to extract the traffic patterns and its spatial and temporal characteristics, (v) classification of the traffic patterns to estimate the traffic state and (vi) clustering of the characteristic spatiotemporal patterns.

Electric road vehicles are more and more being included in today’s traffic imposing new ways how road vehicles should be used and how the transport network should be managed. To ensure optimal usage of electric vehicles, new routing algorithms are needed that take into account the road elevation in order to minimize the energy consumption. Additionally, the charging process has to be optimized so that the electric grid is not overloaded and the electric vehicle can be used as a short-term energy source in times of increased electric energy consumption. In the same time, the charging costs have to be kept on a minimum. Additionally, traffic control should be also adapted to maximize the transport network throughput and minimize the energy consumption. Goal of this project is to build a small scale electric vehicle using the Pioneer 3AT mobile robot, to start the development of a simulation model for the built small scale electric vehicle and of new routing algorithms suitable for electric vehicles in urban environments, create a simulation framework for urban road networks and to start the development of new traffic control algorithms appropriate for traffic flows containing electric vehicles.

Vehicle routing problem finds routes to serve a set of customers. It belongs to the field of intelligent transport systems and logistics. Significant savings can be achieved in real-world scenarios. The mathematical interpretation of the vehicle routing problem is an NP-hard optimization problem. Due to the computational complexity, various heuristics are used to solve the problem within a reasonable processing time. Previous research had been focused mostly on static variants, with constant edge weights represented by expected speed, which results in a too rough approximation of a dynamic traffic environment. The proposed research will take into account the time dependent aspects of the traffic environment. Edge weights will be time dependent functions acquired by analysis of historic GPS paths of vehicles. The proposed method will solve two complex problems: finding a time dependent shortest path in a graph, and solving the time dependent vehicle routing problem.

A Modelling and Optimization Framework for Real-World Vehicle Routing Problems

This book presents recent improvements, innovative ideas and concepts regarding the vehicle routing problem. It will be of interest to students, researchers and practitioners with knowledge of the main methods for the solution of the combinatorial optimization problems.