A HYBRID ALGORITHM FOR THE UNCERTAIN INVERSE p-MEDIAN LOCATION PROBLEM

Akram Soltanpour, Fahimeh Baroughi, Behrooz Alizadeh

DOI Number
https://doi.org/10.22190/FUMI2005399S
First page
1399
Last page
1416

Abstract


In this paper, we investigate the inverse p-median location  problem with variable edge lengths and variable vertex weights on networks in which the vertex weights and modification costs are the independent uncertain variables. We propose a  model for the uncertain inverse p-median location problem  with tail value at risk objective. Then, we show that  it  is NP-hard. Therefore,  a hybrid particle swarm optimization  algorithm is presented  to obtain   the approximate optimal solution of the proposed model. The algorithm contains expected value simulation and tail value at risk simulation.

Keywords

p-median location problem; inverse optimization; Hybrid algorithm; nonlinear programming

Full Text:

PDF

References


Alp O., Erkut E., Drezner Z., An efficient genetic algorithm for the $p$-median

problem, emph{Annals of Operations Research} textbf{10} (2003), 1387-1395.

Alizadeh B., Bakhteh S., A modified firefly algorithm for general inverse $p$-median location problems under different distance norms, emph{ Opsearch} textbf{54} (2017), 618-636.

Baroughi F., Burkard R. E., Gassner E., Inverse $p$-median problems with variable edge

lengths, emph{ Mathematical Methods of Operations Research} textbf{73} (2011), 263-280.

Bashiri M., Mirzaei M., Randall M., Modeling fuzzy capacitated

$p$-hub center problem and a genetic algorithm solution, emph{ Applied Mathematical Modelling} textbf{37(5)} (2013), 3513-3525.

Bai X., Liu Y., Minimum risk facility location-allocation problem with

type-2 fuzzy variables, emph{ The Scientific World Journal} textbf{2014} (2014), 1-9.

Berman O., Sanajian N., Wang J., Location choice and risk attitude of a decision maker, emph{ Omega} textbf{66} (2017), 170-181.

Benkoczi R., Bhattacharya B., A new template for solving $p$-median problems for trees in sub-quadratic time (extended abstract), emph{Lecture Notes in Computer Science} textbf{3669} (2005), 271-282.

Burkard R. E., Krarup J., A linear algorithm for the pos/neg-weighted 1-median problem on a cactus,

emph{Computing} textbf{60} (1998), 193-215.

Burkard R. E., Pleschiutschnig C., Zhan J., Inverse median problems, emph{Discrete Optimization} textbf{1} (2004), 23-39.

Burkard R. E., Pleschiutschnig C., Zhan J., The inverse 1-median problem on a cycle, emph{Discrete Optimization} textbf{5} (2008), 242-253.

Drezner Z., The planar two-center and two-median problems, emph{Transportation Science} textbf{18} (1984), 351-361.

Eilon S., Watson-Gandy C. D. T., Christofides N., emph{Distribution management: mathematical modeling and practical analysis}, New

York: Hafner (1971).

Eiselt H. A., Marianov V., emph{Foundations of location analysis},

Operations Research and Management Science, NewYork: Springer (2011).

Gao Y., Uncertain models for single facility location problems on networks, emph{Applied Mathematical Modelling} textbf{36} (2012), 2592-2599.

Gao Y., Qin Z., A chance constrained programming approach for uncertain $p$-hub center location problem, emph{Computers and Industrial Engineering} textbf{102} (2016), 10-20.

Galavii M., The inverse 1-median problem on a tree and on a path, emph{Electronic Notes in Disrete Mathematics} textbf{36} (2010), 1241-1248.

Goldman A. J., Optimal center location in simple networks, emph{Transportation Science} textbf{5} (1971), 212-221.

Guan X., Zhang B., Inverse 1-median problem on trees under weighted Hamming distance, emph{Journal of Global Optimization} textbf{54} (2012), 75-82.

Guan X., Zhang B., Inverse 1-median problem on trees under weighted $ {l}_{infty}$ norm, emph{Lecture Notes in Computer

Science} textbf{6124} (2010), 150-160.

Hakimi S. L., Optimum locations of switching centers and the absolute centers and medians of a graph, emph{Operations Research} textbf{12} (1964), 450-459.

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

Huang X., Hao D., Modelling uncapacitated facility location

problem with uncertain customers’ positions, emph{Journal of Intelligent and Fuzzy Systems} textbf{28} (2015), 2569-2577.

Hatzl J., 2-balanced flows and the inverse 1-median problem in the

Chebyshev space, emph{Discrete Optimization} textbf{9} (2012), 137-148.

bibitem{Kennedy}

Kennedy J., Eberhart R. C., Particle swarm optimization, emph{Proceeding of IEEE

International Conference on Neural Networks} textbf{4} (1995), 1942-1948.

Liu B., emph{Uncertainty theory}, 2nd ed., Springer-Verlag, Berlin (2007).

Liu B., {Uncertain risk analysis and uncertain reliability analysis}, emph{Journal of Uncertain Systems} textbf{4 (3)} (2010), 163-170.

Liu X., Uncertain programming model for location problem

of multi-product logistics distribution centers, emph{Applied Mathematical Sciences} textbf{9} (2015),

-6558.

Love R. F., emph{Facilities location: models and methods}, Operations Research Series (1988).

Mirzapolis Adeh I., Baroughi F., Alizadeh B., A modified particle

swarm optimization algorithm for general inverse ordered $p$-median location problem on network, in emph{Facta Universitatis, Series: Mathematics and Informatics,} textbf{32} (2017), 447-468.

Nguyen K. T., Inverse 1-median problem on block graphs with variable vertex weights, emph{ Journal of Optimization Theory and Applications } textbf{168} (2016), 944-957.

Nguyen K. T., Chi N. T. L., A model for the inverse 1-median problem on trees under uncertain costs, emph{ Opuscula Mathematica} textbf{36} (2016), 513-523.

Peng J., Risk metrics of loss function for uncertain system, emph{Fuzzy Optimtimization and Decision Making} textbf{12} (2013), 53-64.

Peng J., Zhang B., Li S., Towards uncertain network optimization, emph{Journal of Uncertainty Analysis and Applications} (2015), doi: 10.1186/s40467-014-0022-4.

Qin Z., Gao Y., Uncapacitated $p$-hub location problem with fixed costs and uncertain flows, emph{Journal of Intelligent Manufacturing} textbf{28} (2017), 705-716.

Rahmaniani R., Saidi-Mehrabad M., Ghaderi A., An efficient hybrid solution algorithm for the capacitated facility location-allocation problem under uncertainty, emph{Journal of optimization in Industrial Engineering} DOI: 10.22094/joie.2018.538339 (2018).

Sepasian A. R., Rahbarnia F., An $O(n log n)$ algorithm for the inverse 1-median problem on trees with variable vertex weights and edge reductions, emph{Optimization} textbf{64} (2015), 595-602.

Schobel A., Scholz D., The big cube small cube solution method for multi-dimensional facility location problems, emph{Computers and Operations Research} textbf{37} (2010),

-122.

Sherali H. D., Tuncbilek C. H., A squared Euclidean distance location-allocation problem, emph{Naval Research Logistics} textbf{39} (1992), 447-469.

Tamir A., An $O(p n^2)$ algorithm for the $p$-median and related problems on tree graphs, emph{Operations Research Letters} textbf{19} (1996), 59-64.

Wang K. E., Yang Q., Hierarchical facility location for the reverse logistics network design under uncertainty, emph{World Academic Press, UK} textbf{8} (2014), 255-270.

Wang Sh., Watada J., Pedrycz W., Value at risk based two-stage fuzzy facility location problems, emph{IEEE Transactions on Industrial Informatics} textbf{5} (2009), 465-482.

Wagner M. R., Bhadury J., Peng S., Risk management in uncapacitated facility location models with random demands, emph{Computers and Operations Research} textbf{36} (2009), 1002-1011.

Wen M., Qin Z., Kang R., Yang Y., The capacitated facility location-allocation problem under uncertain environment, emph{Journal of Intelligent and Fuzzy System} textbf{29} (2015), 2217-2226.

Yang K., Liu Y., Yang G., Optimizing fuzzy $p$-hub center problem with generalized value at risk criterion, emph{Applied Mathematical Modelling} textbf{38} (2014), 3987-4005.

Yang K., Liu Y., Yang G., An improved hybrid particle

swarm optimization algorithm for fuzzy $p$-hub center problem, emph{Computers and Industrial Engineering} textbf{64} (2013a), 133-142.

Zhang B., Peng J., Li S., Covering location problem of emergency service facilities in an uncertain environment, emph{Applied Mathematical Modelling} textbf{51} (2017), 429-447.




DOI: https://doi.org/10.22190/FUMI2005399S

Refbacks

  • There are currently no refbacks.




© University of Niš | Created on November, 2013
ISSN 0352-9665 (Print)
ISSN 2406-047X (Online)