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.

Urban traffic congestion is a significant problem for almost every city, affecting various aspects of life. Besides increasing travel time, congestion also affects air and life quality causing economic losses. The construction of infrastructure to solve congestion problems is not always feasible, and, at the end, attracts only additional traffic demand. Thus, a better approach for solving the problem of city congestion is by optimal management of the existing infrastructure. Timely detection of traffic congestion on the road level can prevent congestion formation and even improve road network capacity when used for appropriate traffic control actions. Detecting congestion is a complex process that depends on available traffic data. In this paper, for traffic state estimation, including congestion level, at the intersection level, a new method based on Speed Transition Matrix and Fuzzy-Based System is presented. The proposed method utilizes the Connected Vehicle environment. It is tested on a model of an isolated intersection made in SUMO simulation software based on real-world traffic data. The validation results confirm the successful detection of traffic state (congestion level) at intersections.

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.

Due to the new laws and policies related to greenhouse gas emissions, and the rise of social and ecological awareness of transport sustainability, the electric vehicle market share is continually growing. Electric vehicles (EVs) have a shorter driving range compared to the conventional vehicles with an internal combustion engine. To efficiently manage a route of an EV and increase it's maximal range, it is necessary to give a high-quality estimate of EV's energy consumption on the route. In this paper, we developed a model to estimate energy consumption on the road-link level based on the historical GNSS data. First, the real energy consumption data was used to develop energy consumption models that take as input (i) the GNSS trip data features: speed, acceleration, distance and travel time, and (ii) EV's characteristics: mass, rolling friction, frontal surface area, etc. In total, four models were developed and compared: basic longitudinal dynamics model, multiple linear regression model, polynomial multiple linear regression model, and decision trees model. Further on, the proposed models were used to estimate energy consumption on the road-link level based on the aggregated historical GNSS data. As a case study, the road network in Croatia was selected with GNSS data collected in a five year period from 2009 to 2014. The results support the feasibility of the approach for estimating energy consumption on the road network with the application in the routing of EVs.

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.

Most modern vehicles are equipped with some kind of navigation system which uses GNSS combined with digital maps to provide as accurate as possible real-time positioning and navigation. Navigation in urban areas presents a rather difficult task because optimal route is not unique and can vary, depending on traffic conditions which change during the day as well as in case of unexpected scenarios, like traffic accidents. To allow optimal route planning, providers of navigation systems rely on calculating of speed profiles from GPS traces gathered from users which allowed that option in their navigation systems. Speed profiles are calculated estimates of average speed which can be achieved on a specific road segment during one day. Systems which have possibility to send data using mobile networks are usually mobile phones, while on-boards navigation devices mostly do not have that possibility. This leads to a problem of having technology which is not used to its full potential. Some providers of free navigation solutions, like Google or Here, rely on gathering data from devices which have mobile network connection to provide more accurate estimation of travel time. As a cost function user can specify travel time, which changes throughout a day or in case of an unexpected traffic jam, and navigation system tries to predict the best route for given input parameters. Speed profiles, on the other hand, try to predict a priori scenario which is fixed to a certain period of the day, to specific day of the week and specific part of the year. This approach gives logistic and transport companies a much better tool for route-prediction but it can also help private users when traveling from point A to point B in an unknown city during rush hours. To solve time dependent vehicle routing problem one must be able to gather a large amount of data from vehicles equipped with satellite navigation system and use them to calculate speed profiles for certain road segments. Since gathered GPS traces collected for the same road segment have errors in position due to inaccuracy in GPS positioning, we have used Frequency Modulated Continuous Wave (FMCW) radars to verify the data collected using GPS with actual measurements on road segments. For that purpose we have installed four of such detectors at four different locations and collected vehicle data (speed, length) for more than 1.5 million vehicles. Speed profiles calculated from GPS traces for these locations were compared with radar measurements and from them we are able to conclude that usage of GPS data is accurate enough to calculate the correct speed profile, given that we have enough of individual traces at our disposal.

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.

This paper presents a case study on organization of pretrip route planning and clustering for sales activity. Pre-trip route planning is a standard service of intelligent transportation systems (ITS). The study observed the territory of the Republic of Croatia which is represented with historical data for 16 515 points of sales. The solution should discover the number of sales regions, number of salesmen per region and planned routes for a single month. Constraints and input data are derived from real life points of sales data like sales potentials, geographic position and maximum number of customers for each route.

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

In the city of Zagreb, Capital of Croatia, bakery company daily delivers bread, rolls and other bakery products to customers which have their specific quantity demands and time periods in which delivery must start. Delivery is performed with heterogeneous fleet of vehicles where each vehicle has its own predefined time of depot leaving. All customers are geocoded on the digital city map with transport layer (one-way streets, prohibited turns) thus making possible to calculate asymmetric matrix of minimal distances between them. Also, asymmetric matrix of approximate minimal travel times between customers is calculated where the predicted travel times are based on street categorisation and statistics from historical data included in the digital map. Initial solution obtained using coefficient weighted time-distance heuristics was improved using λ -interchange algorithm. Also, simulated annealing method was used to escape local optima. Algorithms have been implemented in developed programming language which facilitates the writing of algorithms for solving VRP problems. In order to speed up the problem solving procedure, distributed versions of algorithms were implemented. Four times speed-up achieved on cluster of five networked computers was gained using distributed versions of algorithms. Currently, the company uses routes that are constructed manually where experience of dispatcher and drivers plays the main role. On the other side, obtained results shows that it is possible to reduce expenses up to 35% in total travelled distance using computer aided routing system.

Newspaper distribution company daily delivers newspapers to news stands in Zagreb, Croatia. Problem is recognized as the Pick-up and Delivery VRPTW. Initial solution for the problem is obtained by CWTDH algorithm which is further optimized using SA metaheuristics and lambda-interchange heuristics. Also, post optimisation technique was used for single route improvements. To validate the calculated solution, a test drive was performed to insure that every news stand will be served on time.

In the field of vehicle routing, relatively limited attention has been paid to the topics such as stochastic demand. With the data warehouse infrastructure and data mining tools it is possible to predict such variable constraints. This could enable more efficient route construction and as consequence the number of non accomplished routes could be reduced. The paper proposes database infrastructure, data mining module and VRP solver for prediction of uncertain demand. Proposed VRP solver uses constructive, heuristic and metaheuristic algorithms to solve a problem with demanded data.

Određivanje najpovoljnijeg puta, kojeg koristi grupa vozila prilikom posluživanja skupa korisnika predstavlja problem na operativnoj razini tehnologije transporta. U radu je predložen programski jezik i razvojna okolina za izradu konsruktivnih heurističkih algoritama.

The solving of Vehicle Routing Problem is a difficult combinatorial optimisation task. The interactive programming environment Venera and programming language Mars, oriented to ease the build up constructive heuristic algorithms for VRP, have been developed. The structure and functionality of programming environment and programming language are described.

In order to solve the practical Vehicle Routing Problems (VRP) by heuristic methods, the programming language Mars and the interactive program environment Venera have been developed and implemented. The implementation and verification of the heuristic algorithms will be improved by the application of new network (cluster/grid) technologies and by adapting Mars and Venera for the distributed and parallel method of operation.

U ovom radu opisana je implementacija sustava za rješavanje problema usmjeravanja vozila u praksi. Pošto se heuristički algoritmi verificiraju na testnim primjerima, njihova prava uporabna vrijednost može se ocijeniti tek nakon korištenja u realnom prometnom okruženju.

Today s problems in transportation processes in road trffic are growing continuously, even more so in case there are no technological, and particulary information technology innovations. Innovations in the domain of monitoring, directing, managing and controlling systems of traffic llows are realistically possible at present. Experiences show that the significance of technological innovations in the information subsystem in traffic technologies can be of great advantage.