Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks^†

Round 1

Reviewer 1 Report

This study proposes an approach for a space-efficient, fast and exact routing in time-dependent road networks. I think the paper fits well the scope of the journal and addresses an important subject. However, a number of revisions are required before the paper can be considered for publication. There are some weak points that have to be strengthened. Below please find more specific comments:

 

*Page 1 line 13: “smaller indexes than competing approaches” does not sound well. I suggest using “smaller indexes than the alternative approaches”.

*Page 2: Please adjust the position of Fig. 2(b). It seems that it is overlapping with the title of Fig. 2(a).

*Page 3: Some recent and relevant works that are related to vehicle routing are not covered in the literature review. The following recent and relevant studies should be reviewed and acknowledged in the manuscript:

Ruiz, E., Soto-Mendoza, V., Barbosa, A.E.R. and Reyes, R., 2019. Solving the open vehicle routing problem with capacity and distance constraints with a biased random key genetic algorithm. Computers & Industrial Engineering 133, 207-219.

Salavati-Khoshghalb, M., Gendreau, M., Jabali, O. and Rei, W., 2019. An exact algorithm to solve the vehicle routing problem with stochastic demands under an optimal restocking policy. European Journal of Operational Research 273(1), 175-189.

Pasha, J., Dulebenets, M.A., Kavoosi, M., Abioye, O.F., Wang, H. and Guo, W., 2020. An Optimization Model and Solution Algorithms for the Vehicle Routing Problem With a “Factory-in-a-Box”. IEEE Access 8, 134743-134763.

Zhang, H., Zhang, Q., Ma, L., Zhang, Z. and Liu, Y., 2019. A hybrid ant colony optimization algorithm for a multi-objective vehicle routing problem with flexible time windows. Information Sciences 490, 166-190.

Trachanatzi, D., Rigakis, M., Marinaki, M. and Marinakis, Y., 2020. A Firefly Algorithm for the Environmental Prize-Collecting Vehicle Routing Problem. Swarm and Evolutionary Computation, p.100712.

Without review of the recent and relevant studies, the literature review may seem outdated to some readers.

*Page 4: An illustrative figure might be helpful in the problem description, so the readers will better understand the problem at hand.

*Page 8: Please adjust the alignment of Fig. 4. It seems that some segments of the figure do not fit the page.

*Page 17: I suggest adding some supporting references to justify selection of the input data that were used in the experiments.

*Page 25: The authors should add a discussion highlighting the importance of metaheuristics and nature-inspired algorithms for solving complex decision problems in different domains, such as online learning, scheduling, multi-objective optimization, vehicle routing, medicine, data classification, and others. As a part of future research, application of metaheuristics and nature-inspired algorithms could be evaluated for the methods that were used in this study. Furthermore, this discussion should be supported by the relevant references, including the following:

 

Zhao, H. and Zhang, C., 2020. An online-learning-based evolutionary many-objective algorithm. Information Sciences, 509, pp.1-21.

Dulebenets, M.A., 2020. An Adaptive Island Evolutionary Algorithm for the berth scheduling problem. Memetic Computing, 12(1), pp.51-72.

Liu, Z.Z., Wang, Y. and Huang, P.Q., 2020. AnD: A many-objective evolutionary algorithm with angle-based selection and shift-based density estimation. Information Sciences, 509, pp.400-419.

Dulebenets, M.A., 2019. A Delayed Start Parallel Evolutionary Algorithm for just-in-time truck scheduling at a cross-docking facility. International Journal of Production Economics, 212, pp.236-258.

D’Angelo, G., Pilla, R., Tascini, C. and Rampone, S., 2019. A proposal for distinguishing between bacterial and viral meningitis using genetic programming and decision trees. Soft Computing, 23(22), pp.11775-11791.

Panda, N. and Majhi, S.K., 2020. How effective is the salp swarm algorithm in data classification. In Computational Intelligence in Pattern Recognition (pp. 579-588). Springer, Singapore.

Such a discussion will help improving the section devoted to future research directions.

 

 

 

Author Response

Dear reviewer,

thank you for your feedback. Please excuse the broken layout and cut figures in the first version. The version you got was compiled with a different version of the MDPI/algorithms template which caused the layout issues. This should now be fixed in the revised version.

The works that you suggest are excellent resources for the VRP problem and meta-heuristics in general. However, we do not describe VRP solvers in our paper. We compute paths between two fixed nodes. We do not compute tours between many nodes.
One application of our technique is as a subroutine in VRP solvers. We added a brief discussion to the related work section that illustrates this application. Unfortunately, going into depth about VRP seems out-of-scope of our work which focuses on point-to-point path computations and not on VRP.
The problem that we consider is also not NP-hard. The focus of meta-heuristics is to solve hard problems. What makes our problem setting difficult is not its theoretical complexity. It is the huge size of the problem instances considered. We therefore also consider meta-heuristics to be out-of-scope. We do not feel that using meta-heuristics to solve problem settings for which efficient exact algorithms exist is promising future research.
Apologies if something in our work mislead you to the assumption that we would study VRP. We adjusted the abstract and the introduction to explicitly state that we study point-to-point shortest path computations. Is there anything specific in our article which suggested that we would study VRP that we could clarify?
The data we used in our experiments includes most networks used in the experimental evaluations of competing approaches plus some additional instances. We are not aware of any additional publicly available instances and believe that this is sufficient motivation. 

Kind regards
The authors

Reviewer 2 Report

This paper investigates the routing problem in the road transportation network that is a highlight in transportation planning field. The authors provided a complex routing algorithm and demonstrated its feasibility. This paper is very interesting. However, for potential improvement on its current version, I have following concerns for the authors to consider. Thanks.

1. Introduction

1.1. In line 18, the authors claimed that “the core problem is to compute the fastest route between a source and a target”. However, the best route may refer to the one with minimal cost, least time, lowest risk or highest reliability. Consequently, this statement may not be accurate.

1.2. The related work section misses some recently published articles, e.g.:

1) Gendreau et al. (2015). Time-dependent routing problems. https://doi.org/10.1016/j.cor.2015.06.001

2) Huang et al. (2017). Time-dependent vehicle routing problem with path flexibility. https://doi.org/10.1016/j.trb.2016.10.013

3) Sun et al. (2018). A Time-Dependent Fuzzy Programming Approach for the Green Multimodal Routing Problem with Rail Service Capacity Uncertainty and Road Traffic Congestion. https://doi.org/10.1155/2018/8645793

4) Kolovský et al. (2019). The ε-Approximation of the Time-Dependent Shortest Path Problem Solution for All Departure Times. https://doi.org/10.3390/ijgi8120538

……

Therefore, the authors are recommended to search again for the relevant literature, so that their review can reflect the current development of the topic.

1.3. After the related work section, the authors should claim the research gaps based on the literature review section and then present how their research works in this paper bridge these gaps, so that their contributions are more convincing.

1.4. At the end of the introduction section, the authors need to introduce the organization of the remaining sections of their paper.

2. Materials and Methods

This is the major section of this study. However, it seems very difficult for readers to follow. Following revisions are recommended.

2.1. At the beginning of this section, the authors need to explain the research problem in detail, including its objectives and constraints. Then, the authors need to give the reason why such an algorithm is proposed to solve the problem. The feasibility of the algorithm should be introduced in theory.

2.2. The authors need to systematically present their algorithm. A diagram or flowchart is necessary to illustrate the interactions among the modules of the algorithm and how the algorithm works.

2.3. Please explain in detail why your algorithm is “space efficient” and “exact”.

3. Experiment results

3.1. The presentation of the experiment case is too simple. The network and the data of the parameters should be given.

3.1. Please highlight your comparisons between your algorithm and existing ones.

3.2. Please highlight the experiment results demonstrating that the routing algorithm can obtain exact solutions. Are there any comparisons between the proposed algorithm with the classical exact solution algorithm (e.g., branch-and-bound algorithm)?

3.3. Please summarize all your findings that are helpful for routing in the road network.

4. Discussions

The authors need to focus on their unique works in this section, instead of briefly introducing their works. The limitations of this study should be given, and then future works of this study can be claimed accordingly.

Author Response

Dear reviewer,

thank you for your detailed feedback. Please excuse the broken layout and cut figures in the first version. The version you got was compiled with a different version of the MDPI/algorithms template which caused the layout issues. This should now be fixed in the revised version.

> 1.1. In line 18, the authors claimed that “the core problem is to compute the fastest route between a source and a target”. However, the best route may refer to the one with minimal cost, least time, lowest risk or highest reliability. Consequently, this statement may not be accurate.
> 1.2. The related work section misses some recently published articles, e.g.:
> 1) Gendreau et al. (2015). Time-dependent routing problems. https://doi.org/10.1016/j.cor.2015.06.001
> 2) Huang et al. (2017). Time-dependent vehicle routing problem with path flexibility. https://doi.org/10.1016/j.trb.2016.10.013
> 3) Sun et al. (2018). A Time-Dependent Fuzzy Programming Approach for the Green Multimodal Routing Problem with Rail Service Capacity Uncertainty and Road Traffic Congestion. https://doi.org/10.1155/2018/8645793

Thank you for the interesting references. We looked at the suggested papers and found that they mostly focus on the Vehicle Routing Problem (1),2),3)). We do not consider problem settings from the VRP domain in our work. We consider computing shortest paths between two nodes. We do not compute tours between many nodes. We have no TSP subproblem. The problem setting that we consider is not NP-hard. Using the terminology of 1) we study the Time-dependent quickest path problem. What makes the problem difficult is not the theoretical problem complexity but the size of the considered instances. 
VRP algorithms sometimes use shortest path algorithms like ours as subroutines. We added a brief discussion of the use of time-dependent shortest path algorithms in time-dependent VRP. Also, we modified the introduction, to clarify that we study routing problems as they appear in popular map applications such as Google- or Apple-Maps and not VRP. For these applications, the core problem is indeed to find the fastest route. We are well aware that there are other possible problem formulations which deal with costs or risks but our work focuses on fastest routes which for current map applications is the most common and important criteria.
Apologies if something in our work mislead you to the assumption that we would study VRP. Is there anything specific in our article which suggested that we would study VRP that we could clarify?

> 4) Kolovský et al. (2019). The ε-Approximation of the Time-Dependent Shortest Path Problem Solution for All Departure Times. https://doi.org/10.3390/ijgi8120538

We are aware of this work. However, it is not competitive in terms of running times. In the time 4) computes an approximated profile on a city-sized network, [1] can compute an exact profile on a continental-sized instance with three orders of magnitude more arcs. So can our approach.

> 1.3. After the related work section, the authors should claim the research gaps based on the literature review section and then present how their research works in this paper bridge these gaps, so that their contributions are more convincing.

The related work discussion clearly states that all approaches we are aware of have either slow or inexact queries or require large index size. This is the gap we are closing.

> 1.4. At the end of the introduction section, the authors need to introduce the organization of the remaining sections of their paper.

The main sections are the same for every MDPI Algorithms article so we choose to not discuss them. Each section contains a short overview at its beginning.

> 2.1. At the beginning of this section, the authors need to explain the research problem in detail, including its objectives and constraints.

The precise problem statements for queries (earliest-arrival, profile) are introduced in the preliminaries (2.1)

> Then, the authors need to give the reason why such an algorithm is proposed to solve the problem. The feasibility of the algorithm should be introduced in theory.

We intuitively motivated our approach (unpacking shortcuts over storing shortcut travel time functions) in the introduction.
Theoretically arguing why exactly speed-up techniques work so well on road networks is subject to its own research [2,3] and beyond the scope of this article.

> 2.2. The authors need to systematically present their algorithm. A diagram or flowchart is necessary to illustrate the interactions among the modules of the algorithm and how the algorithm works.

We adjusted the beginning of Section 2 to make the interaction of the algorithms more clear. However, there are no modules, so we did not build a diagram. There is just a preprocessing phase and a query phase in which shortest paths can be computed efficiently.

> 2.3. Please explain in detail why your algorithm is “space efficient” and “exact”.

It is exact because it provably obtains shortest paths and distances - as does the baseline, Dijkstra's algorithm.
It is space-efficient because the index size remains manageable (that is can be handled by a commodity server). We cannot formally prove this but our experiments clearly demonstrate this.

> 3.1. The presentation of the experiment case is too simple. The network and the data of the parameters should be given.

Section 3.2 extensively discusses our instances. Section 3.1 discusses our methodology to evaluate queries. if you are missing anything specific we will be happy to add it.

> 3.1. Please highlight your comparisons between your algorithm and existing ones.

Section 3.5 is devoted to comparison with related work.

> 3.2. Please highlight the experiment results demonstrating that the routing algorithm can obtain exact solutions. Are there any comparisons between the proposed algorithm with the classical exact solution algorithm (e.g., branch-and-bound algorithm)?

Table 5 contains relative errors compared to the baseline - Dijkstra's algorithm.
Again, please note that we do not study VRP but efficient shortest path computations!

> 3.3. Please summarize all your findings that are helpful for routing in the road network.

We updated the discussion to point this out more directly.
If you are specifically referring to Section 3.3 -- at the end of 3.3 right before 3.3.1 we clearly point out our main result for time-dependent routing in road networks: path unpacking information allows for a more compact representation and very efficient routing algorithms.

Kind regards
The authors

[1] Batz, G. Veit, et al. "Minimum time-dependent travel times with contraction hierarchies." Journal of Experimental Algorithmics (JEA) 18 (2013): 1-1.
[2] Bauer, Reinhard, et al. "Search-space size in contraction hierarchies." Theoretical Computer Science 645 (2016): 112-127.
[3] Blum, Johannes, and Sabine Storandt. "Lower bounds and approximation algorithms for search space sizes in contraction hierarchies." 28th Annual European Symposium on Algorithms (ESA 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020.

Reviewer 3 Report

The authors propose an extended methodology for improving routing computation considering time-dependent road networks. The contribution is clearly presented and supported by results. Moreover, the paper is well written and structured. Thus, the paper will be suitable for publication after few minor revisions.

Detailed comments:

• According to Fig. 2a and the definition of a shortcut arc in your implementation (i.e., to skip 1 node and 2 arcs), there is one dashed grey arc that doesn’t satisfy the definition (i.e., 2 nodes and 3 arcs). Please check the graph in the figure.
• Please check all tables and figures since some of them appear to be cut (e.g., Figure 4, Table 4, etc.).
• I suggest moving comments in figures/tables captions to the text in order to avoid too long captions and improve readability.

 

Author Response

Dear reviewer,

thank you for your feedback. We adjusted the paper accordingly and moved the very long caption of Fig 7 into the main body. If there is any other caption that you find too long please let us know.

Please excuse the broken layout and cut figures in the first version. The version you got was compiled with a different version of the MDPI/algorithms template which caused the layout issues. This should now be fixed in the revised version.

Regarding Figure 2a - we rechecked the figure but could not find any arc which does not satisfy the definition of skipping two other arcs and one node. Lets number the nodes from left to right (1-5 for the first row, 6-7 for the second row):
1-5 skips over node 2
2-5 skips over node 4 or 6
2-4 skips over 3
6-5 skips over 7
If there is anything we should clarify in the text explanation please let us know.

Best regards

The authors

Reviewer 4 Report

This paper presents a new routing methodology, called CATCHUp That targets on small index size and fast-accurate queries for road networks. It includes an extensive related work, that is sufficient for the reader and experimentation, evaluation, including cross - comparison with related work presented algorithms. Even if it is quite extensive in length, It is quite explanatory and easy to follow and read.

Please pay attention in some tables that are page misaligned (3.1 section Table with no caption, Table at page 22 with no caption,  page 27 Tables)

Author Response

Dear reviewer,

thank you for your feedback. We checked the tables you mentioned but are not quite sure what might be wrong with them. They all do have a caption. The tables use the full page width but the MDPI template explicitly allows this. What exactly do you mean by "page misaligned"?

Best regards

The authors

Reviewer 5 Report

The paper presents a novel speedup technique, called CATCHUp, for providing routes in time-dependent road networks. The proposed technique builds upon other, well-known heuristics, mainly CCH and TCH, the innovation being that it handles combinatorial structures (determination of intermediate nodes in a time-dependent fashion) rather than actual travel-time functions, for the shortcuts that it creates during the preprocessing. CATCHUp achieves competitive preprocessing space and time requirements, as well as query-response times, both for earliest-arrival times and paths and for travel-time functions (profiles), and always produces exact answers.

The presentation of both the algorithmic framework and the experimental evaluation of all the variants of the proposed technique are very well presented and clearly stated. The exploitation of the combinatorial structure of the shortcuts, rather than explicitly storing (exact or approximate) travel-time functions, seems to work very well, as it is demonstrated in the experimental part. CATCHUp manages to simultaneously achieve small preprocessing requirements, few-millisecond query-response times, and provision of exact answers, at the same time. 

The paper should mention though that this idea of maintaining during the preprocessing, not minimum travel-time functions, but timestamped changes in the combinatorial structure of optimal solutions, is indeed not new. It was introduced in another paper for the TDSP problem, that of CFLAT [17], where the entire preprocessing was based on computing time-dependent shortest-path trees from landmark nodes towards all destinations, for carefully selected departure time samples. That work also kept only the combinatorial structures of the optimal solutions for the sampled departure times, and computed the actual travel-time functions (wherever necessary) on-the-fly, within the query algorithm. 

Moreover, the paper should possibly reconsider the importance of the (as called in the literature) Berlin instance. Although much smaller than the other benchmark instances, this instance is in my opinion quite interesting and important, because it is qualitatively different from the other benchmark instances. It focuses on a quite dense urban road-network, whose streets demonstrate much more complicated structure (e.g., number of breakpoints per TD arc), and also the correlation between the characteristics of the travel-time functions is possibly different from that in a nationwide or a continental-size network. It is also a real-world instance, and quite similar with with the other instances real-world instances (in particular, GER17 and EUR17) with respect to other qualitative features (e.g., relative-delays). I would propose that, exactly because this is a benchmark instance different from all the rest considered in the paper, the authors include in the main body of the paper also the experimental evaluation of all the proposed techniques in the literature for this instance as well.

In overall, I find the paper very well written, interesting and novel, and almost ready for publication, modulo the above mentioned points that should be treated by the authors.

In what follows I provide some detailed comments for the authors:

Lines 120-121: The NP hardness of non-FIFO TD instances depends on the waiting model that is considered. For example, if unrestricted waiting at nodes is allowed, and the goal is the earliest arrival at the destination, the problem is strict polynomial-time tractable.

Lines 129-130: The notation $(g \circ f)(\tau) = f(\tau) + g(f(\tau) + \tau)$ for the function-linking operation is confusing, in the sense that it resembles (but is NOT) the operation of function-compositions. To avoid confusing the reader, the authors are advised to either use another symbol for the linking operation (different from the one used for function composition) or, preferably, explicitly mention that this is not a function-composition operation.

Line 137: with little modifications --> with minor modifications

Line 179: Higher ranked reachable from --> The higher-ranked nodes reachable from

Line 190: ordered ascending by rank --> ordered by ascending ranks.

Line 387: a departure time $\tau$ at $s$ --> a departure time $\tau$ from $s$

Line 389 (and anywhere else): can not --> cannot

Line 412: an upper $\overline{t}_v$ --> an upper bound $\overline{t}_v$

Line 436: it's travel time function --> its travel time function 

Line 486: before $t$ will be settled --> before $t$ is settled

Line 503 (and anywhere else): a Dijkstra like search --> a Dijkstra-like search

Line 511: When referring to a phase, you should say, e.g., either "the fourth phase" or "phase 4".

Line 534: We initialize the shortcuts bounds --> We initialize the shortcut bounds

Line 598: That means that while the degree --> This means that the degree

Line 658: corresponds roughly linear to --> corresponds roughly linearly to 

FIGURE 11 (caption): Define what exactly is meant by the term "Dijkstra rank". 

Author Response

Dear reviewer,

thank you for your detailed and constructive feedback. We adjusted the paper accordingly. We hope that you will be satisfied with the revised version.

Best regards

The authors

Round 2

Reviewer 1 Report

The authors took seriously my previous comments and made the required revisions in the manuscript. The quality and presentation of the manuscript have been improved. Therefore, I recommend acceptance.

Reviewer 2 Report

The revisions are fine. I appreciate a lot for the authors' efforts.