
-
Previous Article
Note on $ Z $-eigenvalue inclusion theorems for tensors
- JIMO Home
- This Issue
-
Next Article
Supplier's investment in manufacturer's quality improvement with equity holding
A separation based optimization approach to Dynamic Maximal Covering Location Problems with switched structure
1. | Department of Mathematical Sciences, Universidad EAFIT, Medellín, Colombia |
2. | Department of Basic Science, Universidad de Medellín, Medellín, Colombia |
3. | School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, USA |
4. | Department of Computer Science, Universität der Bundeswehr München, München, Germany |
This paper extends a newly developed computational optimization approach to a specific class of Maximal Covering Location Problems (MCLPs) with a switched dynamic structure. Most of the results obtained for the conventional MCLP address the "static" case where an optimal decision is determined on a fixed time-period. In our contribution we consider a dynamic MCLP based optimal decision making and propose an effective computational method for the numerical treatment of the switched-type Dynamic Maximal Covering Location Problem (DMCLP). A generic geometrical structure of the constraints under consideration makes it possible to separate the originally given dynamic optimization problem and reduce it to a specific family of relative simple auxiliary problems. The generalized Separation Method (SM) for the DMCLP with a switched structure finally leads to a computational solution scheme. The resulting numerical algorithm also includes the classic Lagrange relaxation. We present a rigorous formal analysis of the DMCLP optimization methodology and also discuss computational aspects. The proposed SM based algorithm is finally applied to a practically oriented example, namely, to an optimal design of a (dynamic) mobile network configuration.
References:
[1] |
K. Atkinson and W. Han, Theoretical Numerical Analysis, Texts in Applied Mathematics, 39, Springer, New York, 2005.
doi: 10.1007/978-0-387-28769-0. |
[2] |
V. Azhmyakov, A Relaxation Based Approach to Optimal Control of Hybrid and Switched Systems, Elsevier, Oxford, 2019. |
[3] |
V. Azhmyakov, M. Basin and C. Reincke-Collon,
Optimal LQ-type switched control design for a class of linear systems with piecewise constant inputs, IFAC Proceedings Volumes, 47 (2014), 6976-6981.
doi: 10.3182/20140824-6-ZA-1003.00515. |
[4] |
V. Azhmyakov, M. V. Basin and J. Raisch,
A proximal point based approach to optimal control of affine switched systems, Discrete Event Dyn. Syst., 22 (2012), 61-81.
doi: 10.1007/s10626-011-0109-8. |
[5] |
V. Azhmyakov, J. Cabrera and A. Poznyak,
Optimal fixed-levels control for non-linear systems with quadratic cost functionals, Optimal Control Appl. Methods, 37 (2016), 1035-1055.
doi: 10.1002/oca.2223. |
[6] |
V. Azhmyakov, J. P. Fernández-Gutiérrez, S. K. Gadi and St. Pickl,
A novel numerical approach to the MCLP based resilent supply chain optimization, IFAC - PapersOnLine, 49 (2016), 137-142.
doi: 10.1016/j.ifacol.2016.12.175. |
[7] |
V. Azhmyakov and W. Schmidt,
Approximations of relaxed optimal control problems, J. Optim. Theory Appl., 130 (2006), 61-77.
doi: 10.1007/s10957-006-9085-9. |
[8] |
V. Batanovic, D. Petrovic and R. Petrovic,
Fuzzy logic based algorithms for maximum covering location problems, Information Sci., 179 (2009), 120-129.
doi: 10.1016/j.ins.2008.08.019. |
[9] |
O. Berman, J. Kalcsics, D. Krass and S. Nickel,
The ordered gradual covering location problem on a network, Discrete Appl. Math., 157 (2009), 3689-3707.
doi: 10.1016/j.dam.2009.08.003. |
[10] |
D. Bertsekas, Nonlinear Programming, Athena Scientific Optimization and Computation Series, Athena Scientific, Belmont, 1995.
doi: 10.1057/palgrave.jors.2600425. |
[11] |
M. Boccadoro, Y. Wardi, M. Egerstedt and E. I. Verriest,
Optimal control of switching surfaces in hybrid dynamical systems, Discrete Event Dyn. Syst., 15 (2005), 433-448.
doi: 10.1007/s10626-005-4060-4. |
[12] |
M. S. Canbolat and M. von Massow,
Planar maximal covering with ellipses, Comp. Ind. Engineering, 57 (2009), 201-208.
doi: 10.1016/j.cie.2008.11.015. |
[13] |
R. L. Church and C. S ReVelle,
The maximal covering location problem, Papers of the Regional Science Association, 32 (1974), 101-118.
doi: 10.1111/j.1435-5597.1974.tb00902.x. |
[14] |
C. A. C. Coello, G. B. Lamont and D. A. Van Veldhuizen, Evolutionary Algorithms for Solving Multi-Objective Problems, Genetic Algorithms and Evolutionary Computation, 5, Kluwer Academic, New York, 2002.
doi: 10.1007/978-1-4757-5184-0. |
[15] |
P. Dell Olmo, N. Ricciardi and A. Sgalambro,
A multiperiod maximal covering location model for the optimal location of intersection safety cameras on an urban traffic network, Procedia - Social and Behavioral Sci., 108 (2014), 106-117.
doi: 10.1016/j.sbspro.2013.12.824. |
[16] |
L. Dupont, M. Lauras and C. Yugma,
Generalized covering location problem with multiple-coverage: Exact and heuristic method, IFAC Proceedings Volumes, 46 (2013), 442-447.
doi: 10.3182/20130619-3-RU-3018.00144. |
[17] |
M. H. Fazel Zarandi, S. Davari and S. A. Haddad Sisakht,
The large-scale dynamic maximal covering location problem, Math. Comput. Modelling, 57 (2013), 710-719.
doi: 10.1016/j.mcm.2012.07.028. |
[18] |
R. D. Galvao, L. G. Acosta Espejo and B. Boffey,
A comparison of Lagrangian and surrogate relaxations for the maximal covering location problem, European J. Oper. Res., 124 (2000), 377-389.
doi: 10.1016/S0377-2217(99)00171-X. |
[19] |
M. Gendreau, G. Laporte and F. Semet,
A dynamic model and parallel tabu search heuristic for real-time ambulance relocation, Parallel Comput., 27 (2001), 1641-1653.
doi: 10.1016/S0167-8191(01)00103-X. |
[20] |
J. Gu, Y. Zhou, A. Das, I. Moon and G. M. Lee,
Medical relief shelter location problem with patient severity under a limited relief budget, Comput. Ind. Engineering, 125 (2018), 720-728.
doi: 10.1016/j.cie.2018.03.027. |
[21] |
J. Jahn, Vector Optimization, Springer, Berlin, 2004.
doi: 10.1007/978-3-540-24828-6. |
[22] |
G. Ji and S. Han, A strategy analysis in dual-channel supply chain based on effort levels, Proceedings of the 1th International Conference on Service Systems and Service Management, Beijing, China, 2014.
doi: 10.1109/ICSSSM.2014.6943407. |
[23] |
H. Kellerer, U. Pferschy and D. Pisinger, Knapsack Problem, Springer, Berlin, 2004.
doi: 10.1007/978-3-540-24777-7. |
[24] |
A. Mitsos, B. Chachuat and P. I. Barton,
McCormick-based relaxation algorithm, SIAM J. Optim., 20 (2009), 573-601.
doi: 10.1137/080717341. |
[25] |
G. C. Moore and C. S. ReVelle,
The hierarchical service location problem, Management Sci., 28 (1982), 775-780.
doi: 10.1287/mnsc.28.7.775. |
[26] |
A. Ozkis and A. Babalik,
A novel metaheuristic for multi-objective optimization problems: the multi-objective vortex search algorithm, Information Sci., 402 (2017), 124-148.
doi: 10.1016/j.ins.2017.03.026. |
[27] |
E. Polak, Optimization, Applied Mathematical Sciences, 124, Springer-Verlag, New York, 1997.
doi: 10.1007/978-1-4612-0663-7. |
[28] |
C. ReVelle, M. Scholssberg and J. Williams,
Solving the maximal covering location problem with heuristic concentration, Comput. Oper. Res., 35 (2008), 427-435.
doi: 10.1016/j.cor.2006.03.007. |
[29] |
T. Roubicek, Relaxation in Optimization Theory and Variational Calculus, De Gruyter Series in Nonlinear Analysis and Applications, 4, Walter de Gruyter & Co., Berlin, 1997.
doi: 10.1515/9783110811919. |
[30] |
H. Shavandi and H. Mahlooji,
A fuzzy queuing location model with a genetic algorithm for congested systems, Appl. Math. Comput., 181 (2006), 440-456.
doi: 10.1016/j.amc.2005.12.058. |
[31] |
P. Sitek and J. Wikarek, A hybrid approach to modeling and optimization for supply chain management with multimodal transport, Proceedings of the 18th International Conference on Methods and Models in Automation and Robotics, Miedzyzdroje, Poland, 2013.
doi: 10.1109/MMAR.2013.6670011. |
[32] |
E. Talbi, M. Basseur, A. J. Nebro and E. Alba,
Multi-objective optimization using metaheuristics: Non-standard algorithms, Int. Trans. Oper. Res., 19 (2012), 283-305.
doi: 10.1111/j.1475-3995.2011.00808.x. |
[33] |
E. I. Verriest,
Pseudo-continuous multi-dimensional multi-mode systems, Discrete Event Dyn. Syst., 22 (2012), 27-59.
doi: 10.1007/s10626-011-0113-z. |
[34] |
E. I. Verriest and V. Azhmyakov, Advances in optimal control of differential systems with state suprema, Proceedings of the 56th Conference on Decision and Control, Melbourne, Australia, 2017.
doi: 10.1109/CDC.2017.8263748. |
[35] |
Y. Wardi,
Switched-mode systems: Gradient-descent algorithms with Armijo step sizes, Discrete Event Dyn. Syst., 25 (2015), 571-599.
doi: 10.1007/s10626-014-0198-2. |
[36] |
F. Zarandi, A. Haddad Sisakht and S. Davari,
Design of a closed-loop supply chain (CLSC) model using an interactive fuzzy goal programming, Internat. J. Adv. Manufac. Tech., 56 (2011), 809-821.
doi: 10.1007/s00170-011-3212-y. |
show all references
References:
[1] |
K. Atkinson and W. Han, Theoretical Numerical Analysis, Texts in Applied Mathematics, 39, Springer, New York, 2005.
doi: 10.1007/978-0-387-28769-0. |
[2] |
V. Azhmyakov, A Relaxation Based Approach to Optimal Control of Hybrid and Switched Systems, Elsevier, Oxford, 2019. |
[3] |
V. Azhmyakov, M. Basin and C. Reincke-Collon,
Optimal LQ-type switched control design for a class of linear systems with piecewise constant inputs, IFAC Proceedings Volumes, 47 (2014), 6976-6981.
doi: 10.3182/20140824-6-ZA-1003.00515. |
[4] |
V. Azhmyakov, M. V. Basin and J. Raisch,
A proximal point based approach to optimal control of affine switched systems, Discrete Event Dyn. Syst., 22 (2012), 61-81.
doi: 10.1007/s10626-011-0109-8. |
[5] |
V. Azhmyakov, J. Cabrera and A. Poznyak,
Optimal fixed-levels control for non-linear systems with quadratic cost functionals, Optimal Control Appl. Methods, 37 (2016), 1035-1055.
doi: 10.1002/oca.2223. |
[6] |
V. Azhmyakov, J. P. Fernández-Gutiérrez, S. K. Gadi and St. Pickl,
A novel numerical approach to the MCLP based resilent supply chain optimization, IFAC - PapersOnLine, 49 (2016), 137-142.
doi: 10.1016/j.ifacol.2016.12.175. |
[7] |
V. Azhmyakov and W. Schmidt,
Approximations of relaxed optimal control problems, J. Optim. Theory Appl., 130 (2006), 61-77.
doi: 10.1007/s10957-006-9085-9. |
[8] |
V. Batanovic, D. Petrovic and R. Petrovic,
Fuzzy logic based algorithms for maximum covering location problems, Information Sci., 179 (2009), 120-129.
doi: 10.1016/j.ins.2008.08.019. |
[9] |
O. Berman, J. Kalcsics, D. Krass and S. Nickel,
The ordered gradual covering location problem on a network, Discrete Appl. Math., 157 (2009), 3689-3707.
doi: 10.1016/j.dam.2009.08.003. |
[10] |
D. Bertsekas, Nonlinear Programming, Athena Scientific Optimization and Computation Series, Athena Scientific, Belmont, 1995.
doi: 10.1057/palgrave.jors.2600425. |
[11] |
M. Boccadoro, Y. Wardi, M. Egerstedt and E. I. Verriest,
Optimal control of switching surfaces in hybrid dynamical systems, Discrete Event Dyn. Syst., 15 (2005), 433-448.
doi: 10.1007/s10626-005-4060-4. |
[12] |
M. S. Canbolat and M. von Massow,
Planar maximal covering with ellipses, Comp. Ind. Engineering, 57 (2009), 201-208.
doi: 10.1016/j.cie.2008.11.015. |
[13] |
R. L. Church and C. S ReVelle,
The maximal covering location problem, Papers of the Regional Science Association, 32 (1974), 101-118.
doi: 10.1111/j.1435-5597.1974.tb00902.x. |
[14] |
C. A. C. Coello, G. B. Lamont and D. A. Van Veldhuizen, Evolutionary Algorithms for Solving Multi-Objective Problems, Genetic Algorithms and Evolutionary Computation, 5, Kluwer Academic, New York, 2002.
doi: 10.1007/978-1-4757-5184-0. |
[15] |
P. Dell Olmo, N. Ricciardi and A. Sgalambro,
A multiperiod maximal covering location model for the optimal location of intersection safety cameras on an urban traffic network, Procedia - Social and Behavioral Sci., 108 (2014), 106-117.
doi: 10.1016/j.sbspro.2013.12.824. |
[16] |
L. Dupont, M. Lauras and C. Yugma,
Generalized covering location problem with multiple-coverage: Exact and heuristic method, IFAC Proceedings Volumes, 46 (2013), 442-447.
doi: 10.3182/20130619-3-RU-3018.00144. |
[17] |
M. H. Fazel Zarandi, S. Davari and S. A. Haddad Sisakht,
The large-scale dynamic maximal covering location problem, Math. Comput. Modelling, 57 (2013), 710-719.
doi: 10.1016/j.mcm.2012.07.028. |
[18] |
R. D. Galvao, L. G. Acosta Espejo and B. Boffey,
A comparison of Lagrangian and surrogate relaxations for the maximal covering location problem, European J. Oper. Res., 124 (2000), 377-389.
doi: 10.1016/S0377-2217(99)00171-X. |
[19] |
M. Gendreau, G. Laporte and F. Semet,
A dynamic model and parallel tabu search heuristic for real-time ambulance relocation, Parallel Comput., 27 (2001), 1641-1653.
doi: 10.1016/S0167-8191(01)00103-X. |
[20] |
J. Gu, Y. Zhou, A. Das, I. Moon and G. M. Lee,
Medical relief shelter location problem with patient severity under a limited relief budget, Comput. Ind. Engineering, 125 (2018), 720-728.
doi: 10.1016/j.cie.2018.03.027. |
[21] |
J. Jahn, Vector Optimization, Springer, Berlin, 2004.
doi: 10.1007/978-3-540-24828-6. |
[22] |
G. Ji and S. Han, A strategy analysis in dual-channel supply chain based on effort levels, Proceedings of the 1th International Conference on Service Systems and Service Management, Beijing, China, 2014.
doi: 10.1109/ICSSSM.2014.6943407. |
[23] |
H. Kellerer, U. Pferschy and D. Pisinger, Knapsack Problem, Springer, Berlin, 2004.
doi: 10.1007/978-3-540-24777-7. |
[24] |
A. Mitsos, B. Chachuat and P. I. Barton,
McCormick-based relaxation algorithm, SIAM J. Optim., 20 (2009), 573-601.
doi: 10.1137/080717341. |
[25] |
G. C. Moore and C. S. ReVelle,
The hierarchical service location problem, Management Sci., 28 (1982), 775-780.
doi: 10.1287/mnsc.28.7.775. |
[26] |
A. Ozkis and A. Babalik,
A novel metaheuristic for multi-objective optimization problems: the multi-objective vortex search algorithm, Information Sci., 402 (2017), 124-148.
doi: 10.1016/j.ins.2017.03.026. |
[27] |
E. Polak, Optimization, Applied Mathematical Sciences, 124, Springer-Verlag, New York, 1997.
doi: 10.1007/978-1-4612-0663-7. |
[28] |
C. ReVelle, M. Scholssberg and J. Williams,
Solving the maximal covering location problem with heuristic concentration, Comput. Oper. Res., 35 (2008), 427-435.
doi: 10.1016/j.cor.2006.03.007. |
[29] |
T. Roubicek, Relaxation in Optimization Theory and Variational Calculus, De Gruyter Series in Nonlinear Analysis and Applications, 4, Walter de Gruyter & Co., Berlin, 1997.
doi: 10.1515/9783110811919. |
[30] |
H. Shavandi and H. Mahlooji,
A fuzzy queuing location model with a genetic algorithm for congested systems, Appl. Math. Comput., 181 (2006), 440-456.
doi: 10.1016/j.amc.2005.12.058. |
[31] |
P. Sitek and J. Wikarek, A hybrid approach to modeling and optimization for supply chain management with multimodal transport, Proceedings of the 18th International Conference on Methods and Models in Automation and Robotics, Miedzyzdroje, Poland, 2013.
doi: 10.1109/MMAR.2013.6670011. |
[32] |
E. Talbi, M. Basseur, A. J. Nebro and E. Alba,
Multi-objective optimization using metaheuristics: Non-standard algorithms, Int. Trans. Oper. Res., 19 (2012), 283-305.
doi: 10.1111/j.1475-3995.2011.00808.x. |
[33] |
E. I. Verriest,
Pseudo-continuous multi-dimensional multi-mode systems, Discrete Event Dyn. Syst., 22 (2012), 27-59.
doi: 10.1007/s10626-011-0113-z. |
[34] |
E. I. Verriest and V. Azhmyakov, Advances in optimal control of differential systems with state suprema, Proceedings of the 56th Conference on Decision and Control, Melbourne, Australia, 2017.
doi: 10.1109/CDC.2017.8263748. |
[35] |
Y. Wardi,
Switched-mode systems: Gradient-descent algorithms with Armijo step sizes, Discrete Event Dyn. Syst., 25 (2015), 571-599.
doi: 10.1007/s10626-014-0198-2. |
[36] |
F. Zarandi, A. Haddad Sisakht and S. Davari,
Design of a closed-loop supply chain (CLSC) model using an interactive fuzzy goal programming, Internat. J. Adv. Manufac. Tech., 56 (2011), 809-821.
doi: 10.1007/s00170-011-3212-y. |

[1] |
Tengfei Yan, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial & Management Optimization, 2021, 17 (2) : 827-839. doi: 10.3934/jimo.2019136 |
[2] |
Mahdi Karimi, Seyed Jafar Sadjadi. Optimization of a Multi-Item Inventory model for deteriorating items with capacity constraint using dynamic programming. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2021013 |
[3] |
Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102 |
[4] |
Elvio Accinelli, Humberto Muñiz. A dynamic for production economies with multiple equilibria. Journal of Dynamics & Games, 2021 doi: 10.3934/jdg.2021002 |
[5] |
Chao Xing, Zhigang Pan, Quan Wang. Stabilities and dynamic transitions of the Fitzhugh-Nagumo system. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 775-794. doi: 10.3934/dcdsb.2020134 |
[6] |
P. K. Jha, R. Lipton. Finite element approximation of nonlocal dynamic fracture models. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1675-1710. doi: 10.3934/dcdsb.2020178 |
[7] |
Marcos C. Mota, Regilene D. S. Oliveira. Dynamic aspects of Sprott BC chaotic system. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1653-1673. doi: 10.3934/dcdsb.2020177 |
[8] |
Bahaaeldin Abdalla, Thabet Abdeljawad. Oscillation criteria for kernel function dependent fractional dynamic equations. Discrete & Continuous Dynamical Systems - S, 2020 doi: 10.3934/dcdss.2020443 |
[9] |
Kevin Li. Dynamic transitions of the Swift-Hohenberg equation with third-order dispersion. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2021003 |
[10] |
Franck Davhys Reval Langa, Morgan Pierre. A doubly splitting scheme for the Caginalp system with singular potentials and dynamic boundary conditions. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 653-676. doi: 10.3934/dcdss.2020353 |
[11] |
Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2021012 |
[12] |
Haixiang Yao, Ping Chen, Miao Zhang, Xun Li. Dynamic discrete-time portfolio selection for defined contribution pension funds with inflation risk. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020166 |
[13] |
Chao Xing, Jiaojiao Pan, Hong Luo. Stability and dynamic transition of a toxin-producing phytoplankton-zooplankton model with additional food. Communications on Pure & Applied Analysis, 2021, 20 (1) : 427-448. doi: 10.3934/cpaa.2020275 |
[14] |
Musen Xue, Guowei Zhu. Partial myopia vs. forward-looking behaviors in a dynamic pricing and replenishment model for perishable items. Journal of Industrial & Management Optimization, 2021, 17 (2) : 633-648. doi: 10.3934/jimo.2019126 |
[15] |
Fang Li, Bo You. On the dimension of global attractor for the Cahn-Hilliard-Brinkman system with dynamic boundary conditions. Discrete & Continuous Dynamical Systems - B, 2021 doi: 10.3934/dcdsb.2021024 |
[16] |
Bing Yu, Lei Zhang. Global optimization-based dimer method for finding saddle points. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 741-753. doi: 10.3934/dcdsb.2020139 |
[17] |
C. J. Price. A modified Nelder-Mead barrier method for constrained optimization. Numerical Algebra, Control & Optimization, 2020 doi: 10.3934/naco.2020058 |
[18] |
Hui Gao, Jian Lv, Xiaoliang Wang, Liping Pang. An alternating linearization bundle method for a class of nonconvex optimization problem with inexact information. Journal of Industrial & Management Optimization, 2021, 17 (2) : 805-825. doi: 10.3934/jimo.2019135 |
[19] |
Lekbir Afraites, Chorouk Masnaoui, Mourad Nachaoui. Shape optimization method for an inverse geometric source problem and stability at critical shape. Discrete & Continuous Dynamical Systems - S, 2021 doi: 10.3934/dcdss.2021006 |
[20] |
Gervy Marie Angeles, Gilbert Peralta. Energy method for exponential stability of coupled one-dimensional hyperbolic PDE-ODE systems. Evolution Equations & Control Theory, 2020 doi: 10.3934/eect.2020108 |
2019 Impact Factor: 1.366
Tools
Article outline
Figures and Tables
[Back to Top]