Solving And Application Of The MTSP Based On The Self-Organizing Algorithm

The Self-Organizing Algorithm (SOA) is a new heuristic optimization algorithm based on extremal dynamics, and it is an improvement of Extremal Optimization (EO). SOA has the dynamic character to be far from equilibrium state, and it always updates the species with the worst fitness and the interrelated species in the current state space. SOA not only succeed to EO's advantage, such as rapid in convergence, strong in local search ability, simple in design, easy of accomplishment, but it also has the ability to operate the neighbour solutions and select the new solution following the power-law distribution. So SOA is more effective in deeper and wider search, and it is a more effective dynamic optimization process. SOA has been used to solve the combinatorial optimization problem such as the traveling salesman problem and the hot strip milling scheduling problem.In this thesis, we apply the SOA to solve the combinatorial optimization problem with stronger constraints. We transform the constraints into the objective function by means of model transformation and fitness definition.The main topics studied in this thesis are as follows:Studies on the constrained multiple traveling salesman problem based on Self-Organizing Algorithm. In this paper the MTSP is transformed into a TSP by introduction of virtual cities. The traditional MTSP is solved using SOA directly. The MTSP with the constraint of upper bound of the cities to be visited for each salesman and the MTSP with the constraint of minimize the longest route are studied and the self-organizing algorithm (SOA) is introduced to solve the problem by different definition of the virtual cities' local fitness. The transformation and the definition of the local fitness can deal with the relevant constraints effectively. The computational simulation results with a number of benchmark problems show that SOA can be effectively applied in solving the proposed MTSP with superior performance. Further more the vehicle routing problem, a prevalent application example of the MTSP model, is also solved using SOA. The computational results show that SOA can be effectively applied in solving the vehicle routing problem with the constraints that every vehicle's capacity is limited.Hot strip milling multi-round scheduling based on Self-Organizing Algorithm. Rolling sequencing in the hot strip mill (HSM) scheduling is a typical combinatorial optimization problem with multiple, complex constraints. The task of HSM campaign building is to build up the solutions for multi-round scheduling simultaneously according to the working orders and the process constraints. In this paper, the problem is formulated in terms of a multiple traveling salesman (MTSP) model. Then the self-organizing algorithm (SOA) is introduced to solve the problem and the local fitness of virtual coil is defined to deal with the complex constraints. The parallel algorithm proposed in the thesis can build up multi-round simultaneously and guarantee every rolling round distribution's homogeneity in the same rolling shift. The production size data based simulation results show that SOA can be effectively applied in solving the HSM campaign scheduling problem.