Methodology for Conflating Large-Scale Roadway Networks

Abstract

Transportation agencies are increasingly integrating third-party traffic data into their core business function areas such as system performance monitoring, project programming, traffic incident management, and safety analysis. However, linking private-sector data with agency asset inventory data has been a major challenge because the networks typically have different referencing systems, segmentation schemes, and representations of travel directions. This paper presents an effective conflation algorithm that associates spatial features between large-scale road networks. Instead of breaking lines into smaller pieces, which is a common technique in transportation applications, we use an intersection-based approach that leverages the inherent topological similarities between networks. The underlying uncertainty and imprecision in network geometries and road names are addressed through application of a fuzzy logic inference technique. We then implement an effective mechanism to handle differences in representations of divided roadways and travel directions in the two networks. The algorithm was tested on Kentucky statewide roadway networks and achieved a matching accuracy of over 99%. This approach has been successfully applied by the Kentucky Transportation Cabinet in its project identification and prioritization process.

Keywords

data and data science geographic information science geographic information systems national and state transportation data and information systems geospatial data urban transportation data and information systems probe vehicle data

Recent technological advancements have greatly increased the availability of transportation data, including probe vehicle speeds, travel time, origin–destination matrices, pedestrian and bike activities, and incident alerts. These data, which provide insights into a wide range of travel characteristics, are processed by third-party data providers and made available to transportation agencies as a cost-effective alternative which meet their data needs. Many state departments of transportation (DOT) and metropolitan planning organizations (MPO) have used such data for various business cases, such as real-time traffic management, travel model improvement, safety analysis, and performance management and reporting ( 1 ).

Although private-sector data capture a wide range of information, they lack many critical attributes required for transportation applications (e.g., traffic volume), which must be obtained through agency-maintained databases such as the Highway Performance Monitoring System (HPMS) ( 2 ). With private-sector data and agency-maintained data often being tied to geospatial networks with different referencing systems and segmentation schemes, a direct join is impossible. The challenge is compounded by the need to match directions that are handled differently in these two networks, as integrating transportation data (e.g., speeds, volumes, crashes) by directions is a prerequisite for many transportation applications.

There are other issues associated with conflation that state agencies are struggling with. First, different state agencies and vendors use different networks and the same agency may have different network versions. For example, at the Pennsylvania DOT, interstate segments are always half a mile long and do not consider ramps, while non-interstate roadways break at major landmarks such as intersections and bridges with approximately half a mile length ( 3 ). The Ohio DOT has two Linear Referencing Systems (LRS) (i.e., county-divided and statewide) for their 121,000 centerline mile roadways ( 3 ). At the vendor side, there are INRIX XD, HERE NAVSTREETS, TomTom Multinet, among others, with different segmentations and attributes. Meanwhile, both state and vendor networks are periodically updated, which means the conflated network will have to be updated as well. In addition, developing a conflation process requires extensive Geographic Information System (GIS) and programming knowledge, which can be particularly challenging for agencies with limited IT resources and assets. Many agencies have to outsource the conflation task to consultants, universities, or vendors ( 1 ).

A limited number of transportation-focused publications have proposed automated conflation processes, and none explicitly discuss how to match directions ( 2 , 4 –7). For instance, Lomax et al. ( 4 ) was among the first to match the HPMS and Traffic Message Channel (TMC) based private-sector network. To align segmentations of both networks, they first used HPMS link end points to break the TMC network and then obtained candidate TMCs intersecting with or falling within the buffer created around each HPMS line feature. In a recent study, Kaushik et al. ( 7 ) tried to conflate the HPMS with the TomTom Multinet network by breaking down long HPMS links into shorter ones and then applying a scoring process to determine the matching HPMS link for each Multinet link. In general, existing methods have been designed for arterial networks, such as the National Highway Network. Their performance significantly deteriorates when applied to locations with high network density.

In other fields, such as cartography and photogrammetry, several studies have been conducted to address the conflation of heterogeneous geospatial data ( 8 ). With respect to the main geometric features used in the conflation process, these studies have developed node-based methods ( 9 – 13 ), line-based methods ( 14 – 18 ), and polygon or area-based methods ( 19 , 20 ). Various techniques have been applied to identify matching features, such as growing buffer ( 14 ), probabilistic relaxation ( 15 ), network flow optimization ( 18 ), and a delimited stroke-oriented approach ( 21 ). Yet those studies mainly aimed to find the correspondence of geospatial features in undirected networks. As such, adapting them for directed roadway networks is difficult.

In this paper, we present an effective algorithm for conflating large-scale directed networks from a state transportation agency and private sector. Instead of splitting line features into smaller pieces, as commonly done in transportation studies, we use an intersection-based approach that takes advantage of inherent topological similarities between networks while retaining the geometry of individual links. Additionally, such an approach lets us effectively incorporate link direction information into the conflation process. Our algorithm encompasses three essential steps: (1) preprocessing that sets up the networks for conflation; (2) matching intersections based on geometrical and non-spatial attributes and a fuzzy logic inference technique; and (3) matching links and directions. A tailored mechanism handles differences in representations of divided and undivided highways as well as travel directions. The algorithm only uses common attributes found in both highway inventory and private-sector networks, and can thus be quickly adopted by transportation agencies.

The rest of the paper is organized as follows. In the next section we introduce and compare the two networks used to develop the conflation algorithm. One network is from a public agency (Kentucky Transportation Cabinet) and the other is from a private vendor (HERE Technologies). From here, we describe development of the algorithm, followed by the presentation, evaluation, and discussion of conflation results. The last section concludes the paper.

Description of Networks and Problems

We used two highway networks covering the entire state of Kentucky to develop and demonstrate the conflation algorithm. The first is the All Roads Network of Linear-Referenced Data from the Kentucky Highway Information System. It is maintained by the Kentucky Transportation Cabinet. The All Roads Network served as the target network and is referred to as Network A throughout the rest of this paper. The second is the HERE Technologies proprietary street network, which has attached probe speed data. This network, referred to as Network B, served as the matching network.

Network A covers all the public roads across Kentucky and has 169,816 directional miles. It contains attributes that support various of the Kentucky Transportation Cabinet’s core functions. The network is generated following LRS standards, which characterize the network elements, such as points and lines, as a distance from a specific point along a linear feature. Each line feature has an LRS ID consisting of 17 characters, which are unique to a road and a county in Kentucky, as well as beginning and ending milepoints that indicate location and length. The direction of a divided road section is either cardinal, along which milepoints increase in value, or non-cardinal along which milepoints decrease in value. For undivided roads, Network A uses one line to represent both directions with a cardinal LRS coding and an indication of two-way operation.

Network B, on the other hand, references each line feature with a unique Link ID. Directional coding of lines is contingent on the coordinates of two end nodes. The reference node is the end node with the lower latitude, or longitude if the latitudes are the same. The direction is coded as F if the line emanates from the reference node, and T if it is directed toward the reference node. One line is used to represent an undivided road with the direction denoted as Bi. However, speed data are attached to a unique Link ID and travel direction (T or F) combination.

Spatially, Networks A and B share very similar level of details for public roads, but disparities are apparent at some locations. Figure 1a illustrates the coverage difference as there are links not included in either network. Figure 1b highlights the different segmentation schemes, making it challenging to determine the associations for individual links. Figure 1c captures an example of geometric inconsistencies at an interchange, with ramp merging and diverging locations in two networks being far apart. Figure 1d shows how a segment may be coded differently in the two networks based on whether it is divided (using two lines) or undivided (represented by a single line). These create additional complications in matching travel directions.

Figure 1.

Discrepancies between Networks A and B: (a) coverage; (b) segmentation scheme; (c) geometry; and (d) divided versus undivided.

An Intersection-Based Conflation Algorithm

We present an algorithm that overcomes the challenges described above and effectively associates links and directions between Networks A and B. We designed it to take advantage of an intersection being almost always represented as a node in both networks. The algorithm first identifies the matching nodes for each intersection and then associates the link(s) and directions for each leg of the intersection. Figure 2 illustrates the algorithm’s overall process.

Figure 2.

Flowchart of the conflation algorithm.

Preprocessing

During preprocessing, each road network in the shapefile is converted into a directed graph with a node set and link set consisting of directed links with ordered pairs of nodes. During the conversion, the number of links connected to each node (i.e., node degree) is recorded to identify nodes where at least three links intersect. These nodes are labeled intersections. The direction of each link is based on the milepoints of two end nodes if it is in Network A or latitude/longitude coordinates if it is in Network B. Next, based on ordered node pairs and associated node degrees, the links bound by two intersections are chained into a link sequence.

Figure 3 provides a conceptual example. Two Network A links $l_{1}^{A}$ and $l_{2}^{A}$ are bound by intersections $n_{1}^{A}$ and $n_{3}^{A}$ . Because the milepoints of nodes $n_{1}^{A}$ , $n_{2}^{A}$ , and $n_{3}^{A}$ increase along the travel direction, both links are in the cardinal direction. Accordingly, we can form an A link sequence (i.e., $s^{A} : (l_{1}^{A}, l_{2}^{A})$ ). Similarly, there are three Network B links $l_{1}^{B}, l_{2}^{B}$ , and $l_{3}^{B}$ between two intersections $n_{1}^{B}$ and $n_{4}^{B}$ . Based on the latitudes of $n_{1}^{B}$ , $n_{2}^{B}$ , $n_{3}^{B}$ , and $n_{4}^{B}$ , we know the three links are, respectively, in the T, F, and T direction and have a B link sequence $s^{B} : (l_{1}^{B}, l_{2}^{B}, l_{3}^{B})$ .

Figure 3.

Conceptual example of preprocessing step.

Intersection Matching

Next, the B intersection that best matches each A intersection is identified. The basic presumption is that each network most likely has a node representing an intersection of the road network. For example, in Figure 3, nodes $n_{1}^{A} and n_{1}^{B}$ represent the same intersection in Networks A and B, respectively. Similarly, node $n_{3}^{A}$ and $n_{4}^{B}$ refer to the same intersection. Factors considered when identifying the best match include spatial proximity, node degree, and road name similarity for each link connected to the node. The following sections explain this procedure.

Select Candidate Intersections from Network B

A common method of identifying candidate intersections is to select intersections within a certain distance of the subject intersection. But this often captures irrelevant intersections when a roadway network is dense. For example, as shown in Figure 4a, among three intersections (in Network B) within 400 ft radius of the A intersection, node 2 from the opposing direction of the highway is closer to node A than node 1, which is the correct match for node A. Therefore, using spatial proximity as the sole matching criterion is insufficient.

Figure 4.

Obtain candidate intersections: (a) basing on distance captures irrelevant intersections; and (b) basing on nearby link sequences leads to better matches.

We designed a more sophisticated approach based on the observation that line features are spatially proximate in the two networks. Specifically, we first find all A link sequences connected to the A intersection. In the example shown in Figure 4a, these are the two link sequences on the northbound mainline (partially displayed) and one off-ramp link sequence, which is shaded red. Along each link sequence, we then create at least nine equally spaced shape points and use them to find the nearest B link sequences that are within a radius of 100 ft. We chose a threshold of 100 ft, after testing several values, to balance computational efficiency and flexibility in handling geometric discrepancies between the two networks. Accordingly, the two mainline and one off-ramp link sequences in Network B are identified as in Figure 4b as the best matches for those three link sequences in Network A. The end nodes of these identified B link sequences (i.e., nodes 1 to 4 in Figure 4b) are labeled as the candidate intersections in Network B to the subject A intersection. Each intersection has two attributes—including coordinate and street name from the corresponding line sequence—which are used in next step.

Define Intersection Matching Criteria

Intersection proximity and road name similarity are used to evaluate candidate intersections and determine the best match. Proximity measures the distance between a candidate B intersection and the subject A intersection. Since the networks are projected into a Kentucky State Plane coordinate system, the Euclidean distance is calculated as follows.

d_{i j} = \sqrt{{(x_{i}^{A} - x_{j}^{B})}^{2} + {(y_{i}^{A} - y_{j}^{B})}^{2}}

(1)

where $d_{ij}$ is the distance between intersection $n_{i}^{A}$ and $n_{j}^{B}$ , $x_{i}^{A}$ and $y_{i}^{A}$ are the latitude and longitude of $n_{i}^{A}$ , $x_{j}^{B}$ and $y_{j}^{B}$ are the latitude and longitude of $n_{j}^{B}$ .

Because road names are sometimes coded differently (e.g., 1st Street versus First Street), a string similarity indicator based on the Ratcliff/Obershelp pattern matching algorithm ( 22 ) is used to measure road name similarity (Equation 2).

ρ_{ij} = \frac{2 * k}{| r_{i}^{A} | + | r_{j}^{B} |}

(2)

where

$ρ_{ij}$ denotes the road name similarity,

$| r_{i}^{A} |$ and $| r_{j}^{B} |$ are lengths of road name strings, $r_{i}^{A}$ and $r_{j}^{B}$ , respectively, and

$k$ is the number of matching characters.

When determining $k$ , the Ratcliff/Obershelp algorithm starts by finding the longest common subsequence, which is called anchor, and then recursively identifies the matching subsequence in the remaining parts on either side of the anchor. The process is repeated until the algorithm examines all characters of the road names. The similarity measure, $ρ_{ij},$ ranges from 0 to 1, with 0 indicating that the two names are completely different and 1 denoting they are identical.

With the matching criteria defined, two difficulties must be overcome to combine them into a holistic measure for ranking candidate intersections: 1) geometries and road names are inconsistent between the two networks, resulting in uncertainty and imprecision in the obtained measures; and 2) two measures have different scales with distance ranging from 0 to hundreds of feet while name similarity is measured on a scale of 0 to 1—thus combining them using a representative linear function is challenging.

Determine the Best Match

To deal with above difficulties, a fuzzy logic inference technique is employed to generate an overall matching score using the intersection distance and road name similarity as inputs. Fuzzy logic is effective in dealing with uncertain and imprecise conditions ( 23 ). Input variables with different ranges and scales can also be effectively combined during the inference process. Its utility has been demonstrated in previous transportation engineering studies, including for detecting traffic incidents ( 24 ), developing congestion measures ( 25 ), mapping GPS for vehicle navigation ( 26 ), analyzing bottleneck severity ( 27 ), and crash location mapping ( 28 ).

To run the fuzzy logic inference system, input (i.e., intersection distance and road name similarity) and output (i.e., intersection matching score) variables must be converted into fuzzy variables, a process called fuzzification. This is achieved by defining a membership function that maps an input value to a number in the interval $[0, 1]$ , with the number indicating the degree of belonging of the input to the class of interest. The classes are defined with natural language terms directly related to human thinking, such as “large distance” or “highly similar.” Therefore, a crisp value can be mapped to more than one class but with varying degrees of membership.

Determining an appropriate number of classes and representative membership functions can be subjective and sometimes arbitrary as well as highly dependent on specific applications. Empirical assessment is often conducted to account for the characteristics of a particular application ( 28 ). We fine-tuned the fuzzy logic inference system’s parameters by randomly selecting 500 intersections from Network A and manually matching them with their counterparts in Network B. The locations of those intersections are shown in Figure 5.

Figure 5.

Locations of randomly selected intersections.

Our evaluation found that three classes are sufficient for both input and output variables in this study as they achieve a good balance between efficiency and accuracy. Given the size of the networks being processed, for membership functions we selected triangular and trapezoidal functions for their simplicity. Imprialou et al. ( 28 ) showed that function forms have limited impact on the results. The boundaries of membership functions are determined through trial and error until the performance is satisfactory for sampled locations. The final membership functions implemented in the study are shown in Figure 6. Using Figure 6a as an example, an intersection distance of 75 ft would not be considered as small since it exceeds 40 ft, which is the upper bound of the Small class. The distance would be considered fairly medium with a membership degree of 0.5 and slightly large with a membership degree of 0.11.

Figure 6.

Implemented membership functions for determining matching intersection: (a) intersection distance; (b) road name similarity; and (c) intersection matching score.

After fuzzification, the linguistic representations of intersection distance and road name similarity are combined through a fuzzy inferencing engine, which produces a fuzzy set for the output measure (i.e., intersection matching score). The inferencing engine functions on top of a predefined set of fuzzy rules associating the input classes to the output classes. Table 1 lists all possible inferencing rules based on the previously defined membership functions.

Table 1.

Fuzzy Inference Rules for Intersection Matching

ID	Rule
1	IF (Distance is Small) and (Road Name Similarity is High) THEN (Intersection Matching Score is High)
2	IF (Distance is Small) and (Road Name Similarity is Medium) THEN (Intersection Matching Score is High)
3	IF (Distance is Small) and (Road Name Similarity is Low) THEN (Intersection Matching Score is Medium)
4	IF (Distance is Medium) and (Road Name Similarity is High) THEN (Intersection Matching Score is High)
5	IF (Distance is Medium) and (Road Name Similarity is Medium) THEN (Intersection Matching Score is Medium)
6	IF (Distance is Medium) and (Road Name Similarity is Low) THEN (Intersection Matching Score is Low)
7	IF (Distance is Large) and (Road Name Similarity is High) THEN (Intersection Matching Score is Medium)
8	IF (Distance is Large) and (Road Name Similarity is Medium) THEN (Intersection Matching Score is Low)
9	IF (Distance is Large) and (Road Name Similarity is Low) THEN (Intersection Matching Score is Low)

The last step of the fuzzy inference system is defuzzifying the output classes and associated membership degrees into a crisp value, which indicates the overall quality of the matching. There are several defuzzification methods available, including centroid of the area, mean of maximum, max-membership principal, weighted average, and bisector of the area. Their suitability varies by application. Here, the centroid of the area method is chosen as it is the technique most commonly used in transportation studies and performs well in preliminary evaluation.

By using the fuzzy logic inference technique, each candidate intersection receives a matching score. The one with the highest matching score is chosen as the matching intersection. If there is a tie in the highest score among multiple candidate intersections, the one with the shortest distance to the subject A intersection is chosen.

Link and Direction Matching

Once the matching intersections have been identified, the next step is to determine the correspondence of link sequences and then their comprising links and associated travel directions. Discrepancies in localized topologies between the two networks can lead to different sequence matching scenarios (Figure 7).

Figure 7.

Link sequence matching scenarios: (a) one-to-one matching; (b) one-to-many matching; (c) many-to-one matching between undivided roads in both networks; (d) two directions of divided A road matched to undivided B road; and (e) undivided A road matched to two directions of divided B road.

Scenario (a) represents the majority of matching cases where we can directly find the corresponding A and B link sequences between two matched intersections. Scenarios (b) and (c) represent cases where there is no direct correspondence of existing link sequences in two networks as a result of an intersecting roadway being present in one network but not the other. To deal with this, the sequences split by the intersecting roadway are tied into a new link sequence, which is then matched to the one from the other network. Because scenarios (a), (b), and (c) involve undivided roadways only, the association of the opposite travel direction can be obtained using the same link IDs but reversing their direction codes.

Scenarios (d) and (e) result from different coding of divided and undivided highways in two networks. In scenario (d), two A link sequences in separate directions are both matched to the same B link sequence. Since the B link sequence is two-way, the corresponding B links with correct direction can be found for the respective A link sequence by reversing the beginning and end nodes.

Among all scenarios, Scenario (e) presents the most difficult complication, where the roadway is coded as undivided in Network A but divided in Network B. Therefore, two link sequences represent separate directions in Network B. Under this condition, the intersection matching process only pinpoints the end nodes of the B link sequence that are closer to the A link sequence. As a result, only one directional A link sequence is matched with the closer B link sequence while the other direction of the A link sequence has no matching counterpart as the more distant B link sequence is not included.

To address the above issue, a special procedure is applied to locate the B links within a certain buffer of the subject A link sequence and eliminate the B links that have already been matched so that only the links in the missing direction remain in the candidate list. Road name similarity and the angle between candidate B link and subject A link sequence are used to exclude irrelevant links that have been included because of their closeness. The threshold for road name similarity is set at 0.9 and the angle less than 30°, following the suggestion in Walter and Fritsch ( 14 ). The sequence of remaining links is then determined based on the obtained milepoints of their end nodes.

Based on the matched link sequences, the correspondences of links and associated directions are determined. Since A is the target network and B is the matching network, the B link length is adjusted proportionately to match the total length of A links. The implementation procedure is as follows.

Link and Direction Matching Procedure:
Input: Matching link sequences $s^{A}$ and $s^{B}$ of networks A and B. 1: Initialization 2: $f = {l e n}_{s}^{A} / {l e n}_{s}^{B}$ , where $f$ is the conversion factor to proportionately adjust B links so that their total length is equal to the total length of A links 3: Define $i d x$ as the index of a link in the sequence 4: for $i d x^{A}$ in $s^{A}$ do 5: if ${d i r}_{i d x}^{A}$ = “Cardinal” then 6: directional indicator $α$ = 1 7: $o p p o s i t e_di {r^{A}}_{i d x}$ = “Non-cardinal” 8: else 9: directional indicator $α$ = −1 10: $o p p o s i t e_di {r^{A}}_{i d x}$ = “Cardinal” 11: ${l e n}_{b}^{A} \leftarrow$ cumulative length from the first A link to the $(i d x^{A} - 1)$ th link in $s^{A}$ 12: ${l e n}_{e}^{A} \leftarrow$ cumulative length from the first A link to the $i d x^{A}$ th link in $s^{A}$ 13: for $i d x^{B}$ in $s^{B}$ do 14: ${l e n}_{b}^{B} \leftarrow$ cumulative length from the first B link to the $(i d x^{B} - 1)$ th link in $s^{B}$ 15: if ${l e n}_{b}^{B} \times f < {l e n}_{b}^{A}$ then 16: continue 17: else 18: break 19: Get the index of B link touching the beginning node of the $i d x^{A}$ th A link: ${s e q}_{b}^{B}$ = $i d x^{B}$ 20: for $i d x^{B}$ in $s^{B}$ do 21: ${l e n}_{e}^{B} \leftarrow$ cumulative length from the first B link to th $i d x^{B}$ th link in $s^{B}$ 22: if ${l e n}_{e}^{B} \times f < {l e n}_{e}^{A}$ then 23: continue 24: else 25: break 26: Get the index of B link touching the ending node of the $i d x^{A}$ th A link: ${s e q}_{e}^{B}$ = $i d x^{B}$ 27: $l e n_{p a r t} = {l e n}_{b}^{B} \times f - {l e n}_{b}^{A}$ 27: for $i d x^{B}$ from ${s e q}_{b}^{B}$ to ${s e q}_{e}^{B}$ do 28: ${m p}_{b}^{B}$ = ${m p}_{b}^{A} + α \times l e n_{p a r t} + α \times f \times \sum_{i = {s e q}_{b}^{B} + 1}^{i d x^{B}} {l e n}_{i}^{B}$ 29: ${m p}_{e}^{B}$ = ${m p}_{b}^{A} + α \times l e n_{p a r t} + α \times f \times \sum_{i = {s e q}_{b}^{B} + 1}^{i d x^{B + 1}} {l e n}_{i}^{B}$ 30: if ${d i r}_{i d x}^{B}$ = “F” then 31: $o p p o s i t e_di {r^{B}}_{i d x}$ = “T” 32: else 33: $o p p o s i t e_di {r^{B}}_{i d x}$ = “F” 34: match $[{s e q}_{i d x}^{B}, {d i r}_{i d x}^{B}]$ , $[{s e q}_{i d x}^{A}, {m p}_{b}^{B}, {m p}_{e}^{B}, {d i r}_{i d x}^{A}]$ 35: if $t y p e_{op}_{i d x}^{A} =$ 2 and $t y p e_{op}_{i d x}^{B}$ = “Bi” then 36: match $[{s e q}_{i d x}^{B}, o p p o s i t e_{d i r}_{i d x}^{B}]$ , $[{s e q}_{i d x}^{A}, {m p}_{b}^{B}, {m p}_{e}^{B}, o p p o s i t e_{d i r}_{i d x}^{A}]$

Link and Direction Matching Procedure:

Input: Matching link sequences

s^{A}

and

s^{B}

of networks A and B.
1: Initialization
2:

f = {l e n}_{s}^{A} / {l e n}_{s}^{B}

, where

f

is the conversion factor to proportionately adjust B links so that their total length is equal to the total length of A links
3: Define

i d x

as the index of a link in the sequence
4: for

i d x^{A}

s^{A}

do
5: if

{d i r}_{i d x}^{A}

= “Cardinal” then
6: directional indicator

α

= 1
7:

o p p o s i t e_di {r^{A}}_{i d x}

= “Non-cardinal”
8: else
9: directional indicator

α

= −1
10:

o p p o s i t e_di {r^{A}}_{i d x}

= “Cardinal”
11:

{l e n}_{b}^{A} \leftarrow

cumulative length from the first A link to the

(i d x^{A} - 1)

th link in

s^{A}

12:

{l e n}_{e}^{A} \leftarrow

cumulative length from the first A link to the

i d x^{A}

th link in

s^{A}

13: for

i d x^{B}

s^{B}

do
14:

{l e n}_{b}^{B} \leftarrow

cumulative length from the first B link to the

(i d x^{B} - 1)

th link in

s^{B}

15: if

{l e n}_{b}^{B} \times f < {l e n}_{b}^{A}

then
16: continue
17: else
18: break
19: Get the index of B link touching the beginning node of the

i d x^{A}

th A link:

{s e q}_{b}^{B}

i d x^{B}

20: for

i d x^{B}

s^{B}

do
21:

{l e n}_{e}^{B} \leftarrow

cumulative length from the first B link to th

i d x^{B}

th link in

s^{B}

22: if

{l e n}_{e}^{B} \times f < {l e n}_{e}^{A}

then
23: continue
24: else
25: break
26: Get the index of B link touching the ending node of the

i d x^{A}

th A link:

{s e q}_{e}^{B}

i d x^{B}

27:

l e n_{p a r t} = {l e n}_{b}^{B} \times f - {l e n}_{b}^{A}

27: for

i d x^{B}

from

{s e q}_{b}^{B}

{s e q}_{e}^{B}

do
28:

{m p}_{b}^{B}

{m p}_{b}^{A} + α \times l e n_{p a r t} + α \times f \times \sum_{i = {s e q}_{b}^{B} + 1}^{i d x^{B}} {l e n}_{i}^{B}

29:

{m p}_{e}^{B}

{m p}_{b}^{A} + α \times l e n_{p a r t} + α \times f \times \sum_{i = {s e q}_{b}^{B} + 1}^{i d x^{B + 1}} {l e n}_{i}^{B}

30: if

{d i r}_{i d x}^{B}

= “F” then
31:

o p p o s i t e_di {r^{B}}_{i d x}

= “T”
32: else
33:

o p p o s i t e_di {r^{B}}_{i d x}

= “F”
34: match

[{s e q}_{i d x}^{B}, {d i r}_{i d x}^{B}]

[{s e q}_{i d x}^{A}, {m p}_{b}^{B}, {m p}_{e}^{B}, {d i r}_{i d x}^{A}]

35: if

t y p e_{op}_{i d x}^{A} =

2 and

t y p e_{op}_{i d x}^{B}

= “Bi” then
36: match

[{s e q}_{i d x}^{B}, o p p o s i t e_{d i r}_{i d x}^{B}]

[{s e q}_{i d x}^{A}, {m p}_{b}^{B}, {m p}_{e}^{B}, o p p o s i t e_{d i r}_{i d x}^{A}]

Implementation Results and Discussions

Algorithm Execution

We programmed the conflation algorithm using Python open-sourced tools including geopandas, shapely, numpy, and difflib. Geopandas and shapely were employed to perform spatial operations such as retrieving intersection coordinates and establishing link sequences. Numpy was applied to calculate distance based on coordinates of endpoints, while difflib was used to determine string matching score of road names. Network and computational details are presented in Table 2. Network B contains more roads, including private roads, and tends to have finer segmentations, as reflected by directional mileage and number of links. The conflation algorithm produced over 1 million matches of directional links from two networks. Table 3 presents the format of conflation results.

Table 2.

Computational Details of the Conflation Algorithm

Network detail	A	B
Directional mileage (mi)	169,816	194,661
Number of links	388,203	591,835
Number of intersections	287,829	387,055
Number of sequences	359,942	476,754
Number of conflated links	1,003,636

Table 3.

The Conflation Output Table

A_LRS_ID	A_BEGIN_MP	A_END_MP	A_Direction	B_LinkID	B_Direction
034-I -0064 -000	71	73.3479	Cardinal	1171905203	T
034-I -0064 -000	73.3479	74.0914	Cardinal	1171905202	T
034-I -0064 -010	71.0034	71	Non-cardinal	1172307751	F
034-I -0064 -010	73.3703	71.0034	Non-cardinal	1171905201	F
034-I -0064 -010	74.0631	73.3703	Non-cardinal	1171907859	F
034-KY-0057 -000	0.661	0.683	Cardinal	107027460	F
034-KY-0057 -000	0.661	0.683	Non-cardinal	107027460	T
034-KY-0057 -000	0.683	0.697	Cardinal	107027459	T
034-KY-0057 -000	0.683	0.697	Non-cardinal	107027459	F

Conflation Results Evaluation

To evaluate the algorithm’s effectiveness, we selected four areas with distinctive geographical characteristics to perform manual verification (Figure 8). The first was a 2.5 mi × 2.5 mi area in downtown Louisville with a very dense roadway network and complex interchanges. The second one was a 2.5 mi × 2.5 mi area in a Lexington suburb that features many curvilinear local roads and cul-de-sacs. The last two were located in the western and eastern rural regions of Kentucky; both had 5 mi × 5 mile areas and are characterized by sparse rural roads.

Figure 8.

Four selected areas for quantitative evaluation: (a) Louisville downtown; (b) Lexington suburban; (c) Western rural; (d) Eastern rural.

To evaluate the conflation algorithm’s performance, we used three metrics: accuracy, precision, and recall. All of these are commonly used in machine learning studies. Accuracy measures the overall ability of the algorithm to find correct matches if correspondences exist and to not force matches if links are only in Network A but not Network B (Equation 3). Precision is the percentage of correct matches out of all matches generated by the conflation algorithm (Equation 4). Recall is the percentage of correct matches out of all the matches that should be generated by the conflation algorithm (Equation 5). In each equation, a true positive is recorded when the conflation algorithm identifies the correct link and direction correspondences. A true negative is the product of the conflation algorithm correctly finding no match for a link that is only present in Network A. A false positive is the result of the conflation algorithm locating an incorrect link and/or direction correspondence. False negatives arise when the conflation algorithm fails to find a match when a correspondence exists. Given variations in segmentations, the equations use link length instead of link counts to calculate performance metrics.

A c c u r a c y = \frac{T r u e P o s i t i v e s + T r u e N e g a t i t i v e s}{A l l O b j e c t s i n A} \times 100

(3)

Precision = \frac{T r u e P o s i t i v e s}{T r u e P o s i t i v e s + F a l s e P o s i t i v e s} \times 100

(4)

R e c a l l = \frac{T r u e P o s i t i v e s}{T r u e P o s i t i v e s + F a l s e N e g a t i t i v e s} \times 100

(5)

Table 4 summarizes the matching results for each area, including total directional mileage of roadways and the length of roadways. The small number of false positives and false negatives in all the areas demonstrate the conflation algorithm is effective. The combined accuracy level for all four areas is 99.29%, higher than accuracy levels reported in existing literature. Because the Louisville area has the most complicated network structure, the accuracy level is a bit lower than in other areas, but still reaches 99%. The accuracy level for the other three areas ranges from 99.34% to 99.45%. Precision levels are also highly satisfactory, averaging 99.29%. The recall measures range from 99.96% to 100%, indicating the algorithm is extremely successful in correctly matching corresponding roadway objects.

Table 4.

Performance of the Conflation Algorithm in Four Areas

Area	Louisville downtown	Lexington suburban	Eastern rural	Western rural	Four areas combined
Total length (mi)	226.6	204.6	199.0	153.6	783.8
True positives (mi)	220.9	203.1	197.1	148.1	769.2
True negatives (mi)	3.4	0.3	0.7	4.5	9.0
False positives (mi)	2.3	1.1	1.2	1.0	5.5
False negatives (mi)	0.0	0.0	0.0	0.1	0.1
Accuracy (%)	99.00	99.45	99.41	99.34	99.29
Precision (%)	98.99	99.45	99.40	99.36	99.29
Recall (%)	100.00	100.00	100.00	99.96	99.99

Spot Checks

Along with quantitative evaluations, we undertook manual spot checks to identify locations whose layout challenges our algorithm. Locations across the state were randomly inspected, with particular attention paid to complicated junction areas where geometric inconsistencies tend to occur.

The following examples showcase locations whose complexity may pose challenges for existing methods but where our algorithm works well. The first case is an interchange area nicknamed “spaghetti junction” where I-64, I-65, and I-71 meet in Louisville (Figure 9). Algorithms that only use geometrical attributes (e.g., distance, angle between lines) would not perform well as a result of the intertwining lines. Our algorithm considers additional information (e.g., topology, road name) and thus overcomes geometrical inconsistencies between the two networks, resulting in a highly accurate conflation. For example, at Location 1, the intersections of A and B are matched correctly despite appearing distant from one another. At Location 2, Intersection 4441546 is correctly matched between the two networks, even though the A intersection is much closer to B Intersection 4388289. With correctly matched intersection pairs, the correspondence of links between two intersections is successfully determined. At Location 3, the correct B link is found, even though the corresponding A link nearly overlaps with an irrelevant B link.

Figure 9.

Conflation at a complicated interchange area.

Figure 10 shows an example of conflated road links at a diverging diamond interchange. Even though many diverging/merging points and links from two networks are not aligning well, our algorithm is able to determine the association of these points based on interchange structure and road names and accordingly find matching links.

Figure 10.

Conflation at a diverging diamond interchange.

The conflation algorithm also works well at locations with large topological discrepancies. Figure 11a shows that the algorithm correctly matches links in a complex roundabout as well as on its approaches. Figure 11b displays a successful matching case where Network A roads are divided but Network B roads are undivided. Figure 11c provides an example of segments in Network A being undivided while those in B are divided. As the A link sequence is closer to the westbound B link sequence, existing algorithms using geometric and non-spatial characteristics would only match westbound links. Our algorithm successfully matches links in both directions using the procedure designed for link matching scenario (e) in Figure 7.

Figure 11.

Conflation at locations with topological discrepancies: (a) a complex roundabout; (b) when a road is divided in network A but undivided in network B; and (c) when a road is undivided in network A but divided in network B.

At a small number of locations, complications arise as a result of topological inconsistencies between two networks that are too difficult for the algorithm to handle. Figure 12a shows a mismatch caused by a ramp splitting into two lines in Network A while remaining as one line at the end of the ramp in Network B. Figure 12b presents another challenge caused by the extra roadway having the same road name and small angle with a mainline link. Although rare, in some cases both networks may not reflect recent roadway alignment changes. Any automated conflation algorithms have difficulty handling these cases, thus requiring manual validation.

Figure 12.

Locations where the algorithm gives mismatches: (a) a ramp splitting into two lines in network A; and (b) extra link with same road name in network A.

Conclusions

This paper described an automated process for conflating large-scale directed networks. Conflation processes used in existing transportation applications rely on breaking down links and are unable to effectively match directions. Our algorithm takes advantage of the topological similarity between networks and establishes correspondences between topological elements with a high level of confidence, including intersections and link sequences. Leveraging a diverse set of attributes related to topological, geometrical, and non-spatial characteristics yields considerable gains in effectiveness. A fuzzy logic inference system is incorporated into the conflation process to account for the underlying uncertainty and imprecision in the networks. Based on the intersection matching results, we can accurately determine correspondences of links and associated directions.

Given network complexity, our algorithm achieves satisfactory performance. We analyzed four areas with distinctive geographical characteristics whose road networks encompass over 780 directional miles, finding the algorithm achieves over 99.2% accuracy, 99.2% precision, and 99.9% recall performance. Manual verifications show that the algorithm finds correct matches at complex locations that methods currently or previously in use would struggle with. Conflation errors are mostly restricted to locations where two networks have clear topological inconsistencies (e.g., Figure 11).

The Kentucky Transportation Cabinet is using the conflated network in their statewide network screening and project prioritization process and is in the process of applying it in other applications. We also adapted the conflation algorithm to work with other types of networks for San Francisco County in California ( 29 ). The scripts involved in that work were made public at https://github.com/sfcta. The conflation methodology put forward here will help agencies overcome major challenges associated with integrating third-party data into agency databases.

Footnotes

Acknowledgements

The authors would like to thank Daniel Hulker for data support and technical advice and Chris Van Dyke for draft review.

Author Contributions

The authors confirm contribution to the paper as follows: study conception and design: Zhang; data collection: Zhang, Chen; analysis and interpretation of results: Zhang, Chen; draft manuscript preparation: Zhang. All authors reviewed the results and approved the final version of the manuscript.

Declaration of Conflicting Interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This study is made possible by the funding from the Kentucky Transportation Cabinet.

ORCID iDs

Xu Zhang

Mei Chen

Data Accessibility Statement

The data used to support the findings of this study have not been made available because of the restriction of data use agreement.

References

Zhang

van Dyke

Erhardt

Chen

. NCHRP Synthesis 541: Practices on Acquiring Proprietary Data for Transportation Applications. National Cooperative Highway Research Program, Transportation Research Board, Washington, D.C., 2019.

Pandit

D. M.

Kaushik

Cirillo

. Coupling National Performance Management Research Data Set and the Highway Performance Monitoring System datasets on a Geo-Spatial Level. Transportation Research Record: Journal of the Transportation Research Board, 2019. 2673: 583–592.

Young

Stanley

The ABC’s of Conflation: TMC, LRS, OSM – What Happens When You Muck It Up The Eastern Transportation Coalition. December 1, 2021. https://tetcoalition.org/wp-content/uploads/2019/12/Conflation-Final-Slides-08-19-2021.pdf.

Lomax

Wang

Schrank

Eisele

Turner

Ellis

Koncz

Geng

. Improving Mobility Information With Better Data and Estimation Procedures. Texas A&M Transportation Institute, College Station, 2010.

Green

E. R.

Ripy

Chen

Zhang

. Conflation Methodologies to Incorporate Consumer Travel Data into State HPMS Data Sets. The TRB 92nd Annual Meeting Compendium of Papers, Washington, D.C., 2013.

Daneshgar

Sadabadi

K. F.

Haghani

. A Conflation Methodology for Two GIS Roadway Networks and Its Application in Performance Measurements. Transportation Research Record: Journal of the Transportation Research Board, 2018. 2672: 284–293.

Kaushik

Wood

Gonder

. Coupled Approximation of U.S. Driving Speed and Volume Statistics Using Spatial Conflation and Temporal Disaggregation. Transportation Research Record: Journal of the Transportation Research Board, 2018. 2672: 1–11.

Ruiz

J. J.

Ariza

F. J.

Ureña

M. A.

Blázquez

E. B.

. Digital Map Conflation: A Review of the Process and a Proposal for Classification. International Journal of Geographical Information Science, Vol. 25, No. 9, 2011, pp. 1439–1466.

Rosen

Saalfeld

eds. Match Criteria for Automatic Alignment. Proc., 7th International Symposium on Computer-Assisted Cartography (Auto-Carto 7), Washington, D.C., 1985

10.

Saalfeld

Conflation Automated Map Compilation. International Journal of Geographical Information Systems, Vol. 2, No. 3, 1988, pp. 217–228.

11.

Volz

(ed) An Iterative Approach for Matching Multiple Representations of Street Data. Proc., JOINT ISPRS Workshop on Multiple Representations and Interoperability of Spatial Data, International Society for Photogrammetry and Remote Sensing Hanover, Germany, 2006, pp. 101–110.

12.

Mustière

Devogele

. Matching Networks With Different Levels of Detail. GeoInformatica, Vol. 12, No. 4, 2008, pp. 435–453.

13.

Xiong

A Three-Stage Computational Approach to Network Matching. Transportation Research Part C: Emerging Technologies, Vol. 8, No. 1, 2000, pp. 71–89.

14.

Walter

Fritsch

. Matching Spatial Data Sets: A Statistical Approach. International Journal of Geographical Information Science, Vol. 13, No. 5, 1999, pp. 445–473.

15.

Yang

Zhang

Luan

. A Probabilistic Relaxation Approach for Matching Road Networks. International Journal of Geographical Information Science, Vol. 27, No. 2, 2013, pp. 319–338.

16.

Zhang

Meng

. An Iterative Road-Matching Approach for the Integration of Postal Data. Computers, Environment and Urban Systems, Vol. 31, No. 5, 2007, pp. 597–615.

17.

Zhang

Yao

Meng

. Automatic and Accurate Conflation of Different Road-Network Vector Data Towards Multi-Modal Navigation. ISPRS International Journal of Geo-Information, Vol. 5, No. 5, 2016, p. 68.

18.

Lei

. Optimal Spatial Data Matching for Conflation: A Network Flow-Based Approach. Transactions in GIS, Vol. 23, No. 5, 2019, pp. 1152–1176.

19.

Fan

Yang

Zipf

Rousell

. A Polygon-Based Approach for Matching Openstreetmap Road Networks With Regional Transit Authority Data. International Journal of Geographical Information Science, Vol. 30, No. 4, 2016, pp. 748–764.

20.

Goesseln

Sester

(eds). Integration of Geoscientific Data Sets and the German Digital Map Using a Matching Approach. In Proc., XXth ISPRS Congress, Istanbul, Turkey, January 1, 2004.

21.

Zhang

Meng

. Delimited Stroke Oriented Algorithm-Working Principle and Implementation for the Matching of Road Networks. Geographic Information Sciences, Vol. 14, No. 1, 2008, pp. 44–53.

22.

Ratcliff

J. W.

Metzener

D. E.

. Pattern-Matching-the Gestalt Approach. Dr Dobbs Journal, Vol. 13, No. 7, 1988, p. 46.

23.

Zadeh

L. A.

Fuzzy Sets. Information and Control, Vol. 8, No. 3, 1965, pp. 338–353.

24.

Lee

Krammes

R. A.

Yen

. Fuzzy-Logic-Based Incident Detection for Signalized Diamond Interchanges. Transportation Research Part C: Emerging Technologies, Vol. 6, No. 5, 1998, pp. 359–377.

25.

Hamad

Kikuchi

. Developing a Measure of Traffic Congestion: Fuzzy Inference Approach. Transportation Research Record: Journal of the Transportation Research Board, 2002. 1802: 77–85.

26.

Quddus

M. A.

Noland

R. B.

Ochieng

W. Y.

. A High Accuracy Fuzzy Logic Based Map Matching Algorithm for Road Transport. Journal of Intelligent Transportation Systems, Vol. 10, No. 3, 2006, pp. 103–115.

27.

Liu

Fei

. A Fuzzy-Logic-Based System for Freeway Bottleneck Severity Diagnosis in a Sensor Network. Transportation Research Part C: Emerging Technologies, Vol. 18, No. 4, 2010, pp. 554–567.

28.

Imprialou

M. -I. M.

Quddus

Pitfield

D. E.

. High Accuracy Crash Mapping Using Fuzzy Logic. Transportation Research Part C: Emerging Technologies, Vol. 42, 2014, pp. 107–120.

29.

Sana

Zhang

Castiglione

Chen

Erhardt

G. D.

. Using Probe-Based Speed Data and Interactive Maps for Long-Term and COVID-Era Congestion Monitoring in San Francisco. Transportation Research Record: Journal of the Transportation Research Board, 2022 2676: 48–60.