doi: 10.3934/jimo.2019128

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

* Corresponding author: V. Azhmyakov

Received  December 2018 Revised  May 2019 Published  October 2019

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.

Citation: Vadim Azhmyakov, Juan P. Fernández-Gutiérrez, Erik I. Verriest, Stefan W. Pickl. A separation based optimization approach to Dynamic Maximal Covering Location Problems with switched structure. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2019128
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.  Google Scholar

[2]

V. Azhmyakov, A Relaxation Based Approach to Optimal Control of Hybrid and Switched Systems, Elsevier, Oxford, 2019.  Google Scholar

[3]

V. AzhmyakovM. 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.  Google Scholar

[4]

V. AzhmyakovM. 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.  Google Scholar

[5]

V. AzhmyakovJ. 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.  Google Scholar

[6]

V. AzhmyakovJ. P. Fernández-GutiérrezS. 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.  Google Scholar

[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.  Google Scholar

[8]

V. BatanovicD. 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.  Google Scholar

[9]

O. BermanJ. KalcsicsD. 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.  Google Scholar

[10]

D. Bertsekas, Nonlinear Programming, Athena Scientific Optimization and Computation Series, Athena Scientific, Belmont, 1995. doi: 10.1057/palgrave.jors.2600425.  Google Scholar

[11]

M. BoccadoroY. WardiM. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[15]

P. Dell OlmoN. 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.  Google Scholar

[16]

L. DupontM. 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.  Google Scholar

[17]

M. H. Fazel ZarandiS. 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.  Google Scholar

[18]

R. D. GalvaoL. 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.  Google Scholar

[19]

M. GendreauG. 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.  Google Scholar

[20]

J. GuY. ZhouA. DasI. 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.  Google Scholar

[21]

J. Jahn, Vector Optimization, Springer, Berlin, 2004. doi: 10.1007/978-3-540-24828-6.  Google Scholar

[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.  Google Scholar

[23]

H. Kellerer, U. Pferschy and D. Pisinger, Knapsack Problem, Springer, Berlin, 2004. doi: 10.1007/978-3-540-24777-7.  Google Scholar

[24]

A. MitsosB. Chachuat and P. I. Barton, McCormick-based relaxation algorithm, SIAM J. Optim., 20 (2009), 573-601.  doi: 10.1137/080717341.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[27]

E. Polak, Optimization, Applied Mathematical Sciences, 124, Springer-Verlag, New York, 1997. doi: 10.1007/978-1-4612-0663-7.  Google Scholar

[28]

C. ReVelleM. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[32]

E. TalbiM. BasseurA. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[36]

F. ZarandiA. 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.  Google Scholar

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.  Google Scholar

[2]

V. Azhmyakov, A Relaxation Based Approach to Optimal Control of Hybrid and Switched Systems, Elsevier, Oxford, 2019.  Google Scholar

[3]

V. AzhmyakovM. 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.  Google Scholar

[4]

V. AzhmyakovM. 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.  Google Scholar

[5]

V. AzhmyakovJ. 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.  Google Scholar

[6]

V. AzhmyakovJ. P. Fernández-GutiérrezS. 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.  Google Scholar

[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.  Google Scholar

[8]

V. BatanovicD. 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.  Google Scholar

[9]

O. BermanJ. KalcsicsD. 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.  Google Scholar

[10]

D. Bertsekas, Nonlinear Programming, Athena Scientific Optimization and Computation Series, Athena Scientific, Belmont, 1995. doi: 10.1057/palgrave.jors.2600425.  Google Scholar

[11]

M. BoccadoroY. WardiM. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[15]

P. Dell OlmoN. 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.  Google Scholar

[16]

L. DupontM. 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.  Google Scholar

[17]

M. H. Fazel ZarandiS. 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.  Google Scholar

[18]

R. D. GalvaoL. 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.  Google Scholar

[19]

M. GendreauG. 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.  Google Scholar

[20]

J. GuY. ZhouA. DasI. 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.  Google Scholar

[21]

J. Jahn, Vector Optimization, Springer, Berlin, 2004. doi: 10.1007/978-3-540-24828-6.  Google Scholar

[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.  Google Scholar

[23]

H. Kellerer, U. Pferschy and D. Pisinger, Knapsack Problem, Springer, Berlin, 2004. doi: 10.1007/978-3-540-24777-7.  Google Scholar

[24]

A. MitsosB. Chachuat and P. I. Barton, McCormick-based relaxation algorithm, SIAM J. Optim., 20 (2009), 573-601.  doi: 10.1137/080717341.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[27]

E. Polak, Optimization, Applied Mathematical Sciences, 124, Springer-Verlag, New York, 1997. doi: 10.1007/978-1-4612-0663-7.  Google Scholar

[28]

C. ReVelleM. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[32]

E. TalbiM. BasseurA. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[36]

F. ZarandiA. 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.  Google Scholar

Figure 1.  Optimal dynamics of the switched decision variables $ y^{opt}(t) $
[1]

Rein Luus. Optimal control of oscillatory systems by iterative dynamic programming. Journal of Industrial & Management Optimization, 2008, 4 (1) : 1-15. doi: 10.3934/jimo.2008.4.1

[2]

Tengfei Yanu, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial & Management Optimization, 2017, 13 (5) : 0-0. doi: 10.3934/jimo.2019136

[3]

Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353

[4]

Andrzej Nowakowski, Jan Sokolowski. On dual dynamic programming in shape control. Communications on Pure & Applied Analysis, 2012, 11 (6) : 2473-2485. doi: 10.3934/cpaa.2012.11.2473

[5]

Jérôme Renault. General limit value in dynamic programming. Journal of Dynamics & Games, 2014, 1 (3) : 471-484. doi: 10.3934/jdg.2014.1.471

[6]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2017, 13 (5) : 0-0. doi: 10.3934/jimo.2019102

[7]

Haibo Jin, Long Hai, Xiaoliang Tang. An optimal maintenance strategy for multi-state systems based on a system linear integral equation and dynamic programming. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-26. doi: 10.3934/jimo.2018188

[8]

Oliver Junge, Alex Schreiber. Dynamic programming using radial basis functions. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 4439-4453. doi: 10.3934/dcds.2015.35.4439

[9]

Eduardo Espinosa-Avila, Pablo Padilla Longoria, Francisco Hernández-Quiroz. Game theory and dynamic programming in alternate games. Journal of Dynamics & Games, 2017, 4 (3) : 205-216. doi: 10.3934/jdg.2017013

[10]

Qing Liu, Armin Schikorra. General existence of solutions to dynamic programming equations. Communications on Pure & Applied Analysis, 2015, 14 (1) : 167-184. doi: 10.3934/cpaa.2015.14.167

[11]

Tai-Ping Liu, Shih-Hsien Yu. Hyperbolic conservation laws and dynamic systems. Discrete & Continuous Dynamical Systems - A, 2000, 6 (1) : 143-145. doi: 10.3934/dcds.2000.6.143

[12]

Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial & Management Optimization, 2014, 10 (2) : 557-566. doi: 10.3934/jimo.2014.10.557

[13]

Haiying Liu, Wenjie Bi, Kok Lay Teo, Naxing Liu. Dynamic optimal decision making for manufacturers with limited attention based on sparse dynamic programming. Journal of Industrial & Management Optimization, 2019, 15 (2) : 445-464. doi: 10.3934/jimo.2018050

[14]

Ryan Loxton, Qun Lin. Optimal fleet composition via dynamic programming and golden section search. Journal of Industrial & Management Optimization, 2011, 7 (4) : 875-890. doi: 10.3934/jimo.2011.7.875

[15]

Chun-Xiang Guo, Guo Qiang, Jin Mao-Zhu, Zhihan Lv. Dynamic systems based on preference graph and distance. Discrete & Continuous Dynamical Systems - S, 2015, 8 (6) : 1139-1154. doi: 10.3934/dcdss.2015.8.1139

[16]

Alexey G. Mazko. Positivity, robust stability and comparison of dynamic systems. Conference Publications, 2011, 2011 (Special) : 1042-1051. doi: 10.3934/proc.2011.2011.1042

[17]

I-Liang Chern, Chun-Hsiung Hsia. Dynamic phase transition for binary systems in cylindrical geometry. Discrete & Continuous Dynamical Systems - B, 2011, 16 (1) : 173-188. doi: 10.3934/dcdsb.2011.16.173

[18]

Tian Ma, Shouhong Wang. Dynamic transition and pattern formation for chemotactic systems. Discrete & Continuous Dynamical Systems - B, 2014, 19 (9) : 2809-2835. doi: 10.3934/dcdsb.2014.19.2809

[19]

B. Kaymakcalan, R. Mert, A. Zafer. Asymptotic equivalence of dynamic systems on time scales. Conference Publications, 2007, 2007 (Special) : 558-567. doi: 10.3934/proc.2007.2007.558

[20]

Bruce D. Craven, Sardar M. N. Islam. Dynamic optimization models in finance: Some extensions to the framework, models, and computation. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1129-1146. doi: 10.3934/jimo.2014.10.1129

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (7)
  • HTML views (32)
  • Cited by (0)

[Back to Top]