Determining optimal straight line route of a moving facility on the plane with random demand points

Abdelaziz Foul

doi:10.1016/j.jksus.2011.03.003

View/Download PDF

Buy Reprints

PDF

Translate this page into:

ORIGINAL ARTICLE

24 (

); 19-23

doi:

10.1016/j.jksus.2011.03.003

Determining optimal straight line route of a moving facility on the plane with random demand points

Abdelaziz Foul^*

Department of Statistics and Operations Research, College of Science, King Saud University, P.O. Box 2455, Riyadh 11451, Saudi Arabia

*Tel.: +966 14676335 abdefoul@ksu.edu.sa (Abdelaziz Foul)

Received: 2011-1-9, Accepted: 2011-3-17, Published: 2011-01-01

Disclaimer:
This article was originally published by Elsevier and was migrated to Scientific Scholar after the change of Publisher.

Available online 22 March 2011

Abstract

This paper deals with determining the optimal straight line route that minimizes the sum of the weighted expected distances between the moving service facility and the random demand points. The problem is investigated using different distance measures and different probability distributions of the random demand points.

Keywords

Moving facility location

Probabilistic facility location

Planar location

Show Related Articles from PubMed

1 Introduction

Facility location problems involve locating one or more service facilities, so as to optimally supply a given set of demand points (also called existing facilities). On the macro scale they involve location of airports, waste disposal sites, manufacturing and distribution facilities. Depending on the application being modeled, the facilities and demand points may be nodes in a network or points in a planar region. Facility location involves as well the problem of determining a path of a moving service facility, which during its journey provides service to a set of demand points.

In this paper, we focus on the problem of finding the optimal travel route for a service facility which moves through a planar region and interacts with a number of potential demand points and it is not known which particular ones will request service. In several instances the assumption of known fixed demands points does not hold. Consider for example, the case of determining a route for a patrol car maintaining radio contacts with potential stations and it is not known which particular ones will request service or the case of determining a trajectory for a surveillance aircraft or submarine moving in enemy territory and threatened by several unknown missile sites. Our objective is the minimization of the weighted expected distances between the facility and the existing facilities over all instants of time during the travel period.

There is scarce research work on moving facility location problem with deterministic demands points, but to the best of our knowledge, research on moving facility location with random demand points remains largely unexplored. The problem assessed here is new and has not been treated in the literature. Here is some of the current literature on moving facility location problem with deterministic demands points. Sherali and Seong-in Kim (1992) have introduced a new class of problems involving the determination of an optimal constrained path for a moving facility that interacts with a set of fixed existing facilities. Using weighted-distance related cost function, they have analyzed both the total cost and the average cost problems. Seong-In Kim and In-Chan Choi (1994) extended the model of Sherali and Seong-in Kim (1992) to a larger class that includes a general cost structure. Then they showed that an optimal path can be easily obtained to the model with a specific form of nontrivial cost function. In Seong-In Kim and In-Chan Choi (1997), Kim and Choi have formulated the problem of finding an optimal path of a moving vehicle on a sphere as a variational problem under the assumption that the demands were generated from an independent Poisson process. The perturbation technique, coupled with dynamic programming procedure, was suggested to solve the variational problem.

In Caccetta et al. (2005), Caccetta et al. (2005), Hallam (1997), Howlett et al. (1992), Rehbock et al. (2000), a class of moving facility location problems, called “Transit path problems”, have been investigated. Such problems arise when an object needs to traverse between two points through a specific region. The path must optimize a prescribed criterion such as risk, reliability, or cost and satisfy a number of constraints such as total travel time.

The remaining of the paper is organized as follows. In Section 2, the problem is analyzed and the main results are described. Illustrative examples are provided.

2 Analysis

Suppose there is a set of m demand destinations randomly {Y_i = (U_i,V_i):i = 1, 2, … , m} distributed over some rectangle [0,s] × [0,t] in R²(s,t > 0). Assume that U_i (resp. V_i) has the probability density function $f_{U_{i}} (u)$ (resp. $f_{V_{i}} (v)$ ) and cumulative distribution function $F_{U_{i}} (u)$ (resp. $F_{V_{i}} (v)$ ). Let w_i > 0 be the demand for service at destination i = 1, 2, … , m. Suppose that there is a vehicle moving in this plane along the route z(t) = (x(t),y(t)) at a constant velocity v, starting from some origin S and arriving at a destination located at D. The problem we address here is to determine a route for the moving facility that minimizes the expected sum of the weighted distances between the moving facility and the demand destinations over some time framework T. The problem can be stated as

(1)

{Min}_{z (t)} J (z (t)) = \int_{0}^{T} \{\sum_{i = 1}^{m} w_{i} E [d (z (t), Y_{i})]\} dt

where d(.,.) designates either the rectilinear or the squared Euclidean distance between the facility z(t) and the destination Y_i and E [.] denotes the expected value.

For simplicity, assume that the path traced by the moving facility is represented by z(x) = (x,y(x)), where y(x) is a straight line. Then the feasible set of routes from the origin S to the destination D, denoted by Z, may be described by the set $Z = {z (x) = (x, y (x)) : y (x) = α x + β, x \in I = [0, θ]}$ where α and β are the slope and intercept parameters, respectively, of the straight line. θ is a positive real number. S = (0,y(0)), D = (θ,y(θ)).

Note that $v = \frac{ds}{dt}$ , where ds is the incremental distance travelled in the incremental time dt, we obtain that $ds = \sqrt{(dx)^{2} + (dy)^{2}} = \sqrt{1 + (y^{'})^{2}} . dx$ . The problem may then be stated as follows:

(2)

{Min}_{z (x) \in Z} J (z (x)) = \int_{0}^{θ} \{\sum_{i = 1}^{m} w_{i} E [d (z (x), Y_{i})]\} \sqrt{1 + y^{'} (x)^{2}} dx

In the coming sub-sections, we study Problem (2) for different distance measures d(z(x),Y_i) and different probability distributions for the random demand points Y_i.

2.1

2.1 Case when d(z(x),Y_i) is the rectilinear distance

The rectilinear distance between the demand point Y_i = (U_i,V_i) and moving facility z(x) = (x,y(x)) is given by

d(Y_i,(x,y(x))) = ∣x − U_i ∣ + ∣y(x) − V_i ∣ and its expected value by $E [d (Y_{i}, (x, y (x)))] = E [| x - U_{i} |] + E [| y (x) - V_{i} |]$ Now, let $f_{i} (x) = E [| x - U_{i} |]$ and $g_{i} (y (x)) = E [| y (x) - V_{i} |]$ . Then, we have $f_{i} (x) = E (U_{i}) - x [1 - 2 F_{U_{i}} (x)] - 2 \int_{- \infty}^{x} {uf}_{U_{i}} (u) du$ and $g_{i} (y (x)) = E (V_{i}) - y (x) [1 - 2 F_{V_{i}} (y (x))] - 2 \int_{- \infty}^{y (x)} {vf}_{V_{i}} (v) dv$ Then Problem (2) can be stated as:

(3)

{Min}_{(x, y (x)) \in Z} J (x, y (x)) = \int_{0}^{θ} \{\sum_{i = 1}^{m} w_{i} (f_{i} (x)) + g_{i} (y (x)) \sqrt{1 + (y^{'} (x))^{2}}\} dx

By substituting y(x) = αx + β into the above problem and denoting the real function

\sum_{i = 1}^{m} w_{i} g_{i} (α x + β)

in the variables α and β by G_x(α,β) and the constant

\sum_{i = 1}^{m} w_{i} \int_{0}^{θ} f_{i} (x) dx

by C, Problem (3) then becomes:

(4)

\min_{(α, β)} J (α, β) = \sqrt{1 + α^{2}} \{C + \int_{0}^{θ} G_{x} (α, β) dx\}

In the sequel, (α^∗,β^∗) denotes an optimal solution to Problem (4), and y^∗(x) = α^∗x + β^∗ the optimal straight line route.

Now let’s consider the following sub-problem:

(5)

\min_{(α, β)} G_{x} (α, β)

Optimal solutions to Problem (5) are characterized by the following theorem:

Theorem 1

For arbitrary bivariate distribution of the random demand point Y_i = (U_i,V_i), any solution (α,β) to the following equation: $\sum_{i = 1}^{m} w_{i} (2 F_{V_{i}} (α x + β) - 1) = 0$ is a global minimum to Problem (5).

Proof

By applying first order optimality conditions to the unconstrained Problem (5), we have that:

(6)

\nabla G_{x} (α, β) = [\begin{matrix} x \sum_{i = 1}^{m} w_{i} (2 F_{V_{i}} (α x + β) - 1) \\ \sum_{i = 1}^{m} w_{i} (2 F_{V_{i}} (α x + β) - 1) \end{matrix}] = [\begin{matrix} 0 \\ 0 \end{matrix}] \Leftrightarrow \sum_{i = 1}^{m} w_{i} (2 F_{V_{i}} (α x + β) - 1) = 0

Then clearly any value of α and β satisfying Eq. (6) is a critical point. To determine the kind of these critical points, we use second order optimality conditions. Since the Hessian matrix of G_x(α,β) given by

H (α, β) = [\begin{matrix} 2 x^{2} \sum_{i = 1}^{m} w_{i} f_{V_{i}} (α x + β) & 2 x \sum_{i = 1}^{m} w_{i} f_{V_{i}} (α x + β) \\ 2 x \sum_{i = 1}^{m} w_{i} f_{V_{i}} (α x + β) & 2 \sum_{i = 1}^{m} w_{i} f_{V_{i}} (α x + β) \end{matrix}]

is positive semi-definite, it follows that the function G_x(α,β) is convex and, therefore, each critical point is a global minimum. □

Corollary 1

For arbitrary bivariate distribution of the random demand point, Y_i = (U_i,V_i) if 0, β^∗ (where β^∗ is the solution to Eq. (6) with α = 0) is a global minimum to Problem (5), then it is a global minimum to Problem (4).

Proof

Let 0,β^∗ be a global minimum to Problem (5). Then we have

(7)

G_{x} (α, β) ⩾ G_{x} (0, β^{*}) \Rightarrow C + \int_{0}^{θ} G_{x} (α, β) dx ⩾ C + \int_{0}^{θ} G_{x} (α, β^{*}) dx; \forall α \in R

which implies that:

J (α, β) = \sqrt{1 + α^{2}} \{C + \int_{0}^{θ} G_{x} (α, β) dx\} ⩾ \{C + \int_{0}^{θ} G_{x} (0, β^{*}) dx\} = J (0, β^{*})

∀α ∈ R. This shows that (α^∗,β^∗) is a global minimum to Problem (4). □

Corollary 2

If U_i (resp. V_i) is a random variable that follows the uniform distribution over [a_i,b_i] [(resp. [c_i,d_i]), then $(α^{*} = 0, β^{*} = \frac{{sum}_{i = 1}^{m} w_{i} e_{i}}{2 \sum_{i = 1}^{m} w_{i} e_{i}})$ is a global minimum of Problem (4).(where $e_{i} = \frac{c_{i} + d_{i}}{d_{i} - c_{i}}$ and ${\bar{e}}_{i} = \frac{1}{d_{i} - c_{i}})$ .

Proof

If V_i is uniform over [c_i,d_i] then Eq. (6) can be expressed as: $\sum_{i = 1}^{m} w_{i} [2 (\frac{α x + β - c_{i}}{d_{i} - c_{i}}) - 1] = 0$ By Theorem 1, any (α,β) that solves the above equation is a global minimum to Problem (5). In particular, if we let α = α^∗ = 0, then from the above equation, we obtain $β = β^{*} = \frac{\sum_{i = 1}^{m} w_{i} e_{i}}{2 \sum_{i = 1}^{m} w_{i} {\bar{e}}_{i}}$ , where $e_{i} = \frac{c_{i} + d_{i}}{d_{i} - c_{i}}$ and ${\bar{e}}_{i} = \frac{1}{d_{i} - c_{i}}$ . By Corollary 1, (α^∗,β^∗) is a global minimum to Problem (4). □

Example 1

Consider the routing of military vehicle through explosives detection field. Assume that each explosive is a point Y_i = (U_i,V_i) that could blast according to a bivariate uniform distribution over the rectangular region [a_i,b_i] × [c_i,d_i], i = 1, 2, 3, 4. Let s = 15, t = 10, and θ = s = 15. Table 1 gives the data for this example. According to Corollary 1, the optimal straight line route in the x–y plane is given by the equation y^∗ = β^∗, where $β^{*} = \frac{\sum_{i = 1}^{m} w_{i} e_{i}}{2 \sum_{i = 1}^{m} w_{i} e_{i}}, e_{i} = \frac{c_{i} + d_{i}}{d_{i} - c_{i}}$ and ${\bar{e}}_{i} = \frac{1}{d_{i} - c_{i}}$ . After simple computation, we found that β^∗ = 2.73 and hence y^∗(x) = 2.73 is the optimal route from S = (0,2.73) to D = (15,2.73).

Corollary 3

If U_i (resp. V_i) is a random variable that follows an exponential distribution with parameter ρ_i (resp. τ_i), then α^∗ = 0 and β^∗ (which is the unique solution to equation $\sum_{i = 1}^{m} w_{i} (1 - 2 e^{- τ_{i} β}) = 0)$ form a global minimum to Problem (4).

Proof

If V_i is exponential with parameter τ_i, then Eq. (6) can be expressed as $\sum_{i = 1}^{m} w_{i} (1 - 2 e^{- β τ_{i}}) = 0$ . By Corollary 1, α^∗ = 0 and β^∗ (the solution to the above equation) form a global minimum to Problem (4). To prove that β^∗ is unique and 0 < β^∗ < ln 2/min_1⩽i⩽mτ_i, let $f (β) = \sum_{i = 1}^{m} w_{i} (1 - 2 e^{- β τ_{i}})$ and note that $f^{'} (β) = 2 \sum_{i = 1}^{m} τ_{i} w_{i} e^{- τ_{i} β} > 0$ . Then f(β) is a strictly increasing function. Let a = 0 and b = ln 2/min_1⩽i⩽mτ_i. We have $f (a) = - \sum_{i = 1}^{m} w_{i} < 0$ and $f (b) = \sum_{i = 1}^{m} w_{i} (1 - 2 e^{- τ_{i} b}) > 0$ . Therefore by Bolzano’s intermediate value Theorem (Bartle, 1976), there exists a unique value β^∗ such that f(β^∗) = 0 and 0 < β^∗ < ln 2/min_1⩽i⩽mτ_i. □

Example 2

Suppose that we have three demand points Y_i = (U_i,V_i), i = 1,2,3 distributed according to a bivariate exponential distribution over some rectangular region [0,15] × [0,10]. Let θ = 15, Table 2 gives the data for this example.

Table 1 Data of Example 1.

i	w_i	a_i	b_i	c_i	d_i
1	1	3	1	3	5
2	2	6	2	1	4
3	2	4	7	0	2
4	1	7	10	5	8

Table 2 Data of Example 2.

i	w_i	τ_i
1	2	1
2	1	5
3	2	2

According to Corollary 2, the optimal straight line route in the x−y plane is given by the equation y^∗ = β^∗, where β^∗ solves the following equation: $\sum_{i = 1}^{m} w_{i} (1 - 2 e^{- β τ_{i}}) = 0 \Leftrightarrow 2 (1 - 2 e^{- β}) + (1 - 2 e^{- 5 β}) + 2 (1 - 2 e^{- 3 β}) = 5 - 4 e^{- β} - 2 e^{- 5 β} - 4 e^{- 2 β}$ . Using Mathematica software to find the root of an equation of one variable, we found that β^∗ = 0.368 and hence y^∗(x) = 0.368 is the optimal route from S = (0,0.368) to D = (15,0.368).

Corollary 4

If U_i(resp. V_i ) is a random variable that follows a normal distribution with mean μ_i, and standard deviation σ_i (resp. $μ_{i}^{'}$ and $σ_{i}^{'}$ ), then a^∗ = 0 and β^∗ (which solves the equation $\sum_{i = 1}^{m} w_{i} (1 - 2 P (V_{i} ⩾ β) = 0))$ form a global minimum to Problem (4). (P(.) denotes probability measure).

Proof

W.O.L.O.G. Suppose $μ_{i}^{'} > 0, i = 1, 2, \dots, m$ . Let $f (β) = \sum_{i = 1}^{m} w_{i} (1 - 2 P (V_{i} ⩾ β))$ . $f (β)$ is a strictly increasing function since $f^{'} (β) = 2 \sum_{i = 1}^{m} w_{i} f_{V_{i}} (β) > 0$ . Let $β_{\max} = \max_{1 ⩽ i ⩽ m} \{μ_{i}^{'}\} + ɛ$ , and $β_{\min} = \min_{1 ⩽ i ⩽ m} \{μ_{i}^{'}\} - ɛ$ , where ɛ > 0. We have f(β_max) < 0, and f(β_min) > 0. Therefore by Bolzano’s intermediate value Theorem (Bartle, 1976), there exists a unique value such that f(β^∗) = 0 and β_min < β^∗ < β_max. □

Example 3

Suppose that we have three demand points Y_i = (U_i,V_i), i = 1, 2, 3 distributed according to a bivariate normal distribution over some rectangular region [0,15] × [0,10]. Let θ = 15 Table 3 gives the data for this example.

Table 3 Data of Example 3.

i	w_i	$μ_{i}^{'}$	$σ_{i}^{'}$
1	1	3	1
2	4	10	3
3	2	15	4

According to Corollary 2, the optimal straight line route in the x−y plane is given by the equation y^∗ = β^∗, where β^∗ solves the following equation: $\sum_{i = 1}^{3} w_{i} (1 - 2 P (V_{i} ⩾ β)) = 0 \Leftrightarrow \sum_{i = 1}^{3} w_{i} (1 - 2 P (Z ⩾ \frac{β - μ_{i}^{'}}{σ_{i}^{'}})) = 0$ where Z ∼ N(0,1). We use bisection method to solve the above equation. Evaluations are easily performed with the aid of a cumulative normal table. The interval (Caccetta et al., 2005) is a logical starting interval. After some computation, we found that β^∗ = 10.6 and hence y^∗(x) = 10.6 is the optimal route from S = (0,10.6) to D = (15,10.6).

2.2

2.2 Case when d(z(x),Y_i) is the squared Euclidean distance

The squared Euclidean distance between the demand point Y_i = (U_i,V_i) and moving facility z(x) = (x, y(x)) is given by

d(Y_i,(x,y(x))) = (x − U_i)² + (y(x) − V_i)² and its expected value by: $E [d (Y_{i}, (x, y (x)))] = E [(x - U_{i})^{2}] + E [(y (x) - V_{i})^{2}]$ Now, let f_i(x) = E[(x − U_i)²] and g_i(y(x)) = E[(y(x) − V_i)²]. Then, f_i(x) and g_i(y(x)) can be expressed as: $f_{i} (x) = (x - E [U_{i}])^{2} + Var [U_{i}]$ and $g_{i} (y (x)) = (y (x) - E [V_{i}])^{2} + Var [V_{i}]$ where Var[U_i] (resp. Var[V_i]) denotes the variance of the random variable U_i (resp. V_i).

The following theorem is a restatement of Theorem 1 in case d(z(x),Y_i) is the squared Euclidean distance.

Theorem 2

For arbitrary bivariate distribution of the random demand point Y_i = (U_i,V_i), any solution (α,β), to the following equation: $\sum_{i = 1}^{m} w_{i} (α x + β - E [V_{i}])^{2} = 0$ is a global minimum to Problem (5).

Proof

Following the proof steps of Theorem 1 and equalizing the gradient vector G_x(α,β) to zero, we obtain:

(8)

\nabla G_{x} (α, β) = [\begin{matrix} 2 x \sum_{i = 1}^{m} w_{i} (α x + β - E [V_{i}]) \\ 2 \sum_{i = 1}^{m} w_{i} (α x + β - E [V_{i}]) \end{matrix}] = [\begin{matrix} 0 \\ 0 \end{matrix}] \Leftrightarrow 2 \sum_{i = 1}^{m} w_{i} (α x + β - E [V_{i}]) = 0

Clearly any value of α and β that satisfies (7) is a critical point. To determine the kind of these critical points, we use second order optimality conditions for unconstrained problems. Since the Hessian matrix of G_x(α,β), given by

H (α, β) = [\begin{matrix} 2 x^{2} \sum_{i = 1}^{m} w_{i} & 2 x \sum_{i = 1}^{m} w_{i} \\ 2 x \sum_{i = 1}^{m} w_{i} & 2 \sum_{i = 1}^{m} w_{i} \end{matrix}],

is positive semi-definite, it follows that the function G_x(α,β) is convex and, therefore, each critical point is a global minimum. The following theorem gives a general and unique expression for the global minimum (α^∗,β^∗) to Problem (4) that encompasses all types of bivariate distribution of the random demand point Y_i = (U_i,V_i). □

Theorem 3

For arbitrary bivariate distribution of the random demand point $Y_{i} = (U_{i}, V_{i}) (α^{*} = 0, β^{*} = \frac{\sum_{i = 1}^{m} w_{i} E [V_{i}]}{\sum_{i = 1}^{m} w_{i}})$ is a global minimum to Problem (4).

Proof

Consider Eq. (7) $2 \sum_{i = 1}^{m} w_{i} (α x + β - E [V_{i}]) = 0$ By Theorem 2, any (α,β) that solves the above equation is a global minimum to Problem (5). In particular, let α = α^∗ = 0, then the above equation gives $β = β^{*} = \frac{\sum_{i = 1}^{m} w_{i} E [V_{i}]}{\sum_{i = 1}^{m} w_{i}}$ . By Corollary 1, (α^∗,β^∗) is a global minimum to Problem (4). □

Remark 1

The intercept parameter β^∗ can be seen to be the center of gravity (median) of the random demand points V_i (taken by their expected values E[V_i]). Theorem 3 can be considered as an extension of Theorem 1(a) (Sherali and Seong-in Kim, 1992) to random demand destinations.

3 Conclusion and extensions

In this paper, I have considered an instance of the moving facility location problem. This problem arises in many areas of real life. For example, routing of military vehicles through a detection field; determining an optimal path for a submarine that traverses a field of sonar sensors; or as mentioned in the Introduction, finding a route for a patrol car maintaining radio contacts with potential stations.

I studied the moving facility location problem with random demand destinations and a minimum type of objective and where the route is confined to a straight line. I have shown that, in case of rectilinear distance between the moving facility and the random points an optimal straight line route parallel to the x-axis exists. In case of squared euclidean distance, the last theorem gives a unique expression for the intercept parameter of the optimal straight line route for arbitrary bivariate distribution of the random demand points.

The proposed model can be extended in several ways. These include multifacility considerations, analysis of minimax as opposed to minisum types of objective functions, treatment of other path equations as opposed to a straight line path. These problems will be explored in future research.

References

Bartle R.G., . The Elements of Real Analysis. New York: John Wiley & Sons; 1976.
Caccetta, L., Loosen, I., Rehbock, V., 2005. Modeling transit paths for military vehicles. In: Proceedings of the 16th Congress of the Modelling and Simulation Society of Australia and New Zealand, MODSIM05, Melbourne, Australia, 2005.
Caccetta, L., Loosen, I., Rehbock, V., 2005. Optimal transit path problem for submarines. In: Proceedings of the Fourth International Conference on Engineering Applications and Computational Algorithms, DCDIS, Guelph, Canada, July 27–29.
Hallam C.L., . Hierarchical Path Generation: An Application to Submarine Transit Paths.Honours Dissertation. Western Australia: Murdoch University; 1997.
Howlett, P., Pudney, P., Benjamin, B., 1992. Determination of optimal driving strategies for the control of a train. In: Noye, B.J., Benjamin, B.R., Colgan, L.H. (Eds.), Proceedings of Computational Techniques and applications, CTAC 91, Computational Mathematical Group, Australian Mathematical Society, pp. 241–248.
Kim Seong-In, Choi In-Chan, . A simple variational problem for a moving vehicle. Operations Research Letters. 1994;16:231-239.
[Google Scholar]
Kim Seong-In, Choi In-Chan, . An optimal path of a moving vehicle on a sphere. IIE Transactions. 1997;29:383-389.
[Google Scholar]
Rehbock, V., Caccetta, L., Hallam, C.L., O’Dowd, R., 2000. Optimal Submarine Transit Paths Through Sonar Fields, Research Report, Department of Mathematics and Statistics, Curtin University of Technology.
Sherali H.D., Kim Seong-in, . Variational problems for determining optimal paths of a moving facility. Transportation Science. 1992;26(4):330-345.
[Google Scholar]