A maximum trip covering location problem with an alternative mode of transportation on tree networks and segments

Abstract

In this paper the following facility location problem in a mixed planar-network space is considered: We assume that traveling along a given network is faster than traveling within the plane according to the Euclidean distance. A pair of points (A _i ,A _j ) is called covered if the time to access the network from A _i plus the time for traveling along the network plus the time for reaching A _j is lower than, or equal to, a given acceptance level related to the travel time without using the network. The objective is to find facilities (i.e. entry and exit points) on the network that maximize the number of covered pairs. We present a reformulation of the problem using convex covering sets and use this formulation to derive a finite dominating set and an algorithm for locating two facilities on a tree network. Moreover, we adapt a geometric branch and bound approach to the discrete nature of the problem and suggest a procedure for locating more than two facilities on a single line, which is evaluated numerically.

1 Introduction

Covering problems constitute one of the main branches of Locational Analysis. A maximal covering location problem consists of locating a fixed number of servers or facilities so that the number of given (demand) points for which the facilities are useful is maximized. In this case a point is said to be covered by the facility if the point is located within a given threshold distance or time from the facility. Covering location problems have been studied in continuous and discrete spaces (see Plastria, 2002 and Koolen and Tamir, 1990 for continuous and discrete settings, respectively).

We generalize covering location problems from two points of view: First, we deal with a mixed planar-network space, and second we do not cover points, but origin-destination pairs (O/D pairs) which are pairs of points.

Our first generalization takes into account that the underlying space of the problem is often in practice not homogeneous in terms of spent time, meaning that there are some structures where the speed is higher than in others (ADSL or high-speed railways are examples in the telecommunication and transportation fields, respectively). Secondly, service is not completed only by reaching the facility but also by traveling along the high-speed network and then acceding to another point. We hence assume that the demand to be covered is given by a set of O/D pairs, that is, pairs of points (A _i ,A _j ) with some traffic t _ij between them.

In this paper the goal is to locate several facilities on a given high-speed network that can be used as entry and/or exit points for traveling between the given O/D pairs. We assume three possibilities for traveling: across the plane without using the high-speed network, using the high-speed network only, or by a combination of both transportation systems. Our aim is to maximize the performance of the high-speed network. More precisely, we want to locate the entry and exit points so that it becomes attractive for as much traffic as possible to use the high-speed network instead of the planar direct path.

As an example of this situation in a railway transportation setting, consider Fig. 1, which is based on a real section of the Spanish high-speed network. There are two main cities, Sevilla and Córdoba, linked by a high-speed line. In the geographical area between both cities, there is a number of smaller cities that do not have easy access to this high-speed train because currently there are no intermediate stops. They are linked by a slower network which is dense enough to be roughly approximated by the Euclidean distance. In order to attract more passengers the company operating this high-speed system is thinking about locating two stations in between so that as many potential passengers as possible will use the high-speed line. For instance, in order to travel from Brenes to La Carlota, assuming the two new stations are located where the big dots are, one could go from Brenes to the high-speed train station, take the high-speed line from there to the next station, and finish the journey to La Carlota from there by means of the slower network (as depicted in Fig. 1). We assume that users will take this trip instead of directly going from one town to the other by the slower network, if the time of this journey is lower than a given threshold (which could be the time of the same journey by the slower network). The idea is therefore to locate two stations so that as many potential passengers as possible will find that traveling by the high-speed line is faster than traveling on the alternative network.

Fig. 1

Illustration of the transportation application

There is some literature related to our two aspects of generalization: The maximal trip covering problem was introduced in Laporte et al. (2005) regarding the location of a rapid transit alignment and searching for a location which covers as many O/D pairs as possible. In this paper it was noted that in real-world situations high-speed lines compete with other modes of transportation and therefore the real coverage of a high-speed network depends on the performance of its lines in comparison with other modes. In Laporte et al. (2010, 2011), different models for the railway network design problem in the presence of a competing mode are studied.

There are also some recent papers in which traveling distances are a combination of planar and network distances (Carrizosa and Rodríguez-Chía 1997; Körner and Schöbel 2010; Pfeiffer and Klamroth 2008). Their goal is to locate one or several points so that the sum of all combined distances from the given points is minimized, i.e. these studies deal with the well-known Weber problem under a new metric. In contrast to these papers our goal is to cover O/D-pairs. Some efforts have recently been made to determine the City Voronoi diagram for a set of points in the context of combination of the planar distance l ₁ with the network distance (Abellanas et al. 2003; Bae et al. 2009; Görke et al. 2008). In these models travelers can enter the network at any point. The same holds for the models considered in Cardinal et al. (2008) for locating a high-speed transportation device and in Abellanas et al. (2008), which deals with the Voronoi diagram for the heavy luggage metric.

The remainder of this paper is structured as follows. We first present a formal description of our model and introduce the notation needed. In Sect. 3 we develop a solution approach for the case of two facilities both in segments and tree networks. In the case of locating more than two facilities on a single straight line we suggest a geometric branch and bound approach in Sect. 4. Although this is a methodological paper rather than a computational one, Sect. 5 is devoted to showing some numerical results. The paper finishes with some conclusions and hints for further research.

2 Problem formulation and notation

Our problem makes use of the following input data and notation:

• Let $\mathcal{A}=\{A_{i}=(a_{i},b_{i}) \in\mathbb{R}^{2}:i=1,\ldots,n\}$ be a set of n points on the plane. In practical applications $\mathcal{A}$ might be a set of users, towns, cities, or centroid points of transportation zones in an urban area.

• We assume that the time for traveling between two points in the plane can be estimated by a metric. In this paper we use the Euclidean metric.

• Let T=(t _ij )∈ℝ^n×n be a matrix in which trip patterns are codified, i.e. t _ij is the weight of the ordered pair (A _i ,A _j ). Note that t _ij is a parameter known a priori. In the transportation case, t _ij can be seen as the number of trips from an origin i to a destination j. In the telecommunication setting, t _ij could represent the amount of data transferred from server i to server j.

• Let ${\mathcal{N}}(V,E)$ be the network representing the high-speed system. Each vertex v∈V represents a junction or a node, and each edge e∈E has a length l _e and is assumed to be rectifiable. We suppose that ${\mathcal{N}}(V,E)$ is embedded in the Euclidean plane. Let ${\mathcal{N}}$ be the continuum set of points on the edges. The edge lengths induce a distance function d on ${\mathcal{N}}$. For any two points $x,y\in{ \mathcal{N}}$, d(x,y) is the length of any shortest path connecting x and y.

• For any two points $x,y\in{ \mathcal{N}}$ let us define the high-speed distance $d_{\mathcal{N}}(x,y)=\alpha d(x,y), \alpha\in(0,1)$. It is straightforward that ${\mathcal{N}}$ is a metric space with this distance. Parameter α is a speed factor: the lower α, the faster is traveling on $\mathcal{N}$ with respect to traveling on the plane.

• Let D=(d _ij )∈ℝ^n×n be a (symmetric) matrix with 0≤d _ij <∥A _i −A _j ∥₂. These values represent acceptance levels for using the network, meaning that the O/D pair (i,j) would choose the high-speed network if and only if the traveling time by using it is less than or equal to d _ij .

We aim to locate m facilities $\mathcal{X}=\{X_{1},\ldots,X_{m}\}\subset\mathcal{N}\subset\mathbb{R}^{2}$ so that the use of the high-speed network is maximized.

Consider an O/D pair (i,j). If the set of facilities $\mathcal{X}=\{X_{1},\ldots,X_{m}\}$ is given, a user of the high-speed network $\mathcal{N}$ has to choose an entry point $X_{k} \in \mathcal{X}$ and an exit point $X_{l} \in\mathcal{X}$. For methodological purposes, from now on we will consider $\mathcal{X}$ as an ordered set, therefore denoted by $\mathcal{X} = (X_{1},\ldots,X_{m})$ (for convenience also referred to as m-facility point). The length of the path (A _i ,X _k ,X _l ,A _j ) is denoted by $h_{ij}^{kl}(\mathcal{X})$ and equal to

$$h_{ij}^{kl}:=h_{ij}^{kl}(\mathcal{X}):=\|A_i-X_k\|_2 + d_{\mathcal {N}}(X_k,X_l)+ \|X_l-A_j\|_2.$$

We will propose two ways to calculate the traveling time through the network, because a user may prefer to access and exit the high-speed line either via the nearest facilities or via those that minimize the overall distance. Whether a user will utilize the network $\mathcal{N}$ or not may depend on this choice.

• Minimal distance to the facilities.

  First, we assume that users enter the high-speed network at the closest facility to their origin and exit at the closest facility to their destination. Let

  $$P_{\mathcal{X}}(A_i):= \Bigl\{X\in\mathcal{X}:X=\arg \min_{X\in \mathcal{X}}\bigl\{\|A_i-X\|_2\bigr\} \Bigr\}$$

  be the set of the closest facilities to the point A _i . (Note that usually $P_{\mathcal{X}}(A_{i})$ contains only one facility.) The distance from A _i to A _j is then defined as

  $$ f_{ij}^1(\mathcal{X}):=\min_{X_k\in P_{\mathcal{X}}(A_i) \atop X_l\in P_{\mathcal{X}}(A_j)}\bigl\{\|A_i-X_k\|_2 + d_{\mathcal{N}}(X_k,X_l)+ \| X_l-A_j\|_2\bigr\}=\min_{X_k\in P_{\mathcal{X}}(A_i) \atop X_l\in P_{\mathcal{X}}(A_j)} h_{ij}^{kl}.$$

  (1)

Remark 1

In the definition of $P_{\mathcal{X}}(A_{i})$ we only take into account the facility or facilities that exactly yield the minimum distance to A _i . Therefore, we do not consider facilities that are further from A _i than the minimum by an ε factor. In a passenger transportation framework this is not realistic, as passengers sometimes use another more distant station if reaching the said takes only, say, 15 seconds more than the closest one. This could be solved by alternatively defining

In this case the assertion that usually $P_{\mathcal{X}}(A_{i})$ contains only one facility is not necessarily true.

• Minimal overall distance.

  In this case users choose their entry and exit points in such a way that the overall distance of their trip is minimized. Therefore, the distance from A _i to A _j using the network is

  $$ f_{ij}^2(\mathcal{X}):=\min_{X_k,X_l\in \mathcal{X}}\bigl\{\|A_i-X_k\|_2 + d_{\mathcal{N}}(X_k,X_l)+ \|X_l-A_j\|_2\bigr\} =\min_{X_k,X_l\in\mathcal{X}}h_{ij}^{kl}.$$

  (2)

Note that $f_{ij}^{2}(\mathcal{X}) \leq f_{ij}^{1}(\mathcal{X})$ for any $\mathcal{X}$. The acceptance levels d _ij lead to the following definition.

Definition 1

Given d _ij with 0≤d _ij <∥A _i −A _j ∥₂, the O/D pair (i,j) is covered by the facilities $\mathcal{X}$ with respect to function $f_{ij}^{r},r=1,2$, if

$$f_{ij}^r(\mathcal{X})\leq d_{ij}.$$

Note that this definition leads to different conditions for the two cases r=1 and r=2, because we can only be ensured that $f_{ij}^{2}(\mathcal{X})\leq f_{ij}^{1}(\mathcal{X})$. We want to maximize the number of covered pairs given as

$$F^r(\mathcal{X})=\sum_{(i,j): f_{ij}^r \leq d_{ij}}t_{ij},\quad r\in\{1,2\}.$$

Summarizing, the problem considered in this paper can now be stated:

OD-pair location problem

Given a high-speed network ${\mathcal{N}}$, demand points $\mathcal{A}$, function f ^r with r∈{1,2}, trip patterns T and acceptance levels D, find an m-facility point $\mathcal{X}=(X_{1},\ldots,X_{m}) \in{ \mathcal{N}}^{m}$ such that the number $F^{r}(\mathcal{X})$ of covered trips is maximized. In short,

$$ \max_{\mathcal{X} \in\mathcal{N}^m}\,F^r(\mathcal{X}).$$

(3)

This problem always has an optimal solution, since the feasible region is non-empty and the objective function can only take a finite number of finite values.

Remark 2

If d _ij =d _ji we can assume t _ij =0 for i≥j since both the Euclidean and the network distances are metrics. The reason is that an O/D pair (i,j) is covered by $\mathcal{X}$ if and only if (j,i) is covered by $\mathcal{X}$. We then use the matrix $T'=(t'_{ij})$ with $t'_{ij}=t_{ij}+t_{ji}$ for i<j and $t'_{ij}=0$ for i≥j, instead of T.

We conclude this section by providing some special properties for the case where the network $\mathcal{N}$ is a straight line segment. Note that in this case we can assume that $d_{\mathcal{N}}(X_{k},X_{l}) = \alpha\cdot\|X_{k}-X_{l}\|_{2}$ for every pair of facilities $X_{k}, X_{l} \in\mathcal{L}$. For this case, given an O/D pair (i,j) and two facilities X _k and X _l we will show that it is possible to predict whether $h_{ij}^{kl}$ or $h_{ij}^{lk}$ applies (see Theorem 1), that is, which will be the entry facility and which will be the exit facility.

In order to build easy-to-read proofs, we assume without loss of generality the line segment $\mathcal{L}=[0,L]\times\{0\}$ (otherwise rotate, translate, and scale the coordinate system). Only for simplicity we sometimes write $\mathcal{L}=[0,L]$ although $\mathcal{L}\subset\mathbb{R}^{2}$.

For each point $A_{i}=(a_{i},b_{i})\in\mathcal{A}$ we assume that 0≤a _i ≤L and we define its projection on the line segment $\mathcal{L}$ as

$$\mathcal{P}_{\mathcal{L}}(A_i) = \arg\min_{X \in\mathcal{L}}\|A_i-X\|_2 \in \mathcal{L}.$$

Note that $\mathcal{P}_{\mathcal{L}}(A_{i})$ is a single point since the Euclidean norm is strictly convex and $\mathcal{L}$ is a segment.

In the next theorem we prove that if A _i is left of A _j and the O/D pair (i,j) is covered by $\mathcal{X} = (X_{k}, X_{l})$, then the entry facility X _k must be left of the exit facility X _l .

Theorem 1

Let $\mathcal{L}$ be a line segment, $\mathcal{X}=(X_{1},\ldots,X_{m})$ an m-facility point located on $\mathcal{L}=[0,L]$, and $\mathcal{A}=\{A_{i}=(a_{i},b_{i}): i=1, \dots,n\}$ a set of points such that a _i ≤a _j for all i≤j.

Then, for any O/D pair (i,j) with i<j and any pair of facilities $X_{k}=(x_{k},0), X_{l}=(x_{l},0) \in\mathcal{X}$ satisfying $h^{kl}_{ij} \leq d_{ij}$ we have $\mathcal{P}_{\mathcal {L}}(A_{i})\ne\mathcal{P}_{\mathcal{L}}(A_{j})$. Besides, we have x _k <x _l .

Proof

First, assume that $\mathcal{P}_{\mathcal{L}}(A_{i})=\mathcal{P}_{\mathcal {L}}(A_{j})= S \in\mathcal{L}$. Then we obtain

Hence, $h^{kl}_{ij} \leq d_{ij}$ implies $\mathcal{P}_{\mathcal {L}}(A_{i}) \ne\mathcal{P}_{\mathcal{L}}(A_{j})$.

By contradiction, assume that x _l ≤x _k . Since $\mathcal {P}_{\mathcal{L}}(A_{i}) \ne\mathcal{P}_{\mathcal{L}}(A_{j})$ there exists $X=(x,0) \in\mathcal{L}$ such that $\mathcal{P}_{\mathcal{L}}(A_{i})$ lies on the left of X and $\mathcal{P}_{\mathcal{L}}(A_{j})$ lies on the right of X. The four possible cases can be distinguished: x _l ≤x _k <x, x<x _l ≤x _k , x _l <x<x _k , and x _l =x _k . In the first case ∥X _l −A _j ∥₂≥∥X _k −A _j ∥₂. Hence

which contradicts the assumption $h^{kl}_{ij}\leq d_{ij}$. Analogously, in all remaining cases we obtain a contradiction with the assumption $h^{kl}_{ij} \leq d_{ij}$. Hence, neither x _l <x _k nor x _l =x _k can be true. We obtain x _k <x _l . □If we assume that the optimal m-facility point $\mathcal{X}=(X_{1},\ldots,X_{m})\in\mathcal{L}^{m}$ with X _i =(x _i ,0) satisfies x ₁<⋯<x _m , we can reformulate Theorem1 as follows:

$$h_{ij}^{kl}({\mathcal{X}}) \leq d_{ij} \quad \mbox{and}\quad i < j \quad \Rightarrow\quad k < l.$$

Under this assumption, and for each (i,j):i<j and r∈{1,2}, we can simplify the calculation of $f^{r}_{ij}$ since only $h_{ij}^{kl}$ or $h_{ij}^{lk}$ has to be considered, namely that with k<l, as stated in the following corollary.

Corollary 1

Assume the points $\mathcal{A}=\{A_{i}=(a_{i},b_{i}): i =1, \dots,n\}$ such that a _i ≤a _j for all i≤j and let $\mathcal{X}=(X_{1},\ldots,X_{m}) \in\mathcal{L}^{m}$ with X _i =(x _i ,0) and x ₁<⋯<x _m . Then

$$f_{ij}^1({\mathcal{X}}) = \min_{{X_k\in P_{\mathcal{X}}(A_i) \atop X_l\in P_{\mathcal{X}}(A_j)} \atop k < l}h_{ij}^{kl}({\mathcal{X}}) \quad \textrm{and}\quad f_{ij}^2({\mathcal{X}}) = \min_{k < l}h_{ij}^{kl}({\mathcal{X}}).$$

Corollary 1 is particularly helpful for the case m=2, which is done next.

3 The level set covering method for m=2 facilities

In this section we will consider two cases: First, we analyze the case where the two facilities are to be located on the same edge of the network, which is equivalent to locating the facilities on a straight-line segment. We will then extend the approach to locating two facilities on a tree network. Note that this method cannot be directly extended to a general network since the distance between pairs of points on a general network is not a convex function. We start by providing some general results for the case of m=2 new facilities.

If only two facilities X ₁ and X ₂ are to be located on $\mathcal{N}$, the following lemma shows the analogies between distances $f^{1}_{ij}$ and $f^{2}_{ij}$, as defined in (1) and (2), respectively.

Lemma 1

Let $\mathcal{X}=(X_{1},X_{2}) \in\mathcal{N}^{2}$. Then the O/D pair (i,j) is covered using $f^{1}_{ij}(\mathcal{X})$ if and only if (i,j) is covered using $f^{2}_{ij}(\mathcal{X})$. Besides, if (i,j) is covered, then $f^{1}_{ij}(\mathcal{X}) =f^{2}_{ij}(\mathcal{X})$.

Proof

The proof is divided into two cases.

• Suppose (i,j) is covered using $f^{1}_{ij}$. Since $f^{2}_{ij}(\mathcal{X})\leq f^{1}_{ij}(\mathcal {X})$, we have $f^{2}_{ij}(\mathcal{X})\leq f^{1}_{ij}(\mathcal{X})\leq d_{ij}$. Hence, (i,j) is also covered using $f^{2}_{ij}$.

• Suppose (i,j) is covered using $f^{2}_{ij}$. Without loss of generality assume that $f^{2}_{ij}(\mathcal{X})=h_{ij}^{12}(\mathcal{X})$, otherwise rename the facilities.

  If $X_{1}\in P_{\mathcal{X}}(A_{i})$ and $X_{2} \in P_{\mathcal{X}}(A_{j})$, then we have $f_{ij}^{1}(\mathcal{X})\leq f_{ij}^{2}(\mathcal{X})$, hence (i,j) is covered using $f_{ij}^{1}$ and $f^{2}_{ij}(\mathcal{X}) = f^{1}_{ij}(\mathcal{X})$. We will see that other cases are not possible.

  Let us assume that at least one of the inclusions $X_{1}\in P_{\mathcal{X}}(A_{i})$ or $X_{2} \in P_{\mathcal{X}}(A_{j})$ is not true, say $X_{1}\notin P_{\mathcal{X}}(A_{i})$. Then $\{X_{2}\} =P_{\mathcal{X}}(A_{i})$, i.e. ∥A _i −X ₂∥₂<∥A _i −X ₁∥₂, and therefore

  

  which means that (i,j) is not covered using $f_{ij}^{2}$, in contradiction with the assumption of (i,j) being covered by $f_{ij}^{2}$.

 □

Due to Lemma 1, F ¹=F ² for the case of locating two new facilities, and we therefore make use of the simplified notation

$$F(\mathcal{X})=F^1(\mathcal{X})=F^2(\mathcal{X})$$

in the case of m=2. The next definition gives the distance of the best option between the trip using the high-speed network and the direct trip.

Definition 2

For $\mathcal{A}=\{A_{i}=(a_{i},b_{i}): i =1, \dots,n\}$ and $\mathcal{X}=(X_{1},X_{2}) \in\mathcal{N}^{2}$ we define

The following necessary and sufficient condition for an O/D pair to be covered trivially follows:

Lemma 2

The O/D pair (i,j) is covered by the 2-facility point $\mathcal{X}=(X_{1},X_{2}) \in\mathcal{N}^{2}$ using the functions $f_{ij}^{1}$ or $f_{ij}^{2}$ if and only if $\overline{f_{ij}}(X_{1},X_{2})\leq d_{ij}$.

3.1 The case of a straight-line segment

In this section we deal with the problem of locating m=2 new facilities on a straight line. We use the fact that we can order the two new facilities (from left to right along the line), hence the problem is given as follows.

OD-pair location on a line (m=2)

Given a straight line ${\mathcal{L}}$, demand points $\mathcal{A}$, trip patterns T and acceptance levels D, find an (m=2)-facility point $\mathcal{X}= (X_{1},X_{2}) \in{ \mathcal{L}}^{2}$ such that the number of covered trips $F(\mathcal{X})$ is maximized. In short,

$$ \max_{\mathcal{X} \in\mathcal{L}^2}\,F(\mathcal{X}).$$

(4)

As before we may assume $\mathcal{L}=[0,L]\times\{0\}$. Hence the objective is to locate two facilities X ₁=(x ₁,0) and X ₂=(x ₂,0) on $\mathcal{L}$ with x ₁≤x ₂. For the sake of readability, we will write $\bar{f}_{ij} (x_{1}, x_{2})$ and $h_{ij}^{kl}(x_{1},x_{2})$ to denote $\overline{f_{ij}}(X_{1}, X_{2})$ and $h_{ij}^{kl}(X_{1},X_{2})$, respectively. Therefore both functions depend on two variables when $\mathcal{N}$ is a straight-line segment, and not on four variables as in the general case. Note that for this case, $h_{ij}^{kl}(\mathcal{X})$ is either $h^{12}_{ij}(\mathcal{X})$ or $h^{21}_{ij}(\mathcal{X})$, and according to Theorem 1 we know that $h_{ij}^{12}(\mathcal{X}) \leq h^{21}_{ij}(\mathcal{X})$ if and only if a _i <a _j . From now on we will assume a _i ≤a _j ∀ i<j. Now two technical results that will help us later on are presented.

Lemma 3

For any pair i,j∈{1,…,n} and any η>0 the level set

$$S_{ij}(\eta):=\bigl\{(x_1,x_2)\in[0,L]\times[0,L]:\overline {f_{ij}}(x_1,x_2)\leq \eta\bigr\}$$

is convex.

Proof

Let η>0 and assume a _i <a _j . We consider two cases.

• If η<∥A _i −A _j ∥₂, and because Theorem 1 implies x ₁<x ₂, we have $\overline{f_{ij}}(x_{1},x_{2}) \leq\eta$ if and only if

  $$h^{12}_{ij}(x_1,x_2)=\bigl\|A_i- (x_1,0)\bigr\|_2+\alpha\cdot \bigl\|(x_1,0)-(x_2,0)\bigr\|_2+\bigl\|(x_2,0)-A_j\bigr\|_2 \leq\eta.$$

  Let us define $h_{ij} = \min\{h_{ij}^{12},h_{ij}^{21}\}$. Hence S _ij (η)={(x ₁,x ₂)∈[0,L]×[0,L]:h _ij (x ₁,x ₂)≤η}. Because in this case $h_{ij}=h^{12}_{ij}$, h _ij is a convex function in [0,L]×[0,L], and S _ij (η) is a convex set.

• If η≥∥A _i −A _j ∥₂ we obtain S _ij (η)=[0,L]×[0,L] which is convex.

 □

The convexity of the level sets implies the quasiconvexity of the corresponding function, see Márquez-Diez-Canedo (1987).

Corollary 2

The functions $\overline{f_{ij}}(x_{1},x_{2})$ are quasiconvex for all i,j∈{1,…,n}, i.e. we have

$$\overline{f_{ij}}\bigl(\lambda\mathcal{X} + (1 - \lambda)\mathcal{Y}\bigr)\leq \max \bigl\{\overline{f_{ij}}(X),\overline{f_{ij}}(Y)\bigr\}, \quad \forall\ i,j,$$

for all $\mathcal{X}=(x_{1},x_{2}),\mathcal{Y}=(y_{1},y_{2})\in[0,L]\times [0,L]$ and λ∈[0,1].

In the following we will use

to denote the set of facilities $(x_{1},0),(x_{2},0)\in\mathcal{L}$ which cover the O/D pair (i,j) and its level curve, respectively. Note that all sets S _ij are convex, and that some of them may be empty. If the intersection of two level curves, say C _ij and C _i′j′, is nonempty it consists of (at least) one pair of facilities that cover the demand of both (ordered) pairs (A _i ,A _j ) and (A _i′,A _j′). This yields the following characterization of optimal solutions.

Theorem 2

Let

$$C=\bigcup_{(i,j),(i',j')\atop(i,j)\ne(i',j')} C_{ij} \cap C_{i'j'}.$$

Then (at least) one of the following three cases occurs:

• C contains (at least) one optimal solution to Problem (4).

• There exists an O/D pair (i,j) such that any point of the level set S _ij is optimal.

• Any point in [0,L]×[0,L] is optimal.

Proof

Let $\mathcal{X}=(X_{1}=(x_{1},0),X_{2}=(x_{2},0))$ be an optimal solution to Problem (4) and define

Note that $G(\mathcal{X})$ is non-empty. Moreover, all points in $G(\mathcal{X})$ yield the same objective value as $\mathcal{X}$. Hence all points of $G(\mathcal{X})$ are optimal solutions. We distinguish three cases:

• 1. If $O(\mathcal{X})= \emptyset$ all points in [0,L]×[0,L] are optimal, and therefore the objective function value is equal to zero.

• 2. If $G(\mathcal{X})=S_{ij}$ for some pair $(i,j) \in O(\mathcal{X})$ all points in S _ij are optimal, since all points in $G(\mathcal{X})$ yield the same objective value.

• 3. If $O(\mathcal{X})$ is non-empty and there is no pair (i,j) such that $G(\mathcal{X})=S_{ij}$, then $G(\mathcal{X})$ is the intersection of at least two different level sets. Since all S _ij are closed convex (see Lemma 3), we have that $G(\mathcal{X})$ is convex. Hence, the boundary of $G(\mathcal{X})$ must contain at least one point $\mathcal{Y} = (Y_{1}=(y_{1},0),Y_{2}=(y_{2},0)) \in C_{ij} \cap C_{i'j'}$ for some O/D pairs (i,j) and (i′,j′). Consequently, $\mathcal{Y}=(Y_{1},Y_{2}) \in C$ is an optimal solution to Problem (4).

 □

In accordance with Bezout’s theorem (see Kirwan, 1992) the equation of the intersection of C _ij and C _i′j′ has at most 4² roots, but four of them are at infinity. The remaining twelve solutions could be multiple and/or complex. Therefore, an immediate consequence of Theorem 2 is that there exists a finite dominating set for our problem.

Corollary 3

Let B⊂[0,L]×[0,L] be a set containing exactly one point of each level set S _ij and let C be the set defined in Theorem 2. Then CAND:=C∪B∪{(0,0)} is a finite dominating set for Problem (4).

Proof

Due to the three cases of Theorem 2, at least one optimal solution to Problem (4) is contained in CAND. From Bezout’s theorem we may conclude that the intersection of two level curves C _ij and C _i′j′ contains at most 16 points. Consequently, the set C is finite. Moreover, B is a finite set since we have a finite number of level sets S _ij . Finally note that we need the point (0,0) due to the third case of Theorem 2, because in this case both B and C are empty. To sum up, CAND is a finite dominating set for (4). □

If the input size, i.e. the number of demand pairs, is N=O(n ²) the number of intersections is O(N ²). Hence the complexity of the finite dominating set CAND is O(KN ²), where K is an upper bound on the number of finite intersection points between two level sets C _ij and C _i′j′. As mentioned above, an upper bound for K is 16 but in our numerical experience we saw this constant was always lower than or equal to 4. Using Corollary 3, Algorithm 1 (see below) solves Problem (4) in O(N ³) time, since evaluating F in step 5(a) takes O(N) and the inclusion test for each pair can be done in constant time, cf. e.g. Preparata and Shamos (1985).

Algorithm 1

(Maximum pair covering algorithm in a segment)

Input::

A set of points $\mathcal{A}=\{A_{i}=(a_{i},b_{i}):i=1,\ldots,n\}\subset\mathbb{R}^{2}$ with a _i ≤a _j ∀ i<j, a segment of length L, a demand matrix T=(t _ij ), the high-speed factor of the line α∈(0,1), and the matrix D=(d _ij ) with 0≤d _ij <∥A _i −A _j ∥₂ for 1≤i,j≤n.

• 1. Set C=∅.

• 2. For each O/D pair (i,j) with i<j compute C _ij , the level curve of $\overline{f_{ij}}$.

• 3. For each pair of O/D pairs {(i,j),(i′,j′)} compute the intersection between C _ij and C _i′j′. Set C=C∪(C _ij ∩C _i′j′).

• 4. If C _ij ∩C _i′j′=∅ and C _ij ,C _i′j′≠∅ apply an inclusion test:

  • (a) If C _ij is inside C _i′j′ (or C _i′j′ inside C _ij ), then take one point of C _ij (or C _i′j′) and add it to C, respectively.

  • (b) Otherwise take one point of C _ij and one of C _i′j′ and add it to C.

• 5.

  • (a) If C≠∅, then evaluate the objective function F(x ₁,x ₂) on every point (x ₁,x ₂)∈C and choose a maximum. Let $(X_{1}^{*}, X^{*}_{2})$ be such maximum, with $X_{1}^{*} =(x_{1}^{*},0), X^{*}_{2} = (x_{2}^{*},0)$.

  • (b) Otherwise, choose any pair $X_{1}^{*},X_{2}^{*}\in\mathcal{L}$.

Output::

Two facilities $X_{1}^{*},X_{2}^{*} \in\mathcal{L}$ solving problem (4).

Example 1

Two facilities are to be located on the line segment $\mathcal{L}=[0,5]$ to cover five sites corresponding to the following coordinates:

Let us assume that the O/D matrix is

$$T=\left ( \begin{array}{c@{\quad }c@{\quad }c@{\quad }c@{\quad }c}0 & 46 & 27 & 90 & 75 \\0 & 0 & 70 & 47 & 46 \\0 & 0 & 0 & 25 & 74 \\0 & 0 & 0 & 0 & 46 \\0 & 0 & 0 & 0 & 0\end{array} \right ).$$

Furthermore, we used the high-speed factor α=0.5 and the acceptance values d _ij =0.98⋅∥A _i −A _j ∥₂, i.e. we assume that the high-speed line will be chosen if at least 2% of traveling time is saved.

Each level set S _ij is given by the solution set of the inequality $\overline{f_{ij}}\leq d_{ij}$; that is, each point (x ₁,x ₂)∈S _ij has to satisfy the inequality

$$\sqrt{ (a_i-x_1)^2 +b_i^2} + \alpha(x_2-x_1) + \sqrt {(a_j-x_2)^2 + b_j^2}\leq d_{ij}.$$

Due to Theorem 1 all level sets are contained in the upper left triangle of [0,5]×[0,5]. The intersection of the level sets S ₁₄, S ₁₅, S ₂₃, and S ₂₄ is the set of points (x ₁,x ₂) that maximize the trip coverage, meaning that any (x ₁,x ₂) in this set covers the pairs (1,4), (1,5), (2,3), (2,4), yielding an optimal objective value equal to 282, see Fig. 2.

Fig. 2

Non-empty coverage regions for Example 1

So, for instance, locating one station at (1.5,0) and the other at (3,0) is an optimal solution (because (1.5,3) belongs to the optimal region depicted as the gray area in Fig. 2).

3.2 The case of a tree network

In this section we will deal with the problem of locating two facilities on a given tree network $\mathcal{T}(V,E)$, stated as follows.

OD-pair location on a tree (m=2)

Given a high-speed tree network ${\mathcal{T}}$, demand points $\mathcal{A}$, trip patterns T and acceptance levels D, find an (m=2)-facility point $\mathcal{X}=(X_{1},X_{2}) \in {\mathcal{T}}^{2}$ such that the number of covered trips $F(\mathcal{X})$ is maximized. In short,

$$ \max_{\mathcal{X} \in\mathcal{T}^2}\,F(\mathcal{X}).$$

(5)

Since the problem of locating two facilities on the same edge coincides with that in the previous subsection, we will now study the case in which the facilities are to be located on different edges. Thus, this restricted problem can be formulated as follows.

OD-pair location on an edge-pair of a tree (m=2)

Given a high-speed tree network ${\mathcal{T}}$ with two specified edges e _p and e _q ($e_{p} \not= e_{q}$), demand points $\mathcal{A}$, trip patterns T and acceptance levels D, find an (m=2)-facility point $\mathcal{X}=(X_{1},X_{2}) \in e_{p} \times e_{q}$ such that the number of covered trips $F(\mathcal{X})$ is maximized. In short,

$$ \max_{\mathcal{X} \in e_p\times e_q}\,F(\mathcal{X}).$$

(6)

As usual, $F(\mathcal{X})=\sum_{(i,j)\in G(\mathcal{X})}t_{ij}$ and we do not need to distinguish between F ¹ and F ² since we still consider the case m=2. Our goal is to adapt the Maximum Pair Covering Algorithm of the previous subsection.

In Dearing et al. (1976), a path convex combination of two points Y and Z in a tree is defined as follows:

Definition 3

Let Y,Z be two points on a tree and let p(Y,Z) be the unique path from Y to Z. X is a path convex combination of Y and Z along p(Y,Z) with respect to λ∈[0,1] if

• X∈p(Y,Z), and

• $d_{\tau}(Y,Z)=\lambda d_{\mathcal{\tau}}(Y,Z)$.

(Note that in this case we have d _τ (X,Z)=(1−λ)d _τ (Y,Z).)

Note as well that this notion of path convex combination is different from the usual convex combination concept in the plane (see Fig. 3).

Fig. 3

The point X is a path convex combination of Y and Z with respect to $\lambda=\frac{1}{3}$ while X′ is a convex combination of Y and Z with respect to $\lambda=\frac{1}{3}$

Thus, the segment joining two pairs of points $\mathcal{Y}=(Y_{p},Y_{q}),\mathcal{Z}=(Z_{p},Z_{q})$ in e _p ×e _q is $\mathcal{PS}(\mathcal{Y},\mathcal{Z}) = \bigcup_{\lambda\in[0,1]} \{ \mathcal{X}=(X_{p}, X_{q}) \in e_{p} \times e_{q} : d(Y_{i},X_{i}) + d(X_{i}, Z_{i}) = d(Y_{i}, Z_{i}) ; d(X_{i},Z_{i}) =\lambda d(Y_{i}, Z_{i}), i \in\{p,q\}\}$, where $\mathcal{PS}$ stands for path segment. Thus, a function is path convex on e _p ×e _q if $f(\mathcal{X}) \leq\lambda f(\mathcal{Y}) + (1-\lambda )f(\mathcal{Z}), \ \forall\ \mathcal{X} \in\mathcal{PS}(\mathcal{Y},\mathcal{Z}), \ \forall\ \lambda\in[0,1]$. See Dearing et al. (1976) for more details, where it is proven that $d_{\mathcal{N}}$ is convex in $\mathcal{N} \times\mathcal{N}$ if and only if $\mathcal{N}$ is a tree. As a consequence d _τ (⋅ ,⋅) is a convex function for (Y,Z)∈e _p ×e _q .

Normally, the used notion of convexity is clear from the context. Whenever there might be ambiguity, we will specify whether convexity or path convexity applies.

Next, we will see that Lemma 3 and Corollary 2 can be extended to the case of a tree network as follows.

Lemma 4

For any pair (i,j) and any η>0 the level set

$$S_{ij}(\eta):=\bigl\{(X_1,X_2)\in e_p \times e_q :\overline {f_{ij}}(X_1,X_2)\leq\eta\bigr\}$$

is the union of two disjoint and convex sets.

Proof

According to Definition 2 we have

$$S_{ij} (\eta) =\begin{cases}S_{ij}^{12}(\eta) \cup S_{ij}^{21}(\eta), & \textrm{if } \|A_i - A_j\|_2 > \eta, \\[5pt]e_p \times e_q, & \textrm{if } \|A_i - A_j\|_2 \leq\eta,\end{cases} $$

with

Let η>0. First note that if η≥∥A _i −A _j ∥₂ we obtain S _ij (η)=e _p ×e _q which is convex. We hence analyze the case η<∥A _i −A _j ∥₂, for which we claim:

• 1. $S_{ij}^{12}(\eta) \cap S_{ij}^{21}(\eta) = \emptyset$.

• 2. $S_{ij}^{12}(\eta)$ and $S_{ij}^{21}(\eta)$ are convex.

These two assertions are proven as follows.

• 1. Assume that $(X_{1},X_{2}) \in S_{ij}^{12}(\eta)$. Then we have

  $$h_{ij}^{12} = \|A_i-X_1\|_2+ d_{\mathcal{T}}(X_1,X_2)+\|X_2-A_j\|_2 \leq\eta< \|A_i -A_j\|_2,$$

  therefore,

  $$\|A_i-X_1\|_2+ \|X_2-A_j\|_2 < \|A_i - A_j\|_2.$$

  From this we conclude

  

  hence,

  $$\|A_i-X_2\|_2+ d_{\mathcal{T}}(X_1,X_2)+\|X_1-A_j\|_2 > \|A_i -A_j\|_2 > \eta,$$

  and so $(X_{1},X_{2}) \not\in S_{ij}^{21}$.

• 2. $h_{ij}^{12}(X_{1},X_{2}) \leq\eta$ if and only if

  $$h^{12}_{ij}(X_1,X_2)=\|A_i-X_1\|_2+ d_{\mathcal{T}}(X_1,X_2)+\|X_2-A_j\|_2 \leq\eta,$$

  hence $S^{12}_{ij}(\eta)=\{(X_{1},X_{2})\in e_{p} \times e_{q}:h^{12}_{ij}(X_{1},X_{2})\leq\eta\}$. Since, ∥A _i −X ₁∥₂ and ∥X ₂−A _j ∥₂ are path convex functions on e _p and e _q , respectively, and $d_{\mathcal {T}}(X_{1},X_{2})$ is convex on the convex set e _p ×e _q then $h^{12}_{ij}$ is a convex function on e _p ×e _q , and therefore $S^{12}_{ij}(\eta)$ is a convex set. The convexity of $S_{ij}^{21}(\eta)$ can be proven analogously.

 □

Corollary 4

The functions $h^{12}_{ij}(X_{1},X_{2})$ and $h^{12}_{ij}(X_{1},X_{2})$ are quasiconvex on e _p ×e _q .

Remark 3

We remark that the level set in Lemma 4 cannot be taken for any pair $(X_{1},X_{2}) \in \mathcal{T}$ although $d_{\mathcal{T}}(X_{1},X_{2})$ is still path convex in this case (see Dearing et al., 1976). The reason for this is that path convex combinations are not the same as convex combinations for arbitrary X ₁,X ₂ on a tree (see Fig. 3), meaning that the convexity of function h _ij would be lost if X ₁ and X ₂ vary on a tree.

In order to get a computable representation we parametrize the two edges e _p and e _q such that

with T _p ,T _q ,s _p ,s _q ∈ℝ² and g _p (0)=T _p ,g _q (0)=T _q . Note that T _p , s _p , T _q and s _q are the starting points and directions of edges e _p and e _q , respectively. We hence see that Problem (6) is a continuous two-dimensional problem formulated as

$$ \max_{(\lambda_p,\lambda_q) \in[0,1]^2}\,F\bigl(g_p(\lambda_p),g_q(\lambda_q)\bigr)$$

(7)

and the level set S _ij :=S _ij (d _ij ) is given as

$$S_{ij} := \bigl\{ (\lambda_p, \lambda_q)\in[0,1]^2: \overline{f_{ij}}\bigl(g_p(\lambda_p),g_q(\lambda_q)\bigr) \leq d_{ij} \bigr\}.$$

We now transfer the result of Lemma 4 to this two-dimensional representation.

Corollary 5

The level set $S_{ij} = S_{ij}^{12} \cup S_{ij}^{21} \subseteq\mathbb{R}^{2}$ is the union of two disjoint and convex sets, $S^{12}_{ij}, S_{ij}^{21}$.

Proof

We know that $h_{ij}^{12}, h_{ij}^{21}: e_{p} \times e_{q} \to\mathbb{R}$ are quasiconvex according to Corollary 4, and that g=(g _p ,g _q ):[0,1]²→e _p ×e _q is linear, hence their compositions $h_{ij}^{12} \circ g, h_{ij}^{21} \circ g$ are quasiconvex, yielding the convexity of

Since for η<∥A _i −A _j ∥ we have

we obtain

$$S_{ij} = S_{ij}^{12} \cup S_{ij}^{21}$$

and the result follows. □

For each pair (i,j) let $C^{12}_{ij}$ and $C_{ij}^{21}$ be the boundaries of the sets $S_{ij}^{12}$ and $S_{ij}^{21}$. This gives us all we need to prove the following statement similar to Theorem 2.

Theorem 3

Let

$$C=\bigcup_{(i,j),(i',j'), (i,j)\ne(i',j')\atop(k,l),(k',l') \in\{(1,2),(2,1)\}} C^{kl}_{ij}\cap C^{k'l'}_{i'j'}.$$

Then (at least) one of the following three cases occurs:

• C contains (at least) one optimal solution to Problem (6).

• There exists an O/D pair (i,j) and (k,l)∈{(1,2),(2,1)} such that any point of the level set $S^{kl}_{ij}$ is optimal.

• Any point in [0,1]×[0,1] is optimal.

Again in accordance with Bezout’s theorem (see Kirwan, 1992) the equation of the intersection of $C_{ij}^{kl}$ and $C_{i'j'}^{k'l'}$ has at most 4² roots, but four of them are at infinity. The remaining twelve solutions could be multiple and/or complex. Therefore, we again obtain a finite dominating set.

Corollary 6

Let B⊂[0,1]×[0,1] be a set containing exactly one point of each set $S^{12}_{ij}$ and $S^{21}_{ij}$ and let C be the set defined in Theorem 2. Then CAND:=C∪B∪{(0,0)} is a finite dominating set for Problem (4).

In summary, Algorithm 1 can be extended to the case in which X ₁ and X ₂ are in different edges.

Algorithm 2

(Maximum pair covering algorithm for two facilities in different edges)

Input::

A set of points $\mathcal{A}=\{A_{i}=(a_{i},b_{i}):i=1,\ldots,n\}\subset\mathbb{R}^{2}$, a pair of edges e _p , e _q , a demand matrix T=(t _ij ), the high-speed factor of the line α∈(0,1), and the matrix D=(d _ij ) with 0≤d _ij <∥A _i −A _j ∥₂ for 1≤i,j≤n.

• 1. Set C=∅.

• 2. For each O/D pair (i,j), and each (k,l)∈{(1,2),(2,1)} compute the level curves $C_{ij}^{kl}$.

• 3. For each pair of O/D pairs {(i,j),(i′,j′)}, and (k,l),(k′,l′)∈{(1,2),(2,1)} compute the intersections between $C_{ij}^{kl}$ and $C_{i'j'}^{k'l'}$. Set $C=C \cup(C_{ij}^{kl}\cap C_{i'j'}^{k'l'})$.

• 4. If $C_{ij}^{kl} \cap C_{i'j'}^{k'l'}=\emptyset$ and $C^{kl}_{ij},C_{i'j'}^{k'l'} \neq\emptyset$ apply an inclusion test:

  • (a) If $C_{ij}^{kl}$ is inside $C_{i'j'}^{k'l'}$ (or $C_{i'j'}^{k'l'}$ inside $C_{ij}^{kl}$), then take one point of $C_{ij}^{kl}$ (or $C_{i'j'}^{k'l'}$) and add it to C, respectively.

  • (b) Otherwise take one point of $C_{ij}^{kl}$ and one of $C_{i'j'}^{k'l'}$ and add it to C.

• 5.

  • (a) If C≠∅, then evaluate the objective function F(g _p (λ _p ),g _q (λ _q )) on every point (λ _p ,λ _q )∈C and choose a maximum, given by $(\lambda_{p}^{*},\lambda_{q}^{*})$.

  • (b) Otherwise, choose any pair $\lambda_{p}^{*} \in[0,1],\lambda_{q}^{*}\in[0,1]$.

Output::

Two facilities $X_{1}:=g_{p}(\lambda_{p}^{*}),X_{2}:=g_{q}(\lambda_{q}^{*}) \in e_{p} \times e_{q}$ solving Problem (6).

The complexity of this algorithm is the same as Algorithm 1, O(N ³).

Note that Algorithm 2 gives a pair of points X ₁∈e _p ,X ₂∈e _q maximizing F. From Algorithms 1 and 2, a procedure that calculates a pair of facilities maximizing F on a tree network $\mathcal {T}(V,E)$ is given by the following algorithm. The idea is to iteratively apply the two previous algorithms to locate a pair of facilities on the same edge, or to locate a pair of facilities on different edges, respectively, for any possible combination of edges on the tree, to then pick the best solution. These ideas are summarized in Algorithm 3.

Algorithm 3

(Maximum pair covering algorithm for a tree network)

Input::

A set of points $\mathcal{A}=\{A_{i}=(a_{i},b_{i}):i=1,\ldots,n\}\subset\mathbb{R}^{2}$, a tree network $\mathcal{T}(V,E)$, a demand matrix T=(t _ij ), the high-speed factor of the line α∈(0,1), and the matrix D=(d _ij ) with 0≤d _ij <∥A _i −A _j ∥₂ for 1≤i,j≤n.

• 1. For each edge e _p , apply Algorithm 1. Let $(X_{1}^{p},X_{2}^{p})$ be the solution obtained.

• 2. For each pair of distinct edges e _p , e _q with p<q, apply Algorithm 2. Let $(X^{pq}_{1}, X^{pq}_{2})$ be the solution obtained.

• 3. Determine the best solution (X ₁,X ₂) of all $(X_{1}^{p},X_{2}^{p}), (X_{1}^{pq},X_{2}^{pq})$.

Output::

Two facilities $X_{1},X_{2} \in\mathcal{T}$ solving problem (5).

The complexity of this algorithm is O(MN ³+M ² N ³)=O(M ² N ³), where M=|E|.

4 The big cube small cube method for m≥2 facilities on a line segment

In this section we present an algorithm for locating m facilities along a line, i.e., we consider the following problem.

OD-pair location on a line

Given a straight line ${\mathcal{L}}$, demand points $\mathcal{A}$, trip patterns T, function f ^r with r=1 or 2, and acceptance levels D, find an m-facility point $\mathcal{X}=(X_{1},\ldots,X_{m}) \in{ \mathcal{L}}^{m}$ such that the number of covered trips $F(\mathcal{X})$ is maximized. In short,

$$ \max_{\mathcal{X} \in\mathcal{L}^m}\,F(\mathcal{X}).$$

(8)

Our approach is a modification of the big cube small cube method, see Schöbel and Scholz (2010), which is a generalization of the big square small square (BSSS for short) algorithm, see Hansen et al. (1985) and Plastria (1992).

We want to locate m facilities $\mathcal{X}=(X_{1},\ldots,X_{m})$ on the line segment $\mathcal{L}= [0,L]\times\{0\}$, using the overall minimum distance functions $f_{ij}^{2}$. Therefore, identifying X _i with its first coordinate x _i , our objective function

$$F^2(\mathcal{X})=F^2(x_1,\ldots,x_m)=\sum_{(i,j): f_{ij}^2 \leq d_{ij}}t_{ij}$$

deals with m variables.

The idea we use is based on a geometric branch-and-bound: The solution space is divided into a list of boxes. In every step, one box is selected and split into several smaller boxes. For each smaller box, an upper bound is computed and the objective function is evaluated at the center of the smaller boxes. The greatest value of the evaluated objective values is stored as incumbent. If the upper bounds of some boxes are smaller than the incumbent, these boxes can be discarded. Techniques for obtaining these bounds exist for continuous functions, in particular for d.c-functions.

However, we cannot directly apply these techniques to our problem since for counting the number of covered pairs we have to introduce a discrete variable for any O/D-pair. In the following we will demonstrate how we can nevertheless make use of well-known techniques for solving such a (partly discrete) problem.

We first show how we can make use of our knowledge for calculating bounds for the continuous functions $f_{ij}^{2}$ to derive bounds on the function F ².

Theorem 4

Assume that for each box $Z \subset\mathcal{L}^{m}$ and each pair (i,j) we have a lower bound, i.e.,

$$w_{ij}(Z) \leq f_{ij}^2(\mathcal{X}) \quad \mbox{\textit{for\ all}}\ \mathcal{X} \in Z,$$

and let P(Z)∈Z. Then we have

• 1.
  $$\mathit{LB}(Z):=F^2\bigl(P(Z)\bigr) \leq\max_{\mathcal{X} \in Z}F^2(\mathcal{X}),$$

  i.e. F ²(P(Z)) is a lower bound on the objective value on Z.

• 2.
  $$\mathit{UB}(Z):=\sum_{(i,j): w_{ij}(Z)\leq d_{ij}}t_{ij} \geq F^2(\mathcal{X}) \quad \mbox{\textit{for} \textit{all} } \mathcal{X} \in Z,$$

  i.e., UB(Z) is an upper bound on the objective value on Z.

• 3. Assume that every O/D-pair (i,j) satisfies one of the following three conditions,

  • (i) $f_{ij}^{2}(P(Z))=w_{ij}(Z)$, or,

  • (ii) $d_{ij} > f_{ij}^{2}(P(Z))$, or,

  • (iii) d _ij <w _ij (Z).

  Then UB(Z)=LB(Z), i.e., F ²(P(Z)) is the optimal value on Z.

Note that w _ij (Z) together with P form a bounding operation as defined in Scholz and Schöbel (2010), i.e., the theorem holds true for any bounding operation on Z.

Proof

Consider one box Z and let w _ij :=w _ij (Z) and P:=P(Z).

• 1. P∈Z, i.e., the objective value on Z is better than F ²(P).

• 2. Since $w_{ij} \leq f^{2}_{ij}(\mathcal{X})$ for all $\mathcal{X} \in Z$ we obtain

  $$\mathit{UB}(Z)=\sum_{(i,j):w_{ij} \leq d_{ij}} t_{ij} \geq\sum _{(i,j):f^2_{ij}(\mathcal{X}) \leq d_{ij}} t_{ij} = F(\mathcal{X}).$$
• 3.
  $$\mathit{UB}(Z) - F^2(P)=\sum_{(i,j):w_{ij} \leq d_{ij}}t_{ij} - \sum_{(i,j):f^2_{ij}(P) \leq d_{ij}} t_{ij} = \sum _{(i,j):w_{ij} \leq d_{ij} < f^2_{ij}(P)} t_{ij}.$$

  This expression becomes zero if and only if for all (i,j) we have

  $$d_{ij} \not\in \bigl[w_{ij},f^2_{ij}(P)\bigr),$$

  which is exactly the case if one of the conditions (i), (ii), (iii) applies.

 □

In order to derive a bounding operation for the functions $f^{2}_{ij}$ the whole set of possibilities used for geometric branch and bound methods can be applied, see e.g., Blanquero and Carrizosa (2009), Horst and Thoai (1999), or Scholz (2010), Scholz and Schöbel (2010) for an overview and a discussion of various methods. Having such a bounding operation at hand, the following algorithm calculates an approximate optimal solution.

Algorithm 4

(Geometric branch and bound)

Input::

A set of points $\mathcal{A}=\{A_{i}=(a_{i},b_{i}):i=1,\ldots,n\}\subset\mathbb{R}^{2}$, a segment of length L, a demand matrix T=(t _ij ), the high-speed factor of the line α∈(0,1), the matrix D=(d _ij ) with 0≤d _ij <∥A _i −A _j ∥₂ for 1≤i,j≤n.

• 1. Set $\mathcal{Z}=\{Z=[0,L]^{m}\}$, $P=(\tfrac{L}{2},\ldots,\tfrac {L}{2}) \in Z$.

• 2. Calculate LB:=F ²(P) and UB _max:=UB(Z).

• 3. Division rule: Select a box $Z \in\mathcal{Z}$ with largest upper bound UB _max=UB(Z) and split it into some smaller boxes.

• 4. Insert the smaller boxes in $\mathcal{Z}$ and delete the original box from $\mathcal{Z}$.

• 5. Evaluate the objective function at the center of each smaller box. If at least one of these values is ≥LB, update LB to the largest value and update P to the center of the associated box.

• 6. Calculate UB(Z) for all smaller boxes and update $\mathit{UB}_{\max }:=\max_{Z \in\mathcal{Z}} \mathit{UB}(Z)$.

• 7. Discarding test: Discard all boxes Z

  $$Z=[\underline{x}_1,\overline{x}_1]\times\cdots\times[\underline {x}_m,\overline{x}_m]$$

  with UB(Z)<LB from $\mathcal{Z}$. If LB has not changed we have to check only the smaller boxes. Furthermore, discard all smaller boxes with $\underline{x}_{k}>\overline {x}_{l}$ for some k<l from $\mathcal{Z}$.

• 8. Termination rule: If UB _max=LB, stop. Otherwise return to Step 3.

Output::

An optimal solution $\mathcal{X}=(x_{1},\ldots,x_{m}):=P$ containing a set of m optimal facilities (x ₁,0),…,(x _m ,0) solving Problem (4). (If required, $\mathcal{Z}$ is the set of boxes that contains $\mathcal{X}$ and might contain (other) optimal solutions.)

Note that the discarding test in Step 7 of the algorithm uses the result of Theorem 4.

We remark that no bounding operation for $f^{2}_{ij}$ yields a consistent bounding operation for the function F ², since it may happen that splitting a box into subboxes does not affect the value of F(Z). Nevertheless, due to the third point of Theorem 4, many boxes can be discarded throughout the algorithm such that it will finally stop.

We now use another feature of our problem to derive the set of all optimal solutions for (4). Most algorithms only calculate one individual solution. But sometimes the set of all optimal solutions is required. For Problem (4) we can use Lemma 3 and propose Algorithm 5, which computes a subset of all optimal solutions for the case of locating two facilities if the optimal objective value OPT of Problem (4) is known.

Algorithm 5

(Approximation of optimal solution set for m=2)

Input::

A set of points $\mathcal{A}=\{A_{i}=(a_{i},b_{i}):i=1,\ldots,n\}\subset\mathbb{R}^{2}$, a segment of length L, a demand matrix T=(t _ij ), the high-speed factor of the line α∈(0,1), the matrix D=(d _ij ) with 0≤d _ij <∥A _i −A _j ∥₂ for 1≤i,j≤n.

• 1. Solve problem (4) using Algorithm 1 or Algorithm 4.

• 2. Set $\mathcal{Z}:=\{[0,L]^{2}\}$ in case of Algorithm 1; or take the output $\mathcal{Z}$ of Algorithm 4 if this algorithm has been used in Step 1. Set $\mathcal{D}:=\emptyset$.

• 3. Split all boxes $Z\in\mathcal{Z}$ into some smaller boxes.

• 4. Add all smaller boxes to $\mathcal{Z}$ and delete the original boxes from $\mathcal{Z}$.

• 5. For all boxes $Z\in\mathcal{Z}$ do: Evaluate the functions $\overline{f_{ij}}(V_{k})$ for all i<j at the four vertexes V ₁,V ₂,V ₃,V ₄ of Z. Define

  $$r_{ij}:=\begin{cases}t_{ij}, & \textrm{if}\ \overline{f_{ij}}(V_k)< d_{ij}\ \textrm {for}\ k=1,2,3,4, \\0, & \textrm{otherwise,}\end{cases} $$

  and let

  $$R:=\sum_{i<j}r_{ij}.$$

  If R=OPT, add the box Z to $\mathcal{D}$ and delete Z from $\mathcal{Z}$.

• 6. If all boxes $Z\in\mathcal{Z}$ are small enough, stop. Otherwise return to Step 3.

Output::

A set of optimal solutions $\mathcal{D}^{*}:= \bigcup_{\mathcal{D} \in\mathcal{Z}} \mathcal{D}$ to Problem (4).

The correctness of this algorithm is justified as follows.

Lemma 5

Let $Z\in\mathcal{D}^{*}$ and $\mathcal{X}^{\ast}=(X_{1}^{\ast},X_{2}^{\ast})\in Z$. Then $\mathcal{X}^{\ast}$ is an optimal solution to Problem (4).

Proof

We have to show that all $\mathcal{X} \in Z$ are optimal solutions. Let V ₁,V ₂,V ₃,V ₄ be the four vertices of Z. From Step 5 of the algorithm we know that $\overline{f_{ij}}(V_{k})< d_{ij}~\textrm{for}~k=1,2,3,4$, in particular, V _k ∈S _ij for k=1,…,4, i<j. Since S _ij is convex according to Lemma 3, the complete box Z is in S _ij and the result follows. □

5 Case study and experimental results

We first use Algorithm 4 to analyze the example presented in the introduction for the case 2≤m≤4.

Example 2

The n=12 demand points are given by the data in Table 1 (note that all coordinates have been rotated and translated so that Sevilla (point A ₁) coincides with the origin and Córdoba (point A ₁₂) is on the x-axis). Furthermore, we used the Euclidean distance d ₂, the high-speed factor α=0.5, the line segment $\mathcal{L}=[0,112]$, and the acceptance values

$$d_{ij}=0.9\cdot d_2(A_i,A_j).$$

The trip patterns are estimated by T=(t _ij ) using the gravitation rule, see Ortúzar and Willumsen (2001), as follows:

$$t_{ij} = \tau\cdot\frac{p_i\cdot p_j}{d_2^2(A_i,A_j)},\quad \mbox{and} \quad \tau=0.00016029$$

for i<j and t _ij =0 otherwise. Here, p _i is the population of city A _i , see Table 2. The value of τ has been estimated from traffic data between Sevilla and Córdoba. Note that t _ij need not be integer.

Table 1 The demand points for Example 2

Table 2 Population of the cities A ₁ to A ₁₂ for Example 2

Table 3 shows optimal solutions for the cases m=2 to m=4. The last column presents the run time of the algorithm. The solutions are depicted in Fig. 4. Note as well that the gravitational rule penalizes the number of trips between distant cities.

Fig. 4

Optimal solutions for Example 2 and m=2 to m=4

Table 3 Optimal solutions for Example 2 obtained by Algorithm 4, objective function values, percentages of covered potential travelers, and computational times

Example 3

In this example we consider the same input data as in Example 2 but we now ignore all traffic flow between Sevilla and any other city as well as between Córdoba and any other city. This is a realistic assumption since there already exist high-speed train stations at Sevilla and Córdoba. Our result for m=2 new stations can be found in Fig. 5. Here, one optimal solution is (x ₁,x ₂)=(42.65625,66.28125) with an objective value of 460.05994, which is some 15.30% of the potential demand.

Fig. 5

Optimal solutions for Example 3 and m=2

We now illustrate the efficiency of the geometric branch and bound method, Algorithm 4, when we used the d.c bounding operations, see Horst and Thoai (1999). Our algorithm was implemented in JAVA, compiled by JAVA 2 SDK 1.4, using double precision arithmetic. All tests were run on a 2.4 GHz computer with 1024 MB of memory.

We randomly generated 10≤n≤200 existing facilities A ₁,…,A _n in [0,10]×[−2.5,2.5] ordered by their first coordinates. The line segment was $\mathcal{L}=[0,10]$, the high-speed factor was α=0.5, and the acceptance values were given by d _ij =0.9⋅∥A _i −A _j ∥₂. The traffic was also randomly generated as follows: For i<j we randomly set t _ij ∈{0,1,…,8} in such a way that the probability for t _ij =0 was 1/3 and for k=1,…,8 the probability for t _ij =k was 1/12, respectively.

Ten problems instances were run for various values of n and m. Algorithm 4 stopped when one optimal solution was found. Our results are reported in Table 4 and Fig. 6. Since all results were quite similar for various values of α, we only reported run times for α=0.5.

Fig. 6

Plot of average run time versus number of points for two, three, and four facilities

Table 4 Results using the big cube small cube solution method

For the case m=2, all problems with up to n=200 points and therefore with up to n(n−1)/2=19,900 O/D pairs could be efficiently solved in less than 23 seconds of computer time. But if we want to locate more than two facilities, the run time increases as typical for geometric branch and bound methods. For m=4 and n=25 the average run time was approximately 67 seconds.

6 Conclusions and extensions

In this paper we have dealt with the problem of locating facilities along a given tree-like or segment-like high speed network with respect to the Euclidean distance.

• A facility location problem over a high speed network has been modeled, so that the competition with another (slower) existing alternative means is taken into account.

• Thanks to some convexity properties, a method for locating two facilities has been proposed when the high speed network is a straight line segment or a tree network.

• Geometric branch and bound methods have been extended to deal with the combinatorial part of the problem and can be used for the case of locating m≥2 facilities on a straight-line segment.

• Since the final goal was based on realistic applications, the proposed methodology demanded a deep theoretical analysis.

• The problem could be extended so that more constraints could be included. This way a better approximation to real situations could be made just by slightly modifying the methods and algorithms proposed here.

As a first extension, the problem can be generalized to other distances. For example, an application for the problem with rectangular distance is the location of bus stops in a line in Manhattan: The speed along the line is based on the rectangular distance (multiplied by a speed factor) as well as the speed for accessing the bus line. Some of our results can be transferred to arbitrary norms and also the big cube small cube approach can still be used when the norm used is differentiable. Moreover, we plan to extend our work to other types of metrics and to gauges. In this paper the allocation of trips was made on the basis of a binary variable. In order to extend these reasonings, the type of function that substitutes the 0-1 model should be discussed (see Berman et al., 2003), which is beyond the scope of this work and will be addressed in a future paper.

In this work we have treated edges as straight-line segments. Nevertheless, assuming these edges are sufficiently regular curves, one could apply homeomorphisms and their inverses so our reasoning can be extended to this sufficiently-regular-curve case.

Another extension is to allow different speed factors due to different speeds that might be possible in different parts of the network. To be more precise, in reality the trip between two facilities is often modeled in three phases: acceleration to maximum speed (Phase 1), journey at maximum speed (Phase 2), and braking in order to stop (Phase 3). If distances between facilities do not fall below a critical level, then the quota of Phases 1 and 3 is small and our model assuming constant speed is appropriate. Therefore and for other reasons (e.g. acceptance by travelers) we are interested in computing solutions such that facilities do not fall below a minimum inter-facility space. This extension is to avoid situations in which two stations are located too close to each other, as one may say happens in Fig. 4. To this end let 2δ≥0 be the minimum inter-facility space we would accept. Then an extension of Problem (3) can be formulated as

$$ \max_{\mathcal{X}\subset\mathcal{N}}\ F^r(\mathcal{X}) \quad \textrm {s.t.}\quad \mathcal{N}(X_1,\delta)\cap \mathcal{N}(X_2,\delta)=\emptyset \quad \textrm{forall}\ X_1\neq X_2\in\mathcal{X},$$

(9)

where $\mathcal{N}(X,\delta)$ describes a neighborhood around X with radius δ. In the case where the given network is a line segment, the neighborhood of a facility becomes a smaller line segment, i.e. $\mathcal{N}(X,\delta)=[\max\{0,x-\delta\},\min\{x+\delta ,L\}]\times\{0\}$.

The Maximum Pair Covering Algorithm can be adapted in order to solve Problem (9). Roughly speaking, we need to exclude solutions from the finite dominating set CAND (see Corollary 3) that do not satisfy the inter-facility space condition. This can be done by deleting all solutions from CAND that lie in the halfspace d(x,y)≤δ (note that if (x,y)∈CAND then x≤y). After deleting these points from CAND it could be possible that no optimal solution is included in CAND. Therefore the finite number of intersections between level sets C _ij and the straight line d(x,y)=δ must be added to CAND.

Beyond inter-facility space, there could be other reasons why it is not possible to locate facilities in certain sections of a high-speed network. For example it is possible that a line segment of the network passes under a river or crosses a natural park. Hence, we also extend Problem (3) to more general forbidden regions:

$$ \max_{\mathcal{X}\subset\mathcal{N} \setminus\mathcal{R}}\, F^r(\mathcal{X}),$$

(10)

where $\mathcal{R}$ denotes the forbidden regions where the network cannot pass by. Note that formulation (10) also includes formulation (9) ($\mathcal{R}=\{(x,y) :~d(x,y)\leq\delta\}$) and formulation (3) ($\mathcal{R}=\emptyset$). Just like for Problem (9), it is possible to adapt the Maximum Pair Covering Algorithm in order to deal with forbidden regions. To this end we remove points that lie in forbidden regions from the finite dominating set CAND and add finite intersections between $\mathcal{R}$ and the union of all level sets C _ij .

We have obtained optimal extreme points. In a more general formulation, one could explore a multi-objective version of the problem. As a second objective, one could consider the minimization of the distances between covered pairs (MinSum model, see Körner and Schöbel, 2010), or the maximization of the differences between the acceptance values and the distances $h^{kl}_{ij}$ (MaxMin model). This new formulation will yield inner optimal points, which are more realistic than the points that are on the borders of the acceptance levels.

The fact that all mentioned extensions can be easily included in our models reinforces the validity of our reasoning from the applicability point of view.