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


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
Issue number3
Publication statusPublished - 2004


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

Cite this