General network design: A unified view of combined location and network design problems

https://doi.org/10.1016/j.ejor.2011.11.009Get rights and content

Abstract

This paper presents a unified framework for the general network design problem which encompasses several classical problems involving combined location and network design decisions. In some of these problems the service demand relates users and facilities, whereas in other cases the service demand relates pairs of users between them, and facilities are used to consolidate and re-route flows between users. Problems of this type arise in the design of transportation and telecommunication systems and include well-known problems such as location-network design problems, hub location problems, extensive facility location problems, tree-star location problems and cycle-star location problems, among others. Relevant modeling aspects, alternative formulations and possible algorithmic strategies are presented and analyzed.

Highlights

► Unified view of combined location and network design problems. ► Classification of problems based on type of demand: user-facility or user-user demand. ► Modeling aspects, alternative formulations and algorithmic strategies presented and analyzed.

Introduction

Location analysis and network design have emerged as two major research areas in network optimization. Location problems typically involve siting facilities at nodes of a network whereas network design consists of activating some of the links. In both cases the aim is to ensure cost-effective flows between pairs of nodes to satisfy user demands. General network design problems (GNDPs) offer a unified view of these two streams of research which we emphasize in this paper. In particular, we will concentrate on classes of problems where both the facility location and the selection of links are predominant and non-trivial. These problems involve design decisions, which are to locate facilities and to activate links in an underlying network, and operational decisions, which are to allocate customers to facilities and to route the users demands. Below we discuss the main modeling aspects of such problems.

  • Design decisions: facility location and link activation

    • The facility location decisions indicate where to locate the facilities. In principle, facilities may be located at both the nodes and the arcs of the network. It is well known, however, that when Hakimi’s (1964) node optimality property holds, the set of nodes defines a finite dominating set for the optimal facility locations. In other words, there exists an optimal solution in which all the facilities are located at nodes. In the problems considered in this paper we assume that the set of potential locations for the facilities coincides with the set of nodes of the underlying network, even if the node optimality property does not necessarily hold. Examples of problems that involve location decisions are the well-known p-median and p-center problems (Hakimi, 1964), the uncapacitated facility location problem (Kuehn and Hamburger, 1963), the location-covering problem (Toregas et al., 1971) and the maximum covering location problem (Church and ReVelle, 1974).

    • The network design decisions select the links to be activated. These links are used for connecting users and facilities and, possibly, facilities between themselves.

      Well-known problems involving network design decisions are, for instance, fixed-charge network design problems, which have been studied by Magnanti and Wong, 1984, Balakrishnan et al., 1997, Minoux, 1989, among others.

Several costs may affect the design decisions. When a node is selected to locate a facility, a facility set-up cost is incurred. Analogously, when a link is activated in a network design decision, a link set-up cost is incurred. Set-up costs are fixed and do not depend on the flows that circulate through the network. In addition, capacity dependent variable costs may be incurred both at the facilities and the links.

It is easy to find further examples of network optimization problems that involve design decisions and that can be seen as location or network design problems. For instance, in the minimum cost spanning tree problem (Borůvka, 1926), the minimum cost matching problem (Edmonds, 1965), and the vehicle routing problem (Dantzig and Ramser, 1959, Laporte, 2009), links with fixed set-up costs must be activated. Similarly, in location-vehicle routing problems (Nagy and Salhi, 2007) joint location and network design decisions must be made. The minimum cost Steiner tree problem (Winter, 1987) is a further example where location (the Steiner nodes) and network design decisions (the edges of the tree) have to be made.

  • Operational decisions: allocation and routing

    • The allocation decisions indicate the facilities that will be used to serve each user. There are two types of allocations. In single allocation, each user is assigned to exactly one facility, whereas in multiple allocation each user may be assigned to more than one facility. Some classical location problems that involve allocation decisions are the p-median and p-center problems.

    • The routing decisions dictate the routes that will be used to satisfy the users demands. As is common in network design, we use the term routing to indicate the paths that are used to send flows between pairs of nodes. In this context, the routing and the network design decisions are closely related, as the links that can be used in the paths, are the outcome of the network design decisions. Well-known network optimization problems with routing decisions are the transportation problem (Monge, 1781, Kantorovich, 1942) and, in general, network flow problems (Ahuja et al., 1993).

    Several operational costs may affect the above decisions. These include costs associated with the allocation of users to facilities, as well as transportation costs incurred when routing the users demands through the selected links. Both allocation and transportation (or routing) costs are variable, as they depend on the amount of demand of each user allocated to each facility and on the total amount of flow routed through each arc, respectively. Note, however, that single allocation can be seen as a network design decision, since the allocation set-up cost is then fixed.

There are, indeed, combinations of the above types of decisions that arise in different network optimization problems. Examples of problems that combine design and operational decisions are classical location problems, which involve joint location and allocation decisions, and classical network design problems, which combine network design and routing decisions like the fixed-cost transportation problem (Balinski, 1961), the optimum communication spanning tree problem (Hu, 1974), or the fixed-charge network design problems (Magnanti and Wong, 1984). Observe, however, that these problems do not involve all of the above decisions. For instance, classical location problems involve no network design or routing decisions, as they assume that direct connections between users and their allocated facilities are used to satisfy the users demands. Similarly, fixed-charge network design problems involve no location or allocation decisions, as they focus on deciding the links to be activated and finding the paths to route flows between users.

In general, not every network optimization problem with design decisions includes additional operational decisions. For instance, among the above examples, neither the minimum spanning tree nor the minimum cost perfect matching or the minimum cost Steiner tree problem involves allocation or routing decisions. In a different context, vehicle routing problems require, in general, no allocation decisions unless several depots exist and users must be assigned to depots. Table 1 illustrates combinations of design and operational decisions, and their associated costs, involved in some of the problems mentioned above, namely, p-median (p-MP), uncapacitated facility location problem (PLP), the Steiner tree (STP), minimum cost spanning tree (MCSTP), transportation (TP), optimum communication tree (OCTP), vehicle routing (VRP) and its multidepot counterpart (MVRP), network design (FCNDP), fixed-cost transportation (FCTP) and location-routing (LRP).

A classification of GNDPs based on the type of demand.

In all the GNDPs that we study the aim of the location and allocation decisions is to determine the facilities to select and the allocation of users to facilities. The aim of the network design and routing decisions, however, depends on the role of the facilities, which is dictated by the type of service demand required by users. To better discuss the characteristics of the problems we focus on, we propose a classification of GNDPs in two main categories which are based on the type of users demand.

  • Problems in which service is given at or from the facilities, so that service demand relates users and facilities will be called GNDPs with user-facility (UF) demand. In GNDPs with UF demand the network design and routing decisions determine how to connect users with their allocated facilities. When users travel to the facilities to receive service, the routing decisions consist of finding the minimum cost path from each user to its allocated facility in the network induced by the activated links. When servers travel from facilities to users, the routing decisions may be more involved if the routes contain several users. Classical location problems can be seen as GNDPs with UF demand involving trivial network design and routing decisions. Since the set-up costs of all the links of the underlying network are zero, the network design decisions will activate all the links and, assuming triangle inequality property, the routing decisions will use direct connections between each user and its allocated facilities. GNDPs with UF demand with non-trivial network design decisions include, for instance, the so-called location-network design problems (Melkote and Daskin, 2001a, Contreras et al., 2010c) and location-vehicle routing problems (Nagy and Salhi, 2007).

  • Problems in which service demand is between pairs of users and the facilities are used as intermediate locations in the routes that connect pairs of users will be called GNDPs with user-user (UU) demand. In GNDPs with UU demand the network design and routing decisions determine how to connect both users and facilities and facilities between themselves. Classical network design problems can be seen as GNDPs with UU demand involving trivial location decisions. Since the set-up costs of all the facilities are zero, the location decisions will activate all the nodes. Classical hub location problems (O’Kelly, 1986, O’Kelly, 1992, Campbell, 1994), can be seen as GNDPs with UU demand, in which the location and allocation decisions determine the routing decisions. Other GNDPs with UU demand with non-trivial location decisions include, for instance, concentrator location problems (Yaman, 2005, Labbé and Yaman, 2006, Gouveia and Saldanha-da-Gama, 2006), tree-star location problems (Contreras et al., 2009b, Contreras et al., 2010a), and cycle-star location problems (Labbé et al., 2004, Labbé et al., 2005a).

Fig. 1 presents a classification of various types of GNDPs according to their type of demand. Rows refer to problems with location, network design and combined location-network design decisions. Columns correspond to problems with UF and UU demand, respectively. For each combination a reference of a well-known problem in the class is given along with a schematic illustration that highlights the main decisions and the generic structure of solutions. A square over a node indicates that a facility has been located at the node. Solid lines represent design decisions, whereas dotted lines represent routing decisions.

The subject of this paper are problems that involve joint location and network design decisions together with non-trivial routing decisions (and, possibly, additional allocation decisions). These problems are called GNDPs and include, for instance, network location problems with links set-up costs. In this case, users may be connected to their allocated facilities by paths with more than one arc. Thus, the location and allocation decisions are not sufficient to completely determine the solutions, as they do not indicate which links can be used in the paths connecting users and their allocated facilities. Hence, non-trivial network design and routing decisions are needed in addition to the location and allocation decisions. GNDPs also include network design problems with nodes set-up costs, where some nodes have to be selected, in which flows between pairs of users will be consolidated or re-routed. In this case, the network design and routing decisions do not fully determine the solution and non-trivial location and allocation decisions are also needed to determine the nodes to be activated.

The term “general network design problem” has already been used by several authors, even if not always consistently. In most cases (see, for instance, Balakrishnan et al., 1997) it has been used to refer to multi-commodity network design problems, as opposed to other problems in which demand for service is restricted to a given subset of the pairs of users like, for instance, the so-called single-commodity network design problems. As already mentioned we extend the term “general” to network optimization problems with fixed-charge and routing decisions that involve additional location decisions.

Reviewing such a general class of problems is, indeed, far beyond the scope and space limitations of this paper, and we thus limit our view to only a subset of them. In particular, we focus on problems where both the location and allocation decisions are non-trivial. This excludes pure location allocation problems as well as pure network design problems. The interested reader is referred to Smith et al. (2009) and references therein for a recent overview of location problems, and to up-to-date references of network design problems like, for instance, Croxton et al., 2009, Frangioni and Gendron, 2009. Furthermore, we focus on problems in which the routing decisions determine simple paths. This excludes location-vehicle routing problems, where active and successful research is taking place. In location-vehicle routing problems the routes that serve users are circuits rooted at the selected facilities, and modeling techniques other than those presented here are required. The interested reader is referred to Nagy and Salhi (2007) and references therein for an overview of such problems or to more recent works like, for instance, Belenguer et al., 2011, Catanzaro et al., 2011. We also address problems with a minsum or minmax objective in which costs are derived from design decisions and from allocation or routing decisions. Finally, we focus only on uncapacitated versions of the problems given that, from the modeling point of view, capacitated extensions can be easily obtained from them.

Below we present an example to illustrate how the different modeling hypotheses affect the structure of an optimal solution to GNDPs.

Example 1

Consider the nine-node network of Fig. 2 where each node represents one user as well as a potential location for a facility. The length of any vertical link is 1 and the length of any horizontal link is 2. All the other links have Euclidean distances; for example, the length of the link connecting nodes 1 and 6 is 222.83. The objective is to minimize the sum of the facilities and links set-up costs plus the routing costs.

We analyze nine scenarios, each corresponding to a different combination of costs and type of demand (see Table 2). All the facilities set-up costs have the same value. These values are 1 (scenarios 2 and 4), 5 (scenarios 1 and 3), 45 (scenario 9), 49 (scenarios 6 and 8) and 51 (scenarios 5 and 7). We have considered two different combinations of link set-up costs and routing costs. In scenarios 1, 3, 5, and 7 the link set-up costs are the lengths of the links in the underlying network and all the routing costs are zero. In scenarios 2, 4, 6, 8 and 9 all links set-up costs are zero and the routing costs are the lengths of the links in the underlying network. Finally, scenarios 1 to 4 correspond to instances with UF demand, whereas in scenarios 5 to 9 we work with UU demand. For the scenarios with UF demand all users have one unit of demand, whereas for the scenarios with UU demand each user must send one unit of demand to every other user.

The last two columns of Table 2 give an optimal solution under each scenario and the total optimal cost. This information is complemented in Table 3, which gives the costs of the different solutions of Fig. 2 under each scenario. Optimal values for each scenario are highlighted in boldface. Observe that the routing cost of a solution under different scenarios with identical link routing costs depends on the type of demand. For instance, the routing cost of solution S2 under scenarios 3 and 4, which have UF demand, is 2(3+25)14.94, whereas its routing cost under scenarios 7–9, which have the same link routing costs but have UU demand, is 32(2+35)239.11.

In scenarios 1 and 2 the routing costs are zero. Thus, once the set of facilities and their allocated users are known, the minimum arc set-up arc costs are attained by finding a minimum spanning tree connecting each open facility and its allocated nodes, relative to the links set-up costs. In particular, when the facilities set-up costs are 5, the optimal solution is S1 where only facility 5 is open, whereas when the facilities set-up costs are 1, an optimal solution is S3, with set of open facilities {2, 5, 8} (note that an alternative optimal solution is to open a facility at each node). In scenarios 3 and 4 the arc set-up costs are zero. Once the set of facilities to open is known, minimum routing costs are attained by connecting each user directly with its closest facility (recall we are assuming Euclidean distances). In particular, when the facilities set-up costs are 5, the optimal solution is the star S2 where only facility 5 is open, whereas when the facilities set-up costs are 1, an optimal solution is again S3, with a set of open facilities {2, 5, 8}. When all the routing costs are zero, the only aspect of optimal solutions which is affected by the type of demand is that the subgraph induced by the activated links must be connected in order to allow communication between all pairs of nodes. Hence, for the reasons given above, optimal solutions will be spanning trees relative to the links set-up costs. Thus, the optimal solution to the UU scenarios 5 and 6, is again solution S1. Finally, the optimal solutions to scenarios 7 and 8 are S2 and S4, respectively. Observe that both solutions reflect the tradeoff between the facility set-up costs and the weight of the routing costs in the objective function. If the set-up costs are further decreased to 45, as in scenario 9, the optimal solution is Solution S5.

The remainder of the paper is organized as follows. In Section 3, we study GNDPs with UF demand. In particular, we study facility location-network design problems as well as some extensions and related problems. In Section 4, we review GNDPs with UU demand in which flows must be sent between pairs of users and facilities are used as intermediate locations for routing the flow through the underlying network. As illustrated in the above example, in this case the subgraph induced by the open facilities must be connected. We focus on problems in which facilities are connected by means of a complete subgraph, a tree-star, a star-star, and a cycle-star structure. The paper ends in Section 5 with some conclusions and directions for future research.

Section snippets

Some preliminaries: modeling flows in network design

Before presenting different formulations for several GNDPs, we introduce some notation and recall the usual modeling approaches in network design. Unless otherwise stated, we consider an underlying network N with set of nodes V = {1, 2,  , n}. The links of N can be either edges (undirected) or arcs (directed). As usual, the set of edges is denoted by E and the set of arcs is denoted by A. An edge e  E connecting pair of nodes k, m  V, k < m is denoted by e = (k, m). An arc connecting nodes k, m  V in the

Problems with user-facility demand

In this section, we consider GNDPs with UF demand in which facilities are used to provide service to users. In the problems that we present next the location-allocation decisions do not necessarily imply the routing decisions, in contrast to what happens in most classical location-allocation problems. Therefore, additional network design and routing decisions are needed to define the paths for routing the users demands to or from their allocated facilities. This class of GNDPs are otherwise

Problems with user-user demand

In this section, we consider GNDPs with UU demand, in which the facilities are used as intermediate locations where flows between users are consolidated and re-routed to their final destinations. Like in previous GNDPs, these problems involve location, allocation, network design and routing decisions. The location decisions select the nodes to locate facilities. The allocation decisions indicate the facilities used to send or receive the flows with origin or destination at the users. The

Conclusions

We have presented and discussed General Network design Problems (GNDPs), which combine design decisions to locate facilities and to select links on an underlying network, with operational allocation and routing decisions to satisfy the users demands. GNDPs define a large class of difficult problems which have been presented under a unifying framework. They can be classified in two main categories, according to the type of demand required by the users. In user-facility problems users demand must

Acknowledgements

The authors are grateful to Gilbert Laporte for his comments and suggestions, which have greatly contributed to improve the presentation of the paper. Thanks are also due to an anonymous referee. This research has been partially supported by Grant MTM2009-14039-C06-05 of the Spanish Ministry of Education and Science and by ERDF funds. The research of the first author has partly funded by the Canadian Natural Sciences and Engineering Research Council under Grants 227837-09 and 39682-10. The

References (117)

  • J.-F. Cordeau et al.

    An iterated local search heuristic for the logistics network design problem with single assignment

    International Journal of Production Economics

    (2008)
  • I. Correia et al.

    The capacitated single-allocation hub location problem revisited: A note on a classical formulation

    European Journal of Operational Research

    (2010)
  • A. Costa et al.

    Two-level network design with intermediate facilities: An application to electrical distribution systems

    Omega

    (2011)
  • J.R. Current et al.

    The median tour and maximal covering tour problems: Formulations and heuristics

    European Journal of Operational Research

    (1994)
  • Z. Drezner et al.

    Network design: Selection and design of links and facility location

    Transportation Research Part A

    (2003)
  • J. Ebery et al.

    The capacitated multiple allocation hub location problem: Formulations and algorithms

    European Journal of Operational Research

    (2000)
  • A.T. Ernst et al.

    Efficient algorithms for the uncapacitated single allocation p-hub median problem

    Location Science

    (1996)
  • A.T. Ernst et al.

    Exact and heuristic algorithms for the uncapacitated multiple allocation p-hub median problem

    European Journal of Operational Research

    (1998)
  • A. Frangioni et al.

    0-1 reformulations of the multicommodity capacitated network design problem

    Discrete Applied Mathematics

    (2009)
  • S. Gollowitzer et al.

    MIP models for connected facility location: A theoretical and computational study

    Computers and Operations Research

    (2011)
  • L. Gouveia et al.

    On the capacitated concentrator location problem: A reformulation by discretization

    Computers and Operations Research

    (2006)
  • H.W. Hamacher et al.

    Adapting polyhedral properties from facility to hub location problems

    Discrete Applied Mathematics

    (2004)
  • J.G. Klincewicz

    Hub location in backbone/tributary network design: A review

    Location Science

    (1998)
  • M. Labbé et al.

    Locating median cycles in networks

    European Journal of Operational Research

    (2005)
  • A. Liefooghe et al.

    Metaheuristics and cooperative approaches for the bi-objective ring star problem

    Computers and Operations Research

    (2010)
  • A. Marı́n

    Formulating and solving the splittable capacitated multiple allocation hub location problem

    Computers and Operations Research

    (2005)
  • A. Marı́n et al.

    New formulations for the uncapacitated multiple allocation hub location problem

    European Journal of Operational Research

    (2006)
  • S. Melkote et al.

    An integrated model of facility location and transportation network design

    Transportation Research Part A

    (2001)
  • S. Melkote et al.

    Capacitated facility location/network design problems

    European Journal of Operational Research

    (2001)
  • M.T. Melo et al.

    Facility location and supply chain management - A review

    European Journal of Operational Research

    (2009)
  • J.A. Moreno-Pérez et al.

    Variable neighborhood tabu search and its application to the median cycle problem

    European Journal of Operational Research

    (2003)
  • L. Murawski et al.

    Improving accessibility to rural health services: The maximal covering network improvement problem

    Socio-Economic Planning Sciences

    (2009)
  • G. Nagy et al.

    Location-routing: Issues, models and methods

    European Journal of Operational Research

    (2007)
  • M.E. O’Kelly

    Hub facility location with fixed costs

    Papers in Reginal Science

    (1992)
  • M.E. O’Kelly et al.

    The hub network design problem: A review and synthesis

    Journal of Transport Geography

    (1994)
  • T. Polzin et al.

    A comparison of Steiner tree relaxations

    Discrete Applied Mathematics

    (2001)
  • R.K. Ahuja et al.

    Network Flows: Theory, Algorithms and Applications

    (1993)
  • A. Balakrishnan et al.

    Network design

  • A. Balakrishnan et al.

    A dual ascent procedure for large-scale uncapacitated network design

    Operations Research

    (1989)
  • R. Baldacci et al.

    The capacitated m-ring-star problem

    Operations Research

    (2007)
  • M.L. Balinski

    Fixed-cost transportation problems

    Naval Research Logistics Quarterly

    (1961)
  • M.G. Bardossy et al.

    Dual-based local search for the connected facility location and related problems

    INFORMS Journal on Computing

    (2010)
  • O. Borůvka

    O jistém problému minimálním (About a certain minimal problem) (in Czech)

    Práce mor. přŕodověd. spol. v Brně III

    (1926)
  • J.F. Campbell et al.

    Hub location problems

  • J.F. Campbell et al.

    Hub arc location problems: Part I – Introduction and results

    Management Science

    (2005)
  • J.F. Campbell et al.

    Hub arc location problems: Part II – Formulations and optimal algorithms

    Management Science

    (2005)
  • A.M. Campbell et al.

    Upgrading arcs to minimize the maximum travel time in a network

    Networks

    (2006)
  • H. Chen et al.

    Network design for time-constrained delivery

    Naval Research Logistics

    (2008)
  • H. Chen et al.

    Minimax flow tree problems

    Networks

    (2009)
  • Chimani, M., Kandyba, M., Martens, M., 2009. 2-interconnected facility location: Specifications, complexity results,...
  • Cited by (117)

    • Exact approaches for the Minimum Subgraph Diameter Problem

      2023, Computers and Operations Research
    • Facility Location in Logistics and Transportation: An enduring relationship

      2022, Transportation Research Part E: Logistics and Transportation Review
    View all citing articles on Scopus
    View full text