Search
  • All Journals
Advanced Search
Search articles by Title, Author, Keywords, DOI
3.9CiteScore
1.3Impact Factor
Advanced Search
MAP  >  The Knowledge Engineering Review
2019 Volume 34
Article Contents
Next Previous
RESEARCH ARTICLE   Open Access    

A multi-objective evolutionary hyper-heuristic algorithm for team-orienteering problem with time windows regarding rescue applications

  • Tabriz

  • Department of Electrical Engineering

More Information
  • Abstract: The team-orienteering problem (TOP) has broad applicability. Examples of possible uses are in factory and automation settings, robot sports teams, and urban search and rescue applications. We chose the rescue domain as a guiding example throughout this paper. Hence, this paper explores a practical variant of TOP with time window (TOPTW) for rescue applications by humanoid robots called TOPTWR. Due to the significant range of algorithm choices and their parameters tuning challenges, the use of hyper-heuristics is recommended. Hyper-heuristics can select, order, or generate different low-level heuristics with different optimization algorithms. In this paper, first, a general multi-objective (MO) solution is defined, with five objectives for TOPTWR. Then a robust and efficient MO and evolutionary hyper-heuristic algorithm for TOPTW based on the humanoid robot’s characteristics in the rescue applications (MOHH-TOPTWR) is proposed. MOHH-TOPTWR includes two MO evolutionary metaheuristics algorithms (MOEAs) known as non-dominated sorting genetic algorithm (NSGA-III) and MOEA based on decomposition (MOEA/D). In this paper, new benchmark instances are proposed for rescue applications using the existing ones for TOPTW. The experimental results show that MOHH-TOPTWR in both MOEAs can outperform all the state-of-the-art algorithms as well as NSGA-III and MOEA/D MOEAs.
  • 加载中
  • Abbaszadeh , M. & Saeedvand , S.2014. A fast genetic algorithm for solving university scheduling problem. IAES International Journal of Artificial Intelligence3, 7.

    Google Scholar

    Abbaszadeh , M., Saeedvand , S. & Mayani , H. A.2012. Solving university scheduling problem with a memetic algorithm. IAES International Journal of Artificial Intelligence1, 79.

    Google Scholar

    Alkhanak , E. N. & Lee , S. P.2018. A hyper-heuristic cost optimisation approach for scientific workflow scheduling in cloud computing. Future Generation Computer Systems86, 480–506.

    Google Scholar

    Auer , P., Cesa-Bianchi , N. & Fischer , P.2002. Finite-time analysis of the multiarmed bandit problem. Machine Learning47, 235–256.

    Google Scholar

    Baltes , J., Tu , K.-Y., Sadeghnejad , S. & Anderson , J.2017. HuroCup: Competition for multi-event humanoid robot athletes. The Knowledge Engineering Review32, 1–14.

    Google Scholar

    Bederina , H. & Hifi , M.2017. A hybrid multi-objective evolutionary algorithm for the team orienteering problem. In 2017 4th International Conference on Control, Decision and Information Technologies (CoDIT), 0898–0903. IEEE.

    Google Scholar

    Bottarelli , L., Bicego , M., Blum , J. & Farinelli , A.2019. Orienteering-based informative path planning for environmental monitoring. Engineering Applications of Artificial Intelligence77, 46–58.

    Google Scholar

    Burke , E. K., Gendreau , M., Hyde , M., Kendall , G., Ochoa , G., Özcan , E. & Qu , R.2013. Hyper-heuristics: a survey of the state of the art. Journal of the Operational Research Society64, 1695–1724.

    Google Scholar

    Burke , E. K., Hyde , M., Kendall , G., Ochoa , G., Özcan , E. & Woodward , J. R.2010. A classification of hyper-heuristic approaches. In Handbook of Metaheuristics, Gendreau, M. & Potvin, JY. (eds). Springer.

    Google Scholar

    Campbell , A. M., Gendreau , M. & Thomas , B. W.2011. The orienteering problem with stochastic travel and service times. Annals of Operations research186, 61–81.

    Google Scholar

    Chakhlevitch , K. & Cowling , P.2008. Hyperheuristics: Recent developments. In Adaptive and Multilevel Metaheuristics, Cotta , C., Sevaux , M. & Sörensen , K. (eds). Springer.

    Google Scholar

    Chang , C.-H., Wang , S.-C. & Wang , C.-C.2016. Exploiting moving objects: multi-robot simultaneous localization and tracking. IEEE Transactions on Automation Science and Engineering13, 810–827.

    Google Scholar

    Coello , C. A. C., Lamont , G. B. & Van Veldhuizen , D. A. 2007. Evolutionary Algorithms for Solving Multi-Objective Problems. Springer.

    Google Scholar

    Cordeau , J.‐F., Gendreau , M. & Laporte , G.1997. A tabu search heuristic for periodic and multi‐depot vehicle routing problems. Networks: An International Journal30, 105–119.

    Google Scholar

    Cura , T.2014. An artificial bee colony algorithm approach for the team orienteering problem with time windows. Computers & Industrial Engineering74, 270–290.

    Google Scholar

    Deb , K. & Jain , H.2014. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: Solving problems with box constraints.IEEE Transactions on Evolutionary Computation18, 577–601.

    Google Scholar

    Deb , K., Pratap , A., Agarwal , S. & Meyarivan , T. A. M. T.2002. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation6, 182–197.

    Google Scholar

    DeDonato , M., Dimitrov , V., Du , R., Giovacchini , R., Knoedler , K., Long , X., Polido , F., Gennert , M. A., Padır , T. & Feng , S.2015. Human‐in‐the‐loop control of a humanoid robot for disaster response: a report from the DARPA robotics challenge trials. Journal of Field Robotics32, 275–292.

    Google Scholar

    Diftler , M. A., Culbert , C. J., Ambrose , R. O., Platt , R. & Bluethmann , W. J.2003. Evolution of the NASA/DARPA robonaut control system. In ‘2003 Proceedings of IEEE International Conference on Robotics and Automation ICRA’03, 2543–2548. IEEE.

    Google Scholar

    Dong , N. & Dai , C.2018. An improvement decomposition-based multi-objective evolutionary algorithm using multi-search strategy. Knowledge-Based Systems163, 572–580.

    Google Scholar

    Duchoň , F., Babinec , A., Kajan , M., Beňo , P., Florek , M., Fico , T. & Jurišica , L.2014. Path planning with modified a star algorithm for a mobile robot. Procedia Engineering96, 59–69.

    Google Scholar

    Farinelli , A., Zanotto , E. & Pagello , E.2017. Advanced approaches for multi-robot coordination in logistic scenarios. Robotics and Autonomous Systems90, 34–44.

    Google Scholar

    Feng , S., Whitman , E., Xinjilefu , X. & Atkeson , C. G.2015. Optimization‐based full body control for the DARPA robotics challenge. Journal of Field Robotics32, 293–312.

    Google Scholar

    Fialho , Á., Da Costa , L., Schoenauer , M. & Sebag , M. 2010. Analyzing bandit-based adaptive operator selection mechanisms. Annals of Mathematics and Artificial Intelligence60, 25–64.

    Google Scholar

    Goldberg , D. E.1989Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, Reading, Ma, 1989. Addison-Wesley Longman Publishing.

    Google Scholar

    Golden , B. L., Levy , L. & Vohra , R.1987. The orienteering problem. Naval Research Logistics (NRL)34, 307–318.

    Google Scholar

    Guizzo , G., Vergilio , S. R., Pozo , A. T. & Fritsche , G. M.2017. A multi-objective and evolutionary hyper-heuristic applied to the integration and test order problem. Applied Soft Computing56, 331–344.

    Google Scholar

    Gunawan , A., Lau , H. C. & Lu , K.2018. ADOPT: combining parameter tuning and adaptive operator ordering for solving a class of orienteering problems. Computers & Industrial Engineering121, 82–96.

    Google Scholar

    Gunawan , A., Lau , H. C. & Vansteenwegen , P.2016. Orienteering problem: a survey of recent variants, solution approaches and applications. European Journal of Operational Research255, 315–332.

    Google Scholar

    Gunawan , A., Lau , H. C., Vansteenwegen , P. & Lu , K.2017. Well-tuned algorithms for the team orienteering problem with time windows. Journal of the Operational Research Society68, 861–876.

    Google Scholar

    Gunn , T. & Anderson J.2015. Dynamic heterogeneous team formation for robotic urban search and rescue. Journal of Computer and System Sciences81, 553–567.

    Google Scholar

    Hu , Q. & Lim , A.2014. An iterative three-component heuristic for the team orienteering problem with time windows. European Journal of Operational Research232, 276–286.

    Google Scholar

    Huang , L., Ding , Y. & Jin , Y.2018. Multiple-solution optimization strategy for multi-robot task allocation. IEEE Transactions on Systems, Man and Cybernetics: Systems.

    Google Scholar

    Jiang , Y.2016. A survey of task allocation and load balancing in distributed systems. IEEE Transactions on Parallel and Distributed Systems27, 585–599.

    Google Scholar

    Jin , M., Lee , J. & Tsagarakis , N. G.2017. Model-free robust adaptive control of humanoid robots with flexible joints. IEEE Transactions on Industrial Electronics64, 1706–1715.

    Google Scholar

    Jose , K. & Pratihar , D. K.2016. Task allocation and collision-free path planning of centralized multi-robots system for industrial plant inspection using heuristic methods. Robotics and Autonomous Systems80, 34–42.

    Google Scholar

    Kaneko , K., Morisawa , M., Kajita , S., Nakaoka , S. I., Sakaguchi , T., Cisneros , R. & Kanehiro , F.2015. Humanoid robot HRP-2Kai—Improvement of HRP-2 towards disaster response tasks. In ‘2015 IEEE-RAS 15th International Conference on Humanoid Robots (Humanoids), 132–139. IEEE.

    Google Scholar

    Karakatič , S. & Podgorelec , V.2015. A survey of genetic algorithms for solving multi depot vehicle routing problem. Applied Soft Computing27, 519–532.

    Google Scholar

    Khamis , A., Hussein , A. & Elmogy , A.2015. Multi-robot task allocation: a review of the state-of-the-art. In Cooperative Robots and Sensor Networks. Springer.

    Google Scholar

    Kohlbrecher , S., Romay , A., Stumpf , A., Gupta , A., Von Stryk , O., Bacim , F., Bowman , D. A., Goins , A., Balasubramanian , R. & Conner , D. C.2015. Human‐robot teaming for rescue missions: team ViGIR’s approach to the 2013 DARPA robotics challenge trials. Journal of Field Robotics32, 352–377.

    Google Scholar

    Koubaa , A., Bennaceur , H., Chaari , I., Trigui , S., Ammar , A., Sriti , M. F., Alajlan , M., Cheikhrouhou , O. & Javed , Y.2018. Different approaches to solve the MRTA problem. In Robot Path Planning and Cooperation, Kacprzyk, J. (ed.). Springer.

    Google Scholar

    Kube , C. R. & Bonabeau , E.2000. Cooperative transport by ants and robots. Robotics and Autonomous Systems30, 85–101.

    Google Scholar

    Labadie , N., Mansini , R., Melechovský , J. & Calvo , R. W.2012. The team orienteering problem with time windows: an lp-based granular variable neighborhood search. European Journal of Operational Research220, 15–27.

    Google Scholar

    Lin , S.-W. & Vincent F. Y.2012. A simulated annealing heuristic for the team orienteering problem with time windows. European Journal of Operational Research217, 94–107.

    Google Scholar

    Lin , S.-W. & Vincent , F. Y.2017. Solving the team orienteering problem with time windows and mandatory visits by multi-start simulated annealing. Computers & Industrial Engineering114, 195–205.

    Google Scholar

    Mahajan , A. & Teneketzis , D.2008. Multi-armed bandit problems. In Foundations and Applications of Sensor Management, Hero, AO., Castañón, D., Cochran, D. & Kastella, K. (eds). Springer.

    Google Scholar

    Martín-Moreno , R. & Vega-Rodríguez , M. A.2018. Multi-objective artificial bee colony algorithm applied to the bi-objective orienteering problem. Knowledge-Based Systems154, 93–101.

    Google Scholar

    Michalewicz , Z.2013. Genetic Algorithms+ Data Structures= Evolution Programs. Springer Science & Business Media.

    Google Scholar

    Montemanni , R. & Gambardella L. M.2009. An ant colony system for team orienteering problems with time windows. Foundation Of Computing And Decision Sciences34, 287.

    Google Scholar

    Nunes , E., Manner , M., Mitiche , H. & Gini , M.2017. A taxonomy for task allocation problems with temporal and ordering constraints. Robotics and Autonomous Systems90, 55–70.

    Google Scholar

    Park , J., Lee , J., Ahn , S., Bae , J. & Tae , H.2017. Exact algorithm for the capacitated team orienteering problem with time windows. Mathematical Problems in Engineering2017, 1191–1203.

    Google Scholar

    Righini , G. & Salani , M.2009. Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming. Computers & Operations Research36, 1191–1203.

    Google Scholar

    Saeedvand , S. & Aghdasi , H. S.2016. An energy efficient metaheuristic method for micro robots indoor area coverage problem. In ‘2016 6th International Conference on Computer and Knowledge Engineering (ICCKE), 88–93. IEEE.

    Google Scholar

    Saeedvand , S., Aghdasi , H. S. & Baltes , J.2018. Novel lightweight odometric learning method for humanoid robot localization. Mechatronics55, 38–53.

    Google Scholar

    Saeedvand , S., Aghdasi , H. S. & Baltes , J.2019. Robust multi-objective multi-humanoid robots task allocation based on novel hybrid metaheuristic algorithm. Applied Intelligence49, 4097–4127.

    Google Scholar

    Savelsbergh , M. W. P.1985. Local search in routing problems with time windows. Annals of Operations Research4, 285–305.

    Google Scholar

    Schilde , M., Doerner , K. F., Hartl , R. F. & Kiechle , G.2009. Metaheuristics for the bi-objective orienteering problem. Swarm Intelligence3, 179–201.

    Google Scholar

    Schwarzrock , J., Zacarias , I., Bazzan , A. L., de Araujo Fernandes , R. Q., Moreira , L. H. & de Freitas , E. P.2018. Solving task allocation problem in multi unmanned aerial vehicles systems using swarm intelligence. Engineering Applications of Artificial Intelligence72, 10–20.

    Google Scholar

    Solomon , M. M.1986. On the worst‐case performance of some heuristics for the vehicle routing and scheduling problem with time window constraints. Networks16, 161–174.

    Google Scholar

    Solomon , M. M.1987. Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research35, 254–265.

    Google Scholar

    Souffriau , W., Vansteenwegen , P., Vanden Berghe , G. & Van Oudheusden , D.2013. The multiconstraint team orienteering problem with multiple time windows. Transportation Science47, 53–63.

    Google Scholar

    Spenko , M., Buerger , S. & Iagnemma , K.2018. The DARPA Robotics Challenge Finals: Humanoid Robots To The Rescue. Springer.

    Google Scholar

    Su , X., Wang , Y., Jia , X., Guo , L. & Ding , Z.2018. Two innovative coalition formation models for dynamic task allocation in disaster rescues. Journal of Systems Science and Systems Engineering27, 215–230.

    Google Scholar

    Tang , H. & Miller-Hooks , E.2005. A tabu search heuristic for the team orienteering problem. Computers & Operations Research32, 1379–1407.

    Google Scholar

    Toledo , A. & Riff , M. C.2015. HOPHS: a hyperheuristic that solves orienteering problem with hotel selection. In ‘2015 Fifth International Conference on Digital Information Processing and Communications (ICDIPC), 148–152. IEEE.

    Google Scholar

    Tricoire , F., Romauch , M., Doerner , K. F. & Hartl , R. F.2010. Heuristics for the multi-period orienteering problem with multiple time windows. Computers & Operations Research37, 351–367.

    Google Scholar

    Tsiligirides , T.1984. Heuristic methods applied to orienteering. Journal of the Operational Research Society35, 797–809.

    Google Scholar

    Vansteenwegen , P., Souffriau , W., Berghe , G. V. & Van Oudheusden , D.2009. Iterated local search for the team orienteering problem with time windows. Computers & Operations Research36, 3281–3290.

    Google Scholar

    Vansteenwegen , P., Souffriau , W. & Van Oudheusden , D.2011. The orienteering problem: a survey. European Journal of Operational Research209, 1–10.

    Google Scholar

    Vincent , F. Y., Jewpanya , P., Ting , C. J. & Redi , A. P.2017. Two-level particle swarm optimization for the multi-modal team orienteering problem with time windows. Applied Soft Computing61, 1022–1040.

    Google Scholar

    Wang , J., Zhou , Y., Wang , Y., Zhang , J., Chen , C. P. & Zheng , Z.2016. Multiobjective vehicle routing problems with simultaneous delivery and pickup and time windows: formulation, instances, and algorithms. IEEE Transactions on Cybernetics46, 582–594.

    Google Scholar

    Yang , X.-S.2010. Nature-Inspired Metaheuristic Algorithms. Luniver Press.

    Google Scholar

    Yin , P.-Y., Yu , S. S., Wang , P. P. & Wang , Y. T.2007. Multi-objective task allocation in distributed computing systems by hybrid particle swarm optimization. Applied Mathematics and Computation184, 407–420.

    Google Scholar

    Zhang , Q. & Li , H.2007. MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation11, 712–731.

    Google Scholar

    Zhang , Q., Zhou , A. & Jin , Y.2008. RM-MEDA: a regularity model-based multiobjective estimation of distribution algorithm. IEEE Transactions on Evolutionary Computation12, 41–63.

    Google Scholar

    Zhang , T. & Ueno , H.2007. Knowledge model-based heterogeneous multi-robot system implemented by a software platform. Knowledge-Based Systems20, 310–319.

    Google Scholar

    Zheng , W., Liao , Z. & Qin , J.2017. Using a four-step heuristic algorithm to design personalized day tour route within a tourist attraction. Tourism Management62, 335–349.

    Google Scholar

    Zhu , W., Li , L., Teng , L. & Yonglu , W.2018. Multi-UAV reconnaissance task allocation for heterogeneous targets using an opposition-based genetic algorithm with double-chromosome encoding. Chinese Journal of Aeronautics31, 339–350.

    Google Scholar

    Zitzler , E.1999. Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications. Citeseer.

    Google Scholar

    Zitzler , E. & Thiele , L.1999. Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Transactions on Evolutionary Computation3, 257–271.

    Google Scholar

    Zitzler , E., Thiele , L., Laumanns , M., Fonseca , C. M. & Da Fonseca , V. G.2003. Performance assessment of multiobjective optimizers: an analysis and review. IEEE Transactions on Evolutionary Computation7, 117–132.

    Google Scholar

  • Cite this article

    Hadi S. Aghdasi, Saeed Saeedvand, Jacky Baltes. 2019. A multi-objective evolutionary hyper-heuristic algorithm for team-orienteering problem with time windows regarding rescue applications. The Knowledge Engineering Review. 34:134 doi: 10.1017/S0269888919000134
    Hadi S. Aghdasi, Saeed Saeedvand, Jacky Baltes. 2019. A multi-objective evolutionary hyper-heuristic algorithm for team-orienteering problem with time windows regarding rescue applications. The Knowledge Engineering Review. 34:134 doi: 10.1017/S0269888919000134
    shu
Download PDF

Article Metrics

Article views(15) PDF downloads(554)

Other Articles By Authors

RESEARCH ARTICLE   Open Access    

A multi-objective evolutionary hyper-heuristic algorithm for team-orienteering problem with time windows regarding rescue applications

  • Tabriz

  • Department of Electrical Engineering

  • Received: 19 March 2019
  • Revised: 22 July 2019
  • Accepted: 20 September 2019
The Knowledge Engineering Review  34,  Article number: e19  (2019)  |  Cite this article

Abstract: Abstract: The team-orienteering problem (TOP) has broad applicability. Examples of possible uses are in factory and automation settings, robot sports teams, and urban search and rescue applications. We chose the rescue domain as a guiding example throughout this paper. Hence, this paper explores a practical variant of TOP with time window (TOPTW) for rescue applications by humanoid robots called TOPTWR. Due to the significant range of algorithm choices and their parameters tuning challenges, the use of hyper-heuristics is recommended. Hyper-heuristics can select, order, or generate different low-level heuristics with different optimization algorithms. In this paper, first, a general multi-objective (MO) solution is defined, with five objectives for TOPTWR. Then a robust and efficient MO and evolutionary hyper-heuristic algorithm for TOPTW based on the humanoid robot’s characteristics in the rescue applications (MOHH-TOPTWR) is proposed. MOHH-TOPTWR includes two MO evolutionary metaheuristics algorithms (MOEAs) known as non-dominated sorting genetic algorithm (NSGA-III) and MOEA based on decomposition (MOEA/D). In this paper, new benchmark instances are proposed for rescue applications using the existing ones for TOPTW. The experimental results show that MOHH-TOPTWR in both MOEAs can outperform all the state-of-the-art algorithms as well as NSGA-III and MOEA/D MOEAs.

    HTML

    Acknowledgments

    • This work was financially supported by the ‘Chinese Language and Technology Center’ of National Taiwan Normal University (NTNU) from The Featured Areas Research Center Program within the framework of the Higher Education Sprout Project by the Ministry of Education (MOE) in Taiwan, and Ministry of Science and Technology, Taiwan, under Grant Nos. MOST 108-2634-F-003-002, MOST 108-2634-F-003-003, and MOST 108-2634-F-003-004 (administered through Pervasive Artificial Intelligence Research (PAIR) Labs) as well as MOST 107-2811-E-003-503. We are grateful to the National Center for High-performance Computing for computer time and facilities to conduct this research.

    Rights and permissions
    • © Cambridge University Press, 2019 2019Cambridge University Press
References (81)
  • About this article
    Cite this article
    Hadi S. Aghdasi, Saeed Saeedvand, Jacky Baltes. 2019. A multi-objective evolutionary hyper-heuristic algorithm for team-orienteering problem with time windows regarding rescue applications. The Knowledge Engineering Review. 34:134 doi: 10.1017/S0269888919000134
    Hadi S. Aghdasi, Saeed Saeedvand, Jacky Baltes. 2019. A multi-objective evolutionary hyper-heuristic algorithm for team-orienteering problem with time windows regarding rescue applications. The Knowledge Engineering Review. 34:134 doi: 10.1017/S0269888919000134
    shu

    • Catalog

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return