An Efficient 2-opt Operator for the Robotic Task Sequencing Problem

摘要

Nowadays, automated guided vehicles (AGVs) are widely used in many real life applications, such as in modern factories and logistics systems. Generally, an AGV is assigned a number of random tasks, and different execution orders of the tasks correspond to different moving distances. Therefore, it is important to determine the task execution order. This problem is known as the robotic task sequencing problem, which could be transformed to an equivalent asymmetric travelling salesman problem (ATSP). In the field of TSP, the 2-opt movements is a basic operator which has been widely used by local-search based heuristics. However, for the ATSP, given an incumbent solution with N tasks, the current best method requires a complexity of O(N <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> ) to evaluate all the O(N <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) possible 2-opt based movements, and thus, the computational cost is too expensive, especially for large-scale instances. This paper develops a series of data structures, to reduce the above time complexity from O(N <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> ) to O(N <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ). Experimental results based on 60 task sets indicate that, the proposed method can significantly improve the efficiency of 2-opt based local search.