research-article

The dynamic p-median problem with mobile facilities

Authors:

Hüseyin Güden,

Haldun SüralAuthors Info & Claims

Volume 135, Issue C

Pages 615 - 627

https://doi.org/10.1016/j.cie.2019.06.024

Published: 01 September 2019 Publication History

Highlights

•

The most general version of the dynamic p-median problem is studied.

•

Mobile and immobile facilities are considered separately and together.

•

Distance based decision variables are used in the mathematical model of the problem.

•

Three heuristics and a branch-and-price algorithm are developed.

•

Extensive numerical experiments are performed.

Abstract

Being motivated by real life applications in construction management, we consider the dynamic p-median problem and its extension with mobile facilities. The number of facilities changes over a planning horizon where one or more facilities can be opened, relocated, or closed in any period. The problem is to determine (i) facility locations, (ii) opening/closing times of facilities, (iii) routes of mobile facilities, and (iv) demand allocations to open facilities such that the total cost is minimized. We present a mixed integer programming formulation of the dynamic p-median problem using discretization of distances to control the locational decision variables. We develop a branch and price algorithm and constructive heuristics to solve the problem. Extensive computational results of the solution method are provided on a set of test problem instances.

References

[1]

M. Albareda-Sambola, A. Alonso-Ayuso, L.F. Escudero, E. Fernández, Y. Hinojosa, C. Pizarro-Romero, A computational comparison of several formulations for the multi-period incremental service facility location problem, TOP 18 (2010) 62–80.

[2]

M. Albareda-Sambola, E. Fernández, Y. Hinojosa, J. Puerto, The multi-period incremental service facility location problem, Computers and Operations Research 36 (2009) 1356–1375.

[3]

A. Antunes, D. Peeters, A dynamic optimization model for school network planning, Socio-Economic Planning Sciences 34 (2000) 101–120.

[4]

A. Antunes, D. Peeters, On solving complex multi-period location models using simulated annealing, European Journal of Operational Research 130 (2001) 190–201.

[5]

A.B. Arabani, R.Z. Farahani, Facility location dynamics: An overview of classifications and applications, Computers and Industrial Engineering 62 (2012) 408–420.

[6]

P. Avella, A. Sassano, On the p-median polytope, Mathematical Programming 89 (2001) 395–411.

[7]

P. Avella, A. Sassano, I. Vasil’ev, Computational study of large-scale p-median problems, Mathematical Programming (Ser. A) 109 (2007) 89–114.

[8]

J.E. Beasley, A note on solving large p-median problems, European Journal of Operational Research 21 (1985) 270–273.

[9]

J.E. Beasley, Lagrangian heuristics for location problems, European Journal of Operational Research 65 (1993) 383–399.

[10]

L. Brotcorne, G. Laporte, F. Semet, Ambulance location and relocation models, European Journal of Operational Research 147 (2003) 451–463.

[11]

P. Chardaire, A. Sutter, M. Costa, Solving the dynamic facility location problem, Networks 28 (1996) 117–124.

[12]

N. Christofides, J.E. Beasley, A tree search algorithm for the p-median problem, European Journal of Operational Research 10 (1982) 196–204.

[13]

I. Contreras, J. Cordeau, G. Laporte, The dynamic uncapacitated hub location problem, Transportation Science 45 (2011) 18–32.

[14]

G. Cornuejols, M.L. Fisher, G.L. Nemhauser, Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms, Management Science 23 (1977) 789–810.

[15]

G. Cornuejols, G. Nemhauser, L.A. Wolsey, A canonical representation of simple plant location problems and its applications, SIMAX 1 (3) (1980) 261–272.

[16]

J. Dias, M.E. Captivo, J. Clímaco, Capacitated dynamic location problems with opening, closure and reopening of facilities, IMA Journal of Management Mathematics 17 (4) (2006) 317–348.

[17]

J. Dias, M.E. Captivo, J. Clímaco, Efficient primal-dual heuristic for a dynamic location problem, Computers and Operations Research 34 (2007) 1800–1823.

[18]

J. Dias, M.E. Captivo, J. Clímaco, A dynamic location problem with maximum decreasing capacities, CEJOR 16 (2008) 251–280.

[19]

J. Dias, M.E. Captivo, J. Clímaco, Dynamic multi-level capacitated and uncapacitated location problems: An approach using primal-dual heuristics, Oper Res Int J 7 (2008) 345–379.

[20]

Z. Drezner, Dynamic location problem: The progressive p-median problem, Location Science 3 (1) (1995) 1–7.

[21]

S. Elloumi, A tighter formulation of the p-median problem, Journal of Combinational Optimization 19 (1) (2010) 69–83.

[22]

S. Elloumi, A. Plateau, A computational study for the p-median problem, Electronic Notes in Discrete Mathematics 36 (2010) 455–462.

[23]

R.Z. Farahani, M. Abedian, S. Sharahi, Dynamic facility location problem, in: R.Z. Farahani, M. Hekmatfar (Eds.), Facility location: Concepts, models, algorithms and case studies, Physica-Verlag, Heidelberg, Germany, 2009, pp. 347–372.

[24]

R.Z. Farahani, Z. Drezner, N. Asgari, Single facility location and relocation problem with time dependent weights and discrete planning horizon, Annals of Operations Research 167 (2009) 353–368.

[25]

I.R. Farias Jr., A family of facets for the uncapacitated p-median polytope, Operations Research Letters 28 (2001) 161–167.

[26]

E. Feldman, F.A. Lehrer, T.L. Ray, Warehouse locations under continuous economies of scale, Management Science 12 (1966) 670–684.

[27]

R.L. Francis, T.J. Lowe, A. Tamir, Aggregation error bounds for a class of location models, Operations Research 48 (2000) 294–307.

[28]

M. Frantzeskakis, C.D.T. Watson-Gandy, The use of state space relaxation for the dynamic facility location problem, Annals of Operations Research 18 (1989) 189–212.

[29]

R.D. Galvão, A dual-bounded algorithm for the p-median problem, Operations Research 28 (5) (1980) 1112–1121.

[30]

R.D. Galvão, Use of Lagrangean relaxation in the solution of uncapacitated facility location problems, Location Science 1 (1993) 57–70.

[31]

R.D. Galvão, L.A. Raggi, A method for solving to optimality uncapacitated location problems, Annals of Operations Research 18 (1989) 225–244.

[32]

R.D. Galvão, E. Santibanez-Gonzales, A Lagrangean heuristic for the p_k -median dynamic location problem, European Journal of Operational Research 58 (1992) 250–262.

[33]

S. García, M. Labbé, A. Marín, Solving large p-median problems with a radius formulation, INFORMS Journal on Computing 23 (4) (2011) 546–556.

[34]

R.S. Garfinkel, A.W. Neebe, M.R. Rao, An algorithm for the m-median plant location problem, Transportation Science 8 (1974) 217–236.

[35]

S. Gelareh, R.N. Monemi, S. Nickel, Multi-period hub location problems in transportation, Transportation Research part E: Logistics and Transportation Review 75 (2015) 67–94.

[36]

A. Ghaderi, M.S. Jabalameli, Modeling the budget-constrained dynamic uncapacitated facility location-network design problem and solving it via two efficient heuristics: A case study of health care, Mathematical and Computer Modelling 57 (2013) 382–400.

[37]

E. Gourdin, O. Klopfenstein, Multi-period capacitated location with modular equipments, Computers and Operations Research 35 (2008) 661–682.

[38]

H. Güden, H. Süral, Locating mobile facilities in railway construction management, OMEGA 45 (2014) 71–79.

[39]

S.L. Hakimi, Optimum distribution of switching centers in a communication network and some related graph theoretic problems, Operations Research 13 (1965) 462–475.

[40]

R. Halper, S. Raghavan, The mobile facility routing problem, Transportation Science 45 (3) (2011) 413–434.

Digital Library

[41]

P. Hanjoul, D. Peeters, A comparison of two dual-based procedures for solving the p-median problem, European Journal of Operational Research 20 (1985) 387–396.

[42]

M. Hribar, M. Daskin, A dynamic programming heuristic for the p-median problem, European Journal of Operational Research 101 (1997) 499–508.

[43]

O. Kariv, S.L. Hakimi, An algorithmic approach to network location problems: Part 2. The p-medians, SIAM Journal on Applied Mathematics 37 (1979) 539–560.

[44]

A. Klose, A. Drexl, Facility location models for distribution system design, European Journal of Operational Research 162 (2005) 4–29.

[45]

T. Le-Anh, M.B.M. De Coster, A review of design and control of automated guided vehicle systems, European Journal of Operational Research 171 (1) (2006) 1–23.

[46]

S.K. Lim, Y.D. Kim, An integrated approach to dynamic plant location and capacity planning, The Journal of the Operational Research Society 50 (12) (1999) 1205–1216.

[47]

R. Manzini, E. Gebennini, Optimization models for the dynamic facility location and allocation problem, International Journal of Production Research 46 (2008) 2061–2086.

[48]

M.T. Melo, S. Nickel, F. Saldanha-da-Gama, Facility location and supply chain management: A review, European Journal of Operational Research 196 (2009) 401–412.

[49]

P. Mirchandani, A. Oudjit, R.T. Wong, Multidimensional extensions and e nested dual approach for the m-median problem, European Journal of Operational Research 21 (1985) 121–137.

[50]

S. Mišković, Z. Stanimirović, I. Grujičić, An efficient variable neighborhood search for solving a robust dynamic facility location problem in emergency service network, Electronic Notes in Discrete Mathematics 47 (2015) 261–268.

[51]

N. Mladenović, J. Brimberg, P. Hansen, J.A. Moreno-Pérez, The p-median problem: A survey of metaheuristic approaches, European Journal of Operational Research 179 (2007) 927–939.

[52]

S.C. Narula, U.I. Ogbu, H.M. Samuelson, An algorithm for the p-median problem, Operations Research 25 (1977) 709–713.

[53]

J. Reese, Solution methods for the p-median problem: An annotated bibliography, Networks 48 (3) (2006) 125–142.

[54]

M. Resende, R.F. Werneck, On the implementation of a swap-based local search procedure for the p-median problem, in: Richard E. Ladner (Ed.), Proceedings of the 5^th workshop on algorithm engineering and experiments, SIAM, 2003, pp. 119–127.

[55]

C.S. ReVelle, R. Swain, Central facilities location, Geographical Analysis 2 (1970) 30–42.

[56]

G.M. Roodman, L.B. Schwarz, Optimal and heuristic facility phase-out strategies, AIIE Transactions 7 (2) (1975) 177–184.

[57]

G.M. Roodman, L.B. Schwarz, Extensions of the multi-period facility phase-out model: New procedures and applications to a phase-in/phase-out problem, AIIE Transactions 9 (1) (1977) 103–107.

[58]

K.E. Rosing, C.S. ReVelle, H. Rosing-Vogelaar, The p-median and its linear programming relaxation: An approach to large problems, Journal of the Operational Research Society 30 (1979) 815–822.

[59]

F. Saldanha-da-Gama, M.E. Captivo, A heuristic approach for the discrete dynamic location problem, Location Science 6 (1998) 211–223.

[60]

S. Salhi, R.A. Atkinson, Subdrop: A modified drop heuristic for location problems, Location Science 3 (1995) 267–273.

[61]

E.L.F. Senne, L.A.N. Lorena, M.A. Pereira, A branch and price approach to p-median location problems, Computers and Operations Research 32 (2005) 1655–1664.

[62]

S.M. Seyedhosseini, A. Makui, K. Shahanaghi, S.S. Torkestani, Models, solution, methods and their applicability of dynamic location problems (DLPs) (a gap analysis for further research), Journal of Industrial Engineering International 12 (2016) 311–341.

[63]

A. Shulman, An algorithm for solving dynamic capacitated plant location problems with discrete expansion sizes, Operations Research 39 (3) (1991) 423–436.

[64]

J.E. Torres-Soto, H. Üster, Dynamic-demand capacitated facility location problems with and without relocation, International Journal of Production Research 49 (13) (2011) 3979–4005.

[65]

T.J. Van Roy, D. Erlenkotter, A dual-based procedure for dynamic facility location, Management Science 28 (10) (1982) 1091–1105.

Digital Library

[66]

G.O. Wesolowsky, Dynamic facility location, Management Science 19 (1973) 1241–1247.

Digital Library

[67]

G.O. Wesolowsky, W.G. Truscott, The multi-period location-allocation problem with relocation of facilities, Management Science 22 (1) (1975) 57–65.

[68]

R. Whitaker, A fast algorithm for the greedy interchange for large-scale clustering and median location problems, INFOR 21 (1983) 95–108.

Cited By

Alarcon-Gerbier EBuscher U(2022)Modular and mobile facility location problemsComputers and Industrial Engineering10.1016/j.cie.2022.108734173:COnline publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1016/j.cie.2022.108734

Index Terms

The dynamic p-median problem with mobile facilities

Index terms have been assigned to the content through auto-classification.

Recommendations

The obnoxious facilities planar p-median problem
Abstract
In this paper, we propose the planar obnoxious facilities p-median problem. In the p-median problem the objective is to find p locations for facilities that minimize the weighted sum of distances between communities and their closest facility. In ...
A neural model for the p-median problem

There exist several neural techniques for solving NP-hard combinatorial optimization problems. At the beginning of the 1980s, recurrent neural networks were shown to be able to solve optimization problems. Criticism of this approach includes the ...
Heuristic solution of the multisource Weber problem as a p-median problem

Good heuristic solutions for large multisource Weber problems can be obtained by solving related p-median problems in which potential locations of the facilities are users locations and then solving Weber problems for the sets of users of each facility. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computers and Industrial Engineering

Computers and Industrial Engineering Volume 135, Issue C

Sep 2019

1324 pages

ISSN:0360-8352

Issue’s Table of Contents

Elsevier Ltd.

Publisher

Pergamon Press, Inc.

United States

Publication History

Published: 01 September 2019

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 29 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Alarcon-Gerbier EBuscher U(2022)Modular and mobile facility location problemsComputers and Industrial Engineering10.1016/j.cie.2022.108734173:COnline publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1016/j.cie.2022.108734

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents