Intelligent Search Methods For Complicated Combinatorial Optimization Problems

Complicated combinatorial optimization problems widely exist in communication and transportation,network planning,logistics distribution,cloud computing,big data,manufactur-ing and so on.Intelligent search methods for complicated combinatorial optimization problems with multi-constraint and multi-objective are the key of improving enterprise's efficiency,opti-mization of resource cost,improving user experience,energy saving.Two search methods for combinatorial optimization problems are considered:simple construction search and iterated construction search.According to different applications,properties are analyzed,and different search methods are studied.The main work of this paper is as follows:(1)The shortest path problem with position-based learning effects is considered.Because the suboptimal structure is not satisfied for this problem,traditional series of A*algorithm can not be used.A heuristic accurate search method is proposed for the problem.In the process of search,potential optimal subpaths are saved and the search graph is finally constructed.The admissibility is analyzed and proved.Monotonicity and consistency of the heuristic functions of AA*are redefined and the corresponding properties are analyzed.Consisten-cy/monotonicity relationships between the heuristic functions of AA*and those of A:*are explored.Their impacts on efficiency of searching procedures are theoretically analyzed and experimentally evaluated.(2)The bi-objective shortest path problem is considered.It maybe cost very long time,espe-cially for large size problems.At the same time,the number of nondominated solutions increases quickly.An incremental User-Driven Biobjective A*algorithm(UDBA*)is pro-posed for user-driven biobjective shortest path problems.It makes use of the previous results to avoid repeated search.Some uniformly distributed nondominated solution paths which can image the Pareto front in general can be got in a short time to satisfy user's decision requirement.The admissibility of the proposed algorithm is analyzed and proved.The influence of consistency/monotonicity on the search efficiency is explored.Experimental results show that the proposed algorithm is effective and efficient.(3)The mixed no-wait flowshop problem with both wait and no-wait constraints are wide spread in real-life applications.The problem can be regarded as a generalization of the tradition-al permutation flowshop and the no-wait flowshop.This scheduling setting with makespan minimization is studied for the first time.A mathematical model is proposed firstly and then a speed-up makespan calculation procedure is designed.By introducing a varying num-ber of destructed jobs,a modified iterated greedy algorithm is proposed for the considered problem.To further improve the intensification and efficiency of the proposal,insertion is performed on some neighbor jobs of the best position in a sequence during the initializa-tion,solution construction and reconstruction phases.For improving the diversification of search,the number of jobs in destruction phase is self adaptive changed,and the idea of simulated algorithm is adopted.New neighborhood structures are used in VND(Variable Neighborhood Decent)to improve the intensification of search.After calibrating parameters and components,the proposal is compared with five existing algorithms for similar prob-lems on adapted Taillard benchmark instances.Experimental results show that the proposal always obtains the best performance among the compared methods.