Solving the median problem with continuous demand on a network

Abstract

Where to locate one or several facilities on a network so as to minimize the expected users-closest facility transportation cost is a problem well studied in the OR literature under the name of median problem.

In the median problem users are usually identified with nodes of the network. In many situations, however, such assumption is unrealistic, since users should be better considered to be distributed also along the edges of the transportation network. In this paper we address the median problem with demand distributed along edges and nodes. This leads to a global-optimization problem, which can be solved to optimality by means of a branch-and-bound with DC bounds. Our computational experience shows that the problem is solved in short time even for large instances.

1 Introduction

Location problems on networks have attracted the interest of researchers and practitioners since the 60s of last century. Under the usual assumption, the demand is concentrated at the nodes of the network, and the facilities can be located either at the nodes or along the edges of the transportation network.

Assuming that the demand is concentrated at the nodes is not realistic when modeling so-called networks spatial phenomena, e.g. [18], that is, phenomena which do happen in points along edges of the network, such as, for instance, traffic accidents, or close to such edges, as happens in urban settings, where edges model the city streets, close to the buildings where demand happens. See [18, 19] for further discussion on the advantages on continuous network models against traditional approaches (discrete or planar location models).

For this reason, several researchers have addressed location problems on networks under the assumption that demand is not only concentrated on nodes, but also is (continuously) distributed along the edges of the network.

Most papers consider the case in which, for each edge of the network, demand is uniformly distributed. Nkansah and David [17] addresses the problem of minimizing the expected distance from the users to one facility, [6, 8] consider the two-facility case on very particular network topologies (trees), whereas [15] addresses the minimization of the variance of distances from the users to the facility. Assuming uniform demands on edges should be seen as a first step towards gaining realism of the model, while maintaining tractability. Indeed, the resulting objective functions admits a rather simple form, as a piecewise polynomial function in one variable, whose optimization is reduced to inspecting all critical points, namely, extreme points and points at which the derivative of the polynomial function vanishes.

Assuming more general distributions for the demand has been advocated by several authors. Okabe et al. [18] suggests the use of general density distributions, from which random samples are generated, yielding a discrete approximation to the problem, which is the one which is later analyzed. Statistical kernel methods have also been recently proposed to model the demand, [20, 23], though, as far as the authors know, no optimization has been carried out, excepting, as said above, discretization via simulation.

In this paper we consider a single-facility location problem, namely, the 1-median problem: the point minimizing the expected distance from the users is sought. With respect to the state-of-the-art, we give a further step towards realism, by assuming arbitrary distributions for the demand along edges. Contrary to the planar 1-median problem, known to be convex, [7], the 1-median problem on networks with continuous demand poses nontrivial challenges: we have no longer a simple expression for the objective, and its optimization calls for the use of global-optimization techniques. In particular, it is shown that the objective function is DC, [10, 11, 21, 22] i.e., it can be written as the difference of two convex functions, and thus its optimization can be addressed via branch-and-bound methods customized for DC functions, [1, 4, 5].

The remainder of the paper is organized as follows. In Sect. 2 the 1-median problem with demand distributed on edges and on nodes of the network is formally introduced. Properties of the objective function are discussed in Sect. 3, where it is shown, in particular, how the function can be expressed as the difference of two convex functions on each edge of the network. These properties will be the cornerstone for a branch-and-bound algorithm, as described in Sect. 4. Our numerical experience is reported in Sect. 5, showing that our algorithm enables us to solve problems on large networks in reasonable time.

2 Problem formulation

Let N=(A,E) be a connected and undirected network, with node set A={a ₁,…,a _n } and edge set E, with |E|=m. Let us denote by l _ij the length of each edge e _ij =[a _i ,a _j ]∈E and let d(x,y) be the distance between two points x,y∈N, obtained as the shortest path from x to y. In particular, the distance d _ij =d(a _i ,a _j ) between each pair of nodes {a _i ,a _j } can be worked out by using standard algorithms, [2]. Note that for every pair of nodes a _i ,a _j with [a _i ,a _j ]∈E, it follows that d _ij ≤l _ij , and equality holds if and only if the edge [a _i ,a _j ] is the shortest path joining a _i and a _j .

Given a node a _k ∈A and a point x∈[a _i ,a _j ], obtained after covering a distance l _x on the edge [a _i ,a _j ], the distance d(x,a _k ) from a _k to x is, as a function of x, a piecewise linear concave function given by:

$$ d(x,a_k) = \min\bigl\{r_{ij}^k(x),s_{ij}^k(x) \bigr\} $$

(1)

where

$$ r_{ij}^k(x) = d(a_i,a_k)+l_x \qquad s_{ij}^k(x) = d(a_j,a_k) + (l_{ij}-l_x) $$

(2)

We assume that the demand not only occurs at nodes but also along the edges of the network. More precisely, the demand of a node a∈A will be denoted by ω _a ≥0, the total demand of a given edge e∈E is p _e ≥0, and it is distributed along e according to a random variable with cumulative distribution function (cdf) F _e .

Under the previous assumptions, the median problem with continuous demand can be written as follows:

$$ \min_{x\in N} H(x):= \sum _{a\in A} w_a d(x,a) + \sum _{e\in E} p_e \int_{y\in e} d(x,y) dF_e(y) $$

(3)

Observe that we are making no assumption on the type of distribution followed for the demand. In case the demand on the edges is continuously distributed along e, i.e., when the cdf F _e has a pdf f _e , (3) can be rewritten as

$$ \min_{x\in N} H(x):= \sum _{a\in A} w_a d(x,a) + \sum _{e\in E} p_e \int_{y\in e} d(x,y) f_e(y) dy. $$

(4)

3 Properties

It has been noticed in [12] that the objective function of (3) is neither convex nor concave as a rule. Indeed, the objective function can exhibit local optima which are not globally optimal, as the following example shows. So the use of global optimization techniques is required if one seeks the optimal solution.

Example 1

Let us consider the network N=(A,E) with A={a ₁,a ₂,a ₃} and E={[a ₁,a ₂],[a ₁,a ₃],[a ₂,a ₃]}. Arc lengths, node demands and arc demands are the following:

$$\begin{array}{l@{\qquad}l@{\qquad}l} l_{12} = 1 & l_{13}=1 & l_{23}=1 \\ w_1 =0 & w_2 = 0 & w_3 = 0 \\ p_{12} = 0.35 & p_{13} = 0.30 & p_{23} = 0.35 \end{array} $$

We also assume that the demand along each arc e is distributed according to a beta distribution, i.e., the probability density function f _e has the form

$$f_{e}(x) = \frac{\varGamma(\alpha_e+\beta_e)}{\varGamma(\alpha_e)\varGamma (\beta_e)} x^{\alpha_e-1} (1-x)^{\beta_e-1} \quad x\in[0,1]. $$

The parameters α _e ,β _e of these probability distributions in the three edges are as follows:

Arc e	α e	β e
[a 1,a 2]	0.6	0.5
[a 1,a 3]	0.4	0.8
[a 2,a 3]	0.5	0.5

Under these assumptions, the objective function of Problem (3) restricted to the edge [a ₁,a ₂] takes the form

(5)

Multimodality of the function is clearly seen in Fig. 1.

Fig. 1

Objective function H ₁₂(x) in Example 1

The special structure of the objective function of Problem (3) will be exploited in order to design a deterministic global optimization algorithm that allows us to find an optimal solution to the problem. More precisely, we will show that H(x) in (3) belongs to the broad class of DC functions, [10, 11, 21]. This key property will allow us to solve Problem (3) by branch-and-bound algorithms, as the one described in Sect. 4, since lower and upper bounds can easily be obtained for DC functions as soon as a DC decomposition is available.

Definition 2

Let $\varOmega\subset\mathbb{R}^{n}$ be a convex set. A function $h:\varOmega\rightarrow\mathbb{R}$ is called DC in Ω if there exist two convex functions $h^{+}:\varOmega\rightarrow\mathbb{R}$, $h^{-}:\varOmega\rightarrow\mathbb{R}$ such that

$$ h(x) = h^+(x)-h^-(x) \quad\forall x\in\varOmega $$

(6)

A pair (h ⁺,h ⁻) satisfying (6) is called a DC decomposition of h in Ω.

An interesting property of the class of DC functions is that it is closed under the most common operations in optimization, [3, 10, 11, 21, 22]. In particular, if h ₁,…,h _r are DC functions and $\lambda_{i}\in\mathbb{R}, \; i=1,\ldots,r$, then $\sum_{i=1}^{r} \lambda_{i} h_{i}$, max _i=1,…,r h _i , min _i=1,…,r h _i and ∥(h ₁,…,h _r )∥ are also DC and their DC decompositions can be easily obtained from the DC decompositions of h _i , i=1,…,r.

The following result shows that the objective function H(x) in (3) is DC on each arc of the network.

Proposition 3

Given $\bar{e}\in E$, the function $H_{\bar{e}}:\bar{e} \mapsto \mathbb{R}$ defined as

$$H_{\bar{e}}(x):= \sum_{a\in A} w_a d(x,a) + \sum_{e\in E} p_e \int _{y\in e} d(x,y) dF_e(y) $$

is DC. A DC decomposition of $H_{\bar{e}}$ on $\bar{e}$ is given by the pair $(H_{\bar{e}}^{+},H_{\bar{e}}^{-})$, with

$$ \begin{aligned}[c] H_{\bar{e}}^+(x) & = p_{\bar{e}}\int_{y \in\bar{e}} |x-y|dF_{\bar{e}}(y) \\ H_{\bar{e}}^-(x) & = H_{\bar{e}}^+(x)-H_{\bar{e}}(x) \end{aligned} $$

(7)

Proof

Let us rewrite $H_{\bar{e}}(x)$ as $H_{\bar{e}}(x) = h_{1}(x) + h_{2}(x) + h_{3}(x)$ where

$$\begin{aligned} h_1(x) = & \sum_{a\in A} w_a d(x,a) \end{aligned}$$

(8)

$$\begin{aligned} h_2(x) = & \sum_{e\in E, e\neq\bar{e}} p_e \int_{y\in e} d(x,y) dF_e(y) \end{aligned}$$

(9)

$$\begin{aligned} h_3(x) = & p_{\bar{e}} \int_{y\in\bar{e}} d(x,y) dF_{\bar{e}}(y) \end{aligned}$$

(10)

The function h ₁ is piecewise linear and concave (see [13] for instance), and h ₂ is also concave, see [12]. In what follows it is shown that h ₃ is DC, and a DC decomposition is given. Given $x,y \in\bar{e}=[a_{i},a_{j}]$, the distance d(x,y) between x and y is obtained as the minimum of the lengths of the following paths:

• 1. the subedge of $\bar{e}$ with x,y as end points,

• 2. the subedge of $\bar{e}$ joining x and a _i , the shortest path joining a _i and a _j , and then the subedge of $\bar{e}$ joining a _j and y,

• 3. the subedge of $\bar{e}$ joining x and a _j , the shortest path joining a _j and a _i , and then the subedge of $\bar{e}$ joining a _i and y.

In other words d(x,y) can be expressed as

$$\begin{aligned} d(x,y) = & \min \bigl\{ |x-y|, x+d_{ij}+(l_{ij}-y),(l_{ij}-x)+d_{ij}+y \bigr\} \end{aligned}$$

(11)

$$\begin{aligned} = & \min \bigl\{ |x-y|,l_{ij}+d_{ij}-|x-y| \bigr\} \end{aligned}$$

(12)

$$\begin{aligned} = & |x-y| - \max \bigl\{ 0,2|x-y|-(l_{ij}+d_{ij}) \bigr\} \end{aligned}$$

(13)

Observe that the last expression gives a DC decomposition of d on $\bar{e}$. Hence, h ₃ can be written as

$$ h_3(x) = p_{\bar{e}}\int_{y \in\bar{e}} |x-y|dF_{\bar{e}}(y) - p_{\bar{e}} \int_{y \in\bar{e}} \max \bigl\{ 0,2|x-y|-(l_{ij}+d_{ij}) \bigr\}dF_{\bar{e}}(y), $$

(14)

which yields a DC decomposition of h ₃. Taking into account that $H_{\bar{e}} = h_{1}+h_{2}+h_{3}$, with h ₁,h ₂ concave and h ₃ decomposed as a difference of convex functions in (14), it follows that (7) gives a DC decomposition of $H_{\bar{e}}$, as asserted. □

We end this section with further properties of the objective function H _e under some assumption on the edge e. These results extend previous well-known results for particular topologies, e.g. for networks which are chains or trees.

Corollary 4

Let $\bar{e} \in E$ be an edge such that $p_{\bar{e}}=0$. Then $H_{\bar{e}}$ is concave on $\bar{e}$.

Proof

If $p_{\bar{e}}=0$, then, by Proposition 3, $(0,-H_{\bar {e}})$ is a valid DC decomposition for $H_{\bar{e}}$. □

Proposition 5

Let $\bar{e} \in E$ be an edge such that $E\setminus\{\bar{e}\}$ is a disconnected network. Then $H_{\bar{e}}$ is convex on $\bar{e}$.

4 The algorithm

Problem (3) will be solved by using a standard branch and bound method [14, 16] which will find out the optimal solution within a relative accuracy of ε>0. The bounds of the objective function required to applying the algorithm will be worked out by taking into account its DC structure. A brief description of such an algorithm is shown next.

• Phase 1: Initialization

  • 1. Fix the required accuracy ε>0.

  • 2. Set UB=+∞ (upper bound initialization).

  • 3. Compute the all-pairs distance matrix.

  • 4. Set the list Λ of remaining segments as empty.

  • 5. For each edge e∈E do:

    • (a) Consider e as a segment with its nodes as the segment vertices.

    • (b) Evaluate the objective function at the segment midpoint. If this value is lower than UB, then update UB and store in x _UB the midpoint as incumbent.

    • (c) Calculate a lower bound for the segment e, LB(e).

    • (d) If LB(e)<UB/(1+ε), then insert e into Λ.

• Phase 2: Branch and Bound process

  Repeat as long as no stop was reached:

  • 1. Select from Λ the minimum lower bound segment e _min and remove if from Λ.

  • 2. If LB(e _min )≥UB/(1+ε), then stop the algorithm with x _UB as optimal solution and UB as optimal objective value.

  • 3. Split e _min by its midpoint into two smaller segments, $e_{min}^{1}$ and $e_{min}^{2}$.

  • 4. Evaluate the objective function at the midpoint of the two small segments. If any of these values is lower than UB, then update UB.

  • 5. Compute a lower bound of the objective function on each small segment.

  • 6. If $\mathit{LB}(e_{min}^{i})<\mathit{UB}/(1+\varepsilon)$ for i=1 or i=2, then insert $e_{min}^{i}$ into Λ.

  • 7. If UB has been updated in this iteration, then discard all segments from Λ whose lower bound is greater than UB.

The algorithm uses a data structure Λ where all the segments (bits of edge) that can contain an optimal solution are stored. The loop in Phase 1 establishes the initial composition of the data structure by selecting the edges whose lower bound is not greater that the global upper bound of the optimal objective value. At the same time, that upper bound is improved by evaluating each edge at its middle point and replacing the bound with the objective value when this is smaller.

Phase 2 of the algorithm consists of an undefined loop where the segment with the worst lower bound is processed; the algorithm finishes when the difference between that lower bound and the global upper bound is smaller than the tolerance ε chosen in Phase 1. If the stopping rule is not fulfilled, the selected segment is split into two equal segments which are processed in the same way that the edges in Phase 1. Eventually, if a change in the upper bound took place during an iteration, all the segments in the data structure that cannot contain an optimal solution are removed.

The computation of the objective function’s lower bound on each segment requires more attention and is going to be detailed next.

4.1 Constructing lower bounds

Given an edge $\bar{e}=[a_{i},a_{j}]\in E$, Proposition 3 provides a DC decomposition for $H_{\bar{e}}$ –the restriction of the objective H to e– and this fact can be exploited in order to obtain the lower bounds required in the previous algorithm. Starting from the DC representation (7), a concave underestimate $L_{\bar{e}}(x)$ of $H_{\bar{e}}$ is obtained by replacing $H_{\bar{e}}^{+}$ with an affine underestimate built in the usual way,

$$L_{\bar{e}}(x) = H_{\bar{e}}^+(x_0)+\xi(x-x_0) - H_{\bar{e}}^-(x) $$

where ξ is any point in $\partial H_{\bar{e}}^{+}(x_{0})$, the subdifferential of $H_{\bar{e}}^{+}$ at $x_{0}\in\bar{e}$. Since

$$\partial H_{\bar{e}}^+(x_0) = \int_{(0,x_0)} dF_{\bar{e}}(y) + [-1,1]\int_{\{x_0\}} dF_{\bar{e}}(y) - \int_{(x_0,l_{\bar{e}})} dF_{\bar{e}}(y), $$

one has

$$2F_{\bar{e}}(x_0)-1 \in\partial H_{\bar{e}}^+(x_0), $$

and thus, a concave underestimate $L_{\bar{e}}(x)$ is given by

$$L_{\bar{e}}(x) = H_{\bar{e}}^+(x_0)+\bigl(2F_{\bar{e}}(x_0)-1 \bigr) (x-x_0) - H_{\bar{e}}^-(x) $$

Due to the concavity of $L_{\bar{e}}$, it is enough to evaluate this function at the extreme points of $\bar{e}$ to obtain its minimum on the segment, which is also a lower bound for $H_{\bar{e}}^{+}$. Hence,

$$LB(\bar{e}) = \min\bigl\{L_{\bar{e}}(a_i),L_{\bar{e}}(a_j) \bigr\} $$

5 Computational results

The effectiveness of the proposed algorithm was investigated with the aid of numerical cases.

The algorithm described in Sect. 4 was coded in Fortran and compiled using Intel©Fortran Compiler XE 12.0. Executions were carried out on an Intel Core i7 computer with 8.00 Gb of RAM memory at 2.8 GHz, running Windows 7. The solutions were found to a relative accuracy of 10⁻³ and the integrals were calculated by means of the functions qdags and qdagp available at the IMSL Fortran Numerical Library.

We experimented with a set of 43 test networks obtained from [9, 24]. The number of nodes of these test problems ranges from 150 to 1000, and the number of edges from 296 to 3083. Each problem was solved 10 times over each network using randomly generated parameters: the demands of nodes were obtained from a Uniform distribution on [0,1], as it is also the case of the overall demand of each edge. Regarding the demand along each edge, it was assumed to be distributed following a Beta distribution with parameters randomly generated on the interval [0.1,5], which provides a wide range of density functions with very different shapes.

After the resolution of each set of 10 instances, some statistical measures (minimum, maximum, average and standard deviation) were calculated for the following indicators of the algorithm performance:

• Number of iterations of the Phase 2 of the algorithm.

• Maximum size of the data structure used for storage reached during the algorithm execution.

• CPU time.

Table 1 shows the computational results, where the number of nodes |A| and edges |E| of the graphs are reported as well as the above-mentioned computational measures.

Table 1 Computational results

The number of iterations and the maximum size of the branch-and-bound list remain low in all the executions. However, the CPU time results are quite high mainly due to the computation of the integrals in Phase 1 (steps 5-b and 5-c) and Phase 2 (steps 4 and 5). One can see that the CPU time required to solve different instances of the same problem shows a great stability.

We summarize the findings of this paper. We have addressed the problem of locating one facility on a network with demand distributed on nodes and edges, following arbitrary distributions. The problem is shown to be multimodal, calling for the use of global optimization techniques. The objective function on each edge has been shown to be DC, and a DC decomposition is given. This enables us to obtain concave underestimates of the objective, which are used in a branch and bound procedure. Our numerical tests show that problems of large size are solved rather quickly. Extensions of our techniques to the multifacility case are now under study.