A MODIFIED PARTICLE SWARM OPTIMIZATION ALGORITHM FOR GENERAL INVERSE ORDERED p-MEDIAN LOCATION PROBLEM ON NETWORKS
Abstract
This paper is concerned with a general inverse ordered p-median location problem on network where the task is to change (increase or decrease) the edge lengths and vertex weights at minimum cost subject to given modification bounds such that a given set of p vertices becomes an optimal solution of the location problem, i.e., an ordered p-median under the new edge lengths and vertex weights. A modified particle swarm optimization algorithm is designed to solve the problem under the cost functions related to the sum-type Hamming, bottleneck-type Hamming distances and the recti-linear and Chebyshev norms. By computational experiments, the high efficiency of the proposed algorithm is illustrated.
Keywords
Keywords
Full Text:
PDFReferences
B. Alizadeh and R. E. Burkard, Combinatorial algorithms for inverse absolute and vertex 1-center location problems on trees, Networks, 58 (2011) 190–200.
B. Alizadeh, R. E. Burkard and U. Pferschy, Inverse 1-center location problems with edge length augmentation on trees, Computing, 86 (2009) 331–343.
B. Alizadeh and R. E. Burkard, A linear time algorithm for inverse obnoxious center location problems on networks, Central European Journal of Operations Research, 21 (2013) 585–594.
F. Baroughi-Bonab, R. E. Burkard and E. Gassner, Inverse p-median problems with variable edge lengths, Mathematical Methods of Operations Research, 73 (2011) 263–280.
R. E. Burkard, C. Pleschiutschnig and J. Zhang, Inverse median problems, Discrete Optimization, 1 (2004) 23–39.
R. E. Burkard, C. Pleschiutschnig and J. Zhang, The inverse 1-median problem on a cycle, Discrete Optimization, 5 (2008) 242–253.
M. C. Cai, X. G. Yang and J. Z. Zhang, The complexity analysis of the inverese center location problem, Journal of Global Optimization, 15 (1999) 213–218.
M. Clerc and J. Kennedy, The particle swarm explosion, stability and convergence in a multidimensional complex space, Transactions on Evolutionary Computation , 6 (2002) 58–73.
P. M. Dearing, R. L. Francis and T. J. Lowe, Convex location problems on tree networks, Operations Research, 24 (1976) 628–642.
R. L. Francis, L. F. McGinnis and J. A. White, Facility Layout and Location, An Analytical Approach, Prentice Hall, Englewood Cliffs, 1992.
E. Gassner, The inverse 1-maxian problem with edge length modification, Journal of Combinatorial Optimization, 16 (2007) 50–67.
E. Gassner, An inverse approach to convex ordered median problems, Journal of Combinatorial Optimization, 23 (2012) 261–273.
J. Kalcsics, S. Nickel, J. Puerto and A. Tamir, Algorithmic results for ordered median problems, Operations Research Letters, 30 (2002) 149–158.
J. Kennedy and R. C. Eberhart, Particle swarm optimization, Proceeding of IEEE International Conference on Neural Networks, 4 (1995) 1942–1948.
R. F. Love, J. G. Morris and G. O. Wesolowsky, Facilities Location: Models and Methods, North-Holland, New York, 1988.
B.P. Mirchandani and R.L. Francis, Discrete Location Theory, John Wiley, New York, 1990.
K. T. Nguyen and A. Chassein, The inverse convex ordered 1-median problem on trees under Chebyshev norm and Hamming distance, European Journal of Operational Research, 247 (2015) 774–781.
K. T. Nguyen and A. R. Sepasian, The inverse 1-center problem on trees with variable edge lengths under Chebyshev norm and Hamming distance, Journal of Combinatorial Optimization, (2015) Doi: 10.1007/s10878-015-9907-5.
A. R. Sepasian and F. Rahbarnia, An algorithm for the Inverse 1-median problem on trees with variable vertex weights and edge reductions, Optimization, 64 (2015) 595–602.
Y. Shi and R. C. Eberhart, Parameter selection in particle swarm optimization, Proceedings of Evolutionary Programming, 7 (1999) 591–600.
X. Yang, J. Zhang, Inverse center location problem on a tree, Journal of Systems Science and Complexity, 21 (2008) 651–664.
J. Kratica, Z. Stanimirović, D. Tošić and V. Filipović: Two genetic algorithms for solving the uncapacitated single allocation p-hub median problem, European Journal of Operational Research, 182 (2007), 15-28.
R.F. Love, J.G. Morris and G.O. Wesolowsky: Facilities Location: Models and Methods, North-Holland, New York, 1988.
B.P. Mirchandani and R.L. Francis: Discrete Location Theory, John Wiley, New York, 1990.
N. Mladenović, J. Brimberg, P. Hansen and J. A. Moreno-Pérez: The p-median problem: A survey of metaheuristic approaches, European Journal of Operational Research, 179 (2007), 927-939.
K.T. Nguyen and A. Chassein: The inverse convex ordered 1-median problem on trees under Chebyshev norm and Hamming distance, European Journal of Operational Research, 247 (2015) 774-781.
K.T. Nguyen and A.R. Sepasian: The inverse 1-center problem on trees with variable edge lengths under Chebyshev norm and Hamming distance, Journal of Combinatorial Optimization, (2015) Doi: 10.1007/s10878-015-9907-5.
J. Puerto, D. Pérez-Brito and C. G. García-González: A modified variable neighborhood search for the discrete ordered median problem, European Journal of Operational Research, 234 (2014), 61-76.
S. S. Rao: Engineering Optimization: Theory and Practice, John Wiley, New York, NY, USA, 4th edition, 2009.
M. Sevkli, R. Mamedsaidov and F. Camci: A novel discrete particle swarm optimization for p-median problem, Journal of King Saud University-Engineering Sciences, 26 (2014), 11-19.
A.R. Sepasian and F. Rahbarnia: An algorithm for the Inverse 1-median problem on trees with variable vertex weights and edge reductions, Optimization: A Journal of Mathematical Programming and Operations Research, 64 (2015) 595-602.
Z. Stanimirović, J. Kratica and D. Dugošija: Genetic algorithms for solving the discrete ordered median problem, European Journal of Operational Research, 182 (2007), 983-1001.
Y. Shi and R.C. Eberhart: Parameter selection in particle swarm optimization, Proceedings of Evolutionary Programming, 7 (1999) 591-600.
X. Yang and J. Zhang: Inverse center location problem on a tree, Journal of Systems Science and Complexity, 21 (2008) 651-664.
DOI: https://doi.org/10.22190/FUMI1704447M
Refbacks
- There are currently no refbacks.
ISSN 0352-9665 (Print)