Creating graph partitions for fast optimum route planning

I.C.M. Flinsenberg, M.G. Horst, van der, J.J. Lukkien, J.H. Verriet

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

We investigate fast optimum route planning in large, real-world road networks for car navigation systems. We show how graph partitioning can be used to increase the speed of planning optimum routes. Creating a graph partition with future route planning in mind leads to a non-standard graph partitioning problem. In particular, the quality of a partition, indicated by the objective value, is assumed to represent the execution time of the route planning process. We present an efficient approximation algorithm for creating graph partitions suited for fast optimum route planning. We study the relation between the objective value and the number of edges evaluated by the route planning algorithm, which is an objective measure of the route planning speed. Experiments show that the best partition according to the objective value does not lead to the fastest route planning process. We present a new objective value and show that better partitions result in faster route planning for our new objective value.
Original languageEnglish
Pages (from-to)569-574
JournalWSEAS Transactions on Computers
Volume3
Issue number3
Publication statusPublished - 2004

Fingerprint Dive into the research topics of 'Creating graph partitions for fast optimum route planning'. Together they form a unique fingerprint.

  • Cite this

    Flinsenberg, I. C. M., Horst, van der, M. G., Lukkien, J. J., & Verriet, J. H. (2004). Creating graph partitions for fast optimum route planning. WSEAS Transactions on Computers, 3(3), 569-574.