Terminal Location Models for Intermodal Transport Network Optimization

Show more

1. Introduction

Localization consists of determining the location of one or more installations in order to optimize an economic function depending on the distances between these installations and a set of potential users.

Mathematical models have been developed and used to solve intermodal transport problems. These models can be classified in several ways. The classification can be based on the distinction between the type of space in which the terminal is to be located, the nature of the inputs (for example: static or dynamic, deterministic or probabilistic), the type of metric used, the number of facilities to be located, on the nature of the demand (elastic or inelastic), depending on whether the capacity of the installations is taken into account or not, etc.

If the classification criterion used is the type of space in which the installations are to be located, then the problems are differentiated according to whether the space considered is continuous or discrete. The formulation of the location in a continuous space suggests that a site can be selected anywhere in the plane. In other words, there is a continuum of potential locations. On the other hand, the formulation of the localization in a discrete space considers that there are only a finite number of potential sites.

Recent location models also consider temporal or random aspects [1] . The strategy of location problems implies that the model considers the evolution of demand. The investment required to set up terminals is generally important. Terminal must remain functional for a sufficient period of time.

In this study, we present some location models that form the basis of distribution network design issues. A whole line of research has developed around one of the first pioneers of the theory of localization [2] . Since Weber’s work, several works have been done dealing with location-allocation problems.

This paper is organized as follows. Section two provides terminal location models based on deterministic model, stochastic models and hub location models. The paper ends with a conclusion in Section three.

2. Terminal Location Models

Weber [2] developed the first industrial location model. He considered the problem of locating a service offering point so that the cost of transport is minimized. This model is then enriched by many works such as those of [3] [4] [5] [6] , and [7] .

Since then, many localization models have been developed and require four inputs [8] :

・ customers whose position is known (demand nodes);

・ terminal to locate;

・ the space where customers and terminal are located;

・ a metric that indicates distances (or times, transportation costs, ...) between customers and terminals.

2.1. Deterministic Model

The deterministic models that form the basis of these problems are classified into three categories:

• Covering problem;

• P-center problems;

• P-median problems

a) Covering Problem

In many location problems, the service to the client (from the installation that is located) depends on the distance between the client and the installation to which the client is assigned. Customers are usually assigned to the nearest facility. The service is considered adequate if the distance between the client and the facility to which it is assigned is smaller than a given distance. This leads to the notion of coverage.

The objective of this type of problem is to locate terminals to serve all demand nodes, with a minimum total cost. A demand node is covered by a service, if the distance or time between that node and the nearest terminal is not greater than a specified value.

Parameters:

n: Number of demand points indexed by $j,j\in J=\left\{1,\cdots ,n\right\}$

m: Number of potentials terminals indexed by $i,i\in I=\left\{1,\cdots ,m\right\}$

P: Number of terminal to be located $1\le P\le m$

${a}_{ji}$ = 1 if the potential terminal i cover the demand node j

0 if not

${c}_{i}$ : Installation cost at potential site j

Decision variables

${x}_{i}$ : 1 if terminal is located at i

0 if not

Minimize:

$\underset{i\in I}{\sum}{c}_{i}{x}_{i}$ (1.1)

Constraints:

$\underset{i\in I}{\sum}{c}_{i}}{x}_{i}\ge 1,\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall j\in J$ (1.2)

${x}_{i}\in \left\{0,1\right\}$ (1.3)

The objective function (1.1) minimizes the total cost of the facilities that are selected. The constraints (1.2) stipulate that each demand node j must be served by at least one terminal; the left-hand side of the inequality gives the number of localized terminals that can serve node j. The constraints (1.3) are the integrity constraints.

This problem requires a very restrictive condition: every demand point must be served. In a problem containing a lot of scattered demanded nodes, the full covering condition can lead to solutions with too many terminals so costly. [9] Then introduce the Maximum Covering Location Problem (MCLP). The MCLP abandons full covering to maximize covered demand with a limited number of terminal to open. To formulate this problem, the following notations must be added:

Parameters:

n: Number of demand points indexed by $j,j\in J=\left\{1,\cdots ,n\right\}$

m: Number of potentials terminals indexed by $i,i\in I=\left\{1,\cdots ,m\right\}$

P: Number of terminal to be located $1\le P\le m$

${h}_{j}$ : Demand at node j

Decision variables:

${Z}_{j}$ : 1 if node j is opened

0 if not

With these additional notations, the maximum coverage problem can then be formulated as follows:

Maximize

$\underset{j\in J}{\sum}{h}_{j}}{Z}_{j$ (1.4)

Constraint

$\underset{i\in I}{\sum}{a}_{ji}}{x}_{i}\ge {Z}_{i},\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall j\in J$ (1.5)

$\underset{i\in I}{\sum}{x}_{i}}\le P$ (1.6)

${x}_{i}\in \left\{0,1\right\},\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall i\in I$ (1.7)

${Z}_{j}\left\{0,1\right\},\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall j\in J$ (1.8)

The objective function (1.4) maximizes the number of demand covered. Constraints (1.5) indicate that the demand at node i cannot be covered until at least one site that covers node i is selected. The constraint (1.6) stipulates that p maximum terminals can be located. As long as p is greater than the number of terminals needed to cover all the demand nodes, the constraint (1.6) will not affect the obtaining of the optimal solution to cover all the demand nodes. Constraints (1.7) and (1.8) are integrity constraints on decision variables

b) P-center problem

In the p-center problem, all the demand nodes must be covered. However, rather than using a specified blanking distance exogenous and seeking to minimize the number of installations required to cover the request nodes, the p-center problem minimizes the coverage distance so that each node of request is served by one of the facilities located at a distance less than or equal to a determined endogenous distance.

The p-center problem, therefore, is to open terminal and assign each demand node to one of them so as to minimize the maximum distance between each demand mode and the nearest facility. The problem of the p-center can be formulated as follows:

W: The maximum distance between a demand node and the nearest facility to which it is assigned.

Parameters:

P: Number of terminal to be located $1\le P\le m$

${h}_{j}$ : Demand at node j

${d}_{ji}$ : The distance from a demand node j to a potential location i

Decision variables:

${x}_{i}$ = 1 if terminal is located at i

0 if not

${y}_{ji}$ : The fraction of the demand node j that is assigned to the terminal at node i;

Minimize

W (2.1)

Constraints

$\underset{i\in I}{\sum}{x}_{i}}=P$ (2.2)

$\underset{i\in I}{\sum}{y}_{ji}}=1,\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall j\in J$ (2.3)

${y}_{ji}-{x}_{i}\le 0,\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall j\in J,i\in I$ (2.4)

$W-{\displaystyle \underset{i\in I}{\sum}{d}_{ji}}{y}_{ji}\le 0$ (2.5)

${x}_{i}\in \left\{0,1\right\},\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall i\in I$ (2.6)

${y}_{ji}\in \left\{0,1\right\},\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall j\in J,i\in I$ (2.7)

The objective function (2.1) minimizes the maximum distance between a demand node and the closest facility to that node. The constraint (2.2) stipulates that p terminal must be located. The constraints (2.3) require that each demand node be assigned to an installation located at node j. Constraints (2.4) limit the assignment of demand nodes to open facilities. The constraints (2.5) indicate that the maximum distance between the demand points and the nearest installation must be greater than or equal to the distance between each demand node and the facility to which it is assigned. The set of constraints (2.6) and (2.7) are the standard integrity constraints.

In some cases, the distance must be weighted by the demand, since the constraints (2.5) must be replaced by:

$W-{h}_{i}{\displaystyle \underset{j\in J}{\sum}{d}_{ij}}{y}_{ij}\ge 0,\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall i\in I$

c) P-median problem

The problem of the p-median is not to maximize the number of demand nodes covered but to minimize the costs of travel.

The p-median problem, [10] [11] consists of locating facilities and serving each client from established facilities so that the demands of all clients are served and totals cost are minimized. It is based on three important assumptions. He assumes that:

・ The number of terminal to be located is known

・ The installation cost of a terminal is identical regardless of the potential site;

・ The terminals do not have capacity constraints.

The formulation of this problem is as follows:

Parameters:

n: Number of demand points indexed by $j,j\in J=\left\{1,\cdots ,n\right\}$

m: Number of potentials terminals indexed by $i,i\in I=\left\{1,\cdots ,m\right\}$

P: Number of terminal to be located $1\le P\le m$

${h}_{j}$ : Demand at node j

${c}_{ji}$ : The unit transportation cost of to satisfy the demand of the node i by the installation of the node i

Decision Variables:

${x}_{i}$ = 1 if terminal is located at i (location variable)

0 if not

${y}_{ji}$ = 1 if demand node i is assigned to terminal i (affectation variable)

0 if not

Minimize

$\underset{j\in J}{\sum}{\displaystyle \underset{i\in I}{\sum}{h}_{j}}}{c}_{ji}{y}_{ji$ (3.1)

Constraints

$\underset{i\in I}{\sum}{x}_{i}}=P$ (3.2)

$\underset{i\in I}{\sum}{y}_{ji}}=1,\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall j\in J$ (3.3)

${y}_{ji}-{x}_{i}\le 0,\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall i\in I,j\in J$ (3.4)

${x}_{i}\in \left\{0,1\right\},\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall i\in I$ (3.5)

${y}_{ji}\in \left\{0,1\right\},\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall i\in I,j\in J$ (3.6)

The objective function (3.1) minimizes the total cost needed to serve each demand node from the nearest facility. Constraint (3.2) states that p terminal must be located. The constraints (3.3) require that each demand node i be assigned to exactly one facility j. Constraints (3.4) limit the assignment of demand nodes to open terminals. The set of constraints (3.5) and (3.6) are the standard integrity constraints.

The Uncapacitated Facility Location Problem (UFLP) is similar to the p-median problem except that the number of installations to locate is determined endogenously. A non-negative fixed cost is associated with each potential site and this cost is incurred only if the service is actually implemented on this site. The formulation of the p-median problem is modified by removing the constraint (3.2) and adding the term:

$\underset{i\in I}{\sum}{f}_{i}}{x}_{i$

to the objective function (3.1) where ${f}_{i}$ ’s the cost to implement a terminal at node j. The goal is to minimize the total costs of transportation and installation.

The Capacitated Facility Location Problem (CFLP) adds facility capacity constraints to the UFL problem and thus relaxes the three assumptions of the p-median. If ${\Phi}_{j}$ is the capacity of the terminal j, these constraints are written:

$\sum \left({h}_{j}{y}_{ji}-{\Phi}_{i}{x}_{i}\right)}\le 0,\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall j\in J$

In addition, the demand node j can then be assigned to several terminal, if the nearest terminal sees its capacity limit reached.

2.2. Stochastic Models

The majority of the work reported in the literature, dealing with localization problems, presents deterministic models known as NP-difficult and therefore extremely difficult to solve.

But these models do not faithfully present reality and this is the reason why, several authors have recently tried to relax some simplistic assumptions of deterministic models by introducing aspects related to uncertainty.

The introduction of uncertainty in the data in the study of localization problems is made for the first time by [12] . Study on stochastic problems continues even in [13] the authors consider a location problem assuming random costs of exploitation in the distribution center. The goal is to minimize the total cost of transportation between production centers and distribution centers and between the distribution centers and the demand areas. And also to minimize the average total cost of exploitation of the distribution center they suppose that the location of the distribution centers is previously known.

2.3. Hub Localization Problem

The Hub Location Problems (HLPs) have been investigated by many researchers since the pioneering work by [14] . HLP apply when it is necessary to simultaneously determine the location of hubs and the allocation of potential users to them. This is therefore an assignment-location problem. The basic model assumes that there is no capacity constraint at “hubs”, that there is no implementation cost, that direct transport is not allowed between the origins- destinations, which are not hubs, and all traffic from one origin to one destination goes through two hubs.

The mathematical formulation of the HLP due to O’Kelly (1987) can be presented as follows:

Parameters

${q}_{ij}$ : Quantity of flow between nodes i and j.

${c}_{ij}$ : The transport cost of a unit of flow between node i and j.

p: The total number of hubs to be constructed

n: The total number of nodes in the transport network to be interconnected.

Function

$\mathrm{min}A={\displaystyle \underset{i}{\sum}{\displaystyle \underset{j}{\sum}{q}_{ij}}}\left({\displaystyle \underset{k}{\sum}{c}_{ik}{Y}_{ik}}+a{\displaystyle \underset{k}{\sum}{\displaystyle \underset{m}{\sum}{c}_{km}{Y}_{ik}{Y}_{jk}}}+{\displaystyle \underset{m}{\sum}{c}_{jm}{Y}_{jm}}\right)$

Constraints

$\underset{i}{\sum}{Y}_{ik}}\le \left(n-p+1\right){Y}_{kk},\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall k$ (4.1)

$\underset{k}{\sum}{Y}_{ik}}=1,\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall i$ (4.2)

$\underset{k}{\sum}{Y}_{kk}}=p$ (4.3)

${Y}_{ik}\in \left\{0,1\right\};\text{\hspace{0.17em}}\forall i,k$ (4.4)

The objective function Λ comprises three main terms; the first term is collection costs; the second term is transfer costs then the third term is distribution costs.

Constraint (4.1) ensures that no node is assigned to a location unless a hub is opened at that site and recognizing that nodes can only be assigned to hubs, Constraint (4.2) ensures that each node is assigned to one and only one hub. Constraint (4.3) locates the correct number of hubs. Constraint (4.4) ensures that a hub is either opened or closed.

The problems of p-hub median, p-hub center and covering hub are respectively extension of the p-median, p-center and covering problems of location.

P-hub median was proposed by [14] . The goal of the p-hub median problem is to minimize the total transport cost (time, distance, etc.) to serve flows, given the demand nodes, the flow between the destination- origin path and the number of centers to be located (p).

The p-hub center problem was introduced by [15] . The goal is to minimize the maximum distance between each demand node and the nearest center. According to Campbell (1994) p-HCP can be characterized by three main objective functions; the first is to minimize the maximum cost or distance for any origin-destination pair; the second is to minimize the maximum cost or distance of any single link in an origin-destination path and finally, to minimize the maximum cost or distance between flow origin or destination and a hub.

The hub covering problem is on the one hand to locate the hub to cover all the requests such as the costs of opening a hub are minimized and on the other hand to maximize the demand covered with a large number of hub to locate.

3. Conclusions

Location problems draw attention of numerous researchers in different fields. This paper focused on providing a methodology for determining the optimal locations for intermodal freight transportation terminals in consolidation network. The primary purpose of this study is to describe a method that helps identify the best potential locations. Our goal is to minimize total costs in order to increase the efficiency of the transportation system. This paper also has allowed us to have an overview of the methods and models that exist for solving the problem of intermodal, terminal locating. Despite the rich and diverse literature, location problems face theoretical and practical challenges, because every location problem requires a research approach, appropriate model and methods suitable for solving. This paper is an attempt to provide insight and inspiration for solving practical problems by presenting several basic methods for solving terminal location problems. Each of these models added some insights to the general problem of intermodal terminal location in the literature and applications.

References

[1] Owen, S.H. and Daskin, M.S. (1998) Strategic Facility Location: A Review. European Journal of Operational Research, 111, 423-447.

https://doi.org/10.1016/S0377-2217(98)00186-6

[2] Weber, A. (1909) Theory of the Location of Industries. University of Chicago, Chicago.

[3] Palander, T. (1935) Beitrage zur standortstheorie. Almqvist et Wiksells Boktryckeri, Uppsala.

[4] Hoover, E. (1937) Location Theory and the Shoe and Leather Industries. Harvard University Press, Cambridge.

https://doi.org/10.4159/harvard.9780674498624

[5] Lösch, A. (1940) Die raümliche ordnung der wirtschaft. Iena. Traduction anglaise: The Economics of Location. Yale University Press, Neaw Haven.

[6] Ponsard, C. (1955) Economie et espace. Sedes, Paris.

[7] Devletoglou, N. (1965) A Dissenting View of Duopoly and Spatial Competition. Duopoly and Spatial Competition, Economics.

https://doi.org/10.2307/2552545

[8] ReVelle, C.S. and Eiselt, H.A. (2005) Location Analysis: A Synthesis and Survey. European Journal of Operational Research, 165, 1-19.

https://doi.org/10.1016/j.ejor.2003.11.032

[9] Church, R.L. and ReVelle, C. (1974) The Maximal Covering Location Problem. Papers of the Regional Science Association, 32, 101-118.

https://doi.org/10.1007/BF01942293

[10] Hakimi, S. (1964) Optimum Location of Switching Centers and the Absolute Medians of a Graph. Operations Research, 12, 450-459.

https://doi.org/10.1287/opre.12.3.450

[11] Hakimi, S. (1965) Optimal Distribution of Switching Centers in a Communication Network and Some Related Theoretic Graph Theoretic Problems. Operations Research, 13, 462-475.

https://doi.org/10.1287/opre.13.3.462

[12] Manne, A. (1964) Plant Localization under Economy of Scale: Decentralization and Computation. Management Science, 11, 213-235.

https://doi.org/10.1287/mnsc.11.2.213

[13] Ricciard, N., Tadei, R. and Grosso, A. (2002) Optimal Facility Location with Random throughput Costs. Computers & Operations Research, 29, 593-607.

https://doi.org/10.1016/S0305-0548(99)00090-8

[14] O’Kelly, M. (1987) A Quadratic Integer Program for the Location of Interacting Hub Facilities. European Journal of Operational Research, 32, 393-404.

https://doi.org/10.1016/S0377-2217(87)80007-3

[15] Campbell, J.F. (1994) Integer Programming Formulations of Discrete Hub Location Problems. European Journal of Operational Research, 72, 387-405.

https://doi.org/10.1016/0377-2217(94)90318-2