Use of Planar Graphs to Perform Navigational Routings on Road Networks

RELATED APPLICATIONS

[0001] The subject matter of this application is related to U.S. Provisional Application No. 63344579, filed on 2022-05-21, U.S. Provisional Application No. 63361565, filed on 2022-01-06, and U.S. Provisional Application No. 63259793, filed on 2021-08-13, all of which applications are incorporated herein by reference in their entireties.

BACKGROUND OF THE INVENTION

1 The Computational Problems Addressed, and the Use of Road-Network Distances in Addressing Them

[0002] Many enterprises benefit from repeatedly finding solutions to optimization problems in road networks. The most common such problem is: given a road network and an assignment of lengths to road segments and optionally to intersections, and given an origin-destination pair (x,y), find the shortest x-to-y path, or the length of that path (called the x-to-y distance). In this document we sometimes use dist(x,y) to denote the x-to-y distance.

[0003] The word path here is a technical term for what is commonly called a route, i.e. a planned trajectory along roads that a vehicle or pedestrian could follow. A length assignment for a road network is a table that associates numbers with road segments and optionally with intersections. Note that the length assigned to a road segment need not be related to or solely determined by the geometric length of the road segment; it can reflect, for example, how fast that road segment can be traversed by a vehicle or pedestrian on a specific day or at a specific time of day. The length of a path therefore can represent (in some units) the expected duration of a vehicle's or pedestrian's traversal of that path, or some weighted average of geometric length and duration. Lengths can represent other properties, such as a toll one might need to pay to traverse a road segment or the likelihood of a passenger being on that road segment.

[0004] The scientific literature on finding best routes in a network is vast. One method is the algorithm of Dijkstra. This algorithm takes as input: (a) a suitable computer representation of a road network, and (b) a starting  location in that road network.  In one  form, it outputs a representation of the best paths� �from the starting location to all locations  in the network.  In another form, it takes an addi tional input item: (c) a destination location  in the road network, and in this form, it outputs  the best path from the starting location to  the destination location.   [0005] A road network consists of arcs (which typically rep resent road segments) and  vertices (which typically represent street intersection s), and a specification of how the arcs  and vertices relate (a specification of their inciden ce relation).  An arc has a start vertex (its  tail) and an end vertex (its head).  Each vertex t hus is the start of a collection of arcs and is  the end of a collection of arcs.  A path is a tr aversal through the road network.  Formally it  can be defined as a sequence of arcs such that, fo r any pair (a, b) of consecutive arcs in the  sequence, the head of a is the tail of b.  A pat h in a road network represents a trajectory  along the roads.   [0006] “Best path” is defined with respect to a labelin g of the elements of the road  network with numbers, called costs or scores.  A co st can be assigned to an arc of the road  network (which represents a road segment) or a verte x of the road segment (which  represents a street intersection).  The cost or scor e of a path is the sum of costs of the  elements it traverses.  The “best path” from a  starting location to a destination location is  the least costly path among all those paths from th at starting location to that destination  location.   [0007] The cost of an arc can be its length in some unit s, in which case the cost or score  of a path is its physical length.  The cost of an  arc can represent the expected time required  to traverse an arc, in which case the cost of a p ath is the expected time required to traverse  that path.  The cost can be a combination of lengt h and time, or can take into account other  features, such as road tolls, travel date/time and e nergy efficiency.  The problem of  computing best paths with respect to a given cost f unction is often called shortest paths,  and the cost of the least costly path from one ver tex to another is called the distance, but  this does not mean that costs needs to represent ph ysical lengths.   [0008] Dijkstra’s algorithm is well‐known.  It is typica lly taught to first‐year computer  science students.  The algorithm maintains an assignm ent of numbers (priorities) to the  vertices. In each iteration the algorithm selects the vertex v with the smallest priority number, and updates the priorities of vertices w such that some arc has tail v and head w. This is called scanning v. The process continues until the vertex selected is the desired destination. The algorithm also stores some additional information to enable it to obtain the best path or its cost. The important thing is that the computation time for the algorithm is proportional to the number of vertices scanned, which in turn depends on how priorities are assigned. In Dijkstra's algorithm, the priority of a vertex is an estimate of the minimum cost of a path to that vertex from the starting vertex.

[0009] Dijkstra's algorithm is guaranteed to output the correct answer. However, it has the disadvantage that, even if it is given the starting location and the destination location, it might need to examine much more of the network than merely the arcs and vertices belonging to the best path. As a consequence, it can require a lot of computation time.

[0010] Numerous techniques, referred to as distance oracles, have been proposed to quickly compute a best path from a start vertex to destination vertex using a data structure constructed by preprocessing the road network. The desirability of a distance oracle depends on: (A) how much time the preprocessing takes (preprocessing time), (B) how much storage space is required for the data structure (space), and (C) how much time it takes to subsequently answer a query of the form "what is the best path from start location a to destination location b?" (guery time). Which quantities are most important can depend on the intended application. For example, if costs change only rarely then preprocessing time might not be so important but if costs change frequently (e.g. due to traffic or road closures) then preprocessing time might be important.

[0011] One method is described in U.S. Patent Number 7,603,229 (hereinafter the " '229 patent"), title "Efficiently finding shortest paths using landmarks for computing lower-bound distance estimates". A related scientific paper is: Goldberg, Andrew V. and Harrelson, Chris, "Computing the shortest path: A* search meets graph theory," Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 156-165 (2005). We refer to this method as the “A*, landmarks, and triangle ineguality” method (hereinafter the "ALT method"). [0012] In the ALT method, the preprocessing consists of choosing a small set L of road network locations, called landmarks, and computing the distance from each landmark to and from every vertex in the road network. The data structure consists of a table specifying all those distances. Let k be the number of landmarks. Let n be the number of vertices in the road network. Then the preprocessing time and the space required by the data structure are each proportional to n times k.

[0013] The query-answering algorithm in ALT is a variant of Dijkstra's algorithm called A* search (pronounced "A-star"). A* search dates back to 1968, and its interpretation as a variant of Dijkstra's algorithm dates back to 1971. In the ALT method, a vertex v is assigned priority equal to the sum of two quantities (1) an estimate of the distance from the starting vertex to v (this part is the same as in Dijkstra's algorithm) and (2) an estimate of the distance from v to the destination vertex t. The first quantity is the cost of a path from the starting vertex to v that has already been explored by the algorithm, and is thus greater than or equal to the minimum cost. The second quantity is required to be less than or equal to the minimum cost of a path from v to the destination. In the ALT method, the second quantity is computed as follows:

• For each landmark x, look up the distance from v to x and subtract from it the distance from t to x.

• Compute the maximum of the resulting numbers, and use it as the second quantity.

This way of choosing priorities results in fewer vertices being scanned in practice than choosing priorities according to Dijkstra's original algorithm.

[0014] The '229 patent also describes a slightly more sophisticated variant of the ALT method in which it searches forward from the starting vertex and also searches backward from the ending vertex. This is called bidirectional search, and it results in a further reduction in the number of vertices scanned in practice.

[0015] The ALT method involves a tradeoff. The degree to which the priorities help reduce the number of vertices scanned depends on the choice of landmarks; the more landmarks, generally speaking, the fewer vertices are scanned during the search. On the other hand, the more landmarks, the greater the preprocessing time and the greater the memory space is required. Recall that the preprocessing time and the space are proportional to n times k, where n is the number of vertices and k is the number of landmarks. For example, in the paper describing the ALT method, the authors write "We use ... 16 [as the number of landmarks] because is [sic] the maximum number that fits in memory for our biggest test problem." Further, although the memory used by the ALT system may limit the number of landmarks in the dataset to e.g. 16, typically only a smaller subset of the landmarks, such as 4, would be used to perform a route search from an origin to a destination.

[0016] The computational problem of finding the x-to-y distance or the shortest x-to-y path arises not just in planning a route; it comes up repeatedly in solving more complicated problems. For example, consider the problem of selecting a delivery route for making deliveries to a large collection of locations in a road map. A procedure for selecting such a route typically takes as input (or computes) the distances between pairs of drop-off locations and between each drop-off location and various depot/merchant/fulfillment centers. For another example, consider the problem of dispatching drivers to riders, given their locations; a procedure for selecting which driver is assigned to each rider typically takes as input (or computes) the distances or durations (or some combination) from the drivers' locations to the riders' locations. For another example, consider the problem of deciding where to locate fulfillment centers/stores/clinics (generically called facilities in this context) when given a sample collection of locations of clients; an algorithm that selects a group of facility locations typically takes as input (or computes) the distances or durations from candidate facility locations to sample client locations.

[0017] Moreover, there are optimization problems that involve aspects of several of the above examples. Consider the problem of organizing a large delivery/service crew to deliver goods or services from several available facilities to many delivery/service locations. One must assign a subset of delivery/service jobs to each crew member and provide that crew member with a route that visits all those deliver/service locations. Ideally, the assignment decisions and the route decisions all happen jointly, so that the assignment decisions reflect the durations of the routes and possibly the initial locations of the goods and/or the crew members. SUMMARY OF THE INVENTION

[0018] The present disclosure relates to methods for efficiently and accurately solving optimization problems in road networks. When an input is required to be a planar embedded graph, one can use known efficient algorithms to obtain faster and/or more accurate solutions than for non-planar graphs. Such algorithms have not previously been considered for use in addressing practical problems in real road networks since such road networks are not generally representable by planar graphs. The present disclosure teaches methods that can be used to approximate real road networks using planar graphs and thereby apply more efficient algorithms for solving such optimization problems. In one aspect, the methods can be used to compute or estimate x-to-y distances and shortest or approximately shortest x-to-y paths in road networks. The methods can also be used to solve more complicated optimization problems such as delivery optimization, dispatch, and facility location.

[0019] A computer-implemented method can include: accessing a road network data structure representing a road network having road segments, intersections, crossings, and turn restrictions, wherein the road segments are represented by edges and the intersections are represented by nodes in a road network graph; processing the road network data structure to create an enriched planar embedded graph; identifying one or more portions of the enriched planar embedded graph, wherein each of the portions has a face with a plurality of boundary nodes; and for each portion of the one or more portions: applying a multiple-source shortest path technique to calculate a shortest path data structure representing shortest path distances between each of the plurality of boundary nodes and each node in the each portion; and for each of a plurality of pairs of nodes selected from the nodes in the each portion, computing a greatest from-landmark or to-landmark lower bound on a distance, in the each portion, from a first to a second of the pair of nodes.

[0020] The method can further include, for the each portion, further: performing an A* search to determine a shortest path from an origin node to a destination node in the road network graph, wherein the A* search iteratively uses the from-landmark or to-landmark lower bounds computed for the plurality of pairs in the each portion of the enriched planar embedded graph. [0021] Computing a greatest from-landmark or to-landmark lower bound can include: selecting a boundary node of the each portion as a landmark, wherein the selected boundary node has a greatest from-landmark or to-landmark lower bound on a distance, in the each portion, from the first to the second of the pair of nodes; and using the shortest path data structure to determine shortest path distances between the landmark and each of the first and the second of the pair of nodes; and taking a difference of the shortest path distances.

[0022] The method can further include: decomposing the enriched planar embedded graph into a plurality of disjoint slabs, wherein each of the plurality of disjoint slabs corresponds to one of the one or more portions.

[0023] Processing the road network data structure to create an enriched planar embedded graph can include repeatedly applying enriching transformations to crossings and turn restrictions until none remain.

[0024] Enriching transformations can include: introducing an artificial node at a crossing and replacing each edge participating in the crossing by a pair of edges; and deleting a turn restriction.

[0025] The method can be performed such that every route in the road network corresponds to a route in the enriched planar embedded graph.

[0026] Processing the road network data structure to create an enriched planar embedded graph can include: deriving a non-highway data structure from the road network data structure by removing highways from the road network; and repeatedly applying enriching transformations to crossings and turn restrictions to the non-highway data structure until none remain.

[0027] The method can further include: deriving an augmented highway network data structure, representing an augmented highway network, from the road network data structure; and for the each portion, further: determining a length of a shortest path from the origin node to the destination node in the augmented highway network using the augmented highway network data structure; and comparing the length of the shortest path determined using the augmented highway data structure to a length of the shortest path determined from performing the A* search. [0028] Distance can be based on one or more of: travel duration, travel distance, travel time of day, travel day of week, travel date and time, travel road tolls, and travel energy efficiency.

[0029] A computer-implemented method can include: accessing a road network data structure representing a road network having road segments, intersections, crossings, and turn restrictions, wherein the road segments are represented by edges and the intersections are represented by nodes in a road network graph; processing the road network data structure to create an enriched planar embedded graph, wherein every route in the road network corresponds to a route in the enriched planar embedded graph; processing the road network data structure to create a diminished planar embedded graph, wherein every route in the diminished planar embedded graph corresponds to a route in the road network; determining a lower bound for a cost for a route from an origin to a destination based on the enriched planar embedded graph; determining an upper bound for the cost for the route from the origin to the destination based on the diminished planar embedded graph; and determining that a difference between the upper bound for the cost and the lower bound for the cost meets a predetermined threshold.

[0030] The method can further include: determining a path for the route from the origin to the destination based on the diminished planar embedded graph.

[0031] Processing the road network data structure to create an enriched planar embedded graph can include repeatedly applying enriching transformations to crossings and turn restrictions until none remain.

[0032] Processing the road network data structure to create an diminished planar embedded graph can include repeatedly applying diminishing transformations to crossings and turn restrictions until none remain.

[0033] Enriching transformations can include: introducing an artificial node at a crossing and replacing each edge participating in the crossing by a pair of edges; and deleting a turn restriction.

[0034] Diminishing transformations can include: deleting an edge involved in a crossing; and deleting an edge involved in a turn restriction. [0035] The method can be performed such that every route in the road network corresponds to a route in the enriched planar embedded graph, and every route in the diminished planar embedded graph corresponds to a route in the road network.

[0036] The method can further include: deriving a non-highway data structure from the road network data structure by removing highways from the road network. Processing the road network data structure to create an enriched planar embedded graph can include: repeatedly applying enriching transformations to crossings and turn restrictions to the non- highway data structure until none remain. Processing the road network data structure to create a diminished planar embedded graph can include: repeatedly applying diminishing transformations to crossings and turn restrictions to the non-highway data structure until none remain.

[0037] The method can further include: deriving an augmented highway network data structure, representing an augmented highway network, from the road network data structure; and for the each portion, further: determining a length of a shortest path from the origin node to the destination node in the augmented highway network using the augmented highway network data structure; and comparing the length of the shortest path determined using the augmented highway data structure to a length of the shortest path determined from performing the A* search.

[0038] Cost can be based on one or more of: travel duration, travel distance, travel time of day, travel day of week, travel date and time, travel road tolls, and travel energy efficiency.

[0039] A computer system including at least one processor and a memory can have instructions stored thereon that are executed by the at least one processor and cause the computer system to perform any of the foregoing methods.

[0040] A non-transitory computer readable medium can have instructions stored thereon that are executed by at least one processor and cause the at least one processor to perform any of the foregoing methods.

[0041] As will be appreciated by one skilled in the art, multiple aspects described in this summary can be variously combined in different operable embodiments. All such operable combinations, though they may not be explicitly set forth in the interest of efficiency, are specifically contemplated by this disclosure.

BRIEF DESCRIPTION OF THE DRAWINGS

[0042] Figure 1A shows a drawing that is not a planar embedding.

[0043] Figure 1B shows a drawing that is a planar embedding.

[0044] Figure 2 illustrates a first way to remove a nonplanarity.

[0045] Figure 3 illustrates a second way to remove a nonplanarity.

[0046] Figure 4 illustrates a "no left turn" restriction.

[0047] Figure 5 illustrates how a road network can be processed to produce two graphs, an enriched planar embedded graph and a diminished planar embedded graph.

[0048] Figure 6 shows a fragment of a graph representing a highway network.

[0049] Figure 7 illustrates a process of transforming a road network into two parts that can be handled by two different methods.

[0050] Figure 8A illustrates a planar embedded graph.

[0051] Figure 8B illustrates the same graph highlighting a first face and the nodes bounding that face.

[0052] Figure 8C illustrates the same graph highlighting a second face, an exterior face, and the nodes bounding that face.

[0053] Figure 9A shows a graph where the boundary nodes of the largest face are numbered in counterclockwise order.

[0054] Figure 9B shows the shortest-path tree rooted at L ₁ .

[0055] Figure 9C shows the shortest-path tree rooted at L ₂ .

[0056] Figures 10A-B show possible relationships between two nodes in a shortest-path tree.

[0057] Figure 11 shows a depth-first search applied to a tree that is a subgraph of a planar embedded graph. [0058] Figure 12 illustrates s is an ancestor of t w.r.t. L _a (in the left diagram) or w.r.t. L _b (in the right diagram).

[0059] Figure 13 illustrates s is CW of t w.r.t. L _a and is CCW of t w.r.t. L _b .

[0060] Figure 14 illustrates s is CCW of t w.r.t. L _a and is CW of t w.r.t. L _b .

[0061] Figure 15 illustrates the path P from w to s is interior to the [a, b] w-sector in the left diagram and is exterior in the right diagram.

[0062] Figure 16 illustrates s is CW of t w.r.t. both L _a and L _b .

[0063] Figure 17 illustrates s is CCW of t w.r.t. both L _a and L _b .

[0064] Figure 18 illustrates t is an ancestor of s w.r.t. L _a .

[0065] Figure 19 illustrates t is an ancestor of s w.r.t. L _b .

[0066] Figure 20 illustrates s is weakly CW of t w.r.t. L _a and weakly CCW of t w.r.t. L _b .

[0067] Figure 21 illustrates s is weakly CCW of t w.r.t. L _a and weakly CW of t w.r.t. L _b .

[0068] Figure 22 illustrates s is weakly CCW of t w.r.t. L _a and w.r.t. L _b .

[0069] Figure 23 illustrates s is weakly CCW of t w.r.t. L _a and w.r.t. L _b .

[0070] Figure 24 illustrates two examples of edge contraction.

[0071] Figures 25A-C illustrate three diagrams in which nodes and edges of the planar graph are represented by the dark areas.

[0072] Figure 26 illustrates how to select which decomposition to use for a given origin- destination pair (x, y).

DETAILED DESCRIPTION

[0073] In the following description, references are made to various embodiments in accordance with which the disclosed subject matter can be practiced. Some embodiments may be described using the expressions one/an/another embodiment or the like, multiple instances of which do not necessarily refer to the same embodiment. Particular features, structures or characteristics associated with such instances can be combined in any suitable manner in various embodiments unless otherwise noted. By way of example, this disclosure may set out a set or list of a number of options or possibilities for an embodiment, and in such case, this disclosure specifically contemplates all clearly feasible combinations and/or permutations of items in the set or list.

2 Use of Planar-Graph Algorithms in Addressing Optimization Problems in Road Networks

2.1 Lower Bounds and Upper Bounds

[0074] Consider a pair x, y of nodes in a road network. A lower bound on the x-to-y distance is a number d- that is less than or equal to the x-to-y distance. An upper bound on the distance is a number d ⁺ that is greater than or equal to the distance. We use lower bounds and upper bounds in two ways.

Results, With Fallback:

[0075] Suppose (as in the applications outlined in Section 1) we need a method for fast calculation of exact or approximate road-network distances. In accordance with a first embodiment, the following method can be used to estimate distance in a road network:

Given an origin-destination pair x, y,

• compute a lower bound d- on the x-to-y distance;

• compute an upper bound d ⁺ on the x-to-y distance;

• if d- and d ⁺ are not too far apart (e.g. <10%), output any number between them as the estimate of the distance;

• if they are too far apart, compute a better estimate using a method that is perhaps computationally more expensive.

[0076] This method uses a strategy common in computation: use a computationally cheap method that rarely fails to suffice, with a more expensive fallback. A method outlined in Section 5, below, is a good fallback method for distances in road networks.

[0077] Sometimes an application requires not just a number (e.g. a distance) but also a solution (e.g. a path whose length is that distance). Fortunately, a typical upper-bound method can output not just a number but a solution as well. In the case of road network distances, that means the method can return not just the x-to-y distance but an x-to-y path whose length equals that distance. In accordance with a second embodiment, the following method can be used to determine a path in a road network:

Given an origin-destination pair x, y,

• compute a lower bound d- on the x-to-y distance;

• compute an x-to-y path, and let d ⁺ be its length; • if d- and d ⁺ are not too far apart, output the path found in the previous step;

• if they are too far apart, use a method that is perhaps computationally more expensive to find a shorter path.

Guiding Search:

[0078] Lower bounds are also useful in guiding the search for a good or optimal solution. In the case of shortest paths, the well-known general method A* search method can be used to determine such lower bounds, and a specialization of this search will be discussed below.

2.2 Planar Embedded Graphs

[0079] A graph is the mathematical term for what is often called a network. A graph has nodes and edges. Each edge has two endpoints, which are nodes. Sometimes we think of an edge as being oriented from one endpoint, the edge's tail, to the other endpoint, the edge's head. A drawing of a graph on a plane or a sphere consists of (1) an assignment of distinct locations in the plane to the nodes and (2) an assignment of non-self-intersecting curves in the plane to the edges such that the curve assigned to an edge starts and ends at the locations of the edge's endpoints.

[0080] Figure 1A shows a drawing that is not a planar embedding of a graph because two curves representing edges cross. Figure 1B shows a planar embedding of the graph of Figure 1A. A drawing of a graph is called a planar embedding of the graph if the curves corresponding to two different edges do not intersect except at the locations corresponding to endpoints the edges share. A planar embedded graph is a graph together with a representation of a planar embedding of the graph. For example, one representation of an embedding could be a set of points on a plane representing nodes and for each edge a sequence of line segments connecting two points corresponding to the edge's endpoints.

[0081] There is extensive scientific literature describing algorithms for optimization problems that require their inputs to be planar embedded graphs. One lesson from this literature is that one can obtain faster and/or more accurate solutions to graph problems when the input is required to be a planar embedded graph. This disclosure provides methods to use such solutions in addressing practical problems in real road networks, and methods to apply such solutions to improve methods designed for processing road networks.

[0082] The scientific literature on planar graphs includes work on exact or approximate distance oracles for distances in planar graphs. A distance oracle typically includes: (a) a preprocessing algorithm, (b) a data structure for storing the results of the preprocessing, (c) a query algorithm for using the data stored in the data structure to support origin- destination distance queries. The following two papers provide examples of such distance oracles:

• Long, Yaowei, and Seth Pettie. "Planar distance oracles with better time-space tradeoffs." In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2517-2537. Society for Industrial and Applied Mathematics, 2021

• Le, Hung, and Christian Wulff-Nilsen. "Optimal Approximate Distance Oracle for Planar Graphs." arXiv preprint arXiv:2111.03560 (2021).

2.3 Road Networks Are Not Adequately Modeled by Planar Networks

[0083] Road networks fail in two ways to be adequately modeled by planar networks. First, road networks include crossings. Second, road networks include turn restrictions.

Removing Crossings

[0084] A crossing of edges in a drawing of a graph is called a nonplanarity. There are two ways to modify a graph so as to remove a nonplanarity.

[0085] Figure 2 illustrates a first way to remove a nonplanarity by introducing an artificial node at the location of a crossing and replacing each edge participating in the crossing by a pair of edges. We refer to this as an enriching transformation because there are routes in the transformed graph that do not correspond to routes in the original graph.

[0086] Figure 3 illustrates a second way to remove a nonplanarity by deleting one of two edges involved in a crossing. We refer to this as a diminishing transformation because some routes in the original graph do not correspond to routes in the transformed graph.

Removing Turn Restrictions

[0087] There are data sets (such as that provided by Open Street Map) that represent road networks. A road network is defined only in part by a graph. The road network also specifies turn restrictions. A turn restriction can be represented by a short sequence of road segments (usually of size two) that is not permitted to be part of a route.

[0088] Figure 4 illustrates how a pair of edges might have an endpoint in common but a legal route cannot include the edges because of a "no left turn" restriction. As with crossings, there are two ways to handle a turn restriction: first, an enriching transformation simply deletes the turn restriction, and second, a diminishing transformation deletes one of the edges involved in the turn restriction (rendering the turn restriction moot).

2.4 The Enriched Planar Embedded Graph and the Diminished Planar Embedded Graph

[0089] Figure 5 illustrates that a road network can be processed to produce two graphs, an enriched planar embedded graph and a diminished planar embedded graph.

[0090] To obtain the enriched planar embedded graph corresponding to a road network:

• repeatedly apply enriching transformations to crossings and turn restrictions until none remain.

The original assignment of lengths is simultaneously transformed into a length assignment for the enriched planar graph; when an edge is split into two edges, the lengths of those two edges are chosen so that they sum to the length of the edge being split. The enriched planar embedded graph has the property that every route in the original road network corresponds to a route in the enriched planar graph (but the converse is not necessarily true).

[0091] To obtain the diminished planar embedded graph corresponding to a road network:

• repeatedly apply diminishing transformations to crossings and turn restrictions until none remain.

The assignment of lengths to the original road network's edges and nodes induces a length assignment for the diminished planar embedded graph (every edge and node in the latter is assigned the length of the corresponding element of the original road network). The diminished planar embedded graph has the property that every route in it corresponds to a route in the original road network (but the converse is not necessarily true). [0092] The enriched planar embedded graph for a road network does not depend on the order in which enriching transformations are performed. The diminished planar embedded graph does depend on the order in which diminishing transformations are performed. In particular, there are different sets of edges of the road network whose deletion eliminates all crossings.

[0093] To select which edges to delete in constructing the diminished planar embedded graph, one can use the following method:

• Form an auxiliary graph whose vertices are the edges involved in crossing, and where there is an edge between two such vertices if the corresponding edges cross.

• Assign costs to the vertices of the auxiliary graph where the cost of a vertex is high to the extent that deleting the corresponding segment could impact shortest-path distances; for example, the cost of a vertex could reflect the geometric length of the corresponding segment and/or the frequency that it is used in a shortest path.

• Find the connected components of the auxiliary graph.

• For each connected component, use an algorithm for min-cost vertex cover to select a minimum-cost subset of vertices such that every edge in the component has at least one of its endpoints in the subset.

- If, as is often the case, the connected component is a bipartite graph then one can use any of several well-known efficient algorithms for finding an optimal solution (e.g. known algorithms for maximum-weight matching can be adapted to solve the minimum-weight vertex-cover problem).

- If not, one can instead use an approximation algorithm, such as the primal-dual method for approximation algorithms, to find a nearly optimal solution or the approximation algorithm based on iterative rounding of a linear-programming relaxation.

2.5 Deriving Road-Network Lower Bounds and Upper Bounds From Planar Embedded Graphs

[0094] Consider a pair x, y of nodes in the original road network. The shortest x-to-y path in the original road network corresponds to an x-to-y path (with the same length) in the enriched planar embedded graph. This shows that the x-to-y distance in the enriched graph is no greater than that in the original road network. For this reason, the x-to-y distance in the enriched planar embedded graph is a lower bound on the x-to-y distance in the original road network. Furthermore, any lower bound on the x-to-y distance in the enriched planar embedded graph is a lower bound on x-to-y distance in the original road network. [0095] Now consider a pair x, y of nodes in the diminished planar embedded graph. The shortest x-to-y path in the diminished graph corresponds to an x-to-y path (with the same length) in the original road network. This shows that that the x-to-y distance in the diminished graph is no less than the x-to-y distance in the original road network. For this reason, the x-to-y distance in the diminished graph is an upper bound on the x-to-y distance in the original road network. Furthermore, any upper bound on the x-to-y distance in the diminished graph is also an upper bound on the x-to-y distance in the original road network.

[0096] In accordance with a third embodiment, the following method can be used for processing a road network:

1. Compute the enriched planar embedded graph and/or the diminished planar embedded graph.

2. Preprocess the enriched planar embedded graph and/or the diminished planar embedded graph to create or compute a data structure that supports, for any origin- destination pair x, y of nodes of the road network, the following computations:

- A lower bound on the x-to-y distance in the road network (by computing a lower bound on the x-to-y distance in the enriched planar embedded graph);

- An upper bound on the x-to-y distance in the road network and/or an x-to-y path itself, (by computing an upper bound on the x-to-y distance in the diminished planar embedded graph or an x-to-y path in that graph).

[0097] In Section 4 below, we describe a method for computing a lower bound along with a method for preprocessing to support efficiently computing the lower bound. The upper bound on the x-to-y distance in the road network and/or the x-to-y path itself can be determined, for example, from a distance oracle using methods described in one of the Long and Le papers referenced above.

3 Separating Out the Highway Network

[0098] In various embodiments applying planar-graph algorithms to road networks, the highway network can be separated and processed using different methods from the rest of the road network. In some road networks, a large proportion of crossings arise from limited-access roads that make up the highway network. Often violations of planarity (road segments that cross) arise because of overpasses and tunnels that are part of the highway network. Therefore, in one embodiment, a method solves a road network problem, such as optimal path determination and/or distance, by: (1) deriving the non-highway network from the road network by removing the highways;

(2) deriving the enriched graph and the diminished graph from the non-highway network;

(3) solving the problem on the non-highway network;

(4) solving the problem constrained to solutions that interact with the highway network; and

(5) combining the solutions from the non-highway network and the highway network.

In step 1 above, the absence of some limited-access roads makes the road network closer to planar (and obviates the need to introduce artificial nodes and segments and turn restrictions). In step 2 above, the fact that the roads have limited access and the fact that such roads are much rarer than non-limited-access roads together facilitate use of graph- theoretical techniques that can be used to obtain an efficient distance oracle.

[0099] For most origin-destination pairs in real road networks, the best origin-to- destination path stays within a limited geographic region (e.g. a metropolitan area) and uses a limited-access road then it transitions only a very few times between non-limited access roads and limited-access roads, e.g. the path uses non-limited-access roads to reach a limited-access road, then traverses through the network of limited-access roads, then finally uses non-limited-access roads to reach the destination. For this reason, the steps outlined above usually find the overall best origin-to-destination path.

[0100] The benefit of this method is that, because the non-highway network has fewer crossings, the enriched and diminished graphs of the non-highway network are more similar to the non-highway network than the enriched and diminished graphs of the full road network are to the full network. There is less error, so the bounds obtained from the enriched and diminished graphs will be more accurate.

[0101] Three questions need to be answered to implement this method: (1) how to define the augmented version of the highway network, (2) how to solve the problem on this graph, and (3) how to combine that solution with the solution obtained for the non-highway network.

3.1 Finding Routes That Use Highways

[0102] A data structure can be created in a computer memory to support a fast method, for a given pair s, t of nodes, to find the minimum length of an s-to-t path that at some point passes through a highway. It will be noted that there may be some routes that (1) enter the highway network and traverse some of it, (2) leave the highway network, (3) return to the highway network, and, finally, (4) leave the highway network again. It is rare, however, that the shortest route has this property.

[0103] To simplify finding shortest routes in one embodiment, the method first augments the highway network to include roads that are not classified as highway roads but are useful in traversing between locations on highway networks. One method to find such roads is to choose a sample of locations on highway roads, and then, for each sampled location, find the shortest paths from that location to all other locations in the road network (and, symmetrically, the shortest paths to that location from all other locations in the road network). By inspecting the result of this computation, one can straightforwardly identify non-highway roads needed to get between points on highway roads. All such non-highway roads are then added to the network of highway roads to obtain the augmented highway network.

[0104] Figure 6 shows a fragment of a graph representing a highway network. An intersection node is a node of the augmented highway network where the total number of incident edges of the highway network is not two. A segment is a maximal path in the highway network none of whose internal nodes are intersection nodes. The figure shows two intersection nodes, one with one incident edge and one with three incident edges. The path from the first intersection node to the second is a segment.

[0105] We now present a method to support finding routes that enter and leave the augmented highway network only once. There are two kinds of routes that pass through the (augmented) highway network: routes that pass through intersection nodes and routes that do not. In one embodiment, the method involves constructing one data structure for each kind of route.

Intersection Data Structure

[0106] The intersection data structure can include two parts:

• a table that for each pair s, t of intersection nodes specifies the s-to-t distance in the highway network (and the corresponding shortest path), and

• a structure that specifies for each node s in the road network the nearest k intersection nodes (and the distances to/from these nodes and, implicitly, the corresponding paths).

Here k is a suitably chosen small number, e.g. 5. [0107] Using the above data structure, one can compute the shortest s-to-t path through intersection nodes as follows: for each node x among the k intersection nodes nearest to s, for each node y among the k intersection nodes nearest to t, look up the x-to-y distance in the table compute the sum dist(s,x) + dist(x, y) + dist(y,t) return the smallest sum found

Segment Data Structure

[0108] The segment data structure can specify for each node s in the road network the nearest r nodes on segments (and the distances to/from these nodes, and, implicitly, the corresponding paths). These nodes are organized according to which segment they are on, and sorted according to their appearance in the segment. Here r is a suitably chosen small number, e.g. 25.

[0109] Using the above data structure, one can compute the shortest s-to-t path through a single segment as follows: for each segment S containing nearest points to s and nearest points to t, consider the nearest points in order of their appearance in S use these nearest points to compute the shortest s-to-t path through S return the smallest number found.

3.2 Combining Highway and Non-highway Solutions

[0110] Figure 7 illustrates the process of transforming the road network into two parts that can be handled by two different methods. The enriched and diminished graphs of the non-highway network can be handled by methods that work on planar embedded graphs.

[0111] In one embodiment, to compute the x-to-y distance or approximate distance in a road network, the following method can be used:

• Compute the x-to-y distance in the non-highway graph.

• Compute the x-to-y distance in the augmented highway graph.

• Whichever of these values is smaller is the distance in the road network.

• To additionally compute the shortest x-to-y path itself, compute it from whichever yielded the smaller distance, the non-highway graph or the augmented highway graph.

Computing the exact or approximate x-to-y distance or the shortest or approximately shortest x-to-y path in the non-highway graph involves using the method outlined in Section 2.5, namely constructing the enriched graph and/or the diminished graph and then using methods designed for planar embedded graphs.

4 Obtaining Distance Lower Bounds for Planar Graphs

[0112] In this section, we describe a method, that for any nodes s and t, computes a lower bound on the distance from s to t for a planar graph (hereinafter referred to as a "distance lower bound"). We first review two previously known ideas: (1) lower bounds from landmarks and triangle inequality, and (2) multiple-source shortest paths in planar graphs. We then describe the use of multiple-source shortest paths to compute landmark lower bounds in three parts. First, we describe how any multiple-source shortest path technique can be used to compute a single landmark lower bound. Second, we describe a somewhat general method for using a multiple-source shortest path technique to find the landmark that yields the best landmark lower bound. Third, we describe a specific instantiation of this method that uses a specific multiple-source shortest path technique to very efficiently find the best landmark lower bound.

4.1 Lower Bounds From Landmarks and Triangle Inequality

[0113] The ALT method, referenced in Section 1 above, computes a shortest path via A* search using distance lower bounds derived from triangle inequalities. It will be noted that an A* search uses distance lower bounds in order to determine shortest paths. The tighter the distance lower bounds provided to the A* search, the more efficiently the search will perform. We describe here how to use triangle inequalities to derive distance lower bounds.

[0114] The '229 patent points out that the disclosed ALT method may not use all of the landmarks in a particular search; that in searching for the best path between a start vertex and an end vertex the algorithm can choose a subset of landmarks appropriate to that start vertex and end vertex. Although this can help to speed up the search, by itself it does not reduce the preprocessing time or space.

[0115] The present disclosure teaches a more sophisticated variant of the ALT method, one that is useable in certain specific circumstances that usually hold when the method is applied to a road network. We will therefore briefly describe that ALT method before explaining the variant. [0116] According to the ALT method, given nodes x and y, one way to get a lower bound on the x-to-y distance is to use a third node L, which in this context is called a landmark. We assume for simplicity of exposition that nodes are not assigned costs. The from-L lower bound is the quantity given by the formula dist(L,t) — dist(L,s) and the to-L lower bound is the quantity given by the formula dist(s,L) — dist(t, L)

These quantities are both lower bounds on the x-to-y distance. The first is called a from- landmark lower bound and the second is called a to-landmark lower bound.

[0117] An inequality can be valid and yet uninformative; ten miles is a valid lower bound on the Boston-to-Chicago distance but it is a poor lower bound because it is so far below the actual distance. Whether either of the quantities above is a good lower bound depends on the choice of the landmark L.

[0118] The '229 patent teaches selecting a small collection of nodes of the road network to be landmarks and computing and storing a table. For each selected landmark L and each node v of the road network, the table has an entry specifying dist(v, L) and dist(L,v). The number of pairs of distances is thus the number of selected landmarks times the total number of nodes in the road network. This table requires a large amount of computer memory to store. In addition, the amount of time to produce the table is similarly proportional to its size. For these reasons, because of memory to store the table and additionally because of the time required to construct the table, when using this method one must severely limit the number of landmarks selected. For example, in the scientific paper describing the ALT method, the authors write "We use ... 16 [as the number of landmarks] because is [sic] the maximum number that fits in memory for our biggest test problem." The disadvantage of selecting a small number of landmarks is that, for any given origin-destination pair (x,y), the lower bounds resulting from using the available landmarks might be poor.

[0119] The fourth embodiment improves the ALT method with: (A) a specific way of choosing the set of landmarks, (B) a method for computing a representation of the distances between these landmarks and all other vertices, (C) use of a data structure for storing these distances in a way that permits fast retrieval, and (D) a method to quickly compute the best from-landmark or to-landmark lower bound for a given origin-destination pair (s,t) . These improvements permit the use of a much larger number of landmarks while keeping the preprocessing time and space very small. The time required for the preprocessing of many landmarks is nearly proportional to the time for preprocessing a single landmark, and similarly the space required for storing the distances for these landmarks is nearly proportional to the space required for a table storing distances for a single landmark. This embodiment can be used in situations in which costs change frequently and/or storage space is limited.

4.2 Multiple-Source Shortest Paths in Planar Embedded Graphs

[0120] A set of known techniques, collectively called multiple-source shortest path (MSSP) techniques, take as input a planar embedded graph with a length assignment and a particular face ƒ (explained below) of that planar embedded graph. The nodes on the boundary of a face ƒ are called boundary nodes. The techniques preprocess the graph to create a compact data structure representation of the shortest paths and their corresponding distances from (or to) each of the boundary nodes to (or from) all nodes of the graph. One can then use the data structure to quickly find a distance between any node of the graph and a boundary node.

[0121] We propose use of boundary nodes of planar embedded graphs as landmarks for which from-L and to-L distance lower bounds can be determined using MSSP techniques. The use of such boundary nodes in association with MSSP techniques can vastly increase the number and diversity of landmarks capable of being handled by a system over the limited quantity supported by the ALT method. By increasing the number of possible landmarks, tighter, more accurate, and higher distance lower bounds can be achieved and applied to improve the performance of the A* search.

[0122] The following technical paper introduced an MSSP technique for processing a planar embedded graph to generate a representation of shortest paths from many origins:

• Philip N. Klein, "Multiple-source shortest paths in planar graphs," Proceedings of the

Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 146-155 (2005).

[0123] Other follow-on papers introduced other MSSP techniques and representations: Sergio Cabello and Erin W. Chambers, "Multiple source shortest paths in a genus g graph," Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 89-97 (2007).

• Sergio Cabello, Erin W. Chambers, and Jeff Erickson, "Multiple-source shortest paths in embedded graphs," SIAM Journal on Computing 42:4, pp. 1542-1571 (2013).

• Debarati Das, Evangelos Kipouridis, Maximilian Probst Gutenberg, and Christian Wulff- Nilsen. "A simple algorithm for multiple-source shortest paths in planar digraphs," Proceedings of the Symposium on Simplicity in Algorithms, pp. 1-11 (2022).

[0124] To understand the capabilities of these techniques, one needs to know about faces of a planar embedded graph. A face is a portion of a planar embedding (a drawing) that is made up of white space—has no nodes or edges inside or alternatively outside it— but whose boundary is delineated by nodes and edges. The nodes that delineate the boundary of a face appear in a particular order.

[0125] Figure 8A illustrates a planar embedded graph. Figure 8B illustrates the same graph highlighting a first face and the nodes bounding that face. Figure 8C illustrates the same graph highlighting a second face, an exterior face, and the nodes bounding that face.

[0126] One ingredient in the representation is the notion of a shortest-path tree. Given a graph G with a length assignment and a node r, a from-r shortest-path tree of G is the subgraph consisting of all the edges on shortest paths from r to other nodes.

[0127] Figure 9A shows a graph where the boundary nodes of the largest face are numbered in counterclockwise order. Figure 9B shows the shortest-path tree rooted at L ₁ . Figure 9C shows the shortest-path tree rooted at L ₂ .

[0128] A shortest-path tree can be represented by a table specifying, for each node v of G other than r, the last edge in the shortest r-to-v path. This table allows one to iteratively reconstruct, for any node v, the full r-to-v shortest path. The size of the representation is proportional to the size of the entire graph. Thus it is a joint representation of those paths that is more compact than an explicit representation of all those paths independently. The shortest-path tree, however, is not sufficiently compact for our purposes. Suppose that the number of boundary nodes is k. Representing the shortest-path trees rooted at all the boundary nodes would require space proportional to k times the size of the entire graph. [0129] A multiple-source shortest path technique outputs a representation that is much more compact. An MSSP technique constructs a compact representation of: the L ₁ -rooted shortest-path tree, the L ₂ -rooted shortest-path tree, the L ₃ -rooted shortest-path tree, and so on. The details of the representation can differ between different techniques.

4.3 Choosing the Landmark Index p To Use in Computing an x-to-y Distance Lower Bound

[0130] In accordance with one embodiment, we describe a method that, given a pairs,t of nodes, can compute the landmark index p that maximizes the from-L _p lower bound on dist(s,t). A symmetric method can compute the landmark index p that maximizes the to-L _p lower bound on dist(s,t).

[0131] This embodiment is distinguishable from the '229 patent, which proposes some simple heuristics to select or choose the landmark index p to use in computing a distance lower bound (as opposed to merely choosing an index p).

[0132] Let a, b be two landmark indices such that a < b. The [a,b] to-t sector is the subgraph of the input graph enclosed by (1) the shortest L _a -to-t path, (2) the shortest L _b - to-t path, and (3) the part of the boundary connecting L _b to L _a . A technique for choosing a landmark to use is as follows:

Technique: if the [a, b] to-t sector contains s, then choose a landmark with index p such that a ≤ p ≤ b.

[0133] The method described below uses this Technique to home in on a landmark to use, using a variant of binary search. The method can be generally described as finding the maximum from-landmark lower bound itself, which is all that is needed, rather than the corresponding landmark index; it is easy to modify the method to also return the landmark index. define SEARCH ([a, b],s, t):

[Assume interval [a, b] contains the index p maximizing from-L _p lower bound on dist(s,t)] if a + 1 = b then

[the interval consists of only two indices] compute the from-L _a lower bound on dist(s,t) and the from-L _b , lower bound, and return whichever is greater. else let m be the integer closest to (a + b)/2 * compute if index p maximizing the from-L _p lower bound is in [a, m] or [m, b] if in [a, m] then recursively call SEARCH([a, m], s, t) else recursively call SEARCH([m, b],s, t)

[0134] The step in the above procedure marked * determines whether a given interval (e.g. [a, m] contains the landmark index p that maximizes the from-L _p lower bound on dist(s,t). The method for implementing this step can draw upon the above Technique for choosing a landmark set forth above. A tool for implementing that method is introduced in the next section.

4.4 Topological Relationships and Numbering of Shortest-Path Trees

[0135] Figures 10A-B show possible relationships between two nodes in a shortest-path tree. Consider a shortest-path tree in a planar embedded graph such that the root r of the tree is on the boundary of the graph, let r denote the root of the tree, and consider two nodes x and y. In Figure 10A, we say x is counterclockwise (abbreviated CCW, as opposed to clockwise, abbreviated CW) of y (and y is clockwise of x) with respect to (abbreviated w.r.t.) the root r. In Figure 10B, we say x is an ancestor of y (and y is a descendant of x) with respect to the root r.

[0136] This section describes a method to assign node numberings that allow one to quickly determine the relationship of a pair of nodes. Recall (see Figures 9A-C) that the r- rooted shortest path tree of a graph is the subgraph consisting of the edges on shortest paths from r to all other nodes. There is a well-known method, depth-first search, for computing two numberings of the nodes of a rooted tree such as a shortest-path tree, a preorder numbering and a postorder numbering. Depth-first search traverses the rooted tree starting at the root.

[0137] Figure 11 shows a depth-first search applied to a tree that is a subgraph of a planar embedded graph. The left diagram shows that the children of a node v are visited in counterclockwise order. The right diagram shows the resulting preorder and postorder numbers assigned to the nodes. Each node's preorder number is on its left and the postorder number is on the right. These numbers can be used to determine the relative positions of two nodes in the tree. For example, because 7 is between 1 and 14, we can infer that the node with preorder number 7 is a descendant of the node with preorder number 1 and postorder number 14. Because 5 is less than 12, we can infer that the node with preorder number 2 and postorder number 5 is clockwise of the node with preorder number 12 and postorder number 13.

[0138] To compute preorder and postorder numberings of a tree rooted at r: initialize counter := 0 call dfs(r) where dƒs(·) is the procedure defined below: define dfs(v): v's preorder number is the current value of counter increment counter for each child w of v (i.e. each neighbor of v not already visited) call dfs(w) v's postorder number is the current value of counter

[0139] In the present context, the graph is a planar embedded graph; in embedding- aware depth-first search, each node v's children are visited in, e.g. counterclockwise order, as shown in the left diagram of Figure 11. As shown in the right diagram of Figure 11, the preorder and postorder numbers allow one to quickly determine the relative positions of two nodes in the tree. Specifically, for a rooted tree, for given nodes x and y,

• preorder(x) ≤ preorder(y) and postorder(x) ≥ postorder(y) if and only if x is an ancestor of y.

Assuming x is not an ancestor of y and y is not an ancestor of x,

• x is counterclockwise of y if preorder(x) < preorder(y), and otherwise is clockwise of y.

[0140] Note that preorder numbers alone suffice to distinguish two cases:

• preorder(x) < preorder(y) if and only if x is an ancestor of y or x is clockwise of y.

• preorder(x) > preorder(y) if and only if x is a descendant of x or x is counterclockwise of y.

In former case, we say x is weakly clockwise of y. In the latter case, we say that x is weakly counterclockwise of y . 4.5 Method to Determine if an Interval [a, b] Contains Index p Maximizing the From- L _p Lower Bound

[0141] We describe here a method to determine, for an interval [a,b] and nodes s and t, whether the interval contains an index p that maximizes the from-L _p lower bound on dist(s,t). This can be used in the step of SEARCH([a, b],s, t) that is marked *.

Implementation of the lines marked through is discussed at the end of Section 4.6, below. define CONTAINS([a, b], s, t): if s is an ancestor of t w.r.t. L _a or w.r.t. L _b , return true [Fig. 12] if s is CW of t w.r.t. L _a and is CCW of t w.r.t. L _b then return true [Fig. 13] if s is CCW of t w.r.t. L _a and is CW of t w.r.t. L _b then return false [Fig. 14] let p _a : = dist(L _a ,t) — dist (L _a , s) and let p _b : = dist(L _b ,t) — dist(L _b , s) if p _a = p _b then let w be the first node common to the L _a -to-s shortest path and the L _b -to-s shortest path

[w is necessarily an ancestor of t w.r.t. L _a ] let P be the w-to-s subpath of the L _a -to-s shortest path return true if P is interior to the [a, b] w-sector, and false otherwise [Fig. 15] if s is CW of t w.r.t. L _a and w.r.t. L _b then return true if p _a < p _b and false otherwise [Fig. 16] if s is CCW of t w.r.t. L _a and w.r.t. L _b then return true if p _b < p _a and false otherwise [Fig. 17] if t is an ancestor of s w.r.t. L _a return true if t is clockwise of s w.r.t. L _b and false otherwise [Fig. 18] if t is an ancestor of s w.r.t. L _b return true if s is clockwise of t w.r.t. L _a and false otherwise [Fig. 19]

[0142] The method above needs to determine the relationship between nodes w.r.t. L _a and L _b : clockwise of, counterclockwise of, ancestor of, descendant of. To do so, it uses preorder and postorder numberings. The method returns true if [a, b] contains an index p that maximizes the from-L _p lower bound on dist(s,t). The correctness follows from the Technique discussed earlier and from the assumption of unique shortest paths.

[0143] Figure 12 illustrates s is an ancestor of t w.r.t. L _a (in the left diagram) or w.r.t. L _b (in the right diagram). Figure 13 illustrates s is CW of t w.r.t. L _a and is CCW of t w.r.t. L _b .

Figure 14 illustrates s is CCW of t w.r.t. L _a and is CW of t w.r.t. L _b . Figure 15 illustrates the path P from w to s is interior to the [a,b] w-sector in the left diagram and is exterior in the right diagram. Figure 16 illustrates s is CW of t w.r.t. both L _a and L _b . The cases are distinguished by comparing the lower bounds given by L _a and L _b . Figure 17 illustrates s is CCW of t w.r.t. both L _a and L _b . The cases are distinguished by comparing the lower bounds given by L _a and L _b . Figure 18 illustrates t is an ancestor of s w.r.t. L _a . The cases are distinguished by the relationship of s and t w.r.t. L _b . Figure 19 illustrates t is an ancestor of s w.r.t. L _b . The cases are distinguished by the relationship of s and t w.r.t. L _a .

[0144] We now describe a variant that needs only determine for pairs of nodes whether one is weakly counterclockwise/clockwise of the other and therefore only uses preorder numberings. This allows one to achieve a smaller memory footprint. The correctness criterion for the method is slightly weaker but turns out to be sufficient for the purpose at hand, finding the best lower bound: this method is allowed to return false even if [a, b] contains an index p that maximizes the from-L _p lower bound on dist(s,t) as long as b itself such such an index. define CONTAINS([a, b], s, t): if s is weakly CW of t w.r.t. L _a and is weakly CCW of t w.r.t. L _b then return true [Fig. 20] if s is weakly CCW of t w.r.t. L _a and is weakly CW of t w.r.t. L _b then return false [Fig. 21] let p _a : = dist (L _a , t) — dist (L _a , s) and let p _b : = dist (L _b , t) — dist(L _b , s) if p _a = p _b then let w be the first node common to the L _a -to-s shortest path and the L _b -to-s shortest path

[w is necessarily an ancestor of t w.r.t. L _a ] let P be the w-to-s subpath of the L _a -to-s shortest path return true if P is interior to the [a, b] t-sector, and false otherwise if s is weakly CW of t w.r.t. L _a and w.r.t. L _b then return true if p _a < p _b and false otherwise [Fig. 22] if s is weakly CCW of t w.r.t. L _a and w.r.t. L _b then return true if p _b < p _a and false otherwise [Fig. 23]

[0145] Figure 20 illustrates s is weakly CW of t w.r.t. L _a and weakly CCW of t w.r.t. L _b . This includes the possibility that s is an ancestor of t w.r.t. L _a but even if this happens then it is still true that [a, b] contains an index p (namely, a) that maximizes the from-L _p lower bound on dist(s, t). Figure 21 illustrates s is weakly CCW of t w.r.t. L _a and weakly CW of t w.r.t. L _b . This includes the possibility that s is an ancestor of t w.r.t. L _b ; the algorithm is allowed to return false in this case. Figure 22 illustrates s is weakly CCW of t w.r.t. L _a and w.r.t. L _b . Figure 23 illustrates s is weakly CCW of t w.r.t. L _a and w.r.t. L _b . 4.6 Preprocessing to Support Efficient Choosing of a Landmark

[0146] Next we describe a method for preprocessing the planar embedded graph and cost assignment so that subsequently, for any given nodes s and t, one can efficiently determine the maximum from-landmark lower bound on dist(s, t). The method builds on a recently published technique for multiple-source shortest paths as follows:

• Debarati Das, Evangelos Kipouridis, Maximilian Probst Gutenberg, and Christian Wulff- Nilsen. "A simple algorithm for multiple-source shortest paths in planar digraphs," Proceedings of the Symposium on Simplicity in Algorithms, pp. 1-11 (2022).

This paper presents an algorithm for preprocessing the planar embedded graph and cost assignment so that subsequently, for any boundary node L and node v, one can efficiently compute dist(L, v). The paper does not, however, address landmark lower bounds.

[0147] In one embodiment, we propose a method has the same general form as the algorithm presented in the paper, but requires some additional data be stored to enable subsequent computation of landmark lower bounds. Like the previous algorithm, our method uses contraction of edges to reduce the size of graphs that must be processed.

[0148] Figure 24 illustrates two examples of edge contraction. To contract an edge in a graph, as illustrated in Figure 24, we modify the graph so that the endpoints of the edge are identified, and then remove the edge. define PREPROCESS([a, b], G): for p = a and p = b, let T _{[a ,b ],p} be the L _p -rooted shortest-path tree in G _{a ,b} compute preorder and postorder numberings for T _{[a ,b], a} and T _{[a,b], b} let T be the set of maximal rooted trees consisting of edges in both T _{[a ,b], a} and T _{[a ,b], b} where each tree includes at most one edge incident to its root (its root edge) construct a table A _{a ,b} and obtain graph G' from G and cost assignment as follows: for each tree T in T consisting of at least one edge, if the root edge is exterior to the [a, b] r-sector where r is root of T for each nonroot node v of T, add an entry to the table mapping v to r add dist (r, v) to the costs of edges incident to v in G' contract each edge of T let m : = nearest integer to (a + b)/2 recursively call PREPROCESS([a, m], G') and PREPROCESS([m,b ], G')

[0149] The results of the preprocessing method, specifically (1) the shortest-path trees and their preorder/postorder numberings and (2) the tables, are used in a slightly modified version of the method -SEARCH([a, b], s, t), in particular in the method CONTAINS([a, b], s, t) of Section 4.5 to determine if an interval [a, b] contains the index p maximizing the from-L _p lower bound on dist(s, t).

[0150] As mentioned earlier, a variant of CONTAINS([a, b], s, t) does not require postorder numberings; if one is using that variant, postorder numberings are not computed/stored. define SEARCH ([a, b],s, t):

[Assume interval [a, b] contains the index p maximizing from-L _p lower bound on dist(s, t)] if a + 1 = b then

[the interval consists of only two indices] compute the from-L _a lower bound on dist(s, t) and the from-L _b , lower bound, and return whichever is greater. else if the table A _{a ,b} maps s to a node let s' be that node let δ _s be the s'-to-s distance in T _{[a ,b], a} else let s' = s and δ _s = 0 let δ _t be the t'-to-t distance in T _{[a ,b], a} if the table A _{a ,b} maps s to a node let t' be that node let δ _t be the t'-to-t distance in T _{[a ,b], a} else let t' = t and δ _t = 0 let m be the integer closest to (a + b)/2

* call CONTAiNS([a,m],s, t): if it returns true, return δ _t — δ _S +SEARCH([a, b], s', t') else return δ _t — δ _S +SEARCH([m , b], s, t)

[0151] In the method CONTAINS, the lines through are implemented as follows: if the table A _{a ,b} has an entry that maps s to some node then return false else return true.

4.7 Cutting a Planar Embedded Graph to Create Large Faces

[0152] The methods described above for processing a planar embedded graph to produce distance lower bounds assume that one face has been selected and that the landmarks are the nodes on the boundary of that one face. Having many landmarks to choose from makes it more likely that a lower bound will be good, so it is best if that face has many boundary nodes. In this section, we describe a method for decomposing a planar embedded graph into parts each having a face with many boundary nodes. The method takes a length parameter L. The method seeks to correctly represent paths in G of length at most L. We assume for the purpose of this presentation that lengths are positive integers.

[0153] Let G denote the planar embedded graph for which distance lower bounds are desired, along with the length assignment. For each connected component of G, select one representative node. Next, compute the distance of each node of G from the nearest representative; in what follows, the distance of a node is defined to be the distance computed in this step.

[0154] The method computes two decompositions of G, Decomposition A and Decomposition B. Each decomposition consists of a collection of disjoint slabs. A slab is a section of graph consisting of nodes whose distances lie in a given interval (a.k.a. range).

[0155] Figures 25A-C illustrate three diagrams in which nodes and edges of the planar graph are represented by the dark areas. Figure 25A diagram represents the result of the distance computation. Figure 25B shows the slabs of Decomposition A. Figure 25C shows the slabs of Decomposition B.

[0156] Decomposition A consists of a slab for the interval 0 to 2L, a slab for the interval 2L to 4L, a slab for the interval 4L to 6L, a slab for the interval 6L to 8L, and so on.

[0157] Decomposition B consists of a slab for the interval — L to L, a slab for the interval L to 3L, a slab for the interval 3L to 5L, a slab for the interval 5L to 7L, a slab for the interval 7L to 9L, and so on. Because all lengths are positive, there are no nodes whose distances are negative, so the first slab could be described as being for the interval 0 to L.

[0158] After computing the distances, for each decomposition the method creates a copy of the planar graph without the edges that cross slab boundaries. The method then computes the connected components of the copy, and, for each connected component, executes the MSSP preprocessing method to compute the MSSP data structure for that connected component. For each connected component, a boundary must be selected for use in MSSP preprocessing; one can use any face of the connected component, e.g. the face with the greatest number of nodes. The boundary will typically be chosen in such a way that it coincides with a part of a slab boundary. The purpose of omitting edges in forming the copy is to create new, large boundaries in the resulting connected components.

[0159] After the preprocessing is complete, for a given origin-destination pair (x, y), the lower bound on x-to-y distance is computed as follows. Let d _x be the distance of x (as described earlier in this section) and let d _y be the distance of y. Let d = (d _x + d _y )/2. The present method uses the value of d to choose between Decomposition A and

Decomposition B.

[0160] Figure 26 illustrates how to select which decomposition to use for a given origin- destination pair (x, y). Let d = (d _x + d _y )/2 where d _x is the distance of x and d _y is the distance of y. Each slab for each decomposition has a "middle part" (shown in gray), and the middle parts for Decomposition A do not overlap with the middle parts for

Decomposition B. If d lies in the middle part of a slab of Decomposition A then choose

Decomposition A and otherwise use Decomposition B. The method computes the quantity d mod 2L. If this quantity is between L/2 and 3L/2 then use Decomposition A. If it is less than L/2 or greater than 3L/2 then use Decomposition B.

[0161] As shown in Figure 26, each slab of Decomposition A has a middle part; the nodes at distances L/2 through 2L/2, the nodes at distances 5L/2 through 7L/2, and so on. Each slab of Decomposition B also has a middle part: the nodes at distances —L/2 through L/2, the nodes at distances 3L/2 through 5L/2, and so on. The method chooses the decomposition, A or B, such that d is within the middle part of some slab of the chosen decomposition.

[0162] More precisely, as illustrated in Figure 26, the method computes the quantity d mod 2L (the remainder when d is divided by 2L) and then chooses Decomposition A if the quantity is between L/2 and 3L/2, and chooses Decomposition B otherwise. The reason for this choice is as follows: If the shortest x-to-y path and the shortest y-to-x path have length less than L then these paths lie in a common connected component of the planar graph copy created for the chosen decomposition; therefore the MSSP data structure for that connected component enables computation of a lower bound on the x-to-y distance. 4.8 Computing Landmark Lower Bounds in a Planar Embedded Graph

[0163] In an alternative embodiment, a method for computing distance lower bounds in a planar embedded graph includes two parts. The first part preprocesses the planar graph to prepare for subsequently computing landmark lower bounds as follows:

1. Select a face ƒ of the planar embedded graph.

2. Let L ₁ , L ₂ , ... , L _k be the nodes on the boundary of face ƒ, in counterclockwise order. Designate these nodes as landmark nodes.

3. Execute an MSSP technique as described in Section 4.2 to construct a data structure that supports queries that, given the index p of a landmark and given a node w, returns the w- to-L _p distance.

4. Execute an MSSP technique to construct a data structure that supports queries that, given the index p of a landmark and given a node w, returns the L _p -to-w distance.

[0164] The second part is executed whenever one needs a distance lower bound. Here is the method for computing a from-L _p lower bound:

Given nodes x and y and given the index p of a landmark node, to compute a lower bound on x-to-y distance:

1. Use the persistent data structure of Step 3 to compute the x-to-L _p distance and the y- to-L _p distance.

2. Use the numbers computed in the previous step to calculate x-to-L _p distance minus y- to-L _p distance.

And here is the method for computing a to-L _p lower bound:

Given nodes x and y and given the index p of a landmark node, to compute the from-L _p lower bound on x-to-y distance:

3. Use the persistent data structure of Step 4, above, to compute the L _p -to-x distance and the L„-to-y distance.

4. Use the numbers computed in the previous step to calculate L _p -to-y distance minus L _p - to-x distance.

5. Return the maximum of the numbers computed in Steps 2 and 4.

[0165] One can optionally use just to-L _p lower bounds (in which case Step 4 of the first preprocessing part can be omitted) or just from-L _p lower bounds (in which case Step 3 of the first preprocessing part can be omitted), or one can use from-L _p and to-L _p lower bounds (with different values of the landmark index p) and return the maximum of the two lower bounds thereby computed. 5 Using Distance Lower Bounds in A* Search

[0166] In accordance with the fourth embodiment referenced above in Section 4.1, the ALT method is applied with certain modifications to compute a shortest x-to-y path for given nodes x and y via A* search using distance lower bounds derived from triangle inequalities. The modifications to the ALT method include the following:

• According to the ALT method, a "small set" of landmarks is selected, whereas in the present embodiment the set of landmarks is large.

• According to the ALT method, distances from/to landmarks to/from other nodes are stored in a large table, whereas in the present embodiment a MSSP data structure is used to represent these distances compactly.

• The ALT method includes techniques for selecting the set of landmarks to use, including "random method", "farthest landmark selection algorithm", and "planar landmark selection method" along with techniques to further trim the size of the landmark set while preserving diversity. These considerations are not relevant, since in the present embodiment, the number of landmarks can be large without negatively impacting efficiency, as long as the landmarks all lie on the boundary of a face.

• This embodiment includes a method that, given nodes x and y, computes the landmark L that, among all landmarks, will give the best from-landmark lower bound and a straightforward modification of the method also computes landmark L that, among all landmarks, will give the best to-landmark lower bound. The method can be executed at each iteration of A*.

[0167] Note that one of the approaches of using A* search is bidirectional search; this is described in detail in the '229 patent and the related technical publication. In this case, the search proceeds from s towards t and simultaneously proceeds backwards through the network from t to s.

6 Computer Implementation

[0168] Components of the embodiments disclosed herein, which may be referred to as methods, processes, applications, programs, modules, engines, functions or the like, can be implemented by configuring one or more computers or computer systems using special purpose software embodied as instructions on a non-transitory computer readable medium. The one or more computers or computer systems can be or include one or more standalone, client and/or server computers, which can be optionally networked through wired and/or wireless networks as a networked computer system.

[0169] The special purpose software can include one or more instances thereof, each of which can include, for example, one or more of client software, server software, desktop application software, app software, database software, operating system software, and driver software. Client software can be configured to operate a system as a client that sends requests for and receives information from one or more servers and/or databases. Server software can be configured to operate a system as one or more servers that receive requests for and send information to one or more clients. Desktop application software and/or app software can operate a desktop application or app on desktop and/or portable computers. Database software can be configured to operate one or more databases on a system to store data and/or information and respond to requests by client software to retrieve, store, and/or update data. Operating system software and driver software can be configured to provide an operating system as a platform and/or drivers as interfaces to hardware or processes for use by other software of a computer or computer system. By way of example, any data created, used or operated upon by the embodiments disclosed herein can be stored in, accessed from, and/or modified in a database operating on a computer system.

[0170] Figure 27 illustrates a general computer architecture 2700 that can be appropriately configured to implement components disclosed in accordance with various embodiments. The computing architecture 2700 can include various common computing elements, such as a computer 2701, a network 2718, and one or more remote computers 2730. The embodiments disclosed herein, however, are not limited to implementation by the general computing architecture 2700.

[0171] Referring to Figure 27, the computer 2701 can be any of a variety of general purpose computers such as, for example, a server, a desktop computer, a laptop computer, a tablet computer or a mobile computing device. The computer 2701 can include a processing unit 2702, a system memory 2704 and a system bus 2706. [0172] The processing unit 2702 can be or include one or more of any of various commercially available computer processors, which can each include one or more processing cores that can operate independently of each other. Additional co-processing units, such as a graphics processing unit 2703, also can be present in the computer.

[0173] The system memory 2704 can include volatile devices, such as dynamic random access memory (DRAM) or other random access memory devices. The system memory 2704 can also or alternatively include non-volatile devices, such as a read-only memory or flash memory.

[0174] The computer 2701 can include local non-volatile secondary storage 2708 such as a disk drive, solid state disk, or removable memory card. The local storage 2708 can include one or more removable and/or non-removable storage units. The local storage 2708 can be used to store an operating system that initiates and manages various applications that execute on the computer. The local storage 2708 can also be used to store special purpose software configured to implement the components of the embodiments disclosed herein and that can be executed as one or more applications under the operating system.

[0175] The computer 2701 can also include communication device(s) 2712 through which the computer communicates with other devices, such as one or more remote computers 2730, over wired and/or wireless computer networks 2718. Communications device(s) 2712 can include, for example, a network interface for communicating data over a wired computer network. The communication device(s) 2712 can include, for example, one or more radio transmitters for communications over Wi-Fi, Bluetooth, and/or mobile telephone networks.

[0176] The computer 2701 can also access network storage 2720 through the computer network 2718. The network storage can include, for example, a network attached storage device located on a local network, or cloud-based storage hosted at one or more remote data centers. The operating system and/or special purpose software can alternatively be stored in the network storage 2720.

[0177] The computer 2701 can have various input device(s) 2714 such as a keyboard, mouse, touchscreen, camera, microphone, accelerometer, thermometer, magnetometer, or any other sensor. Output device(s) 2716 such as a display, speakers, printer, or eccentric rotating mass vibration motor can also be included.

[0178] The various storage 2708, communication device(s) 2712, output devices 2716 and input devices 2714 can be integrated within a housing of the computer, or can be connected through various input/output interface devices on the computer, in which case the reference numbers 2708, 2712, 2714 and 2716 can indicate either the interface for connection to a device or the device itself as the case may be.

[0179] Any of the foregoing aspects may be embodied in one or more instances as a computer system, as a process performed by such a computer system, as any individual component of such a computer system, or as an article of manufacture including computer storage in which computer program instructions are stored and which, when processed by one or more computers, configure the one or more computers to provide such a computer system or any individual component of such a computer system. A server, computer server, a host or a client device can each be embodied as a computer or a computer system. A computer system may be practiced in distributed computing environments where operations are performed by multiple computers that are linked through a communications network. In a distributed computing environment, computer programs can be located in both local and remote computer storage media.

[0180] Each component of a computer system such as described herein, and which operates on one or more computers, can be implemented using the one or more processing units of the computer and one or more computer programs processed by the one or more processing units. A computer program includes computer-executable instructions and/or computer-interpreted instructions, such as program modules, which instructions are processed by one or more processing units in the computer. Generally, such instructions define routines, programs, objects, components, data structures, and so on, that, when processed by a processing unit, instruct the processing unit to perform operations on data or configure the processor or computer to implement various components or data structures.

[0181] Components of the embodiments disclosed herein, which may be referred to as modules, engines, processes, functions or the like, can be implemented in hardware, such as by using special purpose hardware logic components, by configuring general purpose computing resources using special purpose software, or by a combination of special purpose hardware and configured general purpose computing resources. Illustrative types of hardware logic components that can be used include, for example, Field-programmable Gate Arrays (FPGAs), Application-specific Integrated Circuits (ASICs), Application-specific Standard Products (ASSPs), System-on-a-chip systems (SOCs), and Complex Programmable Logic Devices (CPLDs).

7 Conclusion

[0182] Although the subject matter has been described in terms of certain embodiments, other embodiments that may or may not provide various features and aspects set forth herein shall be understood to be contemplated by this disclosure. The specific embodiments set forth herein are disclosed as examples only, and the scope of the patented subject matter is defined by the claims that follow.

[0183] In the claims, the terms "based upon" and "based on" shall include situations in which a factor is taken into account directly and/or indirectly, and possibly in conjunction with other factors, in producing a result or effect. In the claims, a portion shall include greater than none and up to the whole of a thing. In method claims, any reference characters are used for convenience of description only, and do not indicate a particular order for performing a method.