Abstract Routing Models and Abstractions in the Context of Vehicle Routing

René Schönfelder, Martin Leucker


The functional and the algebraic routing problem are generalizations of the shortest path problem. This paper shows that both problems are equivalent with respect to the concept of profile searches known from time-dependent routing. Because of this, it is possible to apply various shortest path algorithms to these routing problems. This is demonstrated using contraction hierarchies as an example. Furthermore, we show how to use Cousots' concept of abstract interpretation on these routing problems generalizing the idea of routing approximations, which can be used to find approximative solutions and even to improve the performance of exact queries. The focus of this paper lies on vehicle routing while both the functional and algebraic routing models were introduced in the context of internet routing. Due to our formal combination of both fields, new algorithms abound for various specialized vehicle routing problems. We consider two major examples, namely the time-dependent routing problem for public transportation and the energy-efficient routing problem for electric vehicles.

Original languageEnglish
Title of host publicationComputational Sustainability Track
EditorsM. Wooldridge , Q. Yang
Number of pages7
PublisherInternational Joint Conferences on Artificial Intelligence Organization
Publication date25.06.2015
ISBN (Print)978-157735738-4
Publication statusPublished - 25.06.2015
Event24th International Joint Conference on Artificial Intelligence - Buenos Aires, Argentina
Duration: 25.07.201531.07.2015
Conference number: 116754


Dive into the research topics of 'Abstract Routing Models and Abstractions in the Context of Vehicle Routing'. Together they form a unique fingerprint.

Cite this