Abstract Routing Models and Abstractions in the Context of Vehicle Routing

Abstract

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.