A multiobjective evolutionary algorithm for the task based sailor assignment problem

ABSTRACT

This paper investigates a multiobjective formulation of the United States Navy's Task based Sailor Assignment Problem and examines the performance of a multiobjective evolutionary algorithm (MOEA), called NSGA-II, on large instances of this problem. Our previous work [3, 5, 4], consider the sailor assignment problem (SAP) as a static assignment, while the present work assumes it as a time dependent multitask SAP, making it a more complex problem, in fact, an NP-complete problem. Experimental results show that the presented genetic-based solution is appropriate for this problem.

REFERENCES

• 1: A.D. Doty, Iowa State University. http://www.public.iastate.edu/ddoty/HungarianAlgorithm.html.
• 2: K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2):182--197, 2002.
• 3: Dipankar Dasgupta , German Hernandez , Deon Garrett , Pavan Kalyan Vejandla , Aishwarya Kaushal , Ramjee Yerneni , James Simien, A comparison of multiobjective evolutionary algorithms with informed initialization and kuhn-munkres algorithm for the sailor assignment problem, Proceedings of the 2008 GECCO conference companion on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1388969.1389035]
• 4: Deon Garrett , Joseph Vannucci , Rodrigo Silva , Dipankar Dasgupta , James Simien, Genetic algorithms for the sailor assignment problem, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068333]
• 5: J.D. Garrett, J. Vannucci, R. Silva, D. Dasgupta, and J. Simien. Applying hybrid multiobjective evolutionary algorithms to the sailor assignment problem. In L. Jain, V. Palade, and D. Srinivasan, editors, Advances in Evolutionary Computing for System Design. Springer Verlag, 2007.
• 6: H.W. Kuhn. The hungarian method for the assignment problem. Naval Research Logistic Quarterly, 2:83--97, 1955.
• 7: L. McCauley and S. Franklin. A large multi-agent system for navy personnel distribution. Connection Science, 14(4):371--385, December 2002.
• 8: J. Munkres. Algorithms for the assignment and transportation problems. Journal of the Society of Industrial and Applied Mathematics, 5(1):32--38, March 1957.
• 9: Networking and S. Emerging Optimization (NEO), University of Malaga. JMetal: Metaheuristic algorithms java library. http://mallba10.lcc.uma.es/wiki/index.php/JMetal. Version 1.5, april 2008.
• 10: E. Zitzler, M. Laumanns, and L. Thiele. SPEA2: Improving the strength pareto evolutionary algorithm. Technical Report 103, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH), Gloriastrasse 35, CH-8092 Zurich, Switzerland, May 2001.
• 11: Reuven Cohen , Liran Katzir , Danny Raz, An efficient approximation for the generalized assignment problem, Information Processing Letters, v.100 n.4, p.162-166, 30 November 2006 [doi>10.1016/j.ipl.2006.06.003]
• 12: David B. Shmoys , Éva Tardos, An approximation algorithm for the generalized assignment problem, Mathematical Programming: Series A and B, v.62 n.3, p.461-474, Dec. 8, 1993 [doi>10.1007/BF01585178]
• 13: K. Deb, L. Thiele, M. Laumanns and E. Ziztler. Scalable Multi-objective optimization test problems. In Proceedings of the Congress on Evolutionary Computation (CEC 2002), 825--830, 2002

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.0 GENERAL

Additional Classification:
  J. Computer Applications
  J.0 GENERAL

General Terms:
Algorithms, Experimentation

Keywords:
hybrid metaheuristics, multiobjective evolutionary algorithms, nsga-ii, sailor assignment problem, task based sailor assignment problem