Evolutionary techniques for permutation based problems

Abstract

During the last several decades, the research field of combinatorial optimization has newlineattracted many researchers across various scientific fields owing to their practical newlineimportance in day to day life. The advancement of technology and accelerated newlinecomputer evolution makes large-scale computation practical. Consequently, many newlineindustries have started employing the state-of-the-art techniques available in the literature newlineof combinatorial optimization for efficiently solving their problems. These newlineproblems include allocation of resources and more effective planning, scheduling, newlinemanufacturing, transportation and distribution. Permutation based combinatorial newlineoptimization problems are a specific category of combinatorial optimization problems, newlinewhere the problem possess permutation characteristic. Many real world newlineproblems like routing, scheduling, networking, timetabling have permutation aspect. newlineSince many practical applications can be modeled as a permutation based newlineproblem, these problems have huge practical importance. Apart from practical newlineapplications, these problems pose a serious challenge from theoretical perspective newlinealso. Any improvement that can be made while addressing a permutation based newlineproblem will provide a scope for improvement for several other related permutation newlinebased problems. Motivated by these facts, in this thesis, we have focused on solving newlinesome recent NP-hard permutation based combinatorial optimization problems newlineusing three evolutionary techniques, viz. genetic algorithm (GA), evolution strategy newline(ES) and discrete differential evolution (DDE). newlineSix NP-hard permutation based problems have been addressed in this thesis. newlineThese six problems are as follows: cover scheduling problem in wireless sensor newlinenetworks, total rotation minimization problem in directional sensor networks, newlinesingle machine total stepwise tardiness problem with release dates, rescue unit newlineallocation and scheduling problem, quality of service vehicle routing problem newlinewith time windows and multiobjective vehicle routing problem with time windo