A Centralized Route-Management Solution for Autonomous Vehicles in Urban Areas
, Carlos T. Calafate 1, David Soler 2, Lenin-Guillermo Lemus-Zúñiga 3, Juan-Carlos Cano 1, Pietro Manzoni 1 and Thierry Gayraud 4Round 1
Reviewer 1 Report
The Authors have used a centralized approach to find routes for autonomous vehicles in urban road network. The Authors claim that their method reduces congestion, increases average speed, and decreases travel times. These improvements were demonstrated in comparison with a basic approach implemented in SUMO simulation software.
The paper has important drawbacks:
1) The routing problem and objective were not clearly defined (there is lack of formal description of the undertaken problem).
2) Detailed description of the proposed method is missing. The method should be presented in an algorithmic fashion, preferably with use of a pseudo code.
3) Contribution of this work is very limited as the most important aspects of the method were presented by the Authors in their previous works.
4) Authors have ignored the existing routing methods for autonomous vehicles that can be found in the related literature, e.g.:
- Weyns, D., Holvoet, T., & Helleboogh, A. (2007, September). Anticipatory vehicle routing using delegate multi-agent systems. In 2007 IEEE Intelligent Transportation Systems Conference (pp. 87-93). IEEE.
- Agafonov, A., & Myasnikov, V. (2017). Efficiency comparison of the routing algorithms used in centralized traffic management systems. Procedia engineering, 201, 265-270.
- Rossi, F., Zhang, R., Hindy, Y., & Pavone, M. (2018). Routing autonomous vehicles in congested transportation networks: Structural properties and coordination algorithms. Autonomous Robots, 42(7), 1427-1442.
- Alonso-Mora, J., Wallar, A., & Rus, D. (2017, September). Predictive routing for autonomous mobility-on-demand systems with ride-sharing. In 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (pp. 3583-3590). IEEE.
- Carlino, D., Depinet, M., Khandelwal, P., & Stone, P. (2012, September). Approximately orchestrated routing and transportation analyzer: Large-scale traffic simulation for autonomous vehicles. In 2012 15th International IEEE Conference on Intelligent Transportation Systems (pp. 334-339). IEEE.
5) The proposed method should be compared with routing algorithms that are representative for the works mentioned above.
6) Issues and limitations related to the centralized architecture of the proposed system (e.g. low scalability) were ignored.
Author Response
Title: “A centralized route management solution for autonomous vehicles in urban areas”
Authors: Jorge Luis Zambrano-Martinez, Carlos T. Calafate , David Soler , Lenin Lemus , Juan-Carlos Cano , Pietro Manzoni , Thierry Gayraud.
Date: 2019-06-11
Journal: Electronics
Issue: Smart, Connected and Efficient Transportation Systems
Manuscript Number: electronics-522638
First of all, we would like to thank the reviewers for their generous comments on the original version of this paper. We have incorporated all the changes suggested in the new version of the paper. We think that the current version of the paper has adequately addressed all comments, with their appropriate explanations.
We have prepared the details of the suggested changes, summarizing, in boldface, the issues
pointed out by the reviewers. All the changes have been incorporated to the revised version
of our original manuscript.
____________________________________________________________________________________
Reviewer #1
The Authors have used a centralized approach to find routes for autonomous vehicles in urban road network. The Authors claim that their method reduces congestion, increases average speed, and decreases travel times. These improvements were demonstrated in comparison with a basic approach implemented in SUMO simulation software.
The paper has important drawbacks:
1) The routing problem and objective were not clearly defined (there is lack of formal description of the undertaken problem).
Reply: Currently, vehicular route servers rely on locally stored static information, which is used to calculate the requested routes. There are several commercial and free solutions including TomTom, and Google Maps Navigator. The first deficiency of these systems is that they are based on static information, or on real-time feedback in the best case, but they do not predict future traffic conditions, nor perform any sort of load balancing.
Thus, the main objective of our work is to propose and implement a centralized route manager for autonomous vehicles with the ability to optimize and balance traffic flows by accounting for present and future traffic congestion conditions in terms of travel time depending on the vehicle load, and allowing us to predict the traffic distribution.
We have updated the introduction of the paper to better emphasize on our contribution, which provides several optimal routes according to the congestion estimated behavior of the segments at a given time, as we observe in Figure 10.
2) Detailed description of the proposed method is missing. The method should be presented in an algorithmic fashion, preferably with use of a pseudo code.
Reply: Regarding a detailed description of our proposed method, we have extended the paper by adding two diagrams (see figure 2a and 2b) that allow us to have a clearer and more detailed description of our proposed methodology. Also, a complete pseudo-code algorithm (Algorithm 1) that details the two main tasks performed by our interface (traffic updates and request of the optimal routes, along with the handling of replies from the route server) was added to the paper to make our contribution clearer.
3) Contribution of this work is very limited as the most important aspects of the method were presented by the Authors in their previous works.
Reply: Our contribution is to compare the original traffic conditions in the city with our proposed approach, which is able to balance traffic by exploiting different alternate routes to decongest traffic in critical areas, demonstrating the validity of the proposed characterization and traffic prediction for this city. To achieve this goal, we have connected our vehicular simulators (SUMO, and OMNeT++) with the ABATIS route server through an interface that performs the necessary calculations to perform a conversion between both formats. So, we use our route server capable of handling all the traffic in a city and balancing traffic flows considering present and future traffic congestion conditions.
With respect to previous works, please keep in mind that previously we have merely developed some models to support our solution. In particular, we have shown how to model congestion by developing an equation that can relate street segment occupancy with travel time. In this work, based on those per-segment equations, we develop a full architecture that is actually able to balance traffic throughout the city, and demonstrated how our approach reduce congestion and travel time, and then we evaluate our architecture. Such contribution is completely novel, and was not presented before.
4) Authors have ignored the existing routing methods for autonomous vehicles that can be found in the related literature, e.g.:
- Weyns, D., Holvoet, T., & Helleboogh, A. (2007, September). Anticipatory vehicle routing using delegate multi-agent systems. In 2007 IEEE Intelligent Transportation Systems Conference (pp. 87-93). IEEE.
- Agafonov, A., & Myasnikov, V. (2017). Efficiency comparison of the routing algorithms used in centralized traffic management systems. Procedia engineering, 201, 265-270.
- Rossi, F., Zhang, R., Hindy, Y., & Pavone, M. (2018). Routing autonomous vehicles in congested transportation networks: Structural properties and coordination algorithms. Autonomous Robots, 42(7), 1427-1442.
- Alonso-Mora, J., Wallar, A., & Rus, D. (2017, September). Predictive routing for autonomous mobility-on-demand systems with ride-sharing. In 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (pp. 3583-3590). IEEE.
- Carlino, D., Depinet, M., Khandelwal, P., & Stone, P. (2012, September). Approximately orchestrated routing and transportation analyzer: Large-scale traffic simulation for
autonomous vehicles. In 2012 15th International IEEE Conference on Intelligent Transportation Systems (pp. 334-339). IEEE.
5) The proposed method should be compared with routing algorithms that are representative for the works mentioned above.
Reply: These cited works refer to solutions for traffic routing that do not adequately predict future traffic congestion conditions, which is the purpose of our solution, and they are not directly comparable with our own. However, we have looked in detail to the papers suggested by the reviewer, and we have extended the related works section accordingly.
6) Issues and limitations related to the centralized architecture of the proposed system (e.g. low scalability) were ignored.
Reply: The issue of scalability or performance in our architecture was not addressed as we are performing a simulation study, and thus do not introduce real-time requirements. However, the server execution was shown to be agile, as it has the ability to receive multiple requests from vehicles, which are then stored in shared memory, allowing data sharing between different map updating process to take place. Also, for improving the performance of the query, and for a live-update of the traffic data on the route server, we rely on Multilevel Dijkstra (MLD), which introduces precomputed overlay cells to heuristically speed up the computation.
Therefore, the traffic and network simulators perform requests to our server for the necessary amount of vehicles in the simulation according to the real traffic pattern using our interface, without harming its scalability and performance.
____________________________________________________________________________________
Author Response File: 
Author Response.pdf
Reviewer 2 Report
This paper proposes a technique for balancing the traffic in urban areas by re-routing CAVs. The idea is that vehicles can communicate with a central server that, by evaluating the current traffic conditions and estimating the future evolution of the network, can indicate the best route to take to reach their destination in order to balance the traffic and spread the benefits for all the vehicles. The approach is evaluated using SUMO, and some additional tools/APIs, on the city of Valencia using real-world data.
The problem addressed by the authors is very relevant, and is of growing importance in the current urban traffic control field. The paper is generally well-written and, to the best of my understanding, the work is well-contextualised. I have a few comments that should be taken into account to furtherly improve the work.
- It is not very clear to me where the main equation (i.e., equation 1) comes from. It is listed in page 5, but with no actual description or motivation. How did you design it? Why is it the core equation of the approach? How does it come to play a role for the approach?
As it stands right now, it looks to me like that equation is the only innovative bit of the work. I'm sure it isn't, so it would be great to put the equation in the context.
- A large part of the paper is (correctly) devoted to the experimental analysis. It would be good to give some additional information about the considered data. For instance, a map of the area --with indication of boundaries-- may help. Similarly, an indication of the traffic distribution would be good: did you consider only cars or also other vehicles? What is the considered penetration value? Are you assuming that all the vehicles can communicate with the server?
- line 290: "in Figure 2b we observe that vehicles tend to arrive much earlier when our load balancing technique is used compared to the normal behavior of the reference traffic". I can't really see such a huge difference. It looks to me that there are some changes but not so huge.
In figure 2c, why are vehicles' speed up to 125 km/h? Shouldn't it be much lower as you are considering an urban area?
- Figure 4: I don't see a huge difference between (a) and (b). In fact, it looks like the proposed approach is increasing traffic in some areas, and extending some of the heavy congested areas. Overall, my impression is that it is somehow spreading the traffic, but without huge impact on the congestion levels. Can you please elaborate on that?
- Figure 5: it looks like the AUC of the different curves are very different. Is it really the case? How can that be possible?
- Figure 8: I find here some very counter-intuitive results. Let's focus on (a) and (b), for instance. Why does the average time suddenly drop when new vehicles are injected in the region? While I understand that your approach should improve over the original, it is not clear to me how is it possible that adding more vehicles on a very small area lead to all the vehicles leaving the area faster. Having 100% more vehicles means all the vehicles reach their destination faster than if only 40% are there. Why?
- Figure 10: as in figure 4, I don't see a huge difference in the heatmaps. Even worse, it looks like the heavy congested area is larger on the diagonal when your approach is used..
Summarising, the tackled problem is of primary interest, and the proposed idea may point towards the right direction. However, it is necessary to improve the description of the approach, and to make sure that results of the experimental analysis are correct and well described, and that the setup of the experiments is properly described.
Author Response
Title: “A centralized route management solution for autonomous vehicles in urban areas”
Authors: Jorge Luis Zambrano-Martinez, Carlos T. Calafate , David Soler , Lenin Lemus , Juan-Carlos Cano , Pietro Manzoni , Thierry Gayraud.
Date: 2019-06-11
Journal: Electronics
Issue: Smart, Connected and Efficient Transportation Systems
Manuscript Number: electronics-522638
First of all, we would like to thank the reviewers for their generous comments on the original version of this paper. We have incorporated all the changes suggested in the new version of the paper. We think that the current version of the paper has adequately addressed all comments, with their appropriate explanations.
We have prepared the details of the suggested changes, summarizing, in boldface, the issues
pointed out by the reviewers. All the changes have been incorporated to the revised version
of our original manuscript.
____________________________________________________________________________________
Reviewer #2
This paper proposes a technique for balancing the traffic in urban areas by re-routing CAVs. The idea is that vehicles can communicate with a central server that, by evaluating the current traffic conditions and estimating the future evolution of the network, can indicate the best route to take to reach their destination in order to balance the traffic and spread the benefits for all the vehicles. The approach is evaluated using SUMO, and some additional tools/APIs, on the city of Valencia using real-world data.
The problem addressed by the authors is very relevant, and is of growing importance in the current urban traffic control field. The paper is generally well-written and, to the best of my understanding, the work is well-contextualised. I have a few comments that should be taken into account to furtherly improve the work.
- It is not very clear to me where the main equation (i.e., equation 1) comes from. It is listed in page 5, but with no actual description or motivation. How did you design it? Why is it the core equation of the approach? How does it come to play a role for the approach?
Reply: The elaboration of Equation 1 is further detailed in a previous work [1]. It belongs to the sigmoid family, and is used to represent the relationship between street occupancy and travel times for our data, thus providing a characterization of the different segments of the city.
[1] Zambrano-Martinez, J.L.; Calafate, C.T.; Soler, D.; Cano, J.C. Modeling and characterization of traffic flows in urban environments. Sensors 2018, 18(7), 2020, doi:10.3390/s18072020.
We have updated the paper to further emphasize on our full architecture, which was developed and evaluated only in this work, being completely novel and relevant.
As it stands right now, it looks to me like that equation is the only innovative bit of the work. I'm sure it isn't, so it would be great to put the equation in the context.
Reply: We have included Algorithm 1 to evidence that there were many novel contributions in the current work in addition to that particular equation. Figures 2a and 2b have been introduced to put the equation into context, and to highlight that it is just a minor piece in a larger puzzle.
- A large part of the paper is (correctly) devoted to the experimental analysis. It would be good to give some additional information about the considered data. For instance, a map of the area --with indication of boundaries-- may help. Similarly, an indication of the traffic distribution would be good: did you consider only cars or also other vehicles? What is the considered penetration value? Are you assuming that all the vehicles can communicate with the server?
Reply: The parameters of the two scenarios are included in this paper. The first scenario is the city of Valencia, with an area of 77.42 Km2 excluding suburban areas, as shown in Figure 4. In this scenario, 34.065 vehicles are injected corresponding to the real traces during a peak hour through a period of 15 minutes of simulation. All vehicles injected into the simulator have communication with the server. Similarly, the second scenario is a neighborhood within the city of Valencia called Ruzafa, with an area of 2.15 x 0.5 km, as shown in Figure 10, and injecting about 300 vehicles during the peak hour in 900 seconds of simulation. Additionally, we have gradually injected additional vehicles to this scenario to double the number of vehicles of the real trace, in order to observe the limits of our equations within this scenario.
Our assumptions are that all vehicles are similar from the simulation perspective, and that they all communicate with the server to obtain routes (100% penetration), so that we can correctly assess the effectiveness of our congestion prediction and load balancing strategy.
- line 290: "in Figure 2b we observe that vehicles tend to arrive much earlier when our load balancing technique is used compared to the normal behavior of the reference traffic". I can't really see such a huge difference. It looks to me that there are some changes but not so huge.
Reply: In Figure 2b, we can see slight changes between the original traffic and improved traffic because the data obtained are only the vehicles that have reached their destination, leaving several vehicles halfway through the simulation time that has been introduced (15 minutes) within the rush hour. In this way, it demonstrates that there are several vehicles that reach their destination in the maximum simulation time, while vehicles in the original traffic are slower to reach to their destination.
In figure 2c, why are vehicles' speed up to 125 km/h? Shouldn't it be much lower as you are considering an urban area?
Reply: The data shown in Figure 2c shows the route usage of the original and improved traffic. As shown, some vehicles have been to alternative routes such as auxiliary freeways to load balance the traffic because they are moving close to the edges of the city; thus, our route server sends vehicles on these freeways when balancing the traffic load in the city whenever
it finds that they represent a gain in terms of travel time.
- Figure 4: I don't see a huge difference between (a) and (b). In fact, it looks like the proposed approach is increasing traffic in some areas, and extending some of the heavy congested areas. Overall, my impression is that it is somehow spreading the traffic, but without huge impact on the congestion levels. Can you please elaborate on that?
Reply: Figure 4 shows how traffic congestion is reduced with our contribution. Thus, the same amount of vehicles are present in both scenarios, but in the improved traffic we observe how our server, having a previous knowledge of the behavior of the streets and their expected congestion levels in the near future, balances the traffic by using different routes according to the behavior presented at the time a vehicle requests a route.
- Figure 5: it looks like the AUC of the different curves are very different. Is it really the case? How can that be possible?
Reply: As we can observe in Figure 5, there is a difference between the curves because in the original traffic conditions the vehicles always follow the same route, causing collapse in the streets where the vehicles go through, which congests critical areas due to such static routing approach. However, improved traffic changes this paradigm due to the predictions of the congestion behavior of the streets of the city, information which is updated upon each route request a vehicle makes to the route server. Thus, the route server replies to the vehicle with the optimal route according to the predicted traffic conditions in order to avoid traffic congestion; this means that the server has awareness of several alternative routes, and offers a route that minimizes the delay of the vehicle.
- Figure 8: I find here some very counter-intuitive results. Let's focus on (a) and (b), for instance. Why does the average time suddenly drop when new vehicles are injected in the region? While I understand that your approach should improve over the original, it is not clear to me how is it possible that adding more vehicles on a very small area lead to all the vehicles leaving the area faster. Having 100% more vehicles means all the vehicles reach their destination faster than if only 40% are there. Why?
Reply: As we can see in Figure 8a, the average travel time has this behavior because the results refer only to the vehicles that have reached their destination, leaving out the vehicles that have not completed their route. This explains why the graph contains such oscillations. In any case, notice that our solution always improves upon the original traffic conditions.
- Figure 10: as in figure 4, I don't see a huge difference in the heatmaps. Even worse, it looks like the heavy congested area is larger on the diagonal when your approach is used.
Reply: As we can see in both Figures, the original traffic concentrates all the traffic in critical areas since the vehicles follow a static route, disregarding several empty streets that could decongest the traffic. Thus, we observe in the improved traffic pattern that it tries to occupy all the possible routes to decongest and balance the traffic, reducing the congestion at the critical points. The improvement can be perceived visually by noticing, for example, that the shadowed area has now become larger, which means that vehicles are more distributed throughout the scenario.
Summarising, the tackled problem is of primary interest, and the proposed idea may point towards the right direction. However, it is necessary to improve the description of the approach, and to make sure that results of the experimental analysis are correct and well described, and that the setup of the experiments is properly described.
Reply: We thank the reviewer for the positive remarks and feedback.
Author Response File: Author Response.pdf
Round 2
Reviewer 1 Report
In the revised manuscript, the Authors have stated that "current vehicular route servers rely on locally stored static information which is used to calculate the requested routes. There are several commercial and free solutions including TomTom and Google Maps Navigator. The first deficiency of these systems is that they are based on static information, or on real-time feedback in the best case, but they do not predict future traffic conditions, nor do they to perform any sort of load balancing". The above cited description of state-of-the-art is an excessive simplification. In fact, Google combines historical data with real-time data sent by sensors and smartphones to predict traffic conditions. The prediction feature is also available in TomTom.
The Authors claim that their solution is suitable for autonomous vehicles. However, they do not take into account the specific features of autonomous vehicles, e.g. the ability to reduce congestion by dissipating stop-and-go waves, reducing the time headway and enhancing the traffic capacity. Also the traffic model used for simulation was designed to reflect behavior of human drivers and requires complex calibration to accurately simulate the autonomous vehicles.
Authors should extend experiments to compare their method with existing routing methods for autonomous vehicles to prove the advantages over state-of-the-art alternatives. The experiments reported in the paper are limited to a comparison with a simple approach implemented in SUMO, which is not dedicated for autonomous vehicles.
Issues and limitations related to the centralized architecture of the proposed system (e.g. low scalability) should be discussed in the paper.
Author Response
In the revised manuscript, the Authors have stated that "current vehicular route servers rely on locally stored static information which is used to calculate the requested routes. There are several commercial and free solutions including TomTom and Google Maps Navigator. The first deficiency of these systems is that they are based on static information, or on real-time feedback in the best case, but they do not predict future traffic conditions, nor do they to perform any sort of load balancing". The above cited description of state-of-the-art is an excessive simplification. In fact, Google combines historical data with real-time data sent by sensors and smartphones to predict traffic conditions. The prediction feature is also available in TomTom.
Reply: Thanks for the comment. Indeed Google combines with historical data with data sent by drivers' smartphones, since our smartphones are constantly sending reports about where we are, and how long it takes to get from one place to another. When turning on the smartphone, the GPS starts sending anonymous data about our location and the speed at which the user moves. In the same way, the TomTom solution updates its data through notifications given by users using collaborative social networks, portable browsers, or by a TomTom reporter application. However, this is not effective if the user does not share this information either by the users’ wishes or by regulatory conditions such as the General Data Protection Regulation (GDPR). So, on the one hand, our proposal is powered by the data coming from the induction loops of the Valencia City Hall, and it does not require a smart device as a primary data collection device, as in the case of Google Maps or TomTom. In addition, both Google Maps and TomTom make only short-term predictions based on past and current status, but do not act as centralized controllers for all the traffic in a city. Thus, then cannot make medium-term predictions, nor balance traffic like we do. So, our approach is not at all comparable to these other commercial solutions. We have included these comments into our manuscript.
The Authors claim that their solution is suitable for autonomous vehicles. However, they do not take into account the specific features of autonomous vehicles, e.g. the ability to reduce congestion by dissipating stop-and-go waves, reducing the time headway and enhancing the traffic capacity. Also the traffic model used for simulation was designed to reflect behavior of human drivers and requires complex calibration to accurately simulate the autonomous vehicles.
Authors should extend experiments to compare their method with existing routing methods for autonomous vehicles to prove the advantages over state-of-the-art alternatives. The experiments reported in the paper are limited to a comparison with a simple approach implemented in SUMO, which is not dedicated for autonomous vehicles.
Reply: Although SUMO was not originally designed to address autonomous vehicles, it is a very flexible tool which can include different driver models. In fact, SUMO has been recently updated so as to model autonomous vehicles, and there are several scientific publications that use this mobility simulator for that purpose, see [1] [2]:
[1] Deutsches Zentrum für Luft- und Raumfahrt. (2017). Towards simulation for autonomous mobility (31st ed., p. 192). Berlin-Adlershof
[2]Evamarie Wiessner and Leonhard Lücken and Robert Hilbrich and Yun-Pang Flötteröd and Michael Behrisch and Laura Bieker-Walz and Jakob Erdmann. (2018). SUMO 2018- Simulating Autonomous and Intermodal Transport Systems (2nd ed.,p. 217).
Thus, we beg to differ with the reviewer regarding the non-adequacy of the SUMO tool.
In addition, the issues raised by the reviewer merely highlight that autonomous vehicles are able to further improve system performance, not degrade it, and that their behavior is more predictable than for regular users, which is one of the assumptions of our work.
Taking the aforementioned issues into account, we are confident that our experimental results do have relevance and represent a valid contribution.
In the manuscript we have added the two references that refer to the applicability of SUMO in the scope of autonomous vehicles to further emphasize on this point.
Issues and limitations related to the centralized architecture of the proposed system (e.g. low scalability) should be discussed in the paper.
Reply: The limitations of the proposed centralized architecture are closely associated to the characteristics of the computer used for that task. In our experiments we have used a computer with modest features – Intel Core i5 4-core processor with 16GB of RAM – finding that it is possible to serve up to 2,000 vehicles per second without using parallel processing, and with an average CPU consumption of only 10%. Also, each response from our server takes between 0.5 ms to 4 ms, depending on the length of the route requested by the vehicle. Thus, overall, we do not find scalability problems for our solution. We have updated the paper to refer to these performance issues, as suggested by the reviewer.
Author Response File: Author Response.pdf
Reviewer 2 Report
I thank the authors for their explanations, and for their effort in improving the paper. I still believe that the experimental part can be slightly improved to ease readability and understanding for readers, but I won't object the paper being accepted in its current form.
Author Response
We thank the reviewer for giving us their comments to improve the manuscript.
