1 Introduction

In networked systems, such as those supporting vehicular, energy, data and social movements, a range of services are provided to help ensure efficient and effective operation. Facilities providing these services can take many forms, such as sensors that collect information about network activities, locations at which a service can be obtained (i.e., communications, assistance), staging locations for mounting response to problems (i.e., law enforcement, emergency response), as well as those that relay information to users of a system (i.e., navigation assistance, future/expected conditions, location of disruptive events). The purposes of these types of services though can be very different. Some types of services, such as monitoring network conditions and relaying information about future conditions, are typically provided in hopes that users are exposed to a facility at some point along a path of movement. Other types of services, such as those conveying information on the location of disruptive events, are provided to assist users in making decisions about how to best proceed within the network, once a service is received. For example, facilities that provide such services to users of a transportation system include, kiosks containing analog information, signs/message boards, audio devices, Bluetooth emitters, dynamic message sign (DMS), and highway advisory radio. In such cases, the information is most relevant when it is provided prior to locations offering an opportunity to make effective use of the service. For instance, if the information is provided to alert users to disruptive events so as to reduce travel delays, the service has little value if no opportunity for altering a route exists after receiving the information. Regardless of the intended purpose of a service, there is no guarantee that it will be available and/or effectively received. For instance, in many networked systems, users often do not have the same access to services and/or may not detect, understand, or receive services in a uniform manner given a range of technical, physical, and behavioral differences. Complicating the situation is that networks can support a diversity of flow given the relationships among origins, destination and how users utilize the system. As such, a service provided at one location could vary in relevance to exposed flows. Finally, as with many types of services, siting facilities can be costly in cases where expensive supporting infrastructure, equipment, technology, and operation are involved. For example, siting facilities such as DMS along roadways, can cost hundreds of thousands of dollars and involve significant annual maintenance costs as well (ITS 2017). Therefore, planning new (or extending) service systems often requires imposing limitations on the cost of and/or number of facilities to be sited. To address these planning considerations, several new mathematical models for optimizing the location of facilities for providing service to network flows are developed. The proposed models build primarily upon three location models - the maximal coverage location problem, the maximal expected coverage problem, and the flow capturing location model, which are described in the next section.

2 Background

When siting a limited number of facilities to provide a service, one planning goal is to maximize the amount of demand that can be served. In this sense, it is assumed that a geographic range S is associated with each facility, within which demand locations can be served. The Maximal Covering Location Problem (MCLP), a linear-integer programming problem described by Church and ReVelle (1974) is one modeling approach to this problem in cases where both the candidate facilities and the locations of demand are discrete features. Given a set of locations in need of a service (j ∈ J), a set of candidate facilities (i ∈ I), and a measure of geographic separation between i and j (dij), the subset of facilities (Nj = {j ∈ J| dij ≤ S}) that could serve each demand site can be determined. In the MCLP, a binary-integer variable Xi is defined to reflect the decision to site (Xi = 1) or to not site (Xi = 0) each candidate facility and another binary-integer decision variable Yj is defined to track if the demand (aj) at location j is covered (Yj = 1) or not (Yj = 0). The objective of the MCLP (1) is to maximize the coverage of demand.

$$ \mathit{\operatorname{Maximize}}\ \sum \limits_j{a}_j{Y}_j $$
(1)

s.t.

$$ \sum \limits_{i\in {N}_j}{X}_i\ge {Y}_j\kern0.5em \forall j\in J $$
(2)
$$ \sum \limits_i{X}_i=p $$
(3)
$$ {X}_i=\left\{0,1\right\}\kern0.5em \forall i\in I,{Y}_j=\left\{0,1\right\}\kern0.5em \forall j\in J $$
(4)

Constraints (2) ensures that demand can only be considered covered if at least one facility capable of serving it is sited. Constraint (3) restricts the number of facilities that can be sited to p and Constraints (4) are binary-integer conditions on the decision variables.

While the MCLP is structured to identify facility configurations that can best provide coverage to locations of demand that are independent of one another, there are instances where the interaction among different locations within a system represent the demand to be served (i.e., the movement through a system). To address cases where movements or flows through a network are to be served by a set of facilities, Hodgson (1981, 1990) proposed the flow capturing location model (FCLM). In the FCLM, the flow (fq) moving between each origin-destination (OD) pair (q ∈ Q) is the demand to be served. Therefore, the demand is path-based (versus node-based in the MCLP) and it is assumed that facilities i sited along a path (Nq) are capable of providing service to the path (and the flow along the path). In this sense, the decision variable Yq now reflects the coverage of a path connecting OD pair q (Yq = 1 if path q is served; Yq = 0 if not). The objective of the FCLM (5) is to maximize the coverage of flow among the OD pairs (fq) in a network.

$$ \mathit{\operatorname{Maximize}}\ \sum \limits_{q\in Q}{f}_q{Y}_q $$
(5)

s.t.

$$ \sum \limits_{i\in {N}_q}{X}_i\ge {Y}_q\kern0.5em \forall q\in Q $$
(6)
$$ \sum \limits_i{X}_i=p $$
(7)
$$ {X}_i=\left\{0,1\right\}\kern0.5em \forall i\in I,{Y}_q=\left\{0,1\right\}\kern0.5em \forall q\in Q $$
(8)

Constraints (6) prohibit coverage of a path unless at least one of the facilities along that path is sited. Constraint (7) limits the number of facilities (typically nodes) to be sited to p as in the MCLP. Constraints (8) are binary-integer restrictions on the facility and path decision-variables.

Typical applications of flow capturing models only consider a single demand (i.e., the shortest path) between each OD pair in need of service (Hodgson 1990; Hodgson et al. 1996). Zeng et al. (2010) suggest that the set of facilities that can cover the flows between an OD pair (Nq) can be generalized to include all candidate facilities capable of serving the OD flow, regardless whether or not they are on the shortest path (i.e., along a reasonable alternative path as well). While their approach can account for other facilities that may be able to serve an OD flow, individual paths and their associated flows are not explicitly tracked.

The basic FCLM has also been extended to account for a range of other planning considerations. For example, the problem of determining locations for vehicle refueling stations can involve maximizing coverage of path-based flow, but can also necessitate taking into account issues such as the need for multiple facilities along some paths (Kuby and Lim 2005; Capar et al. 2013), ensuring that certain thresholds on outflow served are met (Hong and Kuby 2016), and addressing changes in flow over time (Miralinaghi et al. 2017). In other applications, the level of benefit provided by facilities can vary depending on the perspectives of different users of a system as addressed by Zeng et al. (2009). Another practical consideration that arises in many contexts is the need to account for coverage of path-based flow given the ability of flow to divert from one path to another. Berman et al. (1995) and Tanaka and Furuta (2012) allow path flow to be served by a sited facility as long as a specified level of deviation is not exceeded. In the context of locating vehicle refueling stations, some approaches consider OD flow served in cases where at least one of the alternative paths among an OD pair is served (Kim and Kuby 2012, 2013; Huang et al. 2015; Yildiz et al. 2016).

Coverage of demand by sited facilities can be subject to many sources of uncertainty. That is, even if a facility is positioned to cover demand, there is some probability that the demand will not be effectively served. As such, there have been many efforts to extend location coverage models to account for the likelihood that demand is served. For MCLP-like problems, Daskin (1983) addresses the case where the probability of coverage is not assumed to vary among facilities and that each facility i can cover demand with probability of 1 − σ, where σ is the probability that a facility is not able to provide service. By way of the additive property of non-mutually exclusive events, the probability that a demand site is covered by h facilities capable of providing service is 1 − σh. Daskin (1983) compares this probability with the probability of a demand site being served by h-1 facilities to calculate the additional expected coverage using h facilities as: uh = (1 − σh) − (1 − σh − 1). A new binary-integer decision variable Yjh is introduced to track whether demand site j can be served by h facilities (Yjh = 1) or cannot be served (Yjh = 0), where h = 1…|I|. Objective (9) can then be written to maximize expected coverage. Objective (9) can be structured as a linear function given that all facilities in a system have the same probability of providing coverage (e.g., combination of facilities selected doesn’t matter) and since Yjh with lower h will naturally be selected first by the objective due to the higher contribution they provide. Constraints (10) ensure that demand j can only be served by h facilities if at least h facilities have been sited. Constraints (11) reflect facility limitations as in (3) and (12) are integer restrictions on the decision variables.

$$ \mathit{\operatorname{Maximize}}\sum \limits_h\sum \limits_j{a}_j{u}_h{Y}_{jh} $$
(9)

s.t.

$$ \sum \limits_h{Y}_{jh}-\sum \limits_{i\in {N}_j}{X}_i\le 0\kern1em \forall j $$
(10)
$$ \sum \limits_i{X}_i=p $$
(11)
$$ {X}_i=\left\{0,1,...,p\right\}\kern0.5em \forall i;\kern0.5em {Y}_{jh}=\left\{0,1\right\}\kern0.5em \forall j,h $$
(12)

In some instances, each facility in a system could have a different probability of providing service (i.e., 1 − σi). Each facility i could also exhibit variation in the probability that it provides service to different demand sites j (ηij). To cope with these different probabilities of service, Polasky et al. (2000) model expected coverage using the non-linear Objective (13).

$$ \mathit{\operatorname{Maximize}}\sum \limits_{j\in J}\left(1-\prod \limits_{i\in I}\left(1-{\eta}_{ij}{X}_i\right)\right) $$
(13)

s.t.

$$ \sum \limits_{i\in I}{X}_i\le p $$
(14)
$$ {X}_i=\left\{0,1\right\}\kern0.5em \forall i\in I $$
(15)

In particular, Objective (13) seeks to maximize the expected coverage of demands j, given that all demands are considered to be of equal importance. Constraint (14) limits the number of facilities to be sited to less than or equal to p and (15) ensure that the decisions to site facilities are binary and integer. Due to the structure of the objective function (13), a separate decision variable reflecting demand coverage (i.e., Yj) is not needed.

ReVelle et al. (2002) describe objective (16), an alternative formulation to objective (13). However, they note that in either case (13) or (16), a linearization of the objective is not likely and solution methods for this highly non-linear formulation are probably limited to heuristics.

$$ \mathit{\operatorname{Maximize}}\sum \limits_{j\in J}\left(1-\prod \limits_{i\in I}{\left(1-{\eta}_{ij}\right)}^{X_i}\right) $$
(16)

Aside from incorporating expected coverage in the objective function, efforts have been made to integrate similar notions as constraints. In particular, Haight et al. (2000) show that demand maximizing objectives, such as (1) can be coupled with a threshold-type constraint (17) to ensure that total probability of the sited facilities not serving a demand is less than or equal to a specified threshold value (α). In other words, a value of α can be selected to represent a level of expected coverage that could be considered acceptable.

$$ \prod \limits_{i\in I}{\left(1-{\eta}_{ij}\right)}^{X_i}\le {\left(1-\alpha \right)}^{Y_j}\kern0.5em \forall j\in J $$
(17)

Although, (17) is non-linear, Haight et al. (2000) provide a linear equivalent that has been utilized in a variety of MCLP-like contexts (Matisziw and Murray 2006).

Along with addressing coverage of demand in a network, it is also important to consider the opportunities that exist for route modification once a service has been received. Toi et al. (2005) examine methods for the location of signs directing travelers to particular destinations. To this end, they propose a model for minimizing the amount that drivers are expected to ‘stray’ from their current route given restrictions of the number of signs that can be sited. Chui and Huynh (2007) describe an approach for locating dynamic message signs (DMS) to assist in notifying drivers of traffic incidents so that they may consider alternative paths of travel to their destinations. To address this problem, they propose a simulation-based heuristic approach that seeks to locate DMS in order to minimize a combination of facility costs and user transportation costs given some type of stochastic event. Li et al. (2016) also seek to identify optimal sites for DMS. To do so, they provide a model that minimizes total travel time given a budgetary constraint that limits the number of DMS that can be sited. They also constrain their model to restrict the amount of information about upcoming portions of the system that will be displayed.

Thus, there are several key issues. First, siting service facilities can be costly and such resources are limited. In such instances, maximization of demand coverage is a well-documented planning strategy. However, multiple paths often support movement among OD pairs and an approach capable of accounting for alternative paths is needed. Second, there can be different objectives for providing services to flows in a network. In some cases, basic exposure to a service facility at any location along a route might be important. In other cases, the ability of the service to provide timely decision support to network flows could be an essential consideration. In those instances, a service, although provided, is not very useful unless some opportunity for making use of the service exists (e.g., altering a route after information is received). Third, regardless of whether general exposure to a service or opportunity to make effective use of a service is important, there is some probability that the service will not reach the flow and assessment of expected coverage becomes warranted. However, formulations for expected coverage have been largely limited to non-network applications and supporting objectives are typically non-linear, requiring the use of heuristic solution methods. To address these issues, several new models are proposed for optimizing expected coverage of network flows in general as well as the opportunity that exists for flows to make effective use of a service once it has been provided. While incorporating probability of coverage typically entails a non-linear formulation (i.e., eq. (13) and (16)), it will be shown that such objectives can be linearized given an ordering in which facilities can serve demand. The developed models are then combined into a multi-objective modeling framework and applied to a case study to demonstrate their characteristics and practical utility.

3 Methods

Given a directed graph G with N nodes and A arcs G(N, A) where some nodes are origins (o ∈ N) and destinations (d ∈ N) for flows (ϕod), consider a set of feasible paths M that represent reasonable alternatives between the OD pairs. Given an assignment of flows between each OD pair ϕod to a set of network paths Nod ∈ M, fm is the amount of flow assigned to path m ∈ Nod. For every path m, the sequence of network locations (i.e., arcs or nodes) i to be traversed is i ∈ κm. These locations represent candidate sites at which facilities could be positioned to serve flow along the path. The probability that a facility at location i can serve flow on the path is ηim. First, to address the problem of accounting for probabilistic coverage of network flows, a Maximal Expected Flow Covering Problem (MEFCP) can be formulated as follows.

$$ \mathit{\operatorname{Maximize}}\sum \limits_{m=1}^{\mid M\mid }{f}_m\left(1-\prod \limits_{i\in {\kappa}_m}{\left(1-{\eta}_{im}\right)}^{X_i}\right) $$
(18)

s.t.

$$ \sum \limits_{i\in A\ \mathrm{or}\ i\in N}{X}_i=p $$
(19)
$$ {X}_i=\left\{0,1\right\}\kern0.75em \forall i\in A $$
(20)

Objective (18) maximizes the expected coverage of flow over all paths connecting OD pairs in the network. This objective is similar in concept to that of Polasky et al. (2000) and ReVelle et al. (2002), but is structured to account for path-based demand. Thus, this formulation extends the basic FCLM to account for probabilistic coverage. Moreover, this formulation moves beyond the consideration of a single shortest path between each OD pair and can accommodate a broader set of alternative paths that could serve to facilitate movement between OD pairs. Constraint (19) stipulates that p facilities (arc or node-based) are to be sited. Constraints (20) are binary-integer restrictions on the facility siting decision variables.

Second, every facility is assumed to present flows along a path some level of opportunity/potential (bim) for making use of its service. For example, information provided to network flows prior to opportunities to divert from a path is assumed to be more important than provision of information when no opportunities to divert exist. However, although information may be provided and opportunities to make use of that information may exist, there is no guarantee that the flow will receive the information. Thus, as is the case in Objective (18), expected coverage of flows should be modeled. To account for both expected coverage of network flows as well as the for the opportunity that exists for benefiting from that coverage, a Maximal Expected Flow Opportunity Coverage Problem (MEFOCP) problem can be formulated as follows.

$$ \mathit{\operatorname{Maximize}}\sum \limits_{m=1}^{\mid M\mid}\sum \limits_{i\in {\kappa}_m}{f}_m{b}_{im}\left(1-\prod \limits_{g<=i\in {\kappa}_m}{\left(1-{\eta}_{gm}\right)}^{X_g}\right) $$
(21)

s.t. Eqs. (19) and (20).

Objective (21) maximizes the expected coverage of flow relative to the opportunities (bim) available to the flow to benefit from coverage. In this sense, although a facility is assumed to provide some level of coverage, the utility of that coverage can vary based upon what portion of the path has already been traversed. For instance, while flow along a path may receive information that an upcoming portion of the path is blocked, the information is of little use if there are no alternatives for circumventing the blockage. Given that the probability that flow along a path receives coverage from a sited facility i can vary, the relative opportunity a facility could provide to flow along a path can be weighted by the expected coverage provided up to that point (the probabilities of the facilities that have already been traversed in a path). To accomplish this, the expected coverage associated with a facility along a path can be computed specifically for each facility along a path (accounting for the probabilities of coverage of that facility as well as those of preceding facilities in the path), rather than for the entire path as was done in Objective (18). Thus, while (18) provides a means for accounting for expected coverage of network paths in general, (21) accounts for the level of opportunity that exists for making use of coverage at different locations in a path, given that the benefit of that coverage can change as flow traverses a path.

The opportunity (bim) available to flow on path m at or prior to location i for making use of a sited facility can be measured in a variety of ways. In this study, the opportunity to divert from a path and circumvent its remaining portions is of interest. Thus, while a facility located earlier in a path (i.e., closer to the origin) could be viewed as being of greater benefit to path flow (e.g., Objective (18)), the opportunity it affords flow to divert to a different path depends upon: a) the availability of alternate paths as well as b) the extent to which portions of the original path can be avoided by switching to an alternative route. For example, a facility sited at the beginning of a path provides no opportunity for diversion if upon exit of that facility no alternative pathways are available.

One way to measure the opportunity for path diversion provided by a facility i is to assess the proportion of path m (i.e., costs or length) that could be avoided by switching to an alternative path(s) upon exiting i. To illustrate this concept, consider the network comprised of six nodes and nine arcs shown in Fig. 1. In this network, there are nine paths, representing reasonable alternatives for connecting a single OD pair. Path 9 involves traversal of two arcs (H then I). Given no opportunity for flow along this path to divert to a portion of any of the alternate paths in the network, the opportunity arcs H and I provide for diversion is 0.0. While Path 1 also involves traversal of two arcs (A then F), flow moving along arc A could be diverted to Path 4 (arcs C, D, G), allowing the flow to bypass arc F, 4/7 of Path 1’s length. Once flow on Path 1 enters arc F though, there are no opportunities for diversion and its benefit is therefore 0.0. Similarly, on Path 5 (arcs B, D, G), flow along arc B can be diverted to Path 7 (avoiding arc D) or Path 6 (avoiding arcs D and G). Given that it is possible to avoid both arcs D and G, the opportunity for diversion that arc B provides to flow along Path 5 is 6/9. Once flow on Path 5 has moved to arc D, opportunity for diversion still exists (Path 8), but the length of Path 5 that can be avoided is less (3/9). Finally, once flow on Path 5 enters arc G, no other opportunities for diversion exist as hence its value for diverting from Path 5 is 0.0.

Fig. 1
figure 1

Example paths for origin and destination

Full size image

Thus, for each network location (arc or node) i in a path m serving an OD pair, this process of assessing opportunities for diversion first involves determining whether or not the location is also used in another path r serving the same OD pair. If it is, the set of arcs traversed after i (denoted here as Him and Hir) in both paths can be compared. In cases where the set of arcs Him and Hir are different in some respect, an opportunity for diverting from path m to path r exists. This general process for computing the opportunity for path diversion provided by facilities along a path, is outlined in the following pseudo-code, DiversionOpportunity.

DiversionOpportunity (G(N,A), o, d ∈ N, m ∈ Nod, Γ).

figure a

DiversionOpportunity iterates through the set of paths serving each OD pair (Step 1). It is assumed that all of the paths in this set are reasonable routing alternatives. That is, diverting from one path to another would not represent a major obstacle to efficient movement. For each network location (i.e., arc or node) i in a path m (Step 2), all other paths supporting movement between the OD pair are then inspected to see if they also involve the use of i (Steps 4-5). If another path r also contains i, the difference (T) between the set of arcs in paths r and m remaining to be traversed after i (Him and Hir) is computed. The difference between these two sets represents the portions of the remainder of path m that can be avoided given information is received at i (Step 6). The portions of path m that can be avoided by diverting to alternative paths are then tracked in Γ (Step 7). Finally, the length of the arcs in the remainder of path m that can be avoided, Γ, are summed relative to the total length of path m (Step 8). The quantity bim thus measures the proportion of path m that could be avoided by switching to other paths if information is received at or along i and can then be incorporated into a model objective as is done in (21).

Objectives (18) and (21) are non-linear and would typically require a heuristic solution approach (Polasky et al. 2000; ReVelle et al. 2002). However, given cases in which facilities serving demand are encountered in a sequence, it can be shown that a linear version of the model can be constructed. First, for ease of presentation, the basic probability calculations can be re-written using the inclusion-exclusion identity for the union of non-mutually exclusive events for any two facilities A,B along a path as shown in Eq. 22.

$$ \left(1-\prod \limits_{i\in \left\{A,B\right\}}{\left(1-{\eta}_{im}\right)}^{X_i}\right)={\eta}_{Am}{X}_A+{\eta}_{Bm}{X}_B-\left({\eta}_{Am}{X}_A\right)\left({\eta}_{Bm}{X}_B\right) $$
(22)

For any path m, the probability that it has been served at or before facility i (Zim) involves assessing the probability that service has been provided at i as well as at the other facilities encountered prior to i. When traversing a path, the probability that service has been provided at the first candidate facility \( {\kappa}_m^1 \)encountered in a path only involves evaluating the probability associated with that facility (Eq. 23).

$$ {Z}_{im}={\eta}_{im}{X}_i\kern0.5em where,i={\kappa}_m^1 $$
(23)

For all other facilities that could potentially serve a path, the probability that service has been provided is the probability associated with the facility, the probability associated with the one directly proceeding it, or their combined probability (Eq. 24).

$$ {Z}_{im}={\eta}_{im}{X}_i+{Z}_{\left(i-1\right)m}-\left({\eta}_{im}{X}_i\right)\left({Z}_{\left(i-1\right)m}\right)\kern0.5em where,i\ne {\kappa}_m^1\in {\kappa}_m $$
(24)

Thus, the computation of any Zim requires that the Zim values for all preceding facilities in the sequence serving a path to be known. These relationships can be used to re-specify the objectives of the MEFCP and MEFOCP as linear equations as in (25) and (26) respectively.

$$ \mathit{\operatorname{Maximize}}\; EC=\sum \limits_{m=1}^{\mid M\mid }{f}_m{Z}_{l_mm} $$
(25)
$$ \mathit{\operatorname{Maximize}}\; EO=\sum \limits_{m=1}^{\mid M\mid}\sum \limits_{i\in {\kappa}_m}{f}_m{b}_{im}{Z}_{im} $$
(26)

Objective (25) is equivalent to (18) given that it accounts for the total expected coverage of the paths by the sited facilities. In this specification, a path’s total expected coverage by sited facilities is equal to that accumulated by the time the last facility lm ∈ κm serving each path \( {Z}_{l_mm} \) is encountered. Objective (26) is equivalent to (21), maximizing the expected coverage of opportunity for flows provided by facilities along OD paths.

A series of constraints (27)-(31) are now needed to track the probability that service has been provided by the time each facility is encountered along a path.

$$ {\eta}_{im}{X}_i-{Z}_{im}=0\kern0.5em \forall m,i={\kappa}_m^1 $$
(27)
$$ {Z}_{\left(i-1\right)m}-{\eta}_{im}{Z}_{\left(i-1\right)m}+{\eta}_{im}\ge {Z}_{im}\kern0.5em \forall m,i\in {\kappa}_m\mid i\ne {\kappa}_m^1 $$
(28)
$$ {\eta}_{im}{X}_i+{Z}_{\left(i-1\right)m}\ge {Z}_{im}\kern0.5em \forall m,i\in {\kappa}_m\mid i\ne {\kappa}_m^1 $$
(29)
$$ \sum \limits_{i\in A}{X}_i=p $$
(30)
$$ {X}_i=\left\{0,1\right\}\kern0.5em \forall i\in A;0.0\le {Z}_{im}\le 1.0\kern0.5em \forall m,i\in {\kappa}_m $$
(31)

Constraints (27) state that the probability that a path m is served by the first candidate facility encountered is equal to the probability of service associated with that facility, in line with eq. (23). Constraints (28) and (29) pertain to all other candidate facilities in the sequence along each path and represent the addition of mutually non-exclusive events as in Eq. (24). Constraints (28) state that the probability path m has been served at or before facility i has to be less than the additive probability of facility i and facility i-1. Constraints (29) state that the probability that path m is served at or before facility i has to be less than or equal to the sum of the probability that service is received at facility i-1 and the probability associated with facility i if it is selected for siting. Constraints (30) limit the number of sited facilities to p. Finally, Constraints (31) ensure that the facility siting decisions are binary-integer and that the probability of service at each facility along each path is non-negative and not more than 1.0.

4 Application: Siting Dynamic Message Signs (DMS)

Road and highway systems are an example of a network in which information provision can be an asset to a variety of decision-makers as well as greatly strengthen users’ ability to make decisions regarding routing choice. A variety of information can be provided to motorists ranging from directions, safety reminders, upcoming roadway conditions, accident/closure locations, alternative routes/detours, public notifications (i.e., Amber Alert), and advertisement of services. These types of information are often conveyed via billboards, dynamic message signs, mobile signage, etc. In some cases, basic exposure to information is important, regardless of where along a route it is made available. In other cases, the information could be useful for assisting a driver in the identification of an alternative route. However, it is known that drivers do not always observe such information due to factors such as distraction, occlusion of information by other vehicles and/or structures, information availability (i.e., changing messages) and/or presentation, or individualistic factors such as age, familiarity with technology, distance driven, level of education, etc. (Collins and Hall 1992; FHWA 2009; Zhong et al. 2012; Gan and Chen 2013; Inman et al. 2014). Thus, the MEFCP and the MEFOCP provide a way of integrating these planning considerations to assist in the identification of a configuration of DMS sites.

Here, the MEFCP and the MEFOCP are applied to the generalized highway network depicted in Fig. 2 to identify configurations of DMS which can optimally provide information to truck flows moving among the 15 metropolitan statistical areas (MSAs) in the state of Ohio, USA. Given each MSA can serve as both an origin and a destination of flow, 210 potential OD pairs exist in this system. Daily truck flow among these 210 OD pairs is approximately 252,697 in passenger car equivalents (PCE). The network consists of 23 nodes, 15 of which represent the MSAs in Ohio, as well as 68 directed arcs. Additional information on this network can be found in Matisziw et al. (2007). While most flow capturing modeling approaches have considered only the shortest path between each OD pair, alternative paths are often present and are crucial for providing opportunities for re-routing. For instance, while 210 shortest paths can serve to connect all OD pairs in this network, 119,582 unique OD paths actually exist. However, many of these paths exceed travel time and/or distances that would present them as reasonable alternatives for a driver. Therefore, in practice, OD flows would be distributed over a subset of the potential paths according to how drivers are assumed to be influenced by travel time, distance and factors such as congestion. In this application, OD flows were assigned to network paths based on a stochastic user equilibrium approach (volumes per segment illustrated in Fig. 2). This assignment scheme resulted in flow assigned to 2259 OD paths, approximately eleven paths serving each OD pair. In many facility siting models, network nodes are often considered as candidate locations for facilities. However, in the case of DMS, it is important that candidate DMS be placed prior to the location at which a change in routing could be made, somewhere in between a pair of nodes. As such, in this application, the network arcs are the candidate facilities that represent the general nature of this locational decision. In other words, if an arc is selected as a DMS site, a DMS is to be positioned somewhere along the arc such that travelers have enough time to receive and utilize the information prior to the next location at when a routing decision could be made.

Fig. 2
figure 2

Generalized highway network

Full size image

In practice, the likelihood of information provided along each arc i being received by flow on path m (ηim) could be premised on any number of factors. Here, it is assumed that ηim will be at least 0.7. Locating information along longer arcs (with respect to overall path length) could provide motorist with an increased amount of time to utilize the information. To incorporate this assumption, additional probability was added to ηim in relation to the length of the arc relative to path length up to ~0.89 in the instance that the arc was nearly 100% of the path length.

To better understand the tradeoff between maximizing expected coverage of network flow and maximizing opportunity for diversion, the objectives of the MEFCP and the MEFOCP were combined into single objective (32) subject to constraints (27)-(31) applying a weight of w = [0,1] to one objective and a weight of 1.0-w to the other (Cohon 1978). Given that the MEFCP already accounts for the path flows, path flows were not included in the MEFOCP objective as to highlight the broader differences between coverage and opportunity for diversion.

$$ \mathit{\operatorname{Maximize}}\kern0.75em \varOmega = wEO+\left(1-w\right) EC $$
(32)

Weights were then selected to optimize each of the two objectives individually (w = 0.999 for maximal expected flow opportunity coverage (Ω1) and w = 0.001 for maximal expected flow coverage (Ω2)). Given these two extreme solutions, the bi-objective model was then iteratively solved using the adjacent line search technique of Daskin (1995) to identify all non-dominated solutions. This approach involves systematically evaluating pairs of adjacent solutions that have been identified, constructing a straight line between them, and then solving a modified version of the objective function to determine if another non-dominated solution exists between the pairs. For example, given the first two solutions Ω1 and Ω2, their relative EC and EO components were used to construct objective (33).

$$ \mathit{\operatorname{Maximize}}\left(-\frac{\varOmega_1(EO)-{\varOmega}_2(EO)}{\varOmega_1(EC)-{\varOmega}_2(EC)}\right) EC+ EO $$
(33)

Model instances for values of p = 1 – 20 were then populated, each involving 31,290 constraints and 16,843 decision variables. For each value of p, the multi-objective solution technique described above was used to identify all non-dominated solutions to the model using the commercial optimization solver Gurobi 5.0 via Python 2.7 on a Windows XP 64bit workstation with four 2.53GHz processors and 16GB RAM.

5 Results and Discussion

In total, 186 non-dominated solutions were identified and are illustrated in Fig. 3. Generally, for values of p > 3, a considerable tradeoff between expected flow coverage and expected opportunity for path diversion, ~25%, was found to exist. The tradeoff among solutions for different values of p can also be observed. For example, there is a solution for p = 14 that has higher opportunity for path diversion than the solution maximizing expected flow coverage for p = 15 while providing only 2% less expected coverage.

Fig. 3
figure 3

Non-dominated solutions for p = 1 – 20

Full size image

Computational characteristics for solutions to p = 12-13 and p = 19-20 are provided in Table 1 to illustrate the nature of typical solutions to the problem. “Iterations” and “Nodes” reflect the effort involved in the branch and bound solution method utilized by Gurobi, while “Time (sec)” is the total solution time for each model in seconds. “% Expected Coverage” is the expected coverage of flow by information while “% Coverage” provides information on the percentage of flow that actually traversed a sited facility, regardless of whether or not the information was actually received for added perspective. For each value of p listed in the table, solutions are ordered according to the weight (w) which was applied to the first objective (expected opportunity for divergence). When the weight on the first objective is lower, maximization of expected coverage of flow was emphasized and solution times were relatively low (3-11 s) with little branching required. For p = 12-13, expected exposure to information can be close to 70% of total system flow while the actual proportion of flow that passes by the sited information is actually closer to 80% of total system flow. For p = 19-20, expected coverage of flow increases to over 80% of total system flow with over 90% of flow passing by a sited facility. As the weighting on the coverage opportunity objective increased, more branch and bound iterations were generally needed as higher solution times were experience (all model instances solved in under 35 s). When the model emphasis is weighted in favor of maximizing opportunity for divergence, expected coverage of flow becomes considerably degraded. For example, for p = 12-13, maximization of divergence opportunity only provides expected coverage to 48% of flow. For p = 19-20, expected coverage is reduced to 57 and 60% of system flow respectively.

Table 1 Non-dominated solutions for p = 12-13 and p = 19-20
Full size table

The locations at which facilities were sited to serve network activity can also be explored. As an example, Fig. 4 illustrates four of the non-dominated solutions for p = 19. Figure 4a depicts a solution maximizing expected coverage of flow (w = 0.001). In this case, arcs corresponding to both directions of each divided segment were selected in all but one instance. Also, the selected arcs clearly target flows entering/leaving the MSAs with larger inflow/outflow in the region (Cleveland, Akron, Cincinnati, Hamilton, Dayton, and Columbus). As the weighting on the first objective is increased, the solutions begin to emphasize opportunities for path divergence as shown in Figs. 4b-c. In Fig. 4b, less arcs (12 out of 19) have a counterpart in the opposite direction while seven arcs only serve one direction of a highway segment. A focus on serving the flows entering/exiting larger MSAs is still evident with 16 out of 19 arcs shared with that in Fig. 4a, but three of the arcs are now located in more intermediate portions of the network. The solution in Fig. 4c) shares 11 of 19 arcs with that in Fig. 4a with the other selected arcs being more dispersed throughout the region. Additionally, only four of the arcs are bi-directional. Finally, Fig. 4d illustrates the solution weighted to maximize diversion opportunity. In this case, only 9 of the 19 arcs are shared with the solution maximizing exposure. Moreover, none of the selected arcs are bi-directional.

Fig. 4
figure 4

Non-dominated solutions for p = 19: aw = 0.001, bw = 0.9712, cw = 0.9843, dw = 0.999

Full size image

6 Conclusion

Services can be provided to network flow to serve a variety of objectives. In some instances, the objective may be simply to expose users of a network to a service at some point during their traversal of the system. In other cases, the objective may be to provide decision support services to users of the network that could assist them in determining how to traverse the system in an efficient manner. In either case, there is some probability the service will be effectively received by users of the system. To address these planning objectives, two new models, the Maximal Expected Flow Covering Problem (MEFCP) and the Maximal Expected Flow Opportunity Coverage Problem (MEFOCP) are proposed.

As with the Flow Capturing Location Model (FCLM), the MEFCP seeks to maximize coverage of flow traversing network paths provided by a set of sited facilities. In this sense, it is assumed that flows along network paths are effectively served as long as a facility is sited somewhere along the path. However, the MEFCP builds upon the basic FCLM by accounting for all relevant paths of movement among OD pairs (versus a single path) as well as allowing for probabilistic coverage given that availability of a service does not alone guarantee it will be utilized or received. While the MEFCP seeks to provide expected coverage to flow, it does not account for the level of opportunity that exists at locations in the network for diverting from a current path of travel and making use of a service. That is, there is no relationship between the location at which coverage is provided and opportunities for making use of that coverage. The MEFOCP is therefore proposed to better associate the value of coverage with the location of flow in the network.

The MEFOCP maximizes the expected coverage of opportunity that is provided to flow along a path. In this research, the opportunity for coverage associated with a location was the availability of opportunities for circumventing remaining portions of a path by diverting to alternate paths. The opportunity to circumvent remaining portions of path m at each network location i (bim) was computed as a function of the proportion of a path that could be avoided if a service was provided at or before that location. Therefore the objective of the MEFOCP is structured to track expected coverage of individual arcs/nodes (which depends on the expected coverage of all preceding arcs/nodes) versus the entire path as is done in the MEFCP. However, in both the MEFCP and the MEFOCP, accounting for the probabilistic coverage of network flow involves a non-linear objective structure (given that the combination of facilities selected to serve a path is important), one for which a linearization has been thought unlikely (ReVelle et al. 2002). In the case where a topological relationships among arcs exists (i.e., a network) though, it is shown here that a linearization of the models can be constructed.

The resulting linear-integer formulations are applied to a generalized highway network supporting regional truck flows to illustrate its applicability. Given that the objectives of the MEFCP and the MEFOCP can be conflicting, they are integrated into a bi-objective model to demonstrate the tradeoffs that may exists between serving network flows at any point along a path and serving paths more broadly where the availability of opportunities for making use of the service (i.e., for diversion to an alternate path) is a factor. The bi-objective formulation was solved to identify all non-dominated tradeoff solutions involving the two objectives using a commercial optimization solver. It was found that exact solutions to the model can be readily obtained and that a significant number of non-dominated tradeoffs among the two siting objectives can exists. Moreover, it was found that the developed approach can easily cope with many alternative paths for each OD pair beyond a single shortest-path.

With this type of modeling approach, a considerable amount of flexibility exists. For example, different schemes for assigning flow to network paths and for associating probabilities of information transmission/reception with facilities can be considered. In the application to DMS location, the network arcs were used to represent the decision to locate a facility somewhere along the arcs. However, other mechanisms for integrating or determining more specific locations along arcs could also be incorporated. The binary-integer restrictions on the facility selection could also be relaxed to allow for siting multiple facilities along each arc as in the expected coverage model of Daskin (1983). Also, while the opportunity coverage objective is structured in this application to maximize expected opportunities for route diversion, it could easily be modified to address alternative route diversion metrics. For example, in this research, higher bim values are associated with network locations that permit diversion of flow over paths that avoid remaining portions of the initial path. Alternatively, other algorithms could be employed to associate higher bim values with network locations that allow flow to divert from a path as to avoid the following arc, that then permit return to the remaining portions of the initial path in the most efficient manner. The bim values associated with network locations could also be based on other types of system characteristics that could influence the ability to effectively make use of a service at some point after being notified of its availability. For instance, in the context of siting facilities that provide commercial services, the level of opportunity for diversion could simply be modeled as the length of diversion required to obtain a service.