A heuristic algorithm to solve the single-facility location routing problem on Riemannian surfaces

Abstract

Location routing problem (LRP) in supply chain management is integration of the vehicle routing (VRP) and facility location problems (FLP). To the best of our knowledge, the known solutions obtained for the LRP in the literature are only obtained for the Euclidean space. Solving LRP on Riemannian manifold surface (RMS) is a more realistic approach than using Euclidean surfaces because of the curved structure of the pathways on Earth with changing local RMS curvatures. The shortest path distances on Earth’s surface can be determined by calculating geodesic distances in local neighborhoods. The special case of the LRP on RMS is the traditional LRP in the Euclidean space when the curvature of the RMS is zero. In this work, we introduce a new LRP to be solved on (RMS) and find a heuristic algorithmic solution to this LRP. In particular, we formulate the LRP for a single facility on RMS; a generalization of the surface and distance assumptions for the traditional single facility LRP. In addition, a heuristic algorithm is formulated to solve the proposed LRP on RMS with the corresponding computational results displayed for a particular scenario. The numerical results corresponding to the theoretical results introduced in this work are incomparable with the ones known in the literature for the traditional LRP because of the change in the surface and distance assumptions.

1 Introduction

Determining the best place for a facility to be allocated and transportation from this facility location to the customers are two important problems in supply chain management. Determining the location of the facility is a tactical and long term investment with one time decision making whereas the routing of vehicles in a transportation problem is a dynamic problem with possible changes by considering multiple tradeoffs. It is possible to determine the best location of a facility and the cost effective transportation from this facility to its customers simultaneously by solving the location routing problem (LRP). LRP is a cost minimization problem obtained by integrating the facility location (FLP) and vehicle routing problems (VRP) that can be solved in a discrete or a continuous (planar) surface platform. FLP is a well-known NP-hard problem concerned with determining the best location of a facility. VRP is also another NP-hard problem concerned with determining the best possible routing to serve from the facility to a set of customers, see for example Bookbinder and Reece (1988). We refer to Daskin (2008) for an overview of FLP and Laporte (2007) for an overview of VRP.

LRP attracted many researchers interest in the recent years. Salhi (1987) initiated integration of routing into the location-allocation and vehicle fleet composition problems. Solutions to the LRP for limited-capacity facilities are obtained by Barreto et al. (2007) and Prins et al. (2007). Important applications of the LRP in discrete space can be seen in allocation of food market stores (Ambrosino et al. 2009), grocery distribution (Semet and Taillard 1993), goods’ distribution (Perl and Daskin 1985), and parcel delivery (Bruns et al. 2000; Wasner and Zapfel 2004). Even though the continuous case yields a better solution for the LRP than the discrete case, determining a feasible solution for the LRP in continuous space can be challenging: It is hard to allocate a facility anywhere on a planar surface that satisfies the geographical conditions. The solution to the continuous case can serve as the lower bound for the solution to the discrete LRP case. Schwardt and Dethloff (2005), and Schwardt and Fischer (2009) used a stochastic approach by employing neural-networks to solve the planar single-facility LRP. In their work, inter-connected neuron rings are used to define the interaction between the customers and the facility. The existing solutions for the Weber Problem (WP) are also improved in Schwardt and Dethloff (2005), and Schwardt and Fischer (2009) by using the end-points of the obtained routes as the customer set. Feasible and good solutions compared to the sequential method are reached by running the corresponding stochastic algorithm; See Gamal and Salhi (2001) and Schwardt and Fischer (2009) for details.

Considering the planar surfaces with Euclidean distances, WP is known to be the Location Problem on planar surfaces; See Tellier (1972). Multi-facility WP (MFWP) is the LRP with multiple facilities introduced by Cooper (1964). The solution to the WP can be obtained by using the algorithm of Weiszfeld (1937) with the optimality obtained iteratively. The LRP for a single facility with unlimited-capacity and capacitated vehicle transportation is investigated by Manzour-al-Ajdad et al. (2012a, b). In their work computationally effective results are obtained that improved the previous existing numerical results for the problems known in the literature. Noting that the LRP for multiple facilities is an NP-hard problem, MFWP is clearly an NP-hard problem; see Sherali and Noradi (1988). The MFWP can be solved for both capacitated and uncapacitated facilities with the integration of the solution to the classical transportation problem. Salhi and Nagy (1999) used an iterative heuristic method to solve a multi-facility planar LRP by determining the solutions to the LRP and VRP independently. In their work a heuristic algorithm is used to solve the VRP by assuming the maximum tour length of the vehicles bounded the capacity of the vehicles. Allocation of each facility is determined by solving the corresponding WP. The algorithmic solutions obtained for the FAP and VRP are integrated to determine the solution to the LRP. For an overview on this topic we refer to Nagy and Salhi (2007), Brimberg et al. (2008) and Luis et al. (2009).

2 Riemannian manifolds and geodesics

Geometry of topological manifolds was studied by Bernhard Riemann in the nineteenth century (Riemann 1851). In Riemannian geometry, the metric properties vary from point to point [see for example Carmo (1976)]. A Riemannian manifold (RM) is a differentiable manifold M in which each tangent space is equipped with an inner product, h, a Riemannian metric, which varies smoothly from point to point. Well known examples of Riemannian manifolds include n-dimensional sphere $\hbox {S}^\mathrm{n}$, and n-dimensional Euclidean space $\hbox {R}^\mathrm{n}$, for all $\hbox {n}\ge 1$. The curvature of a Riemannian manifold surface (RMS) indicates how much the surface is curved in a local neighborhood. For example, $\hbox {R}^\mathrm{n}$ has curvature zero since it is flat and the surface of $\hbox {S}^\mathrm{n}$ has curvature 1. If the curvature of a surface changes from flat to spherical surface then the curvature changes from 0 to 1. Every Riemannian manifold can be considered as a local Euclidean space. This consideration is possible by using a one-to-one and onto map $\upvarphi :\hbox {U}\subset \hbox {M}\rightarrow {\mathbb {R}}^{\mathrm{n}}$ called homeomorphism. By using a homeomorphism, each open neighborhood U in the topology of the manifold M can be mapped to an open neighborhood $\upvarphi$ (U) in the Euclidean space, see for example Carmo (1976) and Jost (2011) for details on Riemannian manifolds.

A connected Riemannian manifold carries the structure of a metric space whose distance function is the arc-length of a minimizing geodesic. Let M be a connected Riemannian manifold and $\gamma \,:\,[a,b]\,\rightarrow \quad M$ be a parameterized differentiable curve in M with the velocity vector $\gamma ^{{\prime }}$. The length of $\gamma$ between a and b is defined by the equality

$$\begin{aligned} l\left( \gamma \right) =\mathop \int \nolimits _{M} h(\gamma ^{{\prime }}\left( t \right) ,\gamma ^{{\prime }}\left( t \right) )dt \end{aligned}$$

(1)

Calculating the possible geodesic distances on Riemann manifolds M vary between the customers and the possible locations of the facilities to be allocated. These distances will be determined by using (1). In $\hbox {M}={\mathbb {R}}^{2}$, the length of a curve $\gamma$ is defined on the interval [a, b] by using the formula

$$\begin{aligned} l\left( \gamma \right) =\mathop \int \nolimits _a^b \Vert \nabla \gamma (t)\Vert dt \end{aligned}$$

(2)

where $\nabla$ is the Levi–Civita connection; See for example Cheeger and Ebin (1975), and Jost (2011) for details of Eqs. (1) and (2). If $\hbox {M}={\mathbb {R}}^{2}$ and the Euclidean planar metric is used, the length of the parametric curve $\gamma$ defined on the interval [a, b] is the following special case of (2):

$$\begin{aligned} l\left( \gamma \right) =\mathop \int \nolimits _a^b\sqrt{{(dx)^{2}}+{(dy)^{2}}} \end{aligned}$$

(3)

Noting that the customer locations are assumed to be on the planar Cartesian coordinates, the choice of differential elements

$$\begin{aligned} dx=x_i -x_j\\ dy=y_i -y_j \end{aligned}$$

yields the special case of (3); the distance formula employed by Manzour-al-Ajdad et al. (2012a):

$$\begin{aligned} l\left( \gamma \right) =\mathop \sum \sqrt{(x_{i}-x_{j})^{2}+(y_{i}-y_{j})^{2}} \end{aligned}$$

In this work, the distances between customers and the single facility to be allocated will be measured on compact connected Riemannian manifold surfaces (CCRMS); a generalization of planar surfaces. The shortest path geodesic distances are the shortest distances between the customers and a possible location of the facility to be allocated. Therefore we change the planar WP to the manifold WP (MWP): Restatement of the WP considering CCRMS to determine the shortest path geodesics is used for distance calculations. We name the corresponding location routing problem to the MWP as manifold location routing problem (MLRP). The multi-facility location routing problem on the manifold surface settings will be called MMLRP. The main contribution in this work is to provide a heuristic algorithm solution to the MLRP by using Riemannian surfaces and geodesic distances. A special case of the MLRP is the planar LRP when the curvature of the Riemannian surface is zero in 2-dimensional space. The distance calculation method we use in this work is a generalization of the planar distances employed by other researchers to solve the existing facility allocation problems. For example, consider a road changing from flat to mountain; this manifold surface has changed curvature from zero (corresponding to the flat surface) to a positive curvature at each local neighborhood throughout the surface towards the mountain. In this case the geodesics are the roads that connect certain intersections in the local regions. The shortest path geodesic between two locations on this surface is the geodesic with the shortest distance between them.

In the next section we formalize the MLRP with the corresponding assumptions. The solution methodology to solve the proposed MLRP is explained in Sect. 4. The details of this proposed heuristic algorithm and its computational complexity are explained in Sect. 5. An application of the algorithmic solution to a specific scenario is explained in Sect. 6 with the corresponding numerical results. In Sect. 7 a summary of the findings in this paper are highlighted with some suggestions for future explorations.

3 Manifold location routing problem (MLRP)

We assume the following for the MLRP:

• Customers and the facility are assumed to be located on a CCRMS;

• Distances between the customers and possible locations of the facility are calculated by using geodesic distances;

• Customers have known demands and locations;

• Vehicles are capacitated and homogeneous;

• Facility to be allocated is incapacitated;

• All the vehicles have the same capacity;

• The number of vehicles to be operated do not exceed the upper bound of the number of vehicles;

• The number of vehicles to be used will be derived as a by-product of the solution;

• There is no fixed cost for vehicles;

• Each vehicle route starts and finishes at the facility to be allocated.

The following notions will be used for the model formulation and the rest of the paper:

$M$ :

CCRMS corresponding to the local region on Earth’s surface

$C$ :

Set of customers $\hbox {c}_{i},\,\hbox {i}\in I = \{1, 2,{\ldots }, \hbox {m}\}$

$\varphi$ :

Homeomorphism defined for projection from M to ${\mathbb {R}}^{2}$

$a_{k}$ :

Customer locations on M with the coordinates $\hbox {c}_\mathrm{k}=(\upvarphi (\hbox {x}_\mathrm{k}),\,\upvarphi \,(\hbox {y}_\mathrm{k}))$ on ${\mathbb {R}}^{2}$

$a_{0}$ :

Facility location on M with the Euclidean coordinate $\hbox {c}_{0}=(\upvarphi \, (\hbox {x}_{0}), \,\upvarphi \,(\hbox {y}_{0}))$ on ${\mathbb {R}}^{2}$

$E$ :

Combined set of customers and the facility with the facility indexed to be 0

$\gamma _{ij}$ :

Parametric geodesic on M connecting customers’ $\hbox {a}_\mathrm{i}$ and $\hbox {a}_\mathrm{j}$

$V$ :

Set of vehicles $v=1, 2,{\ldots }, n$ with $\left| V \right| \le n$

$v_{max}^i$ :

The maximum capacity of vehicle $\hbox {v}^\mathrm{i}$

$D$ :

The demand set with $\hbox {d}_\mathrm{i}\in D$ corresponding to the demand of customer $\hbox {c}_\mathrm{i} \, \in C,\, \hbox {i}\in I$

$$\begin{aligned} \delta _{\mathrm{ijk}} =\left\{ {{\begin{array}{ll} 1&{}\quad \hbox {if nodes i and j are connected via route k} \\ 0&{}\quad \hbox {otherwise} \\ \end{array} }} \right. \end{aligned}$$

Using the model of Salhi and Nagy (2009), the statement of the problem is as follows:

$$\begin{aligned} min\mathop \sum _{i,j\in E,v\in V} \mathop \int \nolimits _M \Vert \gamma ^{{\prime }}_{ij} \left( t \right) \Vert dt\delta _{ijv} \end{aligned}$$

(4)

subject to

$$\begin{aligned}&\mathop \sum _{j\in E} \delta _{ijv} -\mathop \sum _{j\in E} \delta _{jiv} =0\qquad \forall i\in E;v\in V \end{aligned}$$

(5)

$$\begin{aligned}&\mathop \sum _{i\in E,j\in C} \delta _{ijv} d_i \le v_{max}^i \qquad \forall v\in V \end{aligned}$$

(6)

$$\begin{aligned}&\mathop \sum _{v\in V,i\in U,j\in E-U} \delta _{ijv} \ge 1\qquad \forall U\subset C \end{aligned}$$

(7)

$$\begin{aligned}&\mathop \sum _{v\in V,i\in E} \delta _{ijv} =1\qquad \forall j\in C \end{aligned}$$

(8)

$$\begin{aligned}&\mathop \sum _{j\in E} \delta _{0jv} \le 1\qquad \forall v\in V \end{aligned}$$

(9)

$$\begin{aligned}&\delta _{ijv} \in \left\{ {0,1} \right\} \qquad \forall i,j\in E,v\in V \end{aligned}$$

(10)

The minimization of the total transportation cost on the manifold setting M is indicated as the objective function (4). Traffic flow for visiting each customer by the same vehicle is managed by constraints (5). During the transportation, the maximum capacity of the vehicles cannot be violated by constraints (6). Existences of sub-tours are declined by constraints (7) ensuring that there exist at least one vehicle leaving any subset of customers. Each customer belongs to one and only one tour as a result of constraints (8). Each vehicle leaves the facility either once or never used for transportation as a result of constraints (9) noting that not all the vehicles are necessarily used for transportation. The conditions for decision variables are stated in (10). The MLRP is a mixed integer non-linear programming (MINLP) problem with 3 continuous variables and $\hbox {n(m+1)}^{2}$ discrete variables. Two of the continuous variables are the locations of the customers in the Euclidean space and the third continuous variable is the parameter t for the geodesic on the manifold M. In this paper we introduce the Manifold Weber and the Manifold Location Routing Problems to the scientific community in addition to algorithmic solutions for solving these problems. We’ll give an example in Sect. 7 to illustrate the difference between the solutions to the MLRP and LRP to show the differences between the solutions. The numerical results known in the literature for the MLRP are incomparable with the numerical results obtained in this work since the known data sets used for the LRP are not for general manifold settings, see http://www.bernabe.dorronsoro.es/vrp/. This difference in numerical results arises naturally from the change in the surface assumption from planar surfaces to the Riemannian manifold surfaces.

4 Solution methodology

Solutions to the LRP are obtained by using sequential, iterative, and hierarchical methods. Salhi and Rand (1989) compared the sequential and iterative methods and concluded that the iterative method can yield more accurate solutions. In comparison to the sequential and iterative methods, the hierarchical method has the advantage of determining a solution to the LRP by finding a solution to the vehicle routing and facility location problems simultaneously. Manzour-al-Ajdad et al. (2012a) used ellipses for heuristics yielding to computationally effective results compared to the methods known in the literature. Another hierarchical solution approach can determine the location of the facility within a region and then solving the vehicle routing problem. In this section the main steps of the heuristic algorithm to solve the MLRP are explained.

4.1 Main steps of the heuristic algorithm

The first step of the heuristic algorithm we employed to solve the MLRP is projecting the customer locations and geodesic distances from M to ${\mathbb {R}}^{2}$ by using a homeomorphism. At this step the geodesic distances between the customers are calculated on the manifold surface by using the inner product defined on M. These geodesic distances include all possible roads between customers within the compact connected domain on the surface of M. These lengths correspond to the edge lengths of the road network formed by the customers in the Euclidean space. Therefore the metric choice on M determines the metric to be used in the Euclidean space. A homeomorphism (for example orthogonal projection) is used to project the customer locations and the geodesic distances from M to ${\mathbb {R}}^{2}$.

Second step of the algorithm is designed to solve the LRP in the Euclidean space by employing a heuristic approach. At this step we employ Weiszfeld (1937) formula for determining the initial allocation of the facility. Manzour-al-Ajdad et al. (2012a) defined ellipsoids to be the open set topology of the Euclidean space for heuristic calculations. In this work, we employ open balls $B_{i}$ as the topology for heuristic calculations. The ease of using open balls is calculating the radius of the circles rather than calculating two different radii for an ellipsoid. The heuristic method we use at this step is what we call the linked chain method (LCM): A cost effective facility allocation after chaining z open balls with the center of the $\hbox {i}$th open ball being the best location of the center of the step $\hbox {(i -- 1)}$st open ball, i $=$ 1,...,z. The center of each $B_{i}$ is determined by solving the routing problem within the disk obtained by the interior of $B_{i}$ for all i. The radius of the circle $B_{i}$ is determined by calculating the distance between the $\hbox {i}$th and $\hbox {(i -- 1)}$st open balls. The radius of each consecutive circle is modified dynamically. The stopping criteria for adding circles to the LCM is when a sufficiently small distance between the $\hbox {(z -- 1)}$st and $\hbox {z}$th circles is obtained.

Third and last step of the algorithm is projecting the results obtained in the second step from ${\mathbb {R}}^{2}$ to M and determining a feasible location of the facility on M. The cost effective facility location determined on ${\mathbb {R}}^{2}$ may or may not be a feasible location on M, therefore a local neighborhood search is necessary on M for the best allocation of the facility in the case when the solution is not feasible on M. The main steps of the algorithm are summarized in the following table and the details of it will be explained in Sect. 5.

4.2 Computational complexity of the proposed algorithm

It is well known that LRP is an NP-hard problem noting that both routing and location problems are NP-hard on the Euclidean surface (Sherali and Noradi 1988). Therefore MLRP is also an NP-hard problem noting that the special case of the MLRP is the Euclidean space when the curvature of the RMS is zero. There are two main computational challenges in our algorithm for solving the MLRP: First challenge is to calculate the lengths of the pathways [integrals given in (4)] between the customers on the RMS and the second challenge is to solve the routing problem in the Euclidean space at every circle of the LCM. On one hand the algorithm we propose in Fig. 1 has the advantage of calculating a radius per circle compared to the algorithm of Manzour-al-Ajdad et al. (2012a) with computations including two radii for each ellipsoid, on the other hand the computational algorithm we proposed includes the challenge of calculating the objective function [given in (4)] on the manifold surface M rather than ${\mathbb {R}}^{2}$. The heuristic algorithm we designed to solve the proposed MLRP has computational complexity

$$\begin{aligned} \hbox {max}\left\{ \hbox {O}\left( {I_1 } \right) ,(O\left( {t_1 mlog\left( m \right) } \right) \sum \limits _{j=1}^\mathrm{z-1} p^{j},\hbox {O}\left( {I_2 } \right) \right\} \end{aligned}$$

noting that the original complexity is

$$\begin{aligned} O\left( {I_1 +t_1 mlog\left( m \right) \sum \limits _{j=1}^\mathrm{z-1} p^{j}+I_2 } \right) \end{aligned}$$

where

• $\hbox {O}\left( {I_1 } \right)$ is the time complexity of calculating the lengths of the geodesics determined on the Riemannian manifold surface,

  Fig. 1

  

  Proposed algorithm to solve the MLRP

• $\hbox {t}_{1}$ is the number of points chosen within the initial circle,

• $\hbox {t}_{1}\hbox {p}^\mathrm{j}$ is the number of points chosen within the $\hbox {j}$th circle,

• $\hbox {O}\left( {I_2 } \right)$ is the time complexity of determining a feasible location of the facility on manifold’s surface.

The routing sub-problem’s computational complexity is O(mlog(m)); the time complexity obtained by Clarke and Wright (1964). The time complexity of projection from ${\mathbb {R}}^{2}$ to M (3rd step in Fig. 1) and determining the best location of the facility on the manifold can be a constant, therefore can be negligible in computational complexity calculations in the case when the feasible solution is within a close region on the RMS. It can also be the complexity of the proposed algorithm in the case when the feasible location of the facility is too far from the solution on the CCRMS after using our algorithm.

5 MLRP algorithm details

In this section we explain the details of the heuristic algorithm given in Fig. 1 for solving the MLRP.

5.1 Projection from M to ${\mathbb {R}}^{2}$

The first step of allocating a facility on a local Earth surface (on M) is by projecting the customer locations and all possible route lengths between these customers from the surface of M to ${\mathbb {R}}^{2}$. This initial step is necessary because calculations on a Riemannian manifold are not easy and requires projection from M to ${\mathbb {R}}^{2}$.

A possible homeomorphism that can be employed to map the locations of the customers from the Riemannian manifold surface M to the Euclidean surface ${\mathbb {R}}^{2}$ is

$$\begin{aligned} \upvarphi :\hbox {M}&\rightarrow \hbox {R}^{2} \nonumber \\ a_k&\mapsto \left( \hbox {x}_\mathrm{k} \hbox {cos}\uptheta ,\hbox {y}_\mathrm{k} \hbox {sin}\uptheta \right) \end{aligned}$$

(11)

where $a_k$ represents the locations of the customers and $\uptheta$ are randomly generated angles for customers in local regions (Carmo 1976). The choice of the homeomorphism changes the customer locations in the Euclidean space that would affect the LRP solution in the Euclidean space. Our choice of homeomorphism defined in (11) yields to projection of customer locations to a circular setting. The radius of the circles formed by the customers can be easily obtained from (11) by using the formula

$$\begin{aligned} \hbox {R}_\mathrm{k}^\uptheta =\sqrt{\hbox {x}_\mathrm{k}^2 +\hbox {y}_\mathrm{k}^2 } \end{aligned}$$

(12)

that depends on projection angle $\uptheta$. Another homeomorphism that can be employed for projection can be the orthogonal projection. The following figure (Fig. 2) displays the projection of the customers from surface of the compact connected Riemannian manifold M to the Euclidean space by using the homeomorphism introduced in (11). Figure 3 displays the projected customer locations on ${\mathbb {R}}^{2}$.

Fig. 2

Projected customer locations from M to ${\mathbb {R}}^{2}$

Fig. 3

Projected customer locations on ${\mathbb {R}}^{2}$

All possible pathway lengths between customers are calculated by using (4) and the corresponding geodesic functions can be pre-determined by using GIS (Geographic Information Systems). The geodesics determined between customers on the RMS are projected from M to ${\mathbb {R}}^{2}$ and these lengths are assigned to be the edge lengths between the customers on the customer network formed in ${\mathbb {R}}^{2}$. It is important to note that the metric used on the manifold defines the metric used on the RMS. This is due to the fact that the norm we use for the distance calculations is the norm used on the projected Euclidean surface.

5.2 Facility allocation on ${\mathbb {R}}^{2}$

The initial location of the facility to be allocated is determined by using Weiszfeld formula (1937) for circular objects. Therefore, the formula we employ for the initial allocation is

$$\begin{aligned} x_0^i =\frac{\sum \nolimits _{i=1}^n \frac{x_i \hbox {cos}\uptheta }{l(p_0^\mathrm{i-1} ,c_i)}}{\sum \nolimits _{i=1}^n \frac{1}{l(p_0^\mathrm{i-1} ,c_i )}}\quad \hbox { and }\quad y_0^i = \frac{\sum \nolimits _{i=1}^n \frac{y_i \hbox {sin}\uptheta }{l(p_0^\mathrm{i-1} ,c_i )}}{\sum \nolimits _{i=1}^n \frac{1}{l(p_0^\mathrm{i-1} ,c_i )}} \end{aligned}$$

(13)

where $l(p_0^\mathrm{i-1} ,c_i )$ represents the geodesic distances between the point $p_0^\mathrm{i-1} \, = \,(x_0^\mathrm{i-1} \hbox {cos}\uptheta ,y_0^\mathrm{i-1} \hbox {sin}\uptheta )$ and the customer $c_i .$ The following algorithm is employed for generating $\hbox {t}_\mathrm{k}$ points at the $\hbox {k}$th circle:

The algorithm we use for point generation within each circle of the LCM is given in Fig. 4. The points chosen in each are particularly chosen in different directions for homogenous point distribution. Homogenous distribution of points is necessary since the best location of the facility can be in different directions within each circle. The choice of homeomorphism used for the projection from M to ${\mathbb {R}}^{2}$ can yield to a single circle where the center of the circle is the location of the facility.

Fig. 4

Point generation algorithm within each circle used for the LCM and a graph displaying the directions of the chosen points

In the case when the customer and facility locations are the same points by the used homeomorphism, this non-optimal solution will be recovered by reallocating the facility at a $10^{-5}$ distance from the customer.

The next step of the algorithm is solving the routing problem from the initial location of the facility to determine the possible routes to the customers. These local areas are circles in ${\mathbb {R}}^{2}$ corresponding to the local areas on the surface of M since M is a locally Euclidean space. Recall that we choose $\hbox {t}_{1}$ number of points within the first circle to solve the routing problem for each one these points. Figure 5 illustrates an example of local circular regions on which the distances are calculated for the routing problem from the first facility location to all customers.

Fig. 5

Determining a solution to the routing problem from one of the randomly generated points within the circle where the initial location of the facility f0 is allocated

After determining the best location of the facility within the first circle by solving the routing problems for $\hbox {t}_{1}$ points (locations), next step of the algorithm is application of the LCM by determining the circles k $=$ 2, 3, ...z. Consecutive circles are generated by using the radius determined for each circle. At every $\hbox {k}$th step of the LCM, we choose $\hbox {t}_\mathrm{k}$ numbers within the disk region formed by the interior of the circle k, k$=$2, ...,z, to solve the corresponding routing problem. Recalling the vehicle and facility assumptions for the MLRP from Sect. 3, the main objective of the routing problem is to find the minimal length route for each one of the $\hbox {t}_\mathrm{k}$ points generated at the $\hbox {k}$th circle. We use the formula

(14)

to prevent from route duplication between customers i and j proposed in Altinel and Oncan (2005) with computational complexity O(mlog(m)). In this formula $l(\upvarphi _{\hbox {i}0} )$ is the distance on the RMS between the $\hbox {i}$th customer and the possible location of the facility indexed to be “0”; $v$ is total demands of customers $\hbox {c}_\mathrm{i}$ and $\hbox {c}_\mathrm{j}$ divided by the average of the total demand; $\left( {\rho ,\gamma ,\alpha } \right)$ are the weights assigned to the equation components. Figure 6 displays the change in the location from the 1st circle to the 2nd circle.

Fig. 6

Recovering the best allocation of the facility by determining the second circle’s center f1

Circle generation used for the LCM continues until a sufficiently small circle with radius (if exists) $\hbox {r}_\mathrm{k }$ is obtained. This condition is a result of the calculation $|\hbox {r}_\mathrm{z} -\mathrm{r}_{\mathrm{z}-1} |<\varepsilon$ for a sufficiently chosen $\varepsilon$. Determination of the best possible center of the last circle with this radial condition is the final step of the LCM on the Euclidean Surface. Figure 7 illustrates an example of four steps of circle chaining to allocate the best facility following Figs. 1, 2, 3, 4 and 5. The numbers of points chosen within each consecutive circle used for the LCM are forced to decrease by the algorithm given in Fig. 4; therefore the convergence of the circle radiuses $|\hbox {r}_\mathrm{z} -\hbox {r}_{\mathrm{z}-1} |<\varepsilon$ for a randomly chosen $\varepsilon .$

Fig. 7

Four circles determined by LCM with the final location of the facility f4

It is important to note that the final location of the facility determined is close to the best feasible solution but does not necessarily reflect the best feasible location of the facility. The last step of the algorithm to be explained next is the projection of the determined solutions from ${\mathbb {R}}^{2}$ to M.

5.3 Projection from ${\mathbb {R}}^{2}$ to M

The last step of the algorithm is to map the shortest path distribution routes and the facility location back to the RM surface by using the inverse map $\upvarphi ^{-1}$ of the homeomorphism $\upvarphi$ defined in (11):

$$\begin{aligned} \begin{aligned} \upvarphi ^{-1}:\hbox {R}^{2}&\rightarrow \hbox {M}\\ \left( {\hbox {x}_\mathrm{k} ,\hbox {y}_\mathrm{k} } \right)&\mapsto \left( {\upvarphi ^{-1}(\hbox {x}_\mathrm{k} \hbox {cos}\uptheta ),\upvarphi ^{-1}(\hbox {y}_\mathrm{k} \hbox {sin}\uptheta )} \right) \end{aligned} \end{aligned}$$

(15)

Customer location data is pre-existing on M, therefore it is not necessary to map the customer data from the Euclidean surface back to the RM surface.

6 Examples

In this section we will give an example of MLRP solution by using the algorithm proposed in Fig. 1.

Allocation difference between the LRP solutions for the RM and Euclidean surfaces will be compared by using this example. In this example, we assume there are nine customers and a facility satisfies the assumptions stated in Sect. 3 for the MLRP. The geodesic distances between the customers and the facility are calculated by using functions generated randomly. The following table displays the distances between these customers and the facility in the route to be followed:

In Fig. 8 we consider the initial phase of the routing problem with the corresponding possible routes for the formed networks on the Euclidean and RM surfaces. In this setting, the initial location of the facility is determined by using the Weiszfeld (1937) formula. In Graph (a) the Euclidean distances are calculated on the planar setting whereas in Graph (b) the routes are the geodesics projected from the RM surface to the Euclidean surface. These geodesics are length minimizing with respect to the routes considered on the RM surface. This difference between the routes can have a big impact on the next step of facility allocation since the routes can be effected by areas such as parks, mountains etc. Fig. 8b contains more realistic information than Fig. 8a based on the path lengths calculated on Earth’s surface.

Fig. 8

Graph a Network formed by the Euclidean distances in the Euclidean space. Graph b Network formed in the Euclidean space by mapping the routes from RM surface

Both Graphs 9a and 9b follow the corresponding counterparts given in Fig. 8. The distribution routes to be followed are displayed from the 2nd possible location of the facility for the Euclidean surface based on the Euclidean lengths in Graph (9a) and geodesic distances on RM surface in Graph (9b). The distribution route and the customer where the distribution is initiated changes from Fig. 9a, b. This is due to the fact that geodesic distances can make a big impact on the allocation direction of the facility. For example, there is a difference in the location of the 2nd facility between Fig. 9a, b.

Fig. 9

Graph a Shortest path route determined from the 2nd location of the facility in the Euclidean space by using Graph (8a). Graph b Shortest path route determined in the Euclidean space by mapping the routes from RM surface from the new location of the facility

6.1 Numerical results

The choice of the Riemann metric plays an important role in the distance calculations in the Euclidean space since it is assigned to be the distance between customers in the Euclidean space. It is important to note that the change in the homeomorphism does not make a difference in the allocation of the facility since it is a 1–1 and onto map used to determine a location on the RMS. However the metric choice can make a difference in the computational complexity of the algorithm chosen. This is due to the fact that a homeomorphism if chosen to be a complicated function will yield to more calculations. Next, we display the numerical results and the corresponding route differences between the Euclidean and Manifold settings for Fig. 9a, b.

In Fig. 9, we assume the edge lengths in Fig. 8a are calculated by using the usual norm [given in Eq. (3)] defined on the Euclidean space whereas in the manifold setting the curved edge lengths are calculated by using the metric defined in (15). The numerical results in Table 1 are obtained for both RM and Euclidean surfaces.

The changes on the surface assumption with the changes in the corresponding path lengths have a major difference on the allocation of the facility. This important factor is effective starting at the second phase of the allocation solution since the initial allocation is done by using Weiszfeld (1937) formula.

Table 1 First two phases of the distance calculations on the Euclidean and RM surfaces for solving the LRP problem

6.2 Gas well data and storage allocation

In this section we will determine a gas storage facility location under certain assumptions for gas wells that received permission recently. The following map displays recently permitted 155 active gas wells around the Nine Mile Canyon Field at Carbon County of Utah (http://mapserv.utah.gov/oilgasmining). We assume a new facility is needed for gas storage for the existing gas wells (customers) in the following figure. The 22 black dots in Fig. 10 represent the locations of wells with varying well numbers for each black dot.

Fig. 10

Recently permitted active gas wells around Nine Mile Canyon field with the corresponding field number 35 in Carbon Count of Utah

The curved structure of the underlying Manifold indicates importance of geodesics to be used to solve the corresponding MLRP problem. Matlab is a strong programming language for determining geodesics on a manifold setting; see for example Funtanilla (2004). Figure 11 displays the gridlines that determine the locations of the wells in the Euclidean space. It is easy to determine the customer locations on the corresponding RMS by using the underlying grid lines.

Fig. 11

Figure 10 with $15\times 9$ grid lines

Figure 12 displays a possible geodesic network connection between wells and a possible final allocation of the gas storage facility that is represented by the center of the circle.

Fig. 12

Geodesics based on the well data with the corresponding network where circle represents the initial location of the facility to be allocated

We assume there is only one route to be followed for the simplicity of displaying numerical result differences between linear and geodesic curve distances. The total Euclidean linear distances traveled to visit each location is determined to be 21.246 units by using the gas well grid locations displayed in Fig. 11. The corresponding geodesic distances totaled for the same route of visiting location resulted in 44.028 units. This difference in distance traveled will have an important impact on the cost calculations as well as the allocation of the facility for these newly permitted gas wells.

7 Summary and future research ideas

In this work we introduced the Weber and LRP for RMS; a generalization of the well-known classical Weber and LR problems by changing the domain from Euclidean surface to RMS, and we also introduced an algorithm to solve these problems. MWP and MLRP are more realistic problems to tackle than the Euclidean surface correspondences since Earth’s surface is an RMS and roads are geodesics on this RMS connecting the facility and customer locations. Locations such as mountains, lakes, etc. can have big impacts on the distances between customers. A solution to the MLRP by using what we so called “Linked Chain Method” is obtained after introducing a homeomorphism employed for projecting the customer locations from the RMS surface to the Euclidean surface. After solving the LRP on the Euclidean surface, the coordinates of the facility location is mapped back to the RMS. In the Manifold surface case of solution, a feasible solution can be obtained that is not necessarily the best solution as it is well known from the Euclidean surface LRP.

We invite other researchers to work on the MW and MLR problems by introducing new homeomorphisms that can yield to different LRP computationally effective results in the Euclidean space.

Another aspect that can be improved by other researchers in the scientific community is the lack of existing problems for numerical applications in the literature. We hope there will be numerical data introduced for MW and MLR problems stated for RMS settings so that the solution methods can be compared by checking the corresponding numerical results as in the Euclidean Weber and LRP problems.