A Lagrangian relaxation approach to fuzzy robust multi-objective facility location network design problem

Document Type : Article


1 Department of Industrial Engineering, Yazd University, P.C.1684613114, Yazd, Iran

2 School of Industrial and systems Engineering, University of Tehran, Tehran, Iran


This study considers a multi-objective combined budget constrained facility location/network design problem (FL/NDP) in which the system uncertainty is considered. The most obvious practical examples of the problem are territorial designing and locating of academies, airline networks, and medical service centers. In order to assure the network reliability versus uncertainty, an efficient robust optimization approach is applied to model the proposed problem. The formulation is minimizing the total expected costs, including, transshipment costs, facility location (FL) costs, fixed cost of road/link utilization as well as minimizing the total penalties of uncovered demand nodes. Then, in order to consider of several system uncertainty, the proposed model is changed to a fuzzy robust model by suitable approaches. An efficient Sub-gradient based Lagrangian relaxation algorithm is applied. In addition, a practical example is studied. At the following, a series of experiments, including several test problems, is designed and solved to evaluate of the performance of the algorithm. The obtained results emphasize that considering of practical factors (e.g., several uncertainties, system disruptions, and customer satisfaction) in modelling of the problem can lead to significant improvement of the system yield and subsequently more efficient utilization of the established network.  


Main Subjects

1. Kuehn, A.A. and Hamburger, M.J. A heuristic program
for locating warehouses", Management Science,
9(4), pp. 643-666 (1963).
2. Hakimi, S.L. Optimum locations of switching centers
and the absolute centers and medians of a graph",
Operations Research, 12(3), pp. 450-459 (1964).
3. Toregas, C., Swain, R., ReVelle, C., and Bergman, L.
The location of emergency service facilities", Operations
Research, 19, pp. 1363-1373 (1971).
4. Drezner, Z. and Wesolowsky, G.O. Network design:
Selection and design of links and facility location",
Transportation Research, Part A, 37, pp. 241-256
5. Rahmaniani, R. and Ghaderi, A. A combined facility
location and network design problem with multi-type
of capacitated links", Applied Mathematical Modelling,
37(9), pp. 6400-6414 (2013).
6. Ghaderi, A. and Jabalameli, M.S. Modeling the
budget-constrained dynamic uncapacitated facility
location-network design problem and solving it via
two ecient heuristics: a case study of health care",
Mathematical and Computer Modelling, 57, pp. 382-
400 (2013).
7. Ghaderi, A. Heuristic algorithms for solving an integrated
dynamic center facility location-network design
model", Networks and Spatial Economics, 15(1), pp.
43-69 (2015).
8. Rahmaniani, R. and Ghaderi, A. An algorithm with
di erent exploration mechanisms: experimental results
to capacitated facility location/network design problem",
Expert Systems with Applications, 42(7), pp.
3790-3800 (2015).
9. Saman Hassanzadeh, A. and Baki, F. A facility
location model for global closed-loop supply chain
network design", Applied Mathematical Modelling, 41,
pp. 316-330 (2017).
10. Taleizadeh, A.A., Niaki, S.T.A., and Aryanezhad,
M.B. A hybrid method of Pareto, TOPSIS and
genetic algorithm to optimize multi-product multiconstraint
inventory control systems with random
fuzzy replenishments", Mathematical and Computer
Modeling, 49(5-6), pp. 1044-1057 (2009).
11. Taleizadeh, A.A., Niaki, S.T.A., and Aryanezhad,
M.B. Replenish-up-to multi chance-constraint inventory
control system with stochastic period lengths and
total Discount under fuzzy purchasing price and holding
costs", International Journal of System Sciences,
41(10), pp. 1187-1200 (2010-a).
12. Taleizadeh, A.A., Barzinpour, F., and Wee, H.M.
Meta-heuristic algorithms to solve the fuzzy single period
problem", Mathematical and Computer Modeling,
54(5-6), pp. 1273-1285 (2011).
13. Nozick, L.K. The xed charge facility location problem
with coverage restrictions", Transportation Research,
part E., 37, pp. 281-296 (2001).
14. Villegas, J.G., Palacios, F., and Medaglia, A.L. Solution
methods for the bi-objective (cost-coverage)
unconstrained facility location problem with an illustrative
example", Annals of Operations Research,
147(1), pp. 109-141 (2006).
15. Farhan, B. and Murray, A.T. Distance decay and
coverage in facility location planning", The Annals of
Regional Science, 40(2), pp. 279-295 (2006).
16. Taleizadeh, A.A., Naja , A.A., and Niaki, S.T.A.
Multi product EPQ model with scraped items and
limited production capacity", Scientia Iranica, Transactions
E., 17(1), pp. 58-69 (2010-b).
17. Murray, A.T., Tong, D., and Kim, K. Enhancing classic
coverage location models", International Regional
Science Review, 33(2), pp. 115-133 (2010).
18. Jabalameli, M.S. and Mortezaei, M. A hybrid model
for multi-objective capacitated facility location network
design problem", International Journal of Industrial
Engineering Computations, 2, pp. 509-524 (2011).
19. Maliszewski, P.J.K., Michael, J., and Horner, M.W.
A comparison of multi-objective spatial dispersion
models for managing critical assets in urban areas
Computers", Environment and Urban Systems, 36(4),
pp. 331-341 (2012).
20. Taleizadeh, A.A., Pentico, D.W., Jabalameli, M.S.,
and Aryanezhad, M.B. An economic order quantity
model with multiple partial prepayments and partial
backordering", Mathematical and Computer Modeling,
57(3-4), pp. 311-323 (2013).
21. Taleizadeh, A.A. and Pentico, D.W. An economic
order quantity model with known price increase and
partial backordering", European Journal of Operational
Research, 28(3) pp. 516-525 (2013).
22. Xifeng, T., Zhang, J., and Peng, X. A multi-objective
optimization model for sustainable logistics facility
location", Transportation Research, Part D: Transport
and Environment, 22, pp. 45-48 (2013).
23. Eskandarpour, M., Zegordi, S.H., and Nikbakhsh, E.
A parallel variable neighborhood search for the multiobjective
sustainable post-sales network design problem",
International Journal of Production Economics,
145(1), pp. 117-131 (2013).
24. Ozgen, D. and Bahadir, G. Combining possibilistic
linear programming and fuzzy AHP for solving
the multi-objective capacitated multi-facility location
problem", Information Sciences, 268, pp. 185-201
25. Sadjadi, S.J., Soltani, R., and Eskandarpour, A.
Location based treatment activities for end of life
products network design under uncertainty by a robust
multi-objective memetic-based heuristic approach",
Applied Soft Computing, 23, pp. 215-226 (2014).
26. Afshari, H., Shara , M., Elmekkawy, T., and Peng, Q.
Optimizing multi-objective dynamic facility location
decisions within green distribution network design",
Procedia CIRP, 17(1), pp. 675-679 (2014).
D. Shishebori et al./Scientia Iranica, Transactions E: Industrial Engineering 25 (2018) 1750{1767 1765
27. Pasandideh, S.H.R., Niaki, S.T.A., and Asadi, K. Biobjective
optimization of a multi-product multi-period
three-echelon supply chain problem under uncertain
environments: NSGA-II and NRGA", Information
Sciences, 292, pp. 57-74 (2015).
28. Tavakkoli-Moghaddam, R., Vazifeh-Noshafagh, S.,
Taleizadeh, A.A., Hajipour, V., and Mahmoudi, A.
Pricing and location decisions in multi-objective facility
location problem with M/M/m/k queuing systems",
Engineering Optimization, 49(1), pp. 136-160
29. Zhang, W., Cao, K., Liu, S., and Huang, B. A multiobjective
optimization approach for health-care facility
location-allocation problems in highly developed cities
such as Hong Kong", Computers, Environment and
Urban Systems, 59, pp. 220-230 (2016).
30. Hajipour, V., Fattahi, P., Tavana, M., and Di,
Caprio, D. Multi-objective multi-layer congested facility
location-allocation problem optimization with
Pareto-based meta-heuristics", Applied Mathematical
Modelling, 40(7), pp. 4948-4969 (2016).
31. Karasakal, E. and Ahmet, S. A multi-objective genetic
algorithm for a bi-objective facility location
problem with partial coverage", Top, 24(1), pp. 206-
232 (2016).
32. Sheppard, E.S. A conceptual framework for dynamic
location-allocation analysis", Environment and Planning
A, 6, pp. 547-564 (1974).
33. Tsiakis, P., Shah, N., and Pantelides, C.C. Design
of multi-echelon supply chain networks under demand
uncertainty", Industrial & Engineering Chemistry Research,
40, pp. 3585-3604 (2001).
34. Shishebori, D. and Jabalameli, M.S. Improving the
eciency of medical services systems: a new integrated
mathematical modeling approach", Mathematical
Problems in Engineering, pp. 1-13 (2013).
35. Shishebori, D., Jabalameli, M.S., and Jabbarzadeh, A.
Facility location-network design problem: Reliability
and investment budget constraint", Journal of Urban
Planning and Development, 140(3), pp. 4001-4005
36. Shishebori, D., Snyder, L.V., and Jabalameli, M.S.
A Reliable budget-constrained FL/ND problem with
unreliable facilities", Networks and Spatial Economics,
14(3-4), pp. 549-580 (2014).
37. Shishebori, D. and Youse -Babadi, A. Robust and reliable
medical services network design underuncertain
environment and system disruptions", Transportation
Research, Part E., 77, pp. 268-288 (2015).
38. Lu, M., Ran, L., and Shen, Z.J.M. Reliable facility location
design under uncertain correlated disruptions",
Manufacturing & Service Operations Management,
17(4), pp. 445-455 (2015).
39. Huang, X. and Di, H. Modelling uncapacitated
facility location problem with uncertain customers'
positions", Journal of Intelligent & Fuzzy Systems,
28(6), pp. 2569-2577 (2015).
40. Jalali, S., Seifbarghy, M., Sadeghi, J., and Ahmadi,
S. Optimizing a bi-objective reliable facility
location problem with adapted stochastic measures
using tuned-parameter multi-objective algorithms",
Knowledge-Based Systems, 95, pp. 45-57 (2016).
41. Keyvanshokooh, E., Sarah M.R., and Kabir, E. Hybrid
robust and stochastic optimization for closed-loop
supply chain network design using accelerated Benders
decomposition", European Journal of Operational Research,
249(1), pp. 76-92 (2016).
42. Zadeh, L.A. Fuzzy sets", Information and Control, 8,
pp. 338-353 (1965).
43. Zimmermann, H.J. Description and optimization of
fuzzy systems", International Journal of General Systems,
2, pp. 209-215 (1976).
44. Zimmermann, H.J. Fuzzy programming and linear
programming with several objective functions", Fuzzy
Sets and Systems, 1, pp. 45-56 (1978).
45. Hannan, E.L. On fuzzy goal programming", Decision
Sciences, 12, pp. 522-531 (1981-b).
46. Yager, R.R. Multiple objective decision-making using
fuzzy sets", International Journal of Man-Machine
Studies, 9, pp. 375-382 (1977).
47. Pickens, J.B. and Hof, J.G. Fuzzy goal programming
in forestry: an application with special solution problems",
Fuzzy Sets and Systems, 39(3), pp. 239-246
48. Shankar, R. and Vrat, P. Some design issues in
cellular manufacturing using fuzzy programming approach",
International Journal of Production Research,
37(11), pp. 2345-2363 (1999).
49. Zangi abadi, M. and Maleki, H.R. Fuzzy goal programming
technique to solve multiobjective transportation
problems with some non-linear membership
functions", Iranian Journal of Fuzzy Systems, 10(1),
pp. 61-74 (2013).
50. Kanani Nezhad, A.A., Roghanian, E., and Azadi, Z.
A fuzzy goal programming approach to solve multiobjective
supply chain network design problems", International
Journal of Industrial Engineering Computations,
4, pp. 315-324 (2013).
51. C ebi, F. and Otay, _I. Multi-criteria and multi-stage
facility location selection under interval type-2 fuzzy
environment: a case study for a cement factory",
International Journal of Computational Intelligence
Systems, 8(2), pp. 330-344 (2015).
52. Yang, T., Ignizio, J.P., and Kim, H.J. Fuzzy programming
with nonlinear membership functions: piecewise
linear approximation", Fuzzy Sets and Systems, 11,
pp. 39-53 (1991).
53. Rao, S.S., Sundaraju, K., Prakash, B.G., and Balakrishna,
C. Fuzzy goal programming approach for
structural optimization", AIAA Journal, 30(5), pp.
1425-1432 (1992).
54. Sinha, S.B., Rao, K.A., and Mangaraj, B.K. Fuzzy
1766 D. Shishebori et al./Scientia Iranica, Transactions E: Industrial Engineering 25 (2018) 1750{1767
goal programming in multi-criteria decision systems:
a case study inagricultural planning", Socio-Economic
Planning Sciences, 22(2), pp. 93-101 (1988).
55. Mulvey, J.M., Vanderbei, R.J., and Zenios, S.A. Robust
optimization of large-scale systems", Operations
Research, 43, pp. 264-281 (1995).
56. Ben-Tal, A. and Nemirovski, A. Robust convex optimization",
Mathematics of Operations Research, 23,
pp. 769-805 (1998).
57. Ben-Tal, A. and Nemirovski, A. Robust solutions
of uncertain linear programs", Operations Research
Letters, 25, pp. 1-13 (1999).
58. Ben-Tal, A. and Nemirovski, A. Robust solutions
of linear programming problems contaminated with
uncertain data", Mathematical Programming, 88, pp.
411-424 (2000).
59. Bertsimas, D. and Sim, M. Robust discrete optimization
and network
ows", Mathematical Programming,
98, pp. 49-71 (2003).
60. Bertsimas, D. and Sim, M. The price of robustness",
Operations Research, 52, pp. 35-53 (2004).
61. Yu, C.S. and Li, H.L. A robust optimization model
for stochastic logistic problems", International Journal
of Production Economics, 64, pp. 385-397 (2000).
62. Leung, S.C.H., Tsang, S.O.S., Ng, W.L., and Wu, Y.
A robust optimization model for multi-site production
planning problem in an uncertain environment",
European Journal of Operational Research, 181, pp.
224-238 (2007).
63. Bozorgi-Amiri, A., Jabalameli, M., and Mirzapour
Al-e-Hashem, S. A multi-objective robust stochastic
programming model for disaster relief logistics under
uncertainty", OR Spectrum, 35(4), pp. 905-933 (2013).
64. Zhou, Z., Cheng, S., and Hua, B. Supply chain
optimization of continuous process industries with sustainability
considerations", Computer and Chemical
Engineering, 24, pp. 1151-1158 (2000).
65. Chen, C.L., Wang, B.W., and Lee, W.C. Multiobjective
optimization for a multi-enterprise supply
chain network", Industrial and Engineering Chemistry
Research, 42, pp. 1879-1889 (2003).
66. Chen, C.L., Lee, W., and Wen, C. Multi-objective
optimization of multi-echelon supply chain networks,
with uncertain product demands and prices", Computers
and Chemical Engineering, 28, pp. 1131-1144
67. Shankar, B.L., Basavarajappa, S., Chen, J.C., and
Kadadevaramath, R.S. Location and allocation decisions
for multi-echelon supply chain network-A multiobjective
evolutionary approach", Expert Systems with
Applications, 40(2), pp. 551-562 (2013).
68. Narsimhan, R. Goal programming in a fuzzy environment",
Decision Sciences, 11, pp. 325-336 (1980).
69. Hannan, E.L. Linear programming with multiple
goals", Fuzzy Sets and Systems, 6, pp. 235-248 (1981a).
70. Mohamed, R.H. The relationship between goal programming
and fuzzy programming", Fuzzy Sets and
Systems, 89, pp. 215-222 (1997).
71. Li, X. and Yeh, A.G.O. Integration of genetic algorithms
and GIS for optimal location search", International
Journal of Geographical Information Science,
19(5), pp. 581-601 (2005).
72. Held, M. and Karp, R.M. The traveling salesman
problem and minimum spanning trees: Part II",
Mathematical Programming, 1, pp. 6-25 (1971).
73. Holmberg, K., Ronnqvist, M., and Yuan, D. An exact
algorithm for the capacitated facility location problems
with single sourcing", European Journal of Operational
Research, 113, pp. 544-559 (1999).
74. Fisher, M.L. The Lagrangian relaxation method for
solving integer programming problems", Management
Science, 27(1), pp. 1-18 (1981).
75. Fisher, M.L. applications oriented guide to Lagrangian
relaxation", Interfaces, 15(2), pp. 10-21
76. Fisher, M.L. The Lagrangian relaxation method for
solving integer programming problems", Management
Science, 50(12), pp. 1861-1871 (2004).
77. Barcelo, J. and Casanovas, J. A heuristic Lagrangean
algorithm for the capacitated plant location problem",
European Journal of Operational Research, 15, pp.
212-226 (1984).
78. Beasley, J.E. Lagrangean heuristics for location problems",
European Journal of Operational Research, 65,
pp. 383-399 (1993).
79. Agar, M.C. and Salhi, S. Lagrangean heuristics applied
to a variety of large capacitated plant location
problems", Journal of the Operational Research Society,
49(1), pp. 1072-1084 (1998).
80. Cortinhal, M.J. and Captivo, M.E. Upper and lower
bounds for the single source capacitated location problem",
European Journal of Operational Research, 151,
pp. 333-351 (2003).
81. Chen, C.H. and Ting, C.J. Combining Lagrangian
heuristic and antcolony system to solve the single
source capacitated facility location problem", Transportation
Research, Part E: Logistics and Transportation
Review, 44(6), pp. 1099-1122 (2008).
82. Jena, S.D., Cordeau, J.F., and Gendron, B. Solving a
dynamic facility location problem with partial closing
and reopening", Computers & Operations Research,
67, pp. 143-154 (2016).
83. Ronnqvist, M., Tragantalerngsak, S., and Holt, J. A
repeated matching heuristic for the single-source capacitated
facility location problem", European Journal
of Operational Research, 116, pp. 51-68 (1999).
84. Wu, T., Chu, F., Yang, Z., and Zhou, Z. A Lagrangean
relaxation approach for a two-stage capacitated
facility location problem with choice of facility
D. Shishebori et al./Scientia Iranica, Transactions E: Industrial Engineering 25 (2018) 1750{1767 1767
size", IEEE International Conference on Systems,
Man, and Cybernetics, pp. 713-718 (2015).
85. Tragantalerngsak, S., Holt, J., and Ronnqvist, M.
Lagrangian heuristics for the two echelon, singlesource,
capacitated facility location problem", European
Journal of Operational Research, 102, pp. 611-
625 (1997).
86. Tragantalerngsak, S., Holt, J., and Ronnqvist, M. An
exact method for the two echelon, single source, capacitated
facility location problem", European Journal of
Operational Research, 123, pp. 473-489 (2000).
87. Mohammad Nezhad, A., Manzour, H., and Salhi,
H. Lagrangian relaxation heuristics for the uncapacitated
single-source multi-product facility location
problem", International Journal of Production Economics,
145, pp. 713-723 (2013).
88. Mazzola, J.B. and Neebe, A.W. Lagrangean relaxation
based solution procedures for a multi product
capacitated facility location problem with choice of
facility type", European Journal of Operational Research,
115, pp. 285-299 (1999).
89. Lin, C.K.Y. Stochastic single source capacitated facility
location model with service level requirements",
International Journal of Production Economics, 117,
pp. 439-451 (2009).
90. Jayaraman, V. and Pirkul, H. Planning and coordination
of production and distribution facilities for multiple
commodities", European Journal of Operational
Research, 133(2), pp. 394-408 (2001).