pith. sign in

arxiv: 2604.10608 · v1 · submitted 2026-04-12 · 💻 cs.DS

Optimized Customizable Route Planning in Large Road Networks with Batch Processing

Muhammad Farhan , Henning Koehler This is my paper

Pith reviewed 2026-05-10 15:51 UTC · model grok-4.3

classification 💻 cs.DS
keywords route planningroad networkscustomizable algorithmsbatch processingshortcut graphspath reconstructiontree labeling
0
0 comments X

The pith

Optimizations to path storage in shortcut graphs and path arrays, combined with batch processing, make customizable route planning faster and more scalable in large road networks.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper aims to improve the Customizable Tree Labeling framework so that routes can be found quickly even when costs vary by user, such as travel time versus tolls. It creates multiple versions of the algorithm that store different amounts of path detail in the data structures, creating choices between using more memory or getting answers faster. It also adds batch processing so that many queries at once can reuse shared path calculations instead of repeating the work. This addresses the limit where current customizable methods either use too much space or take too long to answer millions of requests. If correct, these changes would let route planners support more flexible, real-time user needs without requiring larger servers.

Core claim

By creating algorithmic variants that retain varying levels of path information in shortcut graphs and path arrays within the Customizable Tree Labeling framework, and by adding a batch processing strategy that shares path data across queries, the method achieves improved trade-offs in memory and query speed while remaining customizable to different cost metrics, as shown by outperforming prior approaches across 13 real road networks.

What carries the argument

The Customizable Tree Labeling framework, where shortcut graphs handle metric customization and path arrays support reconstruction, extended by variants that adjust stored path details and a batch strategy to share information across queries.

If this is right

  • Different storage variants let systems choose memory use versus speed depending on hardware limits.
  • Batch processing eliminates repeated path calculations when queries share segments or metrics.
  • Customization to new cost metrics stays fast without full index rebuilds.
  • The approach scales to handle millions of simultaneous queries on continent-sized networks.
  • Query performance improves for dynamic conditions where costs change frequently.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The batch sharing idea could apply to other graph search tasks such as supply chain routing where many similar requests arrive together.
  • Lower memory per query might allow running personalized planners directly on mobile devices instead of only on central servers.
  • Frequent re-customization for live traffic data could become practical without full re-preprocessing of the network.

Load-bearing premise

That processing queries in batches will share enough path information to reduce total computation time more than any added cost from grouping and coordinating the batches.

What would settle it

Running the batch method on a workload of millions of queries with completely distinct paths and unrelated cost metrics, then checking whether total running time exceeds that of processing the queries one at a time.

Figures

Figures reproduced from arXiv: 2604.10608 by Henning Koehler, Muhammad Farhan.

Figure 1
Figure 1. Figure 1: Framework overview: relationship to existing work; novel contributions highlighted in red. [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: (left) CTL variants from different storage choices in shortcut graphs (SG) and path arrays (PA). (right) [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: A road network 𝐺, customized with a cost metric 𝜔. 3 Preliminaries Let 𝐺 = (𝑉 , 𝐸) represent a road network. A (cost) metric is a function 𝜔 : 𝐸 → R>0 that assigns a positive cost 𝜔(𝑢, 𝑣) to each edge (𝑢, 𝑣) ∈ 𝐸, such as travel time. This metric may be initially unknown or dynamically determined based on the road network’s properties or external factors. A path is a sequence of distinct vertices 𝑝 = (𝑣1, 𝑣… view at source ↗
Figure 4
Figure 4. Figure 4: An illustration of a tree hierarchy 𝐻𝐺 and tree labeling Scheme 𝐿 over 𝐺, where vertices at the first level are assigned the empty bitstring 𝜆. We only show 𝜏 (𝑣) in place of T (𝑣) for brevity. Example 5.4 [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: (a) An illustration of shortcut graph scheme; (b) Shortcut graph scheme after customization. [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Parameterized labeling 𝐿 𝜃 𝜔 with 𝜃 = 2, where vertices at the first level are assigned the empty bitstring 𝜆. hierarchy. Let 𝑑𝑒𝑠𝑐(𝑣) = {𝑤 ∈ 𝑉 | 𝑣 ⪯ 𝑤} denote the descendants of 𝑣. The cost arrays in 𝐿 𝜃 𝜔 are defined as 𝐶 𝜃 = {𝐶 𝜃 (𝑣) | 𝑣 ∈ 𝑉 , |𝑑𝑒𝑠𝑐(𝑣)| > 𝜃 }. Essentially, labels in 𝐿 𝜃 𝜔 are retained unchanged (𝐶 𝜃 (𝑣) = 𝐶(𝑣)) at the upper levels of the tree hierarchy, but truncated (𝐶 𝜃 (𝑣) = ∅) at the… view at source ↗
Figure 7
Figure 7. Figure 7: Fixed-size storage for shortcuts. Each record uses six 32-bit words, interpreted either in triangle mode [PITH_FULL_IMAGE:figures/full_fig_p017_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Query times across query sets of varying distances with [PITH_FULL_IMAGE:figures/full_fig_p027_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Query performance under varying batch sizes with [PITH_FULL_IMAGE:figures/full_fig_p027_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Update time analysis of DHL with varying numbers of updates for both edge cost increases and [PITH_FULL_IMAGE:figures/full_fig_p028_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Preprocessing time of CTL and CCH, and construction time of H2H. [PITH_FULL_IMAGE:figures/full_fig_p030_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Query performance of extended path unpacking variant of CTL using varying valley-path lengths [PITH_FULL_IMAGE:figures/full_fig_p031_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: Shortcuts distribution. 10.2.5 Tradeoffs. As we have seen, there are different tradeoffs to be had between labeling size and customization time on the one hand, and query time on the other. What’s more, these tradeoffs can be achieved in two different ways: choice of threshold parameter 𝜃, and choice of path information stored for shortcuts and label entries. This raises the question which combinations of… view at source ↗
Figure 14
Figure 14. Figure 14: Customization performance with increasing the # of cores on largest three networks. [PITH_FULL_IMAGE:figures/full_fig_p032_14.png] view at source ↗
read the original abstract

Modern route planners such as Google Maps and Apple Maps serve millions of users worldwide, optmizing routes in large-scale road networks where fast responses are required under diverse cost metrics including travel time, fuel consumption, and toll costs. Classical algorithms like Dijkstra or A$^*$ are too slow at this scale, and while index-based techniques achieve fast queries, they are often tied to fixed metrics, making them unsuitable for dynamic conditions or user-specific metrics. Customizable approaches address this limitation by separating metric-independent preprocessing and metric-dependent customization, but they remain limited by slower query performance. Notably, Customizable Tree Labeling (CTL) was recently introduced as a promising framework that combines tree labelings with shortcut graphs. The shortcut graph enables efficient customization to different cost metrics, while tree labeling, supported by path arrays, provides fast query answering. Although CTL enables optimizing routes under different cost metrics, it still faces challenges in storing and reconstructing path information efficiently, which hinders its scalability for answering millions of queries. In this article, we build on the Customizable Tree Labeling framework to introduce new optimizations for the storage and reconstruction of path information. We develop several algorithmic variants that differ in the information retained within shortcut graphs and path arrays, offering a spectrum of trade-offs between memory usage and query performance. To further enhance scalability, we propose a batch processing strategy that shares path information across queries to eliminate redundant computation. Empirically, we have evaluated the performance of our algorithms on 13 real-world road networks. The results show that they significantly outperform state-of-the-art methods.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper extends the Customizable Tree Labeling (CTL) framework for route planning in large road networks under customizable cost metrics. It introduces algorithmic variants that differ in the information retained in shortcut graphs and path arrays to provide trade-offs between memory usage and query performance, along with a batch processing strategy that shares path information across queries to reduce redundant computation. The methods are evaluated empirically on 13 real-world road networks and reported to significantly outperform state-of-the-art approaches.

Significance. If the performance claims hold under broader conditions, the work would advance practical customizable route planning by improving scalability for high-volume queries while allowing metric flexibility. The spectrum of variants and the batching idea address real limitations in prior CTL work, with potential applicability to dynamic mapping services. The multi-network evaluation is a positive aspect, though the absence of machine-checked proofs or parameter-free derivations means the contribution is primarily algorithmic and empirical.

major comments (2)
  1. [Batch processing strategy] The batch processing strategy is load-bearing for the scalability and outperformance claims (see abstract and the description of the batch processing strategy). The manuscript states that sharing path information eliminates redundant computation but provides no analysis, overhead measurements, or experiments for low-overlap cases such as random or adversarial query sets. Without this, it is unclear whether the reported speedups generalize or depend on particular workload overlap.
  2. [Empirical evaluation] The empirical evaluation on 13 networks claims significant outperformance, but the text lacks error bars, detailed baseline implementations, query workload statistics, or per-batch overhead numbers. This makes it difficult to verify the central performance claim or assess the batching contribution independently (see the empirical evaluation section).
minor comments (2)
  1. [Abstract] The abstract contains a typo ('optmizing' instead of 'optimizing').
  2. [Abstract] The notation 'A$^*' appears to be a LaTeX formatting artifact and should be rendered as A^*.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments, which highlight important aspects of the batch processing strategy and empirical evaluation. We will revise the manuscript to address these points by adding the requested analysis, details, and measurements.

read point-by-point responses

  1. Referee: [Batch processing strategy] The batch processing strategy is load-bearing for the scalability and outperformance claims (see abstract and the description of the batch processing strategy). The manuscript states that sharing path information eliminates redundant computation but provides no analysis, overhead measurements, or experiments for low-overlap cases such as random or adversarial query sets. Without this, it is unclear whether the reported speedups generalize or depend on particular workload overlap.

    Authors: We agree that experiments on low-overlap workloads are needed to fully substantiate the generalizability of the speedups. In the revision, we will add results for random query sets and adversarial workloads with minimal path overlap, along with measurements of batching overhead and a discussion of when sharing common subpaths still yields net benefits even under low overlap. revision: yes

  2. Referee: [Empirical evaluation] The empirical evaluation on 13 networks claims significant outperformance, but the text lacks error bars, detailed baseline implementations, query workload statistics, or per-batch overhead numbers. This makes it difficult to verify the central performance claim or assess the batching contribution independently (see the empirical evaluation section).

    Authors: We will enhance the empirical evaluation section by adding error bars (or standard deviations) to all performance figures, expanded descriptions of baseline implementations, statistics on the query workloads used, and explicit per-batch overhead measurements. These additions will allow readers to independently assess the contribution of batch processing. revision: yes

Circularity Check

0 steps flagged

No circularity: algorithmic variants and batch strategy are independent of inputs

full rationale

The paper introduces optimizations to the CTL framework for path storage/reconstruction and a batch processing strategy that shares information across queries. These are described as new algorithmic variants offering explicit memory-query trade-offs, with performance claims supported by empirical evaluation on 13 external real-world road networks against SOTA methods. No equations, derivations, or central claims reduce by construction to fitted parameters, self-definitions, or self-citation chains. The approach uses standard graph data structures and is falsifiable via the reported benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The paper introduces no new free parameters, axioms beyond standard graph theory, or invented entities; all claims rest on algorithmic redesign of existing CTL components and empirical testing.

pith-pipeline@v0.9.0 · 5575 in / 1079 out tokens · 23173 ms · 2026-05-10T15:51:37.610592+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

46 extracted references · 46 canonical work pages

  1. [1]

    Goldberg, and Renato F

    Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. 2011. A Hub-Based Labeling Algorithm for Shortest Paths in Road Networks. InProceedings of the 10th International Conference on Experimental Algorithms. 230–241

    work page 2011

  2. [2]

    Goldberg, and Renato F

    Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. 2012. Hierarchical Hub Labelings for Shortest Paths. InProceedings of the 20th Annual European Conference on Algorithms. 24–35

    work page 2012

  3. [3]

    PTV AG. [n. d.]. Western europe dataset. http://www.ptv.de

    work page

  4. [4]

    Kyoungho Ahn and Hesham Rakha. 2008. The effects of route choice decisions on vehicle energy consumption and emissions.Transportation Research Part D: transport and environment13, 3 (2008), 151–167

    work page 2008

  5. [5]

    Takuya Akiba, Yoichi Iwata, Ken-ichi Kawarabayashi, and Yuki Kawata. 2014. Fast shortest-path distance queries on road networks by pruned highway labeling. In2014 Proceedings of the sixteenth workshop on algorithm engineering and experiments (ALENEX). 147–154

    work page 2014

  6. [6]

    Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida. 2013. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. InProceedings of the ACM SIGMOD International Conference on Management of Data. 349–360

    work page 2013

  7. [7]

    Julian Arz, Dennis Luxen, and Peter Sanders. 2013. Transit node routing reconsidered. InProceedings of the 12th International Symposium of Experimental Algorithms. 55–66

    work page 2013

  8. [8]

    Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F Werneck. 2016. Route planning in transportation networks.Algorithm engineering: Selected results and surveys(2016), 19–80

    work page 2016

  9. [9]

    Holger Bast, Stefan Funke, and Domagoj Matijevic. 2006. Transit ultrafast shortest-path queries with linear-time preprocessing.9th DIMACS Implementation Challenge [1](2006)

    work page 2006

  10. [10]

    Thomas Bläsius, Valentin Buchhold, Dorothea Wagner, Tim Zeitz, and Michael Zündorf. 2025. Customizable Contraction Hierarchies–A Survey.arXiv preprint arXiv:2502.10519(2025)

    work page arXiv 2025

  11. [11]

    Johannes Blum and Sabine Storandt. 2022. Customizable Hub Labeling: Properties and Algorithms. InInternational Computing and Combinatorics Conference. Springer, 345–356

    work page 2022

  12. [12]

    Hans L Bodlaender. 2006. Treewidth: characterizations, applications, and computations. In32nd International Workshop of Graph-Theoretic Concepts in Computer Science. 1–14

    work page 2006

  13. [13]

    Zitong Chen, Ada Wai-Chee Fu, Minhao Jiang, Eric Lo, and Pengfei Zhang. 2021. P2h: Efficient distance querying on road networks by projected vertex separators. InProceedings of the ACM SIGMOD International Conference on Management of Data. 313–325

    work page 2021

  14. [14]

    Edith Cohen, Eran Halperin, Haim Kaplan, and Uri Zwick. 2003. Reachability and distance queries via 2-hop labels. SIAM J. Comput.32, 5 (2003), 1338–1355

    work page 2003

  15. [15]

    Daniel Delling, Andrew V Goldberg, Thomas Pajor, and Renato F Werneck. 2017. Customizable route planning in road networks.Transportation Science51, 2 (2017), 566–591

    work page 2017

  16. [16]

    Daniel Delling, Andrew V Goldberg, Ilya Razenshteyn, and Renato F Werneck. 2011. Graph partitioning with natural cuts. In2011 IEEE International Parallel & Distributed Processing Symposium. IEEE, 1135–1146

    work page 2011

  17. [17]

    2009.The shortest path problem: Ninth DIMACS implementation challenge

    Camil Demetrescu, Andrew V Goldberg, and David S Johnson. 2009.The shortest path problem: Ninth DIMACS implementation challenge. Vol. 74. American Mathematical Soc

    work page 2009

  18. [18]

    Julian Dibbelt, Ben Strasser, and Dorothea Wagner. 2016. Customizable contraction hierarchies.Journal of Experimental Algorithmics (JEA)21 (2016), 1–49. 33

    work page 2016

  19. [19]

    Muhammad Farhan, Henning Koehler, Robert Ohms, and Qing Wang. 2024. Hierarchical Cut Labelling–Scaling Up Distance Queries on Road Networks. InProceedings of the ACM SIGMOD International Conference on Management of Data

    work page 2024

  20. [20]

    Muhammad Farhan, Henning Koehler, and Qing Wang. 2025. Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks.Proceedings of the ACM on Management of Data3, 1 (2025), 1–25

    work page 2025

  21. [21]

    Muhammad Farhan, Henning Koehler, Qing Wang, Jiawen Wang, Moritz Laupichler, and Peter Sanders. 2025. Cus- tomization Meets 2-Hop Labeling: Efficient Routing in Road Networks.Proceedings of the VLDB Endowment18, 10 (2025), 3326–3338

    work page 2025

  22. [22]

    Muhammad Farhan, Qing Wang, Yu Lin, and Brendan Mckay. 2018. A highly scalable labelling approach for exact distance queries in complex networks.arXiv preprint arXiv:1812.02363(2018)

    work page arXiv 2018

  23. [23]

    Robert Geisberger, Peter Sanders, Dominik Schultes, and Daniel Delling. 2008. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. InInternational workshop on experimental and efficient algorithms. 319–333

    work page 2008

  24. [24]

    Robert Geisberger, Peter Sanders, Dominik Schultes, and Christian Vetter. 2012. Exact routing in large road networks using contraction hierarchies.Transportation Science46, 3 (2012), 388–404

    work page 2012

  25. [25]

    Alan George. 1973. Nested dissection of a regular finite element mesh.SIAM journal on numerical analysis10, 2 (1973), 345–363

    work page 1973

  26. [26]

    Andrew V Goldberg and Chris Harrelson. 2005. Computing the shortest path: 𝐴∗ search meets graph theory. InSODA, Vol. 5. 156–165

    work page 2005

  27. [27]

    Peter E Hart, Nils J Nilsson, and Bertram Raphael. 1968. A formal basis for the heuristic determination of minimum cost paths.IEEE transactions on Systems Science and Cybernetics4, 2 (1968), 100–107

    work page 1968

  28. [28]

    Yihao Hu, Gabriele Oliaro, Jiani Yang, and Muhammad Farhan. 2025. Reproducibility Report for ACM SIGMOD 2024 Paper:’Hierarchical Cut Labelling-Scaling Up Distance Queries on Road Networks’. InReproducibility Reports of the 2024 International Conference on Management of Data. 8–9

    work page 2025

  29. [29]

    Ruoming Jin, Ning Ruan, Yang Xiang, and Victor Lee. 2012. A highway-centric labeling approach for answering distance queries on large sparse graphs. InProceedings of the ACM SIGMOD International Conference on Management of Data. 445–456

    work page 2012

  30. [30]

    Sungwon Jung and Sakti Pramanik. 2002. An efficient path computation model for hierarchically structured topo- graphical road maps.IEEE Transactions on Knowledge and Data Engineering14, 5 (2002), 1029–1046

    work page 2002

  31. [31]

    Henning Koehler, Muhammad Farhan, and Qing Wang. 2025. Stable Tree Labelling for Accelerating Distance Queries on Dynamic Road Networks.arXiv preprint arXiv:2501.17379(2025)

    work page arXiv 2025

  32. [32]

    Dennis Luxen and Peter Sanders. 2011. Hierarchy Decomposition for Faster User Equilibria on Road Networks. InExperimental Algorithms, Panos M. Pardalos and Steffen Rebennack (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 242–253

    work page 2011

  33. [33]

    Jens Maue, Peter Sanders, and Domagoj Matijevic. 2010. Goal-directed shortest-path queries using precomputed cluster distances.Journal of Experimental Algorithmics (JEA)14 (2010), 3–2

    work page 2010

  34. [34]

    Dian Ouyang, Lu Qin, Lijun Chang, Xuemin Lin, Ying Zhang, and Qing Zhu. 2018. When hierarchy meets 2-hop-labeling: Efficient shortest distance queries on road networks. InProceedings of the ACM SIGMOD International Conference on Management of Data. 709–724

    work page 2018

  35. [35]

    Dian Ouyang, Dong Wen, Lu Qin, Lijun Chang, Xuemin Lin, and Ying Zhang. 2023. When hierarchy meets 2-hop- labeling: efficient shortest distance and path queries on road networks.VLDB J.32, 6 (2023), 1263–1287

    work page 2023

  36. [36]

    Dian Ouyang, Long Yuan, Lu Qin, Lijun Chang, Ying Zhang, and Xuemin Lin. 2020. Efficient shortest path index maintenance on dynamic road networks with theoretical guarantees.Proceedings of the VLDB Endowment13, 5 (2020), 602–615

    work page 2020

  37. [37]

    1969.Bi-Directional and Heuristic Search in Path Problems

    Ira Sheldon Pohl. 1969.Bi-Directional and Heuristic Search in Path Problems. Ph. D. Dissertation. Stanford, CA, USA. AAI7001588

    work page 1969

  38. [38]

    Yu-Xuan Qiu, Dong Wen, Lu Qin, Wentao Li, Rong-Hua Li, Zhang Ying, et al. 2022. Efficient shortest path counting on large road networks.Proceedings of the VLDB Endowment(2022)

    work page 2022

  39. [39]

    Peter Sanders and Dominik Schultes. 2005. Highway Hierarchies Hasten Exact Shortest Path Queries. InProceedings of the 13th Annual European Conference on Algorithms

    work page 2005

  40. [40]

    Peter Sanders and Dominik Schultes. 2005. Highway hierarchies hasten exact shortest path queries. InProceedings of the 13th annual European conference on Algorithms. 568–579

    work page 2005

  41. [41]

    Peter Sanders and Dominik Schultes. 2006. Engineering highway hierarchies. InEuropean Symposium on Algorithms. Springer, 804–816

    work page 2006

  42. [42]

    2013.High Quality Graph Partitioning

    Christian Schulz. 2013.High Quality Graph Partitioning. Ph. D. Dissertation. Karlsruhe Institute of Technology. http://digbib.ubka.uni-karlsruhe.de/volltexte/1000035713

    work page arXiv 2013

  43. [43]

    1983.Data structures and network algorithms

    Robert Endre Tarjan. 1983.Data structures and network algorithms. SIAM. 34

    work page 1983

  44. [44]

    Mengxuan Zhang, Lei Li, Wen Hua, Rui Mao, Pingfu Chao, and Xiaofang Zhou. 2021. Dynamic hub labeling for road networks. InIEEE 37th International Conference on Data Engineering (ICDE). 336–347

    work page 2021

  45. [45]

    Yikai Zhang and Jeffrey Xu Yu. 2022. Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks. InProceedings of the 2022 International Conference on Management of Data. 1992–2005

    work page 2022

  46. [46]

    Andy Diwen Zhu, Hui Ma, Xiaokui Xiao, Siqiang Luo, Youze Tang, and Shuigeng Zhou. 2013. Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice. InProceedings of the ACM SIGMOD International Conference on Management of Data. 857–868. 35

    work page 2013