Abstract Routing Models and Abstractions in the Context of Vehicle Routing

1 Introduction

Vehicle routing and internet routing have certain similarities, which allows some techniques from one field to be applied to the other. First, in the context of internet routing there have been various approaches to generalize the shortest path problem. Two families of those generalizations are considered here, namely the functional approach and the slightly more restricted algebraic approach [Griffin and Gurney, 2008]. The former is based on weighting edges with functions (see for example [Sobrinho, 2005]), the latter is based on algebraic structures with binary operations usually but not necessarily forming a semiring. Concerning the algebraic approach, we consider two examples, namely incline algebras [Cao et al., 1984] and bounded dioids [Gondran and Minoux, 1984].

∗The first author is a member of the Graduate School of L¨ubeck and is supported by EKSH Gesellschaft f¨ur Energie und Klimaschutz Schleswig-Holstein GmbH.

In the context of vehicle routing, the functional approach was introduced as time-dependent routing where edges are labeled with travel time functions [Delling et al., 2009]: The problem is to find the earliest arrival time for a given departure time (time query) or to find earliest arrival times for all possible departure times (profile search). We show, that profile searches are algebraic routing problems. Similar to that, the energy-efficient routing problem is the problem of finding the most energy conserving path for electric vehicles. This is done by labeling edges with functions mapping battery charge levels to energy costs [Sachenbacher et al., 2011].

There is a large variety on shortest path algorithms, see [Bast et al., 2014] for a current overview. One technique, namely contraction hierarchies by [Geisberger et al., 2012], has caught a lot of attention because of its simplicity and efficiency. It is a bidirectional search on a graph augmented by shortcuts, which drastically reduce the search space. It has also been applied to the time-dependent routing problem [Delling and Wagner, 2009] and to the energy-efficient routing problem [Eisner et al., 2011]. However, in both cases the profile search necessary for the backward search has been identified as the bottleneck, which is why approximations are used to further reduce the search space of profile queries for the time-dependent routing problem [Batz et al., 2010].

In this paper we apply the functional and the algebraic perspective on internet routing problems to vehicle routing problems. We show that especially profile searches form a direct connection between both approaches. Furthermore, we show how to apply formal abstractions known from abstract interpretation to routing problems, which generalizes the idea of routing approximations. Finally, we consider contraction hierarchies as an example for adapting shortest path algorithms and explain how to apply this technique to the algebraic routing problems. An examination of the complexity heavily depends on the underlying structure. Applications are considered for the time-dependent and the energy-efficient routing problem.

The aim is to solve complex routing problems including multiple criteria, e.g. time-dependency for public transportation, congestion in road networks, battery constraints for electric vehicles, uncertainty due to driving behavior and so on. This is achieved by generalizing routing models and routing approximations while preserving the applicability of sophisticated routing algorithms.

2 RoutingModels

Routing models are generalizations of the well-known shortest path problem. We first revise the time-dependent routing problem, which serves as a running example throughout this paper. Two approaches to generalizations of the shortest path problem are presented, namely the functional and the algebraic approach. We show that profile searches known from time-dependent routing connects the functional approach with the algebraic approach.

For both routing models we use the usual definition of semilattices (S,⊕,≤), where ⊕ is an idempotent, associative and commutative operation denoting the unique greatest lower bound of two elements and ≤ denoting the induced partial order, i.e. a ≤ b if and only if a = a ⊕ b for a, b ∈ S. By using a semilattice, the following routing models cover a large variety on routing problems.

2.1 Time-Dependent Road Network

In a road network we can define time-dependency by labeling edges with travel time functions. The following definition is based on a paper by Batz et al.:

Definition 1 (Time-Dependent Routing [2010]). Given a directed graph G = (V,E) and edge weights of the form f : R→R+0 specifying the travel time f(t) at departure time t needed to traverse an edge, we require the FIFO-property, i.e. t + f(t) ≤ t′ + f(t′ ) for all t, t′ ∈ R with t ≤ t′ .

A time-query is to find the earliest arrival time starting in x ∈ V and going to y ∈ V at an initial departure time t ∈ R. A profile search is to find the earliest arrival times for all initial departure times.

The travel time functions may be linked by (f ⋆ g)(t) := g(f(t)+t)+f(t) to describe concatenated edges and merged by (min(f, g))(t) := min(f(t), g(t)) to describe alternative paths.

We distinguish travel time functions f : R → ¯R+0 and departure arrival functions g : R → R with g(t) = f(t) + t. It is easy to see, that linking travel time functions is functional composition of their corresponding departure arrival functions. Merging departure arrival functions is equivalently computed pointwise.

2.2 Functional Routing

Generalizing the idea of time-dependency leads to the following definition of functional routing, where functions describing variable edge costs are defined on a semilattice (S, ⊕, ≤). The crucial difference here is the use of a partial order (instead of a total order) induced by the underlying semilattice.

In the following definition adapted from the work of Sobrinho, we assume function spaces F ⊆ S → S to be closed under composition ◦ and under pointwise application of ⊕.

Definition 2 (Functional Routing [Sobrinho, 2005]). A functional routing network is a tuple (G, S, F,W) where

• G = (V, E) is a directed graph,
• (S,⊕,≤) is a semilattice,
• F ⊆ S → S is a function space, and
• W : E → F is a weighting of edges with functions.

Given two vertices x, y ∈ V and an initial value s ∈ S, the functional routing problem is to determine the value

(e1,...,ek)∈Πx,y

where Πx,y denotes the set of all finite paths from x to y in G and the big ⊕ denotes the greatest lower bound.

Notice, that the ordering of functional composition is inverted (it goes from right to left), because it is defined as (f ◦g)(s) = f(g(s)). The neutral element of functional composition is the identity function idS.

Since the set of all paths Πx,y from x to y may be infinite (when containing cycles) or empty (when y is not reachable from x), there may not be a unique solution to the functional routing problem. Notice also, that we only consider finite graphs. Obviously, if (S,⊕,≤) is a complete lattice, such that any subset of S has a greatest lower bound, then there is a unique solution. Usually, one considers only simple paths (not containing any cycles) and strongly connected graphs to avoid that problem. This way, the search space would be finite and non-empty, so that there is always a unique solution to the problem. Another way is to require cycles to be inefficient, in a way that they do not contribute to any solution.

A slightly more restrictive way to ensure unique solutions is to make weights non-negative. This and some other interesting properties of edge weight functions are described in the following definition.

Definition 3. Let F ⊆ S → S be a function space on a semilattice (S,⊕,≤). A function f ∈ F is called

1. extensive, if s ≤ f(s) for all s ∈ S, that is idS ≤ f,
2. isotonic, if s ≤ t → f(s) ≤ f(t) for all s, t ∈ S.
3. homomorphic, if f(s⊕t) = f(s)⊕f(t) for all s, t ∈ S,
4. right-inclining, if g(s) ≤ f(g(s)) for all s ∈ S and all g ∈ F, that is g ≤ f ◦ g for all g ∈ F,
5. left-inclining, if f(s) ≤ f(g(s)) for all s ∈ S and all g ∈ F, that is f ≤ f ◦ g for all g ∈ F, and
6. distributive, if f(g(s) ⊕h(s)) = f(g(s)) ⊕ f(h(s)) for all s ∈ S and all g, h ∈ F, that is f ◦ (g ⊕ h) = (f ◦ g) ⊕ (f ◦ h) for all g, h ∈ F .

Notice, that extensive functions are also called increasing, non-negative or inflationary, and isotonic functions are also called order-preserving or said to fulfill the FIFO-property. We avoid the term monotonic, because monotonicity sometimes refers to extensivity and sometimes to isotonicity. If a function is both left- and right-inclining, we say it is inclining. The first three properties are called local properties, because they do not depend on other functions in the function space.

All of these properties are preserved under pointwise application of ⊕, while only a), b) and c) are preserved under functional composition. If F is closed under functional composition, then all properties except for left-inclining are preserved under functional composition.

There are some relations between these properties eventually leading to a bridge between the functional approach and the algebraic approach explained in the next section.

Lemma 4. If F ⊆ S →S is a function space on a semilattice (S,⊕,≤), then for functions in F holds:

1. Homomorphic functions are distributive.
2. Extensive functions are right-inclining.
3. Isotonic functions are left-inclining, if all functions in F are extensive.
4. If all function in F are extensive and isotonic, then all functions in F are left- and right-inclining.
5. If idS ∈ F, then right-inclining is equivalent to extensivity.
6. If F contains appropriate waiting functions, that is for all s ∈ S there is a function fs ∈ F such that for all s′ ∈ S we have fs(s′ ) = s for s′ ≤ s, then
7. Left-inclining functions are isotonic.
8. Distributive functions are homomorphic.

Proof. The first four statements can be easily verified. For the fifth, assume that F contains waiting functions fs as defined in the lemma. If a function f is left-inclining, then for all t ∈ S with s ≤ t there is a waiting function ft ∈ F, such that f(s) ≤ f(ft(s)) = f(t), which is the definition of isotonicity.

If f is homomorphic, then for all s and t there are waiting functions fs and ft such that f(s⊕t) = f(fs(s⊕t)⊕ft(s⊕ t)) = f(fs(s ⊕ t)) ⊕ f(ft(s ⊕ t)) = f(s) ⊕ f(t) because s ⊕ t ≤ s, t.

As an example, a time-dependent road network is a functional routing network on the semilattice (R,min,≤) using the common ordering on real numbers, such that all departure arrival functions of the function space are extensive (nonnegative edge costs) and isotonic (FIFO-property). The timequery then is the functional routing problem. Of course, we can also adapt the idea of profile searches to functional routing, this is done in Section 2.4.

2.3 Algebraic Routing

Algebraic routing is another way to generalize the shortest path problem. The basic structure for algebraic routing is a semilattice (S,⊕,≤) with an induced a partial order combined with an associative multiplication ⊗ on S. Probably the weakest variant of such a structure that may still be used for routing are the incline algebras, introduced by [Cao et al., 1984]. A slightly stronger variant is the so called dioid, a semiring with idempotent addition introduced by [Gondran and Minoux, 1984]. We adapt their definitions:

Definition 5 (Incline Algebra [Cao et al., 1984]). The structure (S,⊕,⊗,≤) is an incline algebra if

• ⊕, ⊗ are binary and closed operations on S,
• (S,⊕,≤) is a semilattice,
• ⊗ is associative and distributes over ⊕, and
• a ≤ a ⊗ b and b ≤ a ⊗ b for all a, b ∈ S.

Definition 6 (Dioid [Gondran and Minoux, 1984]). The structure (S,⊕,⊗,≤, 0, 1) is a dioid, if

• (S,⊕,⊗, 0, 1) is a semiring, where
• ⊕ and ⊗ are binary and closed operations on S,
• ⊕ is associative and commutative with a neutral element 0,
• ⊗ is associative with a neutral element 1,
• ⊗ distributes over ⊕,
• 0 absorbs ⊗, i.e. a⊗0 = 0⊗a = 0,
• ⊕ is idempotent, i.e. a ⊕ a = a for all a ∈ S, and
• ≤ is the induced partial order of the semilattice (S,⊕).

The dioid is bounded if 1 absorbs ⊕ (i.e. 1 ⊕ a = a ⊕ 1 = 1).

Notice, that (S,⊕) in Definition 6 is indeed a semilattice with an induced partial order, because associativity and commutativity is given by the semiring structure and idempotency is given by the definition directly.

The binary operation ⊗ does not refer to the dual lattice operation of ⊕, instead it is the multiplication of the underlying semiring. For brevity we sometimes write ab instead of a ⊗ b with precedence over ⊕.

An important property of bounded dioids is given by the following lemma, which implies that bounded dioids are incline algebras.

Lemma 7. If (S,⊕,⊗,≤, 0, 1) is a bounded dioid, then a ≤ a ⊗ b and b ≤ a ⊗ b for all a, b ∈ S.

Proof. We have a ⊕ ab = a1 ⊕ ab = a(1 ⊕ b) = a1 = a, therefore a ≤ ab. Furthermore, we have b ⊕ ab = 1b ⊕ ab = (1 ⊕ a)b = 1b = b, therefore b ≤ ab.

We can now define the algebraic routing problem:

Definition 8 (Algebraic Routing). Let (S,⊕,⊗) be an incline algebra or a bounded dioid, then an algebraic routing network is a tuple (G, S,W), where G = (V,E) is a directed graph, S is the underlying algebraic structure and W : E → S is a weighting, which maps edges to values. Given two vertices x, y ∈ V , the algebraic routing problem is to determine the value

It is easy to see, that incline algebras (and thus also bounded dioids) can be embedded into function space routing. This is done using Cayley's left-representation associating a function fa(b) = a ⊗ b to each a ∈ F and adding an artificial neutral element as an initial value as it was described by [Griffin and Gurney, 2008].

The other way around is more difficult but also possible, if we define the set S to be the disjoint union of values S and functions F then we can define the operation ⊗ to apply functions to values, i.e. s⊗f = f(s) for all s ∈ S and f ∈ F . We may extend this definition to functional composition using f ⊗ g = g ◦ f for all f, g ∈ F . The order changes because f is applied before g. It is easy to see, that forward searches can be done on values, while backward searches are only possible on functions using functional composition. This is described in more detail in the following section.

2.4 Profile Search

The term profile search originates from the field of timedependent routing, where the objective is to find optimal paths for all departure times. This problem can be directly adapted to functional routing networks as follows:

Definition 9 (Profile Search). The problem of finding solutions to the functional routing problem for all initial values is called profile search.

The following theorem captures the essence of profile searches on functional routing networks as an individual routing problem.

Lemma 10. Let F ⊆ S → S be a function space on a semilattice (S,⊕,≤) closed under pointwise ⊕ and functional composition ◦, then the following two propositions are equivalent:

1. F is a set of inclining and distributive functions.
2. (F,⊕, ◦,≤) is an incline algebra.

If the semilattice is bounded by a maximal element ∞ ∈ S and if there are functions 0, 1 ∈ F with 0(s) = ∞ and 1(s) = s for all s ∈ S, then the following two propositions are equivalent:

1. F is a set of extensive, inclining and distributive functions.

Proof. For the former two propositions (a and b) use Lemma 4, for the latter two propositions (c and d):

• ⇒ Due to inclining and distribute properties, we know that (F,⊕, ◦,≤) is an incline algebra. It remains to show the properties of 0 and 1.

Neutral elements: 0 is neutral to ⊕ because s ≤ ∞ (maximal element) and thus f(s) ≤ 0(s) for all s ∈ S, i.e. f ≤ 0 and therefore f = f ⊕0 = 0⊕f . The identity function 1 is neutral to functional composition.

Absorbing elements: 0 absorbs ◦ because since f is extensive we have (0 ◦ f)(s) = f(0(s)) = f(∞) = ∞ and (f ◦0)(s) = 0(f(s)) = ∞. Finally, 1 absorbs ⊕ because f is extensive and thus 1(s) + f(s) = s + f(s) = s = 1(s).

• ⇐ Since bounded dioids are incline algebras due to Lemma 7, we only need to show extensivity, which is implied by right-inclining because 1 = idS ∈ F , see Lemma 4 (5).

Theorem 11. The profile searches on functional routing networks with inclining and distributive functions are algebraic routing problems.

Proof. Comparing the Definitions 2 and 8 shows, that any solution to the algebraic routing problem on the function space with elementwise addition operation and functional composition as multiplicative operation yields a function describing mapping initial values to their respective solutions of the functional routing problem. With Lemma 10 we further know, that if the function space contains only inclining and distributive function the induced algebra is an incline algebra, so that the profile search actually is an algebraic routing problem.

By Lemma 4 (6) we further know that bounded dioids on functions spaces including waiting functions (which we usually do in practice) require the functions to be extensive, isotonic and homomorphic. These are all local properties of functions, which is easier to handle and allows to apply abstractions as described in the following section.

3 Abstractions

We aim to use abstractions because linking and merging operations may be expensive in running time and space consumption. Of course, the result may not be exact if we only use the abstraction, but exact algorithms can benefit from such an abstraction by reducing the search space. This idea was introduced for time-dependent networks by [Batz et al., 2010] using piecewise linear travel-time functions.

3.1 Abstract Interpretation

The following definition of abstractions was adapted from Cousot and Cousot, which is an established technique in static analysis of computer programs.

Definition 12 (Abstraction [Cousot and Cousot, 1977]). Let (S,⊑) and ( ¯ S, ¯⊑) be two partially ordered sets, then a pair of isotonic functions (α : S → ¯ S, γ : ¯ S → S), is an abstraction if

A function ¯ f : ¯ S → ¯ S is a valid abstraction of an isotonic function f : S →S if (for all ¯ s ∈ ¯ S or resp. s ∈ S)

For details about abstractions we refer to the respective paper, which also states that f ≤ γ ◦ f ′ ◦ α. Notice, that functions are required to be isotonic, but as described for profile searches we usually require an inclining property which is close to isotonicity anyway (see Lemma 4). It is well-known that Galois connections are abstractions, but not all abstractions are Galois connections [Cousot and Cousot, 1992].

3.2 Power Set Abstraction for Functional Routing

There are various approaches to apply abstract interpretation to functional routing. It is tempting to examine power sets of possible values, just as it was done by [Cousot and Cousot, 1977] for the static analysis of computer programs. The corresponding order would be the subset relation, which is not necessarily correlated to the ordering of the underlying semilattice. Trying to extend the partial order ≤ to subsets of the semilattice will lead to M ≤ N for M, N ⊆ S if and only if

Because this is actually a closure operator, we have a Galois connection and thus a solid abstraction. In practice however, this seems to be unnecessarily complicated. Instead, we are going to use abstractions for lower and upper bounds to form intervals, a special case of power set abstractions which is more practicable and nearly as powerful.

3.3 Routing Abstraction with Intervals

Abstract interpretation gives an upper bound, that is an over approximation of the desired value. In the context of routing problems a lower bound can be just as interesting, which is an abstraction with respect to the inverted partial order (S,≥). In the following, we will denote a lower bound abstraction by (α↓ , γ ↓ ) and an upper bound abstraction by (α↑ , γ ↑ ), see Figure 1 for an example.

Lemma 13. Let G = (V,E) be a directed graph and let (α, γ) be an abstraction from semilattice (S,⊕,≤) to (S, ⊕, ≤).

If F : S → S and W : E → F form a functional routing network on G and if τ : F → (S → S) maps edge weight functions to valid abstractions, then any solution to the functional routing problem is approximated by the solutions of the functional routing problem on the function space τ(F) with edge weighting W(e) = τ (W(e)).

Proof. Let x, y ∈ V and s ∈ S. We need to show, that any solution s′ on the original problem is less than or equal to the concretization γ(s′ ) of any solution on the abstract routing problem starting with α(s).

Let π = (e1, . . . , ek) ∈ Πx,y be an arbitrary path from x to y in G. We write W(π) to denote W(ek) ◦ . . . ◦ W(e1). Because τ(W(e)) is a valid abstraction of W(e) for all edges e ∈ E, we know that α(W(e)(s)) ≤ τ (W(e)(α(s)) and also for functional composition due to the order-preserving (isotonic) properties: α(W(π)(s)) ≤ τ(W(π))(α(s)).

Because s′ is a greatest lower bound of the set of all W(π)(s) with π ∈ Πx,y, we have s′ ≤ W(π)(s) and because α is order-preserving we have α(s′ ) ≤ α(W(π)(s)). Therefore α(s′ ) is a lower bound of any solution s′ to the abstract functional routing problem with the initial value α(s).

Theorem 14. Routing abstractions yield valid lower and upper bounds on functional routing problems with isotonic functions.

Using Theorem 11 routing abstraction may also be applied to the algebraic routing problem, if the the corresponding unary (curried) functions fb mapping a ∈ S to a ⊗ b are isotonic.

4 Algorithms

There is a large variety on shortest path algorithms, [Bast et al., 2014] gives an overview on current techniques. We want to ensure their applicability to the routing models presented in the previous sections. This is done by examining the basic building blocks of shortest path algorithms, especially for contraction hierarchies, which were proposed by [Geisberger et al., 2012]. Throughout this section we will focus on the algebraic routing problem. As stated in Theorem 11, the profile searches of functional routing problems are algebraic routing problems.

4.1 Dijkstra's Algorithm

Probably the most important building block for any sophisticated shortest path algorithm is Dijkstra's algorithm. Each vertex is labeled with a tentative shortest path distance and a predecessor, which are updated using an edge relaxation procedure: If the sum of the tentative distance of the current vertex and the current edge costs are less than the tentative distance of the successive vertex, then this value is updated and the predecessor is set appropriately. The edge costs are required to be non-negative in order to get correct results [Dijkstra, 1959].

From time-dependent routing, we know that Dijkstra's algorithm can be applied to functional routing if all functions are extensive and isotonic and the underlying semilattice is selective (a ⊕ b ∈ {a, b} for all a, b ∈ S), i.e. the induced order is total. Dijkstra's algorithm can be generalized to partial orders, see for instance [Hansen, 1980]. In the context of functional routing we would require functions to be extensive, isotonic and homomorphic. However, inclining and distributive functions have the same effect for all occuring values, these properties are sufficient.

An extension of Dijkstra's algorithm is A⋆ , which uses a lower bound on remaining distances in order to stall relaxations of non-promising edges. Such heuristics are also available both in functional and algebraic routing, where heuristic values may be taken from the underlying semilattice.

The crucial difference between functional and algebraic routing is, that bidirectional searches can only be applied to algebraic routing, because backward searches would require the final value in the first place.

4.2 Contraction Hierarchies

Contraction hierarchies introduced by [Geisberger et al., 2012] augment a graph with shortcuts in order to greatly reduce the search space. Vertices are contracted one by one such that shortcuts between neighboring vertices are added, if the contracted vertex can not be shown to be irrelevant to the shortest path between those neighboring vertices.

In the case of algebraic routing, we can apply contraction hierarchies in the same way, where linking edges is replaced by the multiplicative operation and merging is replaced by the additive operation of the semilattice. The proof of correctness may be done by structural induction starting from the correctness of contraction hierarchies for time-dependent routing. We can therefore state:

Theorem 15. Bidirectional searches on contraction hierarchies yield correct results to algebraic routing problems.

There is, however, a special case that needs to be considered. Contraction hierarchies on algebraic routing networks with bounded dioids behave exactly like on time-dependent routing networks, but the more general approach on an incline algebra does not imply optimal substructure. Therefore using incline algebras, shortcuts may also be loops.

In the context of time-dependency, approximations can be used to drastically reduce the search space even when querying for exact results [Batz et al., 2010]. Due to Theorem 14 this technique can also be applied to the bidirectional search on contraction hierarchies for algebraic routing problems.

4.3 Complexity

An examination of the time- and space complexity heavily depends on the underlying operations, i.e. the semilattice operation ⊕ as well as the functions F or the multiplication ⊗.

For time-dependency we usually use piecewise linear functions, which can be evaluated in linear time (or even logarithmic when using binary search), so that the functional routing problem is efficiently solved in theory by Dijkstra's algorithm. In practice, the query times are still not satisfying, so that precomputation techniques like contraction hierarchies are applied to the network in order to greatly reduce query times in practice. In order to that, the profile search is considered to get the structure of an algebraic routing problem. The problem is that merging and linking piecewise linear functions greatly increases the descriptive complexity (space consumption) of resulting functions. See [Delling et al., 2009] for instance.

One approach to overcome the increasing descriptive complexity is to use approximations [Batz et al., 2010], which corresponds to the routing abstractions described in the previous section.

5 Applications

The routing models discussed in this paper have various applications. Besides the running example of time-dependent routing, we furthermore discuss energy-efficient routing for electric vehicles by considering battery constraints and potential energy levels.

5.1 Time-Dependent Routing

As we have already seen, the time-dependent routing problem is an example of the functional routing problem using the semilattice (R, min, ≤) and requiring all departure arrival function to be extensive and isotonic.

The corresponding profile search forms an incline algebra on the set S of all departure arrival functions, such that (S,min,≤) is a semilattice and multiplication is given by linking those functions. If we add a neutral element ∞ to the set of reals, then we may also add 1(x) = ∞ and (x) = x in order to get a bounded dioid. Then we may apply any technique for algebraic routing problems.

There are two useful abstractions for departure arrival functions introduced by [Batz et al., 2010] using piecewiselinear functions. One is the interval search, where functions are approximated with the least and maximal costs. This corresponds to two distinct abstractions, both on the semilattice (R,min,+). The lower bound considering the least costs of a function is an abstraction with respect to the inverted relation ≥ and the upper bound considering the maximal costs of a function is an abstraction with respect to ≤. Actually, these two abstracted routing problems may be merged by defining (a, b) ⊕ (c, d) = (min(a, c), min(b, d)) and (a, b)⊗(c, d) = (a+c, b+d) for a, b, c, d ∈ R. The other abstraction is an interesting technique to reduce the number of points of the piecewise-linear functions accepting a certain relative error.

5.2 Energy-Efficient Routing

Battery constraints are modelled using values from an interval [0,K], where K is the capacity of an electric vehicles battery, this was introduced by [Sachenbacher et al., 2011]. By traversing an edge there are three cases:

• The battery may run empty, because costs are higher than the remaining battery energy.
• Because the costs may be negative in case of recuperation of energy, the battery may get fully charged up to its capacity K.
• Otherwise, the costs are just subtracted from the current battery charge.

This is similar to the piecewise linear functions of timedependent routing, but linking those functions does not increase the descriptive complexity. Even though, merging may increase the descriptive complexity, experimental results have shown that contraction hierarchies are suitable to solve the corresponding routing problem efficiently [Eisner et al., 2011]. The profile search - that is, finding the most energyefficient paths for all initial battery charges - is also interesting and was examined further in [Sch¨onfelder et al., 2014]. We aim to increase the efficiency and the quality of these results even more by applying the theoretical results presented in this paper.

6 Conclusions

This paper discussed two generalizations of the shortest path problem, the functional and the algebraic routing problem, that are closely related by the concept of profile searches. The functional routing problem is suitable for modelling various practical routing problems, such as the time-dependent routing and the energy-efficient routing problem. The problem is, that many sophisticated shortest path algorithms can not directly be applied to functional routing, mainly because backward searches are not available.

Theorem 11 states that the profile search of functional routing problems form algebraic routing problems. With Theorem 14 routing abstractions can be applied to get lower and upper bounds, which can also be used to narrow down the search space for exact queries greatly reducing query times in practice, as it was described by [Batz et al., 2010]. Finally, Theorem 15 is given as an illustrating example of how to apply shortest path algorithms to the algebraic routing problem.

In the future, we aim to use routing abstractions and contraction hierarchies for the energy-efficient routing problem and also for probabilistic routing problems taking into account inaccuracies, traffic congestion, driving behavior and other probabilistic factors.