A DMOLKH Algorithm For Dynamic Multi-Object Traveling Salesman Problem

Traveling Salesman Problem, or TSP for short, is a well known hard problem with a longhistory. It's a branch of combinational optimization problems. Dynamic Multi-Object TravelingSalesman Problem, or DMOTSP for short, is a recently proposed problem which is adevelopment of TSP. DMOTSP contains many conflicting optimization targets, and has its citylocations changing while searching the solutions. It belongs to the class of multi-objectoptimization problems and the class of dynamic optimization problems simultaneously. We cansay, more precisely, that DMOTSP is a combination of DTSP and MOTSP.Some researches have been done on DTSP and/or MOTSP respectively. However, seldomresearches on DMOTSP are published till now. As a result, the research on algorithms forDMOTSP appears to be a significant groundbreaking work now.The concept of DMOTSP is explained via DTSP and DMOTSP. This eliminates theabsence of the definition on DMOTSP.DMOLKH algorithm is proposed for DMOTSP. DMOLKH is build based on LKHalgorithm, which is a generally accepted efficient algorithm for TSP. Furthermore, analysis hasbeen done for the concept of the problem, for the feasibility and performance of the algorithm.The following lists the key points of DMOLKH algorithm:●Simplify the creation of candidate set. This strategy reduces time on creating candidateset. Thus, much time on search for solutions is available. Experimental results showthat this strategy improves the efficiency. The larger the problem scale, the greater theefficiency improved.●Create mixed candidate set. Experimental results show that the mixed candidate setcontains great most edges in pareto solutions. Under this strategy, the search space isconstricted while seldom solutions are excluded.●Adjust the mixed candidate set dynamically. The adjusted mixed candidate set containsall edges in pareto solutions.●Use the solution space under last sampled circumstance as the initial solution spaceafter sampling new circumstance. This strategy is made under the observation that thesequential solutions are some kind adjacent in consecutively changing circumstance.●Eliminate the restriction that LKH algorithm does not break the edges which are common in some certain solutions. That restriction is of very little value in solvingDMOTSP while consuming much computational time.·Use non-worse rather than better. Using non-worse restriction all through the searchingprocess gets more pareto solutions.·Propose speeding-up strategy. Many solutions can be found in a short instance underthis strategy.Multiple objective problem instances KroAB10, KroAB20, and KroAB30 are used astesting initial problems. All cities change their locations after every 0.5 seconds. Cities aremoving under the velocity of 50 per second. The directions to move are randomly generated atstarting calculation or when the city reaches the certain board. Take 10 samples from eachproblem and get two ratios as results. Experimental results show that 100％tours in paretosolutions are found for 2-object-and-10-city problems, and about 69.2％tours are found for2-object-and-20-city problems, and 9.1％for 2-object-and-30-city problems.