1 Introduction

We examine the multi-type Facility Location Problem (FLP) motivated by real FLP variants in parcel delivery and in printing services. In the former case, a third party logistics (3PL) company wishes to select shops from which clients will be served and warehouses supplying these shops. In the latter case, a company offering ‘printing-as-a-service’ wishes to select which printers to install at which locations inside an office space in order to cover the demand of employees.

Both cases assume facilities of different types, capacities in both locations and facilities, unsplittable client demand, nonlinear setup cost depending on the number of facilities in a location and varying per location and facility type, nonlinear service cost depending on the volume of demand served and varying per facility type and, last, linear connection cost per client and location. Thus both cases impose a quite challenging setting, not only by assuming facilities of multiple types and unsplittable demand, but mostly by having non-linear terms for both setup and service costs. Indicatively, even modern variants like (Irawan et al. 2019) that handle unsplittable demand with different capacity levels per location, consider it sufficient to assume only fixed service costs per such level.

Formally, we assume three disjoint sets representing clients, facilities and locations. Every client must be assigned to a unique facility-location pair, whereas multiple facilities can be placed in a location and the same facility type can occur in multiple locations. This yields a three-index integer program (IP), while linearisation imposes a fourth index. Although not uncommon for FLP formulations (Aardal et al. 1996; Mazzola and Neebe 1999; Wu et al. 2006; Zheng et al. 2019), multi-indexed variables restrict the problem size that can be handled by exact methods. Hence, motivated by the scale of the real applications examined here, we define a two-index IP with a nonlinear objective function, whose piecewise linearisation requires a third index. The linearised IP is strengthened with additional constraints to obtain a tighter LP-relaxation and thus improved lower bounds.

Beyond mathematical modeling, we introduce a set of greedy construction heuristics (with one of them relying on LP-rounding) and a metaheuristic that combines local improvement operations with a Variable Neighborhood Descent (VND) strategy. The solutions derived are computationally shown to be near-optimal thus also serving as effective upper bounds for an exact solver. In several instances, even the greedy heuristics provide quick solutions of acceptable quality, as shown by the empirical gap ratio against the initial LP (i.e., at the top node of the Branch & Cut tree). All these features are investigated computationally via an extensive list of both random (Beasley 1988) and real-life instances, ranging from \(10^4\) to \(10^7\) variables. To be more precise, due to the richer structure of our model compared with those in the literature, we carefully extend the benchmark random instances. We compute the exact solution for all instances except for some very large benchmark ones (where an exact solver runs out of memory), for which we only show near-optimality through the empirical gap ratio.

In a typical FLP variant, each location can host a single facility and the assignment cost is distinguished between the connection cost from clients to locations and the setup cost of a location to place the corresponding facility. A prominent review study appears in Sridharan (1995), where constant setup costs are taken into account together with hard capacity constraints on facilities, and client demand splittable among multiple facilities. Multi-level FLPs impose that each client must be assigned to a location through a hierarchical sequence of facilities, each belonging to a distinct level/class and the optimal solution should balance the connection cost of clients to locations through their assigned sequence of facilities and the setup costs of the facilities used (Aardal 1998; Aardal et al. 1996; Ortiz-Astorquiza et al. 2018). An interesting application of uncapacitated 2-level FLP (Zhang et al. 2019) examines the transportation of commodities from a set of depots to a set of customers, selecting several distribution centers (from a potential set) as intermediates to allocate each customer, with the goal to minimize the sum of fixed costs subject to constraints on the supply of each depot.

Real problems exhibit additional structure, hence leading to the introduction of multitype, or even multiproduct variants (Lee 1991; Mazzola and Neebe 1999). Nonlinear terms appear in the objective due to economies of scale or the mingling of multiple factors that affect the actual unitary cost. Some indicative examples are the use of concave costs in Soland (1974), the multiperiod FLP in transportation networks (Wu et al. 2015) where the transportation cost from facilities to retailers follows non-convex economies of scale, a location-inventory model (Shu et al. 2015) where the annual operating and handling cost of a facility is a non-decreasing concave function of the demand volume served.

Therefore, FLP-related research has focused on the linearisation of nonlinear functions, e.g., Holmberg (1999) suggest an exact method for transportation problems with convex costs. This linearisation method is extended in Wu et al. (2006) and that extension is employed for our linearised model. Since the exact linearisation of decision variables is not plausible computationally (Holmberg 1999), the piecewise linear approximation method offers an effective treatment (Harkness and ReVelle 2003; Wu et al. 2015), while Lagrangian FLP heuristics present another alternative (Lu et al. 2014; Saif and Elhedhli 2016; Shu et al. 2015).

In this paper we opt for the former approach, since we are interested in solving exactly large-scale linearised FLPs and also because the setup and service cost functions do not always have a compact form. We strengthen such a linearisation by valid inequaltiites proposed in Aardal (1998). Then, we introduce several heuristics motivated by algorithms for nonlinear generalised assignment problems (see e.g., Sharkey and Romeijn 2010) and particularly the ones handling concave setup cost (Jain et al. 2003; Hajiaghayi et al. 2003). Given also LP-rounding heuristics for the capacitated FLP (Shmoys et al. 1997) and the near-optimal lower bounds achieved by our strengthened LP-relaxation, we introduce a greedy approach, based on the filtering and rounding method (Lin and Vitter 1992), which produces high-quality solutions particularly for our parcel delivery instances.

Despite the combined effectiveness of these heuristics, there are real instances where their performance worsens considerably due to varying capacities of locations and facilities. Thus, we complement them by a VND approach (Hansen et al. 2010), whose local improvement stages are inspired by the multiexchange operations of Zhang et al. (2005). Although several local search methods have been applied to FLP variants (e.g., Contreras and Díaz 2008), VND appears quite versatile and has therefore attracted strong attention (e.g., Irawan et al. 2019). More precisely, our VND approach considers two neighborhoods of subsets of locations (carefully selected through a neighborhood reduction mechanism) or facilities and explores them through local improvement stages using three different strategies (Next-Fit, kth-Best-Fit and Best-Fit) under both a fast greedy approach that computes near-optimal solutions and a linearised IP that computes optimal ones per neighborhood. Although the former approach reduces the objective cost considerably in a few seconds, the latter ends up computing almost optimal solutions, in just a few minutes for most instances. Both local search methods produce improved solutions that speed up an exact solver when used as upper bounds.

The rest of the paper is organised as follows. In Sect. 2, we provide a formal definition of our FLP model, propose a nonlinear integer programming formulation and address its computational hardness. In the same section, we introduce a linearisation of this model, as also enhanced by strong valid inequalities, and describe in detail how this model captured the features of managed printing services and parcel delivery through micro-hubs. Section 3 presents our algorithmic framework comprised by construction heuristics and a VND metaheuristic. In Sect. 4, we experiment with an extensive set of benchmark random instances (Beasley 1988) plus real ones and report results showing the efficiency of our integrated approach, particularly in large scale instances. We conclude in Sect. 5.

Our data and code can be found in https://github.com/i-avgerinos/Multitype-Facility-Location An appendix, provided as supplementary material, contains further details on the size of the instances and the numerical results obtained.

2 Modelling

2.1 A nonlinear IP and its linearisation

The key FLP features of our model are as follows: the demand of each client has to be completely served by a single facility located at a single location; locations can host multiple facilities and facilities are distinguished into types and multiple facilities of the same type can be placed in the same or different locations. There is a fixed opening cost per location, while all other forms of cost are associated with two of the three entities involved: a connection cost applies per client and location, which for simplicity is charged per unit of demand; a nonlinear setup cost applies per location and facility type and depends only on the number of facilities of that type placed in the location in hand; last, a nonlinear service cost arises per type of facility and depends on the total demand served by a facility of that type (also known as ‘production cost’ Harkness and ReVelle 2003). There is an upper bound on the total demand served by a facility and by all facilities placed in a location.

Table 1 Model parameters
Full size table
Table 2 Decision variables
Full size table

This FLP setting is broader than the ones in the literature, and at least in literature reviewed here. Still, it is not as general as one could be, because costs are associated with at most two of the entities, whereas in theory costs could be associated with each triple assignment of a client to a facility and a location. To present our nonlinear integer program (NIP) and its linearisation (LIP), we employ the notation of Tables 1 and 2.

The objective function of (NIP) includes: the unit connection cost \(a_{ij}\) between client i and location j, the opening cost \(c_j\) of j, the setup cost \(f_{jl} (\cdot )\) of location j regarding facilities of type l that depends on the number of these facilities l placed in j thus written as \(f_{jl}\left( \sum _{k \in K_l} y_{jk} \right) \), the service cost \(g_l (\cdot )\) for a facility of type l as a function of the total demand served hence written as \(g_{l}\left( \sum _{i \in I} d_i \cdot z_{ik} \right) , ~k \in K_l\) (this somehow awkward notation emphasises that g is the same function for all facilities of the same type).

$$\begin{aligned} (\mathbf{NIP}):\nonumber \\ \text {min}&\sum _{i\in I} \sum _{j\in J} a_{ij} \cdot d_i \cdot x_{ij} + \sum _{j\in J} w_j \cdot c_j +&\sum _{j\in J} \sum _{l\in L} f_{jl}\left( \sum _{k\in K_l} y_{jk}\right) + \sum _{l\in L} \sum _{k\in K_l} g_l\left( \sum _{{i\in I}} d_i \cdot z_{ik} \right) \nonumber&\\&\text {subject to:}&\nonumber&\\&\sum _{k \in K} z_{ik} = 1&\forall i \in I&\end{aligned}$$
(1)
$$\begin{aligned}&w_j \ge y_{jk}&\forall j \in J, k\in K&\end{aligned}$$
(2)
$$\begin{aligned}&\sum _{j\in J} y_{jk} \ge \sum _{i\in I} z_{ik}&\forall k \in K&\end{aligned}$$
(3)
$$\begin{aligned}&\sum _{j\in J} y_{jk} \le 1&\forall k \in K&\end{aligned}$$
(4)
$$\begin{aligned}&y_{jk} + z_{ik} \le x_{ij} + 1&\forall i\in I, j\in J, k \in K&\end{aligned}$$
(5)
$$\begin{aligned}&\sum _{i \in I} d_i \cdot z_{ik} \le e_l&\forall k \in K_l, l\in L&\end{aligned}$$
(6)
$$\begin{aligned}&\sum _{i \in I} d_i \cdot x_{ij} \le b_j&\forall j\in J \nonumber&\\&x_{ij}, y_{jk}, z_{ik}, w_{j} \in \{0,1\}&\forall i\in I, j\in J, k \in K&\end{aligned}$$
(7)

Constraints (1) ensure that every client is assigned to a facility, while (2) ensure that if a facility is placed at a location this location must first open. Constraints (3) impose that a facility must be placed somewhere in order to serve some clients, while (4) indicate that every facility can be placed at most once (although other facilities of the same type may be used). Constraints (5) connect all indices thus skipping the necessity of three-indexed variables: for a client to be served by a facility placed in a location, this client should also be explicitly associated with that location. Constraints (6) and (7) impose the capacity limits per facility type and location, respectively.

This FLP model generalises the NP-hard capacitated FLP (Mirchandani and Francis 1990). Since it allows non-metric connection costs among clients and locations, it is at least as hard as set-covering hence not admitting a constant approximation algorithm unless \(P=NP\) (Williamson and Shmoys 2011). Let us also observe that our model is a non-trivial generalisation of the unsplittable hard-capacitated FLP (Bateni and Hajiaghayi 2012; Levi et al. 2012): (NIP) includes hard capacities in the sense that each location is either opened or not, and unsplittable client demands. As shown in Bateni and Hajiaghayi (2012), even for single-facility locations, linear setup and service costs, metric (or zero) connection cost, no approximation algorithm can be achieved without violating (by some small positive factor) the location capacities. Overall, the increased detail of our model leaves no room for approximation algorithms with proven performance guarantees, hence justifying our focus on mathematical programming formulations and (meta)heuristics.

The introduce the linearisation of (NIP), let us not that it is imposed not only by the need to solve (NIP) to optimality but also by the lack of compact forms for the nonlinear terms in the objective functions, i.e., setup cost \(f_{jl} (\cdot )\), \(j\in J, l\in L\) and service cost functions \(g_{l}(\cdot ),~l\in L\), whose values, instead, are given implicitly by an ‘oracle’ determining the actual cost of the corresponding decision.

Regarding the setup cost functions, we apply the exact linearisation approach suggested in Holmberg (1999) and Wu et al. (2006), adding an index to represent that n facilities of type l are placed at location j,  (i.e., using binary variables \(y^{\prime }_{jln}\) instead of \(y_{jk}, k \in K_l,\)), thus replacing each setup cost function \(f_{jl}\) by the constants \(f^{\prime }_{jln}=f_{jl}(n).\) Although this simple method achieves an exact linearisation, it is impractical when the number of units gets large. Similarly, for the service cost functions we add an index for every facility type and every capacity-wise feasible subset of clients, hence resulting in an exponential number of binary variables \(z^{\prime }_{ik}, i \in 2^I.\) Consequently, we implement the standard piecewise linear approximation approach (as in Harkness and ReVelle 2003) by assuming that each function \(g_l\) is given by a finite number of linear segments, hereafter referred to as bands. The cost coefficient associated with each band can be obtained through any approximate way from the original function, e.g., linear interpolation or sampling through a number of calls to the oracle. A service cost \(g'_{lm}\) is applied to each demand unit whenever the total demand served by facilities of type l falls within the upper and lower bounds (\(u_{lm}, \ell _{lm}\) respectively) of band m. For simplicity, we assume that the set of bands M is the same for all facility types; generalizing to different bands per type is straightforward.

The artificial variable \(v_{jkm}\) determines whether facility k is placed in location j serving under the band \(m \in M\) and is used to exclude the use of multiple bands per facility. Each variable \(z_{ik}\) is replaced by variables \(z^{\prime }_{ikm}, m \in M,\) to associate the service cost with the band m in the objective function. All other variables remain as in the (NIP) model.

$$\begin{aligned} (\mathbf{LIP}):\nonumber \\ \text {min}&\sum _{i\in I} \sum _{j\in J} a_{ij} \cdot d_i \cdot x_{ij} + \sum _{j\in J} w_j \cdot c_j +&\sum _{j\in J} \sum _{l\in L} \sum _{n \in [K_l]} f^{\prime }_{jln}\cdot y^{\prime }_{jln} + \sum _{l\in L} \sum _{k\in K_l} \sum _{m \in M} g^{\prime }_{lm} \cdot d_i \cdot z^{\prime }_{ikm} \nonumber&\\&\text {subject to:}&\nonumber&\\&\sum _{k \in K} \sum _{m \in M} z^{\prime }_{ikm} = 1&\forall i \in I&\end{aligned}$$
(8)
$$\begin{aligned}&\sum _{i\in I} d_i \cdot z^{\prime }_{ikm} \le u_{lm} \sum _{j\in J} v_{jkm}&\forall k\in K_l, l\in L, m\in M&\end{aligned}$$
(9)
$$\begin{aligned}&\sum _{i\in I} d_i \cdot z^{\prime }_{ikm} \ge \ell _{lm} \sum _{j\in J} v_{jkm}&\forall k\in K_l, l\in L, m\in M&\end{aligned}$$
(10)
$$\begin{aligned}&\sum _{n\in [K_l]} y^{\prime }_{jln} \le 1&\forall j\in J, l\in L&\end{aligned}$$
(11)
$$\begin{aligned}&\sum _{k\in K_l} \sum _{m\in M} v_{jkm} \le \sum _{n\in [K_l]} n \cdot y^{\prime }_{jln}&\forall j\in J, l\in L&\end{aligned}$$
(12)
$$\begin{aligned}&o_j \le b_j \cdot w_j&\forall j \in J&\end{aligned}$$
(13)
$$\begin{aligned}&\sum _{j\in J} \sum _{m\in M} v_{jkm} \le 1&\forall k \in K&\end{aligned}$$
(14)
$$\begin{aligned}&\sum _{m\in M} v_{jkm} + \sum _{m\in M} z^{\prime }_{ikm} \le x_{ij} + 1&\forall i\in I, j\in J, k \in K&\end{aligned}$$
(15)
$$\begin{aligned}&\sum _{i \in I} \sum _{m\in M} d_i \cdot z^{\prime }_{ikm} \le e_l&\forall k \in K_l, l\in L&\end{aligned}$$
(16)
$$\begin{aligned}&o_j = \sum _{i\in I} d_i \cdot x_{ij}&\forall j\in J&\end{aligned}$$
(17)
$$\begin{aligned}&\sum _{j\in J} o_j = \sum _{i\in I} d_i \nonumber&\\&o_j \ge 0&\forall j\in J&\nonumber&\\&x_{ij}, y^{\prime }_{jkn}, z^{\prime }_{ikm}, v_{jkm}, w_j\in \{0,1\}&\forall i\in I, j\in J, k \in K, n \in [K_l], m \in M&\end{aligned}$$
(18)

(LIP) is the linearised version of (NIP). As usual \([K_l]\) stands for \(\{1,2,\ldots ,|K_l|\}.\) Constraints (8) replace (1). Constraints (9) and (10) enforce the band selection for the service costs. Constraints (11) ensure that the number n of facilities of type l per location is unique and (12) define its value. Constraints (13) replace (2) and (7), by exploiting the dummy variable \(o_j\), while (14) ensure that every facility is assigned to at most one location and at a single band. Constraints (15) and (16) replace (5) and (6). Constraints (17) secure that the value of the dummy variable will be equal to the assigned demand for all locations, while (18) ensure that the total demand assigned to the selected locations is equal to the demand of all clients.

(LIP) includes a set of redundant constraints, which lead to near-optimal lower bounds of its LP-relaxation (as shown later on). In particular, we adapt the valid inequalities proposed in Aardal (1998) for the capacitated single- and 2-level FLP (although these FLP variants assume linearity and splittable demand thus admitting flow formulations), and induce a “dummy” non-negative variable \(o_{j}\) that is set equal to the total demand assigned to location j. These inequalities are (13), (17), and (18) in (LIP) and their validity is easy to show. Although further valid inequalities could be drawn from Aardal (1998), e.g., minimal covers of the surrogate knapsack on the total demand, these have no considerable impact on the tightness of (LIP)’s LP-relaxation.

Let us now proceed by showing how (LIP) is slightly differentiated in two applications. Both have not received attention in the FLP literature, despite their significance and their existence in the corresponding industrial domains for more than a decade.

2.2 Managed printing services

Managed Printing Services (or MPS for short) is the growing industrial sector that offers printing as-a-service. Large office spaces have traditionally been buying printers and then paying separately for their consumables and maintenance. Instead, a growing number of them now buys a MPS contract for a period of 3–5 years and pays a fixed price per copy of black & white (BW) or colour page printed. That cost-per-copy covers all costs associated with the entire life-cycle of the so-called fleet of printers associated with this contract. Contracts may have additional constraints, for example regarding the minimum or maximum number of BW copies printed monthly, the ability for A3 printing or stapling, or printing speed and quality.

A MPS provider must then solve the problem of covering each customer’s wish-list and printing specifications using a MPS plan that minimises the total operational cost over the contract’s duration, which is called total cost of ownership. A typical customer has several existing positions in which people currently print, called ‘slots’. In the MPS plan offered, each slot must be served by a single printer located in a single place inside a large floor or building. The FLP setting should now be clear: slots define our clients I,  locations J are the places in the building where a printer could be placed and printers are the facility types L cloned in multiple copies to define facilities K. However, there are certain features that require minor changes in our model.

  1. (a)

    There is no setup cost per location, i.e., multiple printers can be placed side-by-side at zero setup cost, while fixed opening costs are considered also negligible.

  2. (b)

    There is no capacity constraint per location, but only per printer.

  3. (c)

    The set of locations is a large subset of the locations of existing clients (‘slots’) and it is not uncommon that \(|I|=|J|\), i.e., J is quite large in the context of the FLP literature.

  4. (d)

    Partly balancing the previous feature, the number of locations serving each client is limited. Typically, most of the clients are preassigned to some location while the rest might be served by \(2-5\) different locations, therefore many among the variables \(x_{ij}\) are set to 0. Similarly not all printers are eligible for all locations due to specific characteristics that must be offered at that location (e.g., A3 printing) hence many among variables \(z_{ik} (z^{\prime }_{ikm})\) are also set to 0.

  5. (e)

    Although the purchase cost per printer is fixed, the service cost is calculated by an oracle that appears to represent an irregularly formed nonlinear function. In fact, this calculation is a private and confidential knowledge of each MPS provider since including travel, personnel and equipment costs.

  6. (f)

    Each client demand consists of two types, i.e., BW and colour printing demand. This means that if a client demand includes also colour printing, then at least one colour printer should be used, either for serving the entire demand or only the colour demand of that client.

  7. (g)

    Since each client has demand of two types (BW, colour), we replace each variable \(z^{\prime }_{ikm}\) with two new variables \(z^{\prime BW}_{ikm}, z^{\prime C}_{ikm},\) which represent each band for BW and colour printing per printer and client. We similarly replace \(g^{\prime }_{lm}\) with \(g^{\prime BW}_{lm}\) and \(g^{\prime C}_{lm}.\)

2.3 Parcel delivery through micro-hubs

Consider a set of clients each having a weekly demand measured in parcels for products ordered electronically and delivered to them through shops, which either keep a parcel for a client to pick it up (this is the so-called ‘click & collect’ procedure) or deliver parcels directly to the client’s address. This problem has been given to us by a Greek 3rd party logistics (3PL) provider, who serves multiple e-shops and collaborates with various physical shops. In fact, this 3PL company wishes to examine whether its costs could be significantly reduced if the set of shops that act as micro-hubs enabling click & collect practices were enlarged.

The 3PL’s focus is not on routing because cost mainly arises from the processes of parcel handling in warehouses that supply the shops and then the handling at the shops themselves. That is, there is a pre-defined connection cost per parcel associated with each client and all shop-warehouse pairs through which this client can be served; multiple (but not all) shops are eligible for each client, mainly in terms of distance to the client’s delivery address, while multiple warehouses are eligible to supply each shop. Beyond this connection cost, concave functions can represent the cost of supplying multiple shops by a single warehouse (this is our setup cost) and the service cost of clients from shops which are usually determined by an internal (and possibly disclosed) procedure of the 3PL or a courier company.

To adopt the above application to our FLP model we consider as I the set of clients and as J the set of warehouses which are the ‘locations’ from which shops are supplied. Although set K is related to shops viewed as ‘facilities’, we face the complication that, although each client will be served by a single shop, each shop could be served by multiple warehouses (while the demand of each client must be served by a single warehouse). To overcome this, we consider shops to be facility types thus defining set L,  with multiple copies of shop \(l \in L\) (one per eligible warehouse) defining the set \(K_l\) and the union of all such copies comprising the set of facilities J. Both shops and warehouses have capacities but the capacity of each shop applies to all its copies. Let us note here that the initial 3PL’s suggestion for a single warehouse per shop yields, as expected, solutions of increased cost.

Interestingly, this application generalises the capacitated 2-level FLP variant (Aardal 1998; Aardal et al. 1996), where the setup and service costs are nonlinear functions and the client demands are unsplittable. In 2-level FLP each client demand must be shipped from a warehouse location via an intermediate transit station which belongs to a certain level/class of facilities. Here, the set of possible intermediate stations for each client demand would be all nearby shops. However, this setting would associate costs with each triple assignment of a client to a shop and a location, while imposing a three-index formulation (Aardal 1992), which becomes a fourth-index in the linearisation process, resulting at a rapid growth on the (LIP)’s constraints and variables as instances become larger.

Hence, our FLP formulation has to be altered as follows.

  1. (a)

    The nonlinear service cost function must be applied to the volume served by all copies of a single shop, i.e., to each \(K_l, l \in L\) instead of each \(k \in K.\) For that purpose Constraints (9) and (10) are replaced as follows in order for the model to select the proper band m.

    $$\begin{aligned}&\sum _{i\in I} \sum _{k\in K} z^{\prime }_{ikm} \cdot d_i \le u_{lm} \cdot \sum _{j\in J} \sum _{k\in K_{l}} v_{jkm}&\forall l\in L, m\in M&\end{aligned}$$
    (19)
    $$\begin{aligned}&\sum _{i\in I} \sum _{k\in K} z^{\prime }_{ikm} \cdot d_i \ge \ell _{lm} \cdot \sum _{j\in J} \sum _{k\in K_{l}} v_{jkm}&\forall l\in L, m\in M \end{aligned}$$
    (20)

    Note that Constraints (19) and (20) refer to the sum of copies for every facility type \(l\in L\), while (9) and (10) referring to all copies of all facility types.

  2. (b)

    The connection cost is no longer defined per client and location, i.e., not associated with the variables \(x_{ij}\). Here, this cost is related to a parcel transferred from a warehouse to a shop and then to the client. Therefore, the decision variables \(x_{ij}\) are replaced with variables \(x_{ip}\), \(p \in L\times J\), where p is a pair of location and facility type.

  3. (c)

    The replacement of Constraints (9) and (10) affects also Constraints (15), because the variables \(z_{ikm}\) and \(v_{jkm}\) are forced to be equal to 1 not for the same copy of facility k, but for the sum over all copies of the same facility type. This issue can be handled by replacing Constraints (15) with:

    $$\begin{aligned}&\sum _{k\in K_l} \sum _{m\in M} v_{jkm} + \sum _{k\in K_l} \sum _{m\in M} z^{\prime }_{ikm} \le x_{ip} + 1&\forall i\in I, j\in J, l \in L, p\in L\times J,&\end{aligned}$$
    (21)

    while adding the following constraints.

    $$\begin{aligned}&\sum _{i\in I} \sum _{m\in M} z^{\prime }_{ikm} \le \sum _{j\in J} \sum _{m\in M} |I| \cdot v_{jkm},&\forall k\in K&\end{aligned}$$
    (22)

3 Solution methodology

3.1 Combinatorial heuristics

We propose a set of greedy heuristics that can tackle nonlinear cost functions, inspired by the dual-fitting method for linear (Jain et al. 2003) and concave (Hajiaghayi et al. 2003) setup cost functions. The latter has been designed for the standard uncapacitated FLP variant where unit-demand clients are assigned to facilities to minimise their total connection and setup costs, so it is not directly applicable here.

Our setting requires to explore more elaborate greedy variants in order to deal also with multi-type facilities, their capacities and nonlinear service costs. Each of the variant we propose proceeds greedily based on the dual fitting method in one or two stages, starting with the empty set and iteratively augmenting the current partial solution with an additional assignment that minimises the increase in the total cost objective, while respecting the capacity constraints.

A two-stage greedy can either assign first each client to a location and then facilities to ‘filled’ locations or assign first clients to facilities and then ‘filled’ facilities to locations. The option of assigning first facilities to locations and then distributing the clients is neglected because capacity constraints are affected only by client demand. For the same reason, a single-stage greedy could only assign each client directly to a facility and a location. Hence the heuristics are as follows.

  • LocationsFirst. It assigns each client to a location according only to the connection cost, while respecting the capacities of each location. Then, it assigns facilities to filled locations according to both the setup cost associated with facility types and locations and the service cost associated with clients and facilities, while respecting the capacity of each facility.

  • FacilitiesFirst. This inverts the order of assignment: it assigns each client to a facility according only to the service cost, while respecting the capacities of each facility type. Then, it assigns filled facilities to locations according to both the setup cost associated with facility types and locations and the connection cost associated with clients and locations, while respecting the capacity of each location.

  • SingleStage. This algorithm assigns each client simultaneously to a facility and a location according to the total cost, while respecting the capacity of each location and each facility.

figure a

Algorithm 1 details the steps of the SingleStage heuristic, following the notation of Table 1. The two-stage approaches are implemented quite similarly, except for the two-stage assignment part. As indicated by the dual fitting method (Hajiaghayi et al. 2003), the assignment of client to facilities and locations is guided by a varying cost contribution, which is updated through an (iteratively increasing) time variable t (see Line 3) in order for each new client to be assigned to a facility and location.

To speed up the execution of the algorithm, instead of increasing t by one in each iteration, we consider a set of discrete time events corresponding to the potential assignment of clients to facilities and facilities to locations. An event becomes eligible (i.e., secures the potential assignment, see Lines 15, 25, 27) only if it equals the marginal total cost (i.e., the increase in total setup, service and connection cost) that arises when the assigned clients and/or facilities are increased by one. Also, if in some iteration s of Algorithm 1 an eligible event occurs, then t will start the next iteration from a value equal to the minimum cost contribution over all events occurred during s and not necessarily from the eligible one. This intervention, although it slows down the termination of the process, secures that better solutions are also considered.

Concerning the use of marginal costs (see Lines 11, 13, 23) they are commonly used to handle the concavity of a cost function (see in Jain et al. 2003): a cost function \(f: \mathbb {N}\rightarrow \mathbb {N}\) is called concave if and only if, for each \(x\ge 1\), \(f(x+1) - f(x)\le f(x) - f(x-1)\). This means that by assigning a new client to a facility or placing a new facility to a location, automatically reduces the assignment costs of the rest clients or facilities respectively. Since a large part of our instances exhibit concavity due to economies of scale, the latter approach appears to be efficient when it is applied to our real-life instances.

To speedup the assignment process and avoid a pseudo-polynomial number of iterations we make use of a priority queue to maintain the list of event triggers (Jain et al. 2003), while omitting time intervals with no assignments. If \(n=\max \{|I|,|J|,|K|\}\), the time complexity of FacilitiesFirst and LocationsFirst is \(O(n^4\log n)\) and that of SingleStage \(O(n^5\log n)\). Clearly, algorithm SingleStage is slower, however it provides much better upper bounds for most instances and this is why we will consider only the results of SingleStage in terms of empirical evidence. It is also easy to guess that the algorithm FacilitiesFirst handles better the service cost and LocationsFirst behaves more effectively in the presence of large connection costs.

3.2 An LP-rounding heuristic

Rounding the solution of an LP-relaxation is a standard approach for designing near-optimal solutions to IP models (Vazirani 2013). However, implementing such LP-based approaches is often ineffective (Wolsey 1998) mainly because of a loose relaxation. Motivated by the strength of our relaxation, we exploit the LP-rounding algorithm in Shmoys et al. (1997).

Our algorithm proceeds in two phases. First, it calculates a new fractional solution by applying the filtering technique (Lin and Vitter 1992) which guarantees that, whenever a fractional assignment of a client to a facility and a facility to a location is made, the service and setup costs do not get too big; this is done by using a configurable parameter called \(\alpha \)-point, \(\alpha \in (0,1]\), which indicates the minimum cost at which an \(\alpha \)-fraction of a client is assigned to a facility (respectively, an \(\alpha \)-fraction of a facility is placed to a location). Secondly, our algorithm determines the best possible value of \(\alpha \) (i.e., the one that leads to the smallest possible upper bound on the total cost) by carefully rounding the variables to produce a near-optimal integral feasible solution to the (LIP) model.

figure b

Note that, in Shmoys et al. (1997) the \(\alpha \) value is determined as a part of the algorithm’s approximation analysis, however, due to the increased complexity of our model (see Sect. 2) this analysis is not applicable here. We overcome this issue by applying binary search on \(\alpha \).

Algorithm 2 presents the details. For the filtering and rounding it suffices to bound (based on the \(\alpha \)-point) only variables \(z'\) and u of the LP-relaxation of (LIP), where \(z'\) guides the assignment of clients to facilities and u the placement of facilities to locations; in fact, since \(z'\) and u are fixed, the other variables (y, x, w) can be easily rounded to 0 or 1, i.e., by opening the selected locations (variable w) and assigning the clients to locations where their facility is already placed (variable x). Moreover, in cases where the candidate value of \(\alpha \) is too big compared with the fractions of clients assigned to facilities and facilities placed to locations in \(\bar{S}\) the algorithm does not produce a feasible solution, thus we decrease the value of \(\alpha \) (see Line 7) by a small amount that leads to a feasible solution. Overall, by testing only a few number of \(\alpha \)-points (2–3 different values of \(\alpha \) are sufficient for each instance) Algorithm 2 determines the one which produces the less costly solution.

3.3 A VND improvement metaheuristic

Although the above heuristics can produce fast and good upper bounds, there are cases where their optimality gap rises to almost 1.3. As locations are the entities that contribute the largest part of (opening, setup and connection) cost the increased optimality gap is attributed to a suboptimal selection of locations. Specifically, in instances where locations are varying in terms of capacity and opening cost, the best heuristic prefers to open multiple locations of small capacities and opening costs, instead of a few large and expensive ones that might lead to an improved solution. This is of no supripse, as non-uniform hard capacities are problematic for greedy algorithms (Hajiaghayi et al. 2003; Shmoys et al. 1997).

To reduce the negative effects of hard capacities on the solution quality, Pal et al. (2001) proposed a local search approach for the capacitated FLP, albeit under splittable client demands. Three types of local improvement operations were introduced: open one facility; open one location and close one or more locations; close one location and open one or more locations. This approach was further extended by a the so-called multiexchange operations (Zhang et al. 2005) that might exchange multiple locations. Most importantly, each time a new set of locations is considered as opened, the reassignment of clients to locations can be done in polynomial time using a linear programming formulation of the reduced problem instance, exactly because client demands are splittable. Although this approach leads to the best known approximation guarantee for the capacitated FLP, it appears slow because of the large-sized neighborhoods, thus requiring a restricted subset of these operations in order to be applicable.

Inspired by the above results, we develop a variable neighborhood descent (VND) strategy (Hansen et al. 2010), guided by the following three improvement stages. First, we fix the assignment of clients to facilities according to the solution of the construction heuristic and explore a neighborhood of carefully selected subsets of locations; whenever a new subset of locations is explored the rest of the locations are considered as closed. Secondly, we fix the locations opened at Stage 1 as well as the clients assigned to them and the set of different facility types used by the construction heuristic; we then explore a neighborhood consisting of the facility types which are yet unused, and for each of them, we update the fixed set of facility types and reassign the clients to facilities (of that set) and the facilities to the opened locations. Third, we fix the sets of locations and facilities opened at Stages 1 and 2 and we check if the client assignment can be improved, by reassigning all clients to the opened locations and facilities.

To speed up the execution of Stage 1 we apply a neighborhood reduction mechanism which constructs minimal location subsets, i.e., consisting of a minimal number of locations whose total capacity is greater or equal than the total demand of all clients. This mechanism restricts the number of feasible assignments in each neighborhood exploration as all variables linked to locations which are not part of the explored subset are fixed to 0. Although the selection of minimal location subsets ensures that combinations among locations will not be explored more than once, it eliminates solutions where the clients are assigned in some superset of the selected locations. However, since in most of our instances the location costs are quite larger than the other costs, selecting supersets of minimal location subsets normally leads to solutions of increased total cost.

In most of our instances the number of locations, |J|, is a small constant (from 10 to 25) and thus the number of neighborhoods is a small multiple of |J|, ranging from \(3\times |J| - 10\times |J|\), even if location capacities are high. Note that in the MPS case, where the number of locations is quite large (from 91 to 206), each client is associated to a single location and thus Stage 1 is omitted and the algorithm starts directly from Stage 2. In Stage 2, the size of the neighborhood is linear in the number of unused facility types, which is usually a small constant (10–34 types).

Regarding the exploration of each neighborhood, we apply two approaches: a greedy procedure which computes fast near-optimal neighboring solutions, and an exact procedure which solves optimally, a reduced in terms of size, (LIP) formulation. More precisely, due the fixed assignments in each Stage, i.e., clients to facilities (Stage 1), clients to locations (Stage 2), facilities to locations (Stage 3), the size of the sub-problems arising from each new neighbor is strongly reduced. Thus, by using the greedy procedure we are able to compute neighboring solutions in a few seconds, while, by applying the exact procedure we need a few minutes to compute exact neighboring solutions, however increasing the overall solution quality to almost optimal values. Note that, in contrast to the neighborhood exploration proposed in Zhang et al. (2005) and Pal et al. (2001), here, it is not possible to use a LP formulation for each new neighbor, but an IP formulation is necessary due to the unsplittable client demands of our model.

Next, we present our three-stage approach more formally. We denote by \(A_{X,Y} = \{(x,y)~|~x\in X, y\in Y\}\) the set consisting of the assignment of input parameters \(x\in X\) to \(y\in Y\), where \(X\subseteq I\) or \(X\subseteq K\), and \(Y\subseteq K\) or \(Y\subseteq J\). Let S be the set that maintains a feasible solution to the (LIP) model. Initially S is computed by one of our construction heuristics, thus \(S=A_{I,K}\cup A_{K,J}\cup A_{I, J}\). Concerning the local neighborhood: (i) in Stage 1, where we consider subsets of the locations in J, it is denoted by \(N(J) = \{J'~|~J'\subseteq J\}\), (ii) in Stage 2, it is denoted by \(N(K') = \{k~|~k\in K'\}\), where \(K'\) is the set of all facilities whose facility types are not used in the feasible solution S. We consider the following local improvement operations.

  • OPEN\((J', N(J))\): The locations \(j\in J'\), where \(J'\in N(J)\), are considered as open, while all locations \(j\in J{\setminus } J'\) are considered as closed.

  • OPEN\((k, N(K'))\): The facilities \(k\cup \{K{\setminus } K'\}\), where \(k\in N(K')\) are available to be explored, while all facilities \(k'\in K'{\setminus } k\) are considered as closed.

As already mentioned the neighboring solutions are computed in two ways, by a fast greedy approach and by an exact solver which uses as input a reduced (LIP) formulation. Concerning the greedy approach, in Stage 1, it places each opened facility \(k\in K\) and the clients assigned to it, to the location of \(J'\in N(J)\) with the minimum setup plus connection costs, with respect to locations’ capacities, while in Stage 2, reassigns each client \(i\in I\) to the facility of the new set \(k\cup \{K{\setminus } K'\}\), where \(k\in N(K')\), with the minimum service cost, with respect to facilities’ capacities. In Stage 3, the greedy algorithm simply reassigns each client \(i\in I\) to the opened location and facility with the minimum total cost, with respect to capacities.

Concerning the exact approach, in Stage 1, the decision variables \(z', w\) are fixed according to S and \(J'\in N(J)\), respectively, so (LIP) formulation is reduced to Constraints (9)–(12), (14) and (15), where, the set of locations \(J'\) is a small subset of J and the facilities are only those opened by the construction heuristic. In Stage 2, the decision variables \(x', w\) are fixed according to Stage 1, so (LIP) formulation is reduced to Constraints (8)–(12), (14) and (16), where, the set of locations comprises those opened at Stage 1, and the set facilities is a subset of K. In Stage 3, the decision variables \(y',w\) are fixed according to Stages 1–2, so (LIP) formulation is reduced to Constraints (8)–(10), (12), (14)–(18), where, the set of locations includes those opened a Stage 1, and the set of facilities the ones from Stage 2. Note also that in Stage 3, the number of decision variables v that are active is restricted only to the facilities placed in the locations of Stages 1–2.

figure c

Algorithm 3 presents in detail our VND metaheuristic method. Note that for each test instance, Algorithm 3 is executed for each construction heuristic, and the solution of minimum cost is returned. We denote by ALG the algorithm used to explore the neighboring solutions in each stage, which might be one of the two above-described approaches i.e., greedy or exact. More precisely, we use the following notation: (a) ALG\((J', A_{I,K})\) represents the method to solve the reduced problem instance comprised by a fixed assignment \(A_{I,K}\) from S and a set of locations \(J'\in N(J)\), (b) ALG\((k\cup {K{\setminus } K'}, A_{I,J})\) represents the method to solve the reduced problem instance comprised by a fixed assignment \(A_{I,J}\) from Stage 1 and a set of facilities \(k\cup {K{\setminus } K'}\), where \(k\in N(K')\), and (c) ALG\((I, A_{K, J})\) represents the method to solve the reduced problem instance comprised by a fixed assignment \(A_{K, J}\) from Stage 2 and a set of clients I. Note that in Stage 3, since all clients must be assigned to the opened facilities and locations we do not need to proceed with a neighborhood construction. As we show next, Algorithm 3 produces near-optimal solutions within a few seconds when the greedy approach is applied, or a few minutes when the exact approach is used.

Algorithm 3 is based on the Best-Fit strategy, which performs an exhaustive neighborhood exploration before the best solution is returned. Although this approach is considered as the most efficient in terms of solution quality, it usually requires increased running time. To further exhibit ‘solution quality versus time’ trade-off, we also consider two improvement strategies: (a) Next-Fit, which terminates just after an improved solution is found, and (b) \(k{\text {th}}\)-Best-Fit, which terminates after k improvements are found. As we noticed, after testing various possible values for k, when \(k > 3\) the algorithm fails to find k improvements before all neighborhoods are explored in most of our instances, thus its results become equal to the ones of the Best-Fit strategy. Hence, we also introduce the 3-Best-Fit strategy which is proved to be quite efficient in several instances compared to both Best-Fit and Next-Fit. The comparison of the above improvement strategies is evaluated in the following section.

It is important to note that the execution order of Stages 1 and 2 of Algorithm 3 do not follow some certain rule, yet they are based on our straightforward observation that locations are the entities that contribute the most in the objective function so prioritising their careful selection is crucial for the algorithm’s solution quality. To explore all possible improvements for our VND approach, we also consider a variation in which Stages 1 and 2 are reversed; note that the role of Stage 3 is to check if the changes in opened locations and facilities result in a change in clients’ assignment, so it should be executed at the end. As we show next, the latter variation does not imply any remarkable impact on the algorithm’s performance compared to the initial order (which achieves slightly better results for most of our instances). Note also that the reversed variation does not apply on the MPS instances, as Stage 1 is omitted in that case.

4 Empirical evidence

The exact solver and the LP-relaxation of (LIP) have been implemented in CPLEX 12.10 using the Python API, while all greedy heuristics and the metaheuristic approach are also implemented in Python. Using CPLEX-defined RAM thresholds, the exportation of nodes to files has been activated for larger instances. The experiments conducted under CentOS Linux 7 (x86-64), on a quad-core machine (Intel i7, 3.6GHz CPU speed, 16GB RAM). Table 3 summarizes the notation used in this section.

Table 3 Experiment parameters and abbreviations
Full size table

4.1 The case of MPS

The application of (LIP) to MPS, as described in Sect. 2.2, is examined on three representative datasets consisting of: (i) 91 clients and locations, 33 facility types of 10 copies each and 12 bands, (ii) 206 clients and locations, 12 facility types of 20 copies each and 12 bands, and (iii) 191 clients and locations, 18 facility types of 20 copies each and 12 bands. This yields an (LIP) of \(7.6\cdot 10^5\), \(1.3\cdot 10^6\) and \(1.8\cdot 10^6\) constraints respectively. Note that the number of bands M is predefined by the data provider, while the set of potential locations coincides with the locations of the existing clients (‘slots’), thus \(J=I\) and each client is associated to a specific location. The number of facility types L corresponds to the available printer models and the number of copies \(K_l,~ l\in L\) of each printer model is large enough to ensure solution feasibility.

Table 4 MPS: Cost and CPU time (in seconds) for (meta-)heuristics and CPLEX with GrVND providing the UB
Full size table
Table 5 MPS: Performance guarantees of metaheuristics and LB
Full size table

Results appear in Table 4 in terms of cost and CPU time in seconds (within parentheses), where the CPLEX solver uses the solution of GrVND as an initial upper bound. Note that the SS heuristic achieves solutions \(\sim 10\%\) better than FR, while being 2.7 times faster (all numbers are averages). As a result, GrVND is \(15\%\) better and \(230\%\) faster if it starts from the SS solution rather than the FR one; ExVND gets only \(4\%\) better and \(76\%\) faster. Let us also notice that ExVND produces \(23\%\) better solutions but is \(159\%\) slower than GrVND.

Concerning our tested improvement strategies: a) under greedy neighborhood exploration, Best-Fit provides \(4.8\%\), \(2.2\%\) less costly and \(6.3\%\), \(4.5\%\) slower solutions, compared to Next-Fit and 3-Best-Fit, respectively, while b) under exact neighborhood exploration, Next-Fit and 3-Best-Fit are \(8.1\%\) and \(2\%\) more costly than Best-Fit, but in terms of CPU time they are \(33\%\) and \(14\%\) faster than Best-Fit, respectively.

On the other hand, CPLEX (UB) computes an optimal solution in 4h, and reaches a 2%Err in 2h and a 5%Err in \(40'\), while requiring almost 7h if not fetched with the GrVND solution. As shown in Tables 4 and 5, our approach outperforms CPLEX (even when using GrVND as an upper bound) in two ways: either via ExVND, whose %Err is \(3.4\%\), computed in less than \(11'\) or through GrVND variation, whose %Err is much higher (\(27.7\%\)) but computed in \(\sim 5'\). That is, our approach offers a leverage between time and solution quality, while remaining competent for large instances regardless of the metaheuristic employed. Another common theme throughout our experimentation is the strength of the LP-relaxation, as shown by the Ig in Table 5, which is computed in less than 5 s and corresponds to a %Gap of 9.5–17.7% regarding ExVND.

The FLP handling of MPS is of huge practical importance, because a MPS solution currently requires a few days of calculations by a specialised MPS manager. Apart from time savings, the MPS company providing us the data sets observes a cost reduction of 6-\(9\%\) compared to its current solution method. Hence, and to the best of our knowledge, this is the first exact solution approach for MPS, which also proves to be very successful.

4.2 The case of parcel delivery through micro-hubs

For the problem discussed in Sect. 2.3, the 3PL has provided 79 instances, each spanning a week, thus covering two consecutive years for a cluster of its network in the region of Attica, Greece. The number of warehouses (locations) is \(|J|=8\) in all instances, the number of clients is increasing per instance from 104 to 194,  shops (micro-hubs) are sustained at the same value \(|L|=34\) to offer a sound basis of comparison, the same holding for their total copies \(|K|=102\) and the number of bands \(|M|=5.\) This yields an (LIP) of \(4.8\times 10^4\)–\(8.7\times 10^4\) and \(3.3\times 10^4\)–\(6\times 10^4\) constraints.

The 3PL’s current design is static in the sense of assigning shops to single warehouses twice per year and clients to their closest shops. This approach cannot capture the seasonality and overall total volatility of demand across different weeks. Hence, the 3PL uses our approach to examine whether the calculation of a optimal distribution per week reduces annual operating costs. Another topic question not reported here is whether the enlargement of the set of shops through collaborations with retail chains could further reduce costs. The 3PL has therefore appreciated the value of our FLP approach because of its ability to solve all problem instances in reasonable time.

Table 6 Parcel delivery through micro-hubs: Performance guarantees of GrVND, ExVND and LB
Full size table

Due to the large number of instances, we illustrate our algorithmic results in Figs. 1, 2 and 3. FR is 38 times faster than SS (Fig. 1). As a result, GrVND is 25 times faster if paired with FR rather than SS, while also achieving \(21\%\) less costly solutions. We attribute that to the limitations imposed to the assignment of clients-to-facilities, as each client is restricted to be assigned to a subset of micro-hubs according to its geographical position. Hence, an LP-rounding method like FR fixes a great range of variables to zero, thus reducing the number of variables to be rounded. FR’s performance is also related to the fact that LB achieves an average Ig of 1.24 and a %Gap of 16.9–60.9% using FR (Table 6), taking less than 1 s. ExVND exhibits the same ‘time versus cost’ trade-off by achieving \(26\%\) better solutions than GrVND and being 69 times slower (Fig. 1); also, it yields pretty similar results under both FR, SS (Fig. 1).

Fig. 1
figure 1

Parcel delivery: CPU time (in seconds) and cost for (meta-)heuristics

Full size image
Fig. 2
figure 2

Parcel delivery: CPU time (in seconds) and cost for BF-ExVND and CPLEX with GrVND providing the UB

Full size image
Fig. 3
figure 3

Parcel delivery: CPU time (in seconds) for CPLEX without upper bound, and 2%Err, 5%Err against CPLEX (using UB)

Full size image

Regarding our improvement strategies, Next-Fit computes \(15\%\) and \(21\%\) more costly solutions than Best-Fit under greedy and exact neighborhood exploration, respectively, without significantly improving the Best-Fit’s already short CPU time; Next-Fit solutions are from 1.5 s up to \(4.4'\) faster. On the other hand, 3-Best-Fit computes slightly worse solutions than Best-Fit, under both neighborhood explorations, i.e., \(3\%\) more costly on average, while being \(4\%\) faster in terms of CPU time. As we observe, for 40% of the instances (tested under all possible VND variations, i.e., Greedy vs Exact neighborhood exploration, SS vs FR construction heuristic, order of Stages 1 and 2) the solutions of 3-Best-Fit are identical to the ones of Best-Fit in terms of both cost and time; interestingly for \(75\%\) of the latter instances 3-Best-Fit computes the same solution with Best-Fit in \(5\%\) less CPU time. We also examine the VND variation where the order of Stages 1 and 2 is reversed. We observe that the initial order produces better solutions on average, but their difference is less than \(1\%\) over all instances, thus reversing stages does not imply any remarkable impact on the performance of our VND metaheuristic.

Interestingly, by providing the fast upper bound of GrVND to CPLEX, the latter computes an optimal solution in \(8.4'\) on average, while reaching 2%Err and 5%Err in \(2.6'\) and \(1.6'\), respectively (Fig. 2); without this upper bound, these numbers rise to \(\sim 31'\), \(6'\) and \(2.6'\) (Fig. 3). Let us also note that ExVND achieves in \(\sim 10'\) an average %Err of \(0.6\%\) on all instances and of \(0.4\%\) in \(90\%\) of instances (Table 6), that is \(75\%\) and 3 times slower compared to the CPU time of CPLEX (without the upper bound) to obtain 2%Err and 5%Err, respectively (Fig. 3).

Overall, near optimal solutions are obtained \(2'\)-\(42'\) by ExVND. Alternatively, by using the fast upper bound on CPLEX, computed by GrVND, optimal solutions are obtained in 47 s-2h, while 2%Err and 5%Err in 41 s-\(32'\) and 41 s-\(2.8'\), respectively. This is why a planner can use our set of methods not only for weekly distributions but for simulating numerous scenarios in order to examine alternative distribution policies.

4.3 Benchmark instances

We extend the Beasley (1988) instances in our setting which has not been examined before. We take from Beasley (1988) the sets of clients and locations, including client demands, client-to-location connection costs, fixed location opening costs and location capacities. We then adopt part of the data generated in Tragantalerngsak et al. (1997) for a 2-level FLP variant that considers separate sets for locations and facilities, because Tragantalerngsak et al. (1997) uses a range of client demand values similar to Beasley (1988), thus the capacitated (in terms of total demand) facilities in Tragantalerngsak et al. (1997) fit perfectly to our FLP model. Afterwards, we construct a concave function based on Wu et al. (2006), where each location has a setup cost that is a concave function of the number of opened facilities. Please note that Wu et al. (2006) applies this function on the instances of Beasley (1988) but for a capacitated FLP variant with multitype facilities; that model could be thought of as the special case of (LIP) where there is a fixed service cost for each client and facility not depending on the client demand (as demand in Wu et al. 2006 is considered splittable).

For self-containment of our presentation, let us explicitly detail instance generation. As in Beasley (1988), demand values are integers drawn uniformly at random (u.a.r. for brevity) from [1, 100]. The connection cost of each client to a location is a real number chosen u.a.r. from [0.1, 0.4], in proportion to the connection costs in Beasley (1988). The locations’ capacities receive integer values u.a.r. from [5000, 14, 000], and a fixed opening cost is calculated by an integer uniform distribution from [750, 2500] in 100 units increments. Note that these values are 10 times less than the opening costs in Beasley (1988), so as not to limit the optimizer choices, who would avoid locations of high cost for cheaper ones. Finally, as in Tragantalerngsak et al. (1997), the capacity of each facility type is an integer value chosen u.a.r. from [100, 500]. The concave functions have form \(h(x) = \beta \cdot x \cdot 0.9^{log_{2}x}\), where for the service cost \(\beta \) is calculated per unit of demand by a uniform distribution between 0.1 and 0.4 (Beasley 1988), while for the setup cost, \(\beta \) is an integer drawn u.a.r. from [100, 500] (Tragantalerngsak et al. 1997).

In accordance to the above, we report on the 32 instances defined by the combinations of \(|I|\in \{100, 150\}\), \(|J|\in \{5,10\}\), \(|L|\in \{10, 15\}\) for any \(l\in L,~ |K_l|\in \{10, 15\}\), and \(|M|\in \{5,10\}\). These instances have \(5.4\times 10^4\)–\(3.6\times 10^5\) variables and \(5.2\times 10^4\)–\(3.5\times 10^5\) constraints. As CPLEX runs out of memory in most of these without an appropriate upper bound, we list only results for CPLEX (using UB).

Figure 4 visualizes the results for the two heuristics, their combination with the two meta-heuristics and the LB. SS outperforms FR, being 2.8 times faster while finding \(16\%\) better solutions (numbers are averages). This is simply because, as the number of variables to be rounded by FR grows, so does its CPU time. This affects GrVND that now performs slightly better under SS i.e., it requires \(82\%\) less time than under FR in average, while producing \(18\%\) better solutions. As shown in Table 7, GrVND achieves also a good %Err (\(35.4\%\) on average), so it constitutes an ideal upper bound method for CPLEX. More precisely, CPLEX (UB) is quite efficient, computing OPT in \(33'\) on average, while reaching 2%Err and 5%Err in \(6'\) and \(16'\) respectively (Fig. 5). Best-Fit provides \(10\%\) and \(2\%\) less costly solutions compared to Next-Fit and 3-Best-Fit, respectively, while being \(5\%\) slower in CPU time. By reversing Stages 1 and 2 we yield similar solutions of \(0.5\%\) and \(1\%\) more cost and CPU time, respectively.

Fig. 4
figure 4

Benchmark instances: CPU time (in seconds) and on cost of (meta-)heuristics and LB

Full size image
Table 7 Benchmark instances: Performance guarantees of GrVND, ExVND and LB
Full size table
Fig. 5
figure 5

Benchmark instances: CPU time (in seconds) and cost of ExVND and CPLEX with GrVND providing the UB

Full size image

On the other hand, ExVND produces solutions of similar costs under both SS and FR, while it is 110% faster under the former. What is impressive is that ExVND offers the optimal solution in all instances in 78 s (7 times faster than CPLEX (Using UB)) that is 30, 15 and 6 times faster than 2%Err and 5%Err, respectively (Table 7 and Fig. 5). Also LB remains efficient as in the real-life instances, with an average Ig of 1.45 and a 11–80% %Gap (Table 7).

Overall, ExVND outperforms CPLEX (UB), computing an optimal solution on every test instance in less than a minute, which is on average 3, 7, and 11 times faster than 5%Err, 2%Err and OPT, respectively. GrVND computes fast near-optimal results, which help CPLEX to reach optimality without running out of memory. 3-Best-Fit under exact neighborhood exploration is also efficient, providing almost optimal solutions (with \(\%\) Err less than \(3\%\)) for almost all instances, while its CPU time is \(4\%\) less compared to Best-Fit.

Table 8 Large instances: Cost, CPU time (in seconds) and empirical performance guarantees for GrVND and ExVND
Full size table

Last, let us experiment with some of the largest instances in Beasley (1988). The purpose here is to show the scalability of our approach in terms of finding provably near-optimal solutions even for the largest instances. We generate 5 Instances with 500 clients and 5 instances with 1000 clients, each with locations, facility types, copies, and bands chosen from \(\{5, 10, 15, 20, 25\}\) respectively. The resulting 10 instances have \(9.9\times 10^5\)–\(1.2\times 10^6\) variables and \(3.8\times 10^6\)–\(5.6\times 10^6\) constraints.

CPLEX runs out of memory in all of them, even when using the fast GrVND bound, hence the optimal solution is unknown. Therefore, we only compute LB in 113 s-216 s to list %Gap as a worst-case performance metric, in Table 8. As ExVND becomes also quite slow (recall that it solves a reduced version of (LIP) for a large number of neighborhoods), we use the ExVND solution after a maximum of 24 hours. Given that, ExVND achieves a %Gap of \(38.36\%\) on average, whereas GrVND accomplishes an average %Gap of \(61.9\%\) in \(\sim 2\) h. As the range of %Gap values for both GrVND and ExVND is quite similar to those of Table 7, one could reasonably expect that %Err and Ig might also remain close to the range observed in Table 7.

It is interesting to note that the time limit is reached for all instances when applying Best-Fit under exact neighborhood exploration, so the algorithm cannot explore all the available neighborhoods. 3-Best-Fit also fails to provide three improvements before the end of the time limit for \(42.5\%\) of the tested instances (considering all possible VND variations, i.e., SS vs FR construction heuristic, order of Stages 1 and 2) while, for the rest of them, a solution is obtained in \(\sim 16\) h on average. On the other hand, Next-Fit provides solutions over all instances in 11 h. Given the fact that it computes \(19.94 \%\) more costly solutions on average compared with Best-Fit, while achieving \(54 \%\) less CPU time, Next-Fit constitutes an effective strategy for large instances. Under greedy neighborhood exploration, Next-Fit computes solutions of \(11\%\) increased costs compared to Best-Fit, while the reduction in CPU time is limited to \(13\%\). Moreover, 3-Best-Fit produces solutions of \(10\%\) more cost compared to Best-Fit, but in similar CPU time, so there is no need to be used instead of it.

5 Concluding remarks

We have proposed an FLP variant that generalises several existing ones and is strongly motivated by two actual applications. In that regard, we have also shown two exemplar real-life problems admitting a nonlinear FLP formulation. We have solved them through an optimisation approach that combines methods of complementary strength, thus remaining effective not only in all real instances but also on an extensive list of benchmark ones. Our approach starts from our linearised Integer Program, which, strengthened by some additional constraints, exhibits a tight relaxation. This, apart from providing good lower bounds, has motivated the use of an LP-rounding heuristic (FR), whose strength complements that of our second heuristic (SS). FR is faster up to medium-sized instances and slower thereafter, but it appears to handle highly-capacitated problems more effectively than SS. That is nicely demonstrated in one of our applications (Sect. 4.2), for which FR is also efficient because of limited potential client-location assignments, since the number of variables to be rounded is then restricted, contrary to SS which is negatively affected by the very same reason. This complementarity justifies the use of both heuristics for our FLP setting, together with their combined effectiveness.

We also introduce two VND metaheuristics, ExVND as the most efficient in terms of solution quality regardless of the construction heuristic used, and the much faster GrVND. ExVND achieves optimality gaps of 3% on average, while GrVND needs up to a few hours even for the largest instances examined and is also stable in terms of achieving reasonable empirical gaps in all instances. For both VND metaheuristics, we experiment with Best-Fit, Next-Fit and 3-Best-Fit improvement strategies and evaluate their performance in terms of cost and time under two different orders of execution of the local search stages. As we note, Best-Fit strategy provides almost optimal solutions, while the 3-Best-Fit trades a small increase on cost with a considerable reduction in CPU time. Next-Fit provides good solutions as well and is proved quite effective on large benchmark instances, however it fails to compete with the other two strategies in real-life instances. Hence, complementarity is sustained in our VND approach.

Regarding our two applications, although the MPS instances are remarkably larger than the benchmark ones, the execution times of our VND is not accordingly increased. This occurs because each client is associated with a specific location, and thus the assignment of clients to locations is limited. To the contrary, although the parcel delivery instances are smaller than the benchmark ones, VND requires more time because the higher the capacity of a location is, the larger the size of the corresponding neighborhood becomes and this can easily occur in the parcel delivery setting. Despite these case-specific aspects, our approach is competent in terms of solution time and quality, thus covering the requirements for decision-support in both cases. It remains efficient across all benchmark instances, computing optimal or almost-optimal solutions much faster than an exact solver.