Font Size: a A A

A Colored Traveling Salesman Problem And Its Dynamics Problem

Posted on:2018-01-28Degree:DoctorType:Dissertation
Country:ChinaCandidate:X H MengFull Text:PDF
GTID:1368330545964249Subject:Control theory and control engineering
Abstract/Summary:PDF Full Text Request
Based on the scheduling problem of multi-bridge waterjet cutting system,a general Colored Traveling Salesman Problem(CTSP)is proposed.It is a generalization of the existing Traveling Salesman Problem(TSP)and Mutiple Traveling Salesman Problem(MTSP)and innovatively introduces the colors to describe the accessibility difference of cities to all salesmen.It can be widely applied to the description and modeling of the optimal static scheduling problem which owns the multi tasks with different accessibilities in the real world,such as multi-machine scheduling problem.To generalize and systematize CTSP,this dissertation proposes a serial CTSP(S-CTSP),a general-CTSP(G-CTSP),two kinds of dynamic CTSPs,and their solution methods,derived from the prior radial CTSP(R-CTSP).The main research contents and work are as follows:1)This work clarifies the differences and relations among R-CTSP,MTSP and TSP.First,R-CTSP is proved to be the generalization of MTSP and TSP,in theory.Second,from the aspects of models and solution spaces,we confrim that R-CTSP is not the combination of MTSP and TSP,but their generalizations.In addition,with the help of an industrial examples and extensive simulation experiments,R-CTSP is comfirmed to be superior to the combinatorial problem of MTSP and TSP in solving.2)Based on R-CTSP,an S-CTSP is proposed in this work.Each of its salesmen has some exclusive cities and shares some cities with its neighbor(s)in a serial manner.It can be used to model the scheduling problem of multimachine engineering systems whose machines are arranged serially with partially overlapped workspaces.Accordingly,a population-based incremental learning(PBIL)approach is presented to solve it.Extensive simulation is conducted and the results show that the proposed PBIL is effective and well outperforms three prior genetic algorithms(GA)presented by us,i.e.,GA with greedy initialization,hill-climbing GA,and simulated annealing GA,in terms of solution quality,time consumption,and convergence rate.3)A general CTSP(G-CTSP)is proposed,where a city color matrix is introduced to describe the accessibility difference of cities to the salesmen.It can be applied to a large class of scheduling problems in which individual tasks have different and diversitified accessibilities.A metaheuristic called variable neighborhood search(VNS)is proposed to address G-CTSP.It exploits an efficient direct-route coding that does not yield duplicated solutions.Then,a two-stage greedy algorithm and a 2-opt method are adopted to achieve powerful local search ability.The results of extensive simulation show that VNS is effective for CTSP and it outperforms greedy initialized GA,hill-climbing GA,simulated annealing GA,and PBIL,with respect to solution quality,time consumption,and convergence rate.4)Based on the general CTSP,two kinds of dynamic CTSP(DCTSP)are proposed,namely,CTSP with varying edge weights(CTSP-VEW)and CTSP with varying city colors(CTSP-VCC).They can be applied to dynamic routing problems of logistics distribution system with various accessibilities of goods to different types of vehicles and supply decision problem of the multi-warehouses online retailers with the varying supply,respectively.A VNS algorithm is proposed to address CTSP-VEW and CTSP-VCC.It adopts multi-population strategy and population immigration strategy to enhance its population diversity and promote convergence speed of the algorithm in the dynamic environments,respectively.Two dynamic environment simulators are designed for simulating the environment changes of the two DCTSPs,and several evaluation criteria of algorithm performance are designed,including off-line performance,dynamic performance curve and standard deviation of solutions.The results of extensive simulation show that the greedy-initialization VNS with the best population immigrant scheme is the best approach for CTSP-VEW and CTSP-VCC,among VNS,greedy-initialization VNS,and VNS with the best population immigrant scheme,in terms of the proposed evaluation criteria.
Keywords/Search Tags:Colored Traveling Salesman Problem, dynamic optimization, path optimization, evolutionary algorithm, metaheuristic
PDF Full Text Request
Related items