Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Solving bi-objective uncertain stochastic resource allocation problems by the CVaR-based risk measure and decomposition-based multi-objective evolutionary algorithms

  • S.I.: MOPGP 2017
  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

This paper investigates the uncertain stochastic resource allocation problem in which the results of a given allocation of resources are described as probabilities and these probabilities are considered to be uncertain from practical aspects. Here uncertainties are introduced by assuming that these probabilities depend on random parameters which are impacted by various factors. The redundancy allocation problem (RAP) and the multi-stage weapon-target assignment (MWTA) problem are special cases of stochastic resource allocation problems. Bi-objective models for the uncertain RAP and MWTA problem in which the conditional value-at-risk measure is used to control the risk brought by uncertainties are presented in this paper. The bi-objective formulation covers the objectives of minimizing the risk of failure of completing activities and the resulting cost of resources. With the aim of determining referenced Pareto fronts, a linearized formulation and an approximated linear formulation are put forward for RAPs and MWTA problems based on problem-specific characteristics, respectively. Two state-of-the-art decomposition-based multi-objective evolutionary algorithms (i.e., MOEA/D-AWA and DMOEA-\(\varepsilon \hbox {C}\)) are used to solve the formulated bi-objective problem. In view of differences between MOEA/D-AWA and DMOEA-\(\varepsilon \hbox {C}\), two matching schemes inspired by DMOEA-\(\varepsilon \hbox {C}\) are proposed and embedded in MOEA/D-AWA. Numerical experiments have been performed on a set of uncertain RAP and MWTA instances. Experimental results demonstrate that DMOEA-\(\varepsilon \hbox {C}\) outperforms MOEA/D-AWA on the majority of test instances and the superiority of DMOEA-\(\varepsilon \hbox {C}\) can be ascribed to the \(\varepsilon \)-constraint framework.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Notes

  1. Since the single objective RAP and MWTA problem are both NP-hard (Chern 1992; Lloyd and Witsenhausen 1986), their multi-objective formulations can only be harder to solve. This implies that bi-objective RAPs and MWTA problems are also NP-hard.

  2. For uncertain multi-objective optimization problem, multiple repeated function evaluations of a solution usually get different function values under different uncertain scenarios. Thus, it is difficult to definitely determine the quality of two solutions, which affects the ability of algorithms to find the optimum.

  3. \(pro{b_{ij}}({{\varvec{\xi }}})\) equals to \({r_{ij}}({{\varvec{\xi }}})\) and \({p_{ij}}(s,{{\varvec{\xi }}})\) for RAPs and MWTA problems, respectively.

References

  • Ahuja, R. K., Kumar, A., Jha, K. C., & Orlin, J. B. (2007). Exact and heuristic algorithms for the weapon-target assignment problem. Operations Research, 55(6), 1136–1146.

    Google Scholar 

  • Blodgett, D. E., Gendreau, M., & Potvin, J. Y. (2003). A Tabu search heuristic for resource management in naval warfare. Journal of Heuristics, 9(2), 145–169.

    Google Scholar 

  • Braford, J. C.: Determination of optimal assignment of a weapon system to several targets,. Tech. rep., Vought Aeronautics, Dallas, Texas (1961, AEREITM-9).

  • Buche, D., Stoll, P., Dornberger, R., & Koumoutsakos, P. (2002). Multiobjective evolutionary algorithm for the optimization of noisy combustion processes. IEEE Transactions on Systems Man and Cybernetics: Part C, 32(4), 460–473.

    Google Scholar 

  • Cai, H. P. (2010). Study on firepower optimal distribution of artillery group based on NSGA-II. Ph.D. thesis, Changsha, Hunan, P. R. China: National University of Defense Technology.

  • Cai, H., Liu, J., Chen, Y., & Wang, H. (2006). Survey of the research on dynamic weapon-target assignment problem. Journal of Systems Engineering and Electronics, 17(3), 559–565.

    Google Scholar 

  • Caserta, M., & Voß, S. (2016). A corridor method based hybrid algorithm for redundancy allocation. Journal of Heuristics, 22(4), 405–429.

    Google Scholar 

  • Chen, J., Li, J., & Xin, B. (2017). DMOEA-$\varepsilon {\rm C}$: Decomposition-based multi-objetive evolutionary algorithm with the $\varepsilon $-constraint framework. IEEE Transactions on Evolutionary Computation, 21(5), 714–730.

    Google Scholar 

  • Chen, T. C., & You, P. S. (2005). Immune algorithms-based approach for redundant reliability problems with multiple component choices. Computers in Industry, 56, 195–205.

    Google Scholar 

  • Chern, M. (1992). On the computational complexity of reliability redundancy allocation in a series system. Operations Research Letters, 11(5), 309–315.

    Google Scholar 

  • Chu, H. Y., Xu, P. P., & Yang, C. C. (2016). Joint relay selection and power control for robust cooperative multicast in mmWave WPANs. Science China-Information Sciences, 59(8), 082301.

    Google Scholar 

  • Day, R. H. (1966). Allocating weapons to target complexes by means of nonlinear programming. Operations Research, 14(6), 992–1013.

    Google Scholar 

  • Deb, K. (2000). An efficient constraint handling method for genetic algorithms. Computer Methods in Applied Mechanics and Engineering, 186(2–4), 311–338.

    Google Scholar 

  • Dehghan Hardoroudi, N., Keshvari, A., Kallio, M., & Korhonen, P. (2017). Solving cardinality constrained mean-variance portfolio problems via milp. Annals of Operations Research, 254(1), 47–59.

    Google Scholar 

  • denBroeder, G. G, Jr., Ellison, R. E., & Emerling, L. (1959). On optimum target assignments. Operations Research, 7(3), 322–326.

    Google Scholar 

  • Gomes de Mattos, R., Oliveira, F., Leiras, A., Baptista de Paula Filho, A., & Gonçalves, P. (2018). Robust optimization of the insecticide-treated bed nets procurement and distribution planning under uncertainty for malaria prevention and control. Annals of Operations Research.

  • Hosein, P. A., Walton, J. T., & Athans, M. (1988). Dynamic weapon-target assignment problems with vulnerable C2 nodes. Massachusetts Inst of Tech Cambridge Lab for Information and Decision Systems: Tech. rep.

  • Huang, C. L. (2015). A particle-based simplified swarm optimization algorithm for reliability redundancy allocation problems. Reliability Engineering and System Safety, 142, 221–230.

    Google Scholar 

  • Hughes, E. J. (2001). Evolutionary multi-objective ranking with uncertainty and noise. In Proceedings of IEEE international conference on evolutionary multi-criterion optimization (pp. 329–343).

  • Jiang, S. W., Cai, Z. H., Zhang, J., & Ong, Y. S. (2011). Multiobjective optimization by decomposition with Pareto-adaptive weight vectors Pareto-adaptive weight vectors. In Proceedings of IEEE international conference on natural computation (pp. 1260–1264).

  • Johnson, B. L., Porter, A. T., King, J. C., & Newman, A. M. (2018). Optimally configuring a measurement system to detect diversions from a nuclear fuel cycle. Annals of Operations Research, 275, 393–420.

    Google Scholar 

  • Khalili-Damghani, K., & Amiri, M. (2012). Solving binary-state multi-objective reliability redundancy allocation series-parallel problem using efficient epsilon-constraint, multi-start partial bound enumeratio nalgorithm, and DEA. Reliability Engineering and System Safety, 103(4), 35–44.

    Google Scholar 

  • Kline, A., Ahner, D., & Hill, R. (2019). The weapon-target assignment problem. Computers and Operations Research, 105, 226–236.

    Google Scholar 

  • Krokhmal, P., Murphey, R., Pardalos, P., & Uryasev, S. (2004). Use of conditional value-at-risk in stochastic programs with poorly defined distributions (pp. 225–241). Boston: Springer.

    Google Scholar 

  • Leboucher, C., Shin, H. S., Siarry, P., Chelouah, R., Menec, S. L., & Tsourdos, A. (2013). A two-step optimisation method for dynamic weapon target assignment problem. IntechOpen: Tech. rep.

  • Lee, M. Z. (2010). Constrained weapon-target assignment: Enhanced very large scale neighborhood search algorithm. IEEE Transactions on Systems Man and Cybernetics Part A, 40(1), 198–204.

    Google Scholar 

  • Lee, C. Y., Gen, M., & Kuo, W. (2002). Reliability optimization design using hybridized genetic algorithm with a neural network technique. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 84, E627-A–637.

    Google Scholar 

  • Li, J., Chen, J., Xin, B., & Dou, L. H. (2015). Solving multi-objective multi-stage weapon target assignment problem via Adaptive NSGA-II and Adaptive MOEA/D: A comparison study. In Proceedings of IEEE congress on evolutionary computation (pp 3132–3139).

  • Li, J., Chen, J., Xin, B., Dou, L. H., & Peng, Z. H. (2016). Solving the uncertain multi-objective multi-stage weapon target assignment problem via MOEA/D-AWA. In Proceedings of IEEE congress on evolutionary computation (pp 4934–4941).

  • Li, M. H., Huang, G. M., & Zhou, D. (2016). A yield-enhanced global optimization methodology for analog circuit based on extreme value theory. Science China-Information Sciences, 59(8), 082401.

    Google Scholar 

  • Li, X., Qin, Z., & Kar, S. (2010). Mean-variance-skewness model for portfolio selection with fuzzy returns. European Journal of Operational Research, 202(1), 239–247.

    Google Scholar 

  • Li, Z. J., Liao, H. T., & Coit, D. W. (2009). A two-stage approach for multi-objective decision making with applications to system reliability optimization. Reliability Engineering and System Safety, 94(10), 1585–1592.

    Google Scholar 

  • Liefooghe, A., Basseur, M., Jourdan, L., & Talbi, E. G. (2007). Combinatorial optimization of stochastic multi-objective problems: An application to the flow-shop scheduling problem. In Proceedings of IEEE international conference on evolutionary multi-criterion optimization (pp 457–471).

  • Liu, B. D. (2009). Theory and practice of uncertain programming. Berlin: Springer.

    Google Scholar 

  • Lloyd, S. P., & Witsenhausen, H. S. (1986). Weapons allocation is NP-complete. In Proceedings of IEEE summer conference on simulation (pp. 1054–1058).

  • Manne, A. S. (1958). A target-assignment problem. Operations Research, 6(3), 346–351.

    Google Scholar 

  • Ma, X. L., Qi, Y. T., Li, L. L., Liu, F., Jiao, L. C., & Wu, J. S. (2014). MOEA/D with uniform decomposition measurement for many-objective problems. Soft Computing, 18(12), 1–24.

    Google Scholar 

  • Miettinen, K. (1999). Nonlinear multiobjective optimization. Boston: Kluwer Academic Publishers.

    Google Scholar 

  • Montgomery, D. C. (2005). Design and analysis of experiments. Arizona: Wiley.

    Google Scholar 

  • Nahas, N., & Nourelfath, M. (2005). Ant system for reliability optimization of a series system with multiple-choice and budget constraints. Reliability Engineering and System Safety, 87, 1–12.

    Google Scholar 

  • Pavlikov, K., & Uryasev, S. (2018). Cvar distance between univariate probability distributions and approximation problems. Annals of Operations Research, 262(1), 67–88.

    Google Scholar 

  • Prasad, V. R., & Kuo, W. (2000). Reliability optimization of coherent systems. IEEE Transactions on Reliability, 49, 323–330.

    Google Scholar 

  • Qi, Y. T., Ma, X. L., Liu, F., Jiao, L. C., Sun, J. Y., & Wu, J. S. (2014). MOEA/D with adaptive weight adjustment. Evolutionary Computation, 22(2), 231–264.

    Google Scholar 

  • Roy, R. K. (2010). A Primer on the Taguchi method. Dearborn: Society of Manufacturing Engineers.

    Google Scholar 

  • Sulieman, D., Jourdan, L., & Talbi, E. (2010). Using multiobjective metaheuristics to solve VRP with uncertain demands. In Proceedings of IEEE international conference on evolutionary computation (pp. 1–8).

  • Sung, C. S., & Cho, Y. K. (2000). Reliability optimization of a series system with multiple-choice and budget constraints. European Journal of Operational Research, 127, 158–171.

    Google Scholar 

  • Taboada, H. A., Baheranwala, F., Coit, D. W., & Wattanapongsakorn, N. (2007). Practical solutions for multi-objective optimization: An application to system reliability design problems. Reliability Engineering and System Safety, 92(3), 314–332.

    Google Scholar 

  • Teich, J. (2001). Pareto-front exploration with uncertain objectives. In Proceedings of IEEE international conference on evolutionary multi-criterion optimization (pp. 314–328).

  • Tillman, F. A., Hwuang, C. L., & Kuo, W. (1980). Optimization of system reliability. New York: Marcel Dekker.

    Google Scholar 

  • Wang, Z. T., Guo, J. S., Zheng, M. F., & Yang, Y. S. (2014). A new approach for uncertain multiobjective programming problem based on ${P_E}$ principle. Journal of Industrial and Management Optimization, 11(1), 13–26.

    Google Scholar 

  • Wu, L., Wang, H. Y., Lu, F. X., & Jia, P. F. (2008). An anytime algorithm based on modified GA for dynamic weapon-target allocation problem. In Proceedings of IEEE congress on computational intelligence (pp. 2020–2025).

  • Xin, B., Chen, J., Peng, Z. H., Dou, L. H., & Zhang, J. (2011). An efficient rule-based constructive heuristic to solve dynamic weapon-target assignment problem. IEEE Transactions on Systems Man and Cybernetics: Part A Systems and Humans, 41(3), 598–606.

    Google Scholar 

  • Xin, B., Chen, J., Zhang, J., Dou, L. H., & Peng, Z. H. (2010). Efficient decision makings for dynamic weapon-target assignment by virtual permutation and tabu search heuristics. IEEE Transactions on Systems Man and Cybernetics: Part C, 40(6), 649–662.

    Google Scholar 

  • Xu, L., Yang, Y. W., & Li, Y. P. (2014). Resource allocation of limited feedback in clustered wireless mesh networks. Wireless Personal Communications, 75(2), 901–913.

    Google Scholar 

  • Zhang, Q., & Li, H. (2007). MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation, 11(6), 712–731.

    Google Scholar 

  • Zhou, A., Zhang, Q., Jin, Y., Tsang, E., & Okabe, T. (2005). A model-based evolutionary algorithm for bi-objective optimization. In Proceedings of the IEEE congress on evolutionary computation (pp. 2568–2575).

  • Zhu, X., & Kuo, W. (2014). Importance measures in reliability and mathematical programming. Annals of Operations Research, 212(1), 241–267.

    Google Scholar 

  • Zitzler, E., & Thiele, L. (1999). Multiobjective evolutionary algorithm: A comparative case study and strength pareto approach. IEEE Transactions on Evolutionary Computation, 3(4), 257–271.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Mechatronical Engineering, Beijing Institute of Technology, Beijing, 100081, People’s Republic of China

    Juan Li

  2. School of Automation, Beijing Institute of Technology, Beijing, 100081, People’s Republic of China

    Bin Xin & Jie Chen

  3. State Key Laboratory of Intelligent Control and Decision of Complex Systems, Beijing Institute of Technology, Beijing, 100081, People’s Republic of China

    Bin Xin & Jie Chen

  4. Beijing Advanced Innovation Center for Intelligent Robots and Systems, Beijing Institute of Technology, Beijing, 100081, People’s Republic of China

    Bin Xin & Jie Chen

  5. Department of Industrial and Systems Engineering, University of Florida, Gainesville, USA

    Panos M. Pardalos

Authors
  1. Juan Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bin Xin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Panos M. Pardalos
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Jie Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Bin Xin.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This work was supported in part by the National Natural Science Foundation of China under Grant 61822304 and 61673058, the NSFC-Zhejiang Joint Fund for the Integration of Industrialization and Informatization under Grant U1609214, the Foundation for Innovative Research Groups of the National Natural Science Foundation of China under Grant 61621063, the Projects of Major International (Regional) Joint Research Program NSFC under Grant 61720106011, the China Scholarship Council, and the Peng Cheng Laboratory.

Panos M. Pardalos is supported by the Paul and Heidi Brown Preeminent Professorship in Industrial and Systems Engineering, University of Florida (USA) and a Humboldt Research Award (Germany).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Li, J., Xin, B., Pardalos, P.M. et al. Solving bi-objective uncertain stochastic resource allocation problems by the CVaR-based risk measure and decomposition-based multi-objective evolutionary algorithms. Ann Oper Res 296, 639–666 (2021). https://doi.org/10.1007/s10479-019-03435-4

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-019-03435-4

Keywords

Search

Navigation