Time-efficient trajectory optimization in patrolling problems with non-prespecified depots and robots

摘要

Two new formulations are presented in this paper for the minimum-time trajectories in the patrolling problem, where a number of robots are desired to patrol a given set of viewpoints in the shortest possible time. In the first problem, it is assumed that the starting depots and their corresponding robots are non-prespecified. In the second problem, it is desired to obtain the minimum-distance trajectories among all the possible minimum-time trajectories that could be the output of the first problem. The problem is considered to be a variant of the well-known Traveling Salesman Problem (TSP), namely, Minimum-Time Multidepot multiple Traveling Salesmen Problem (MTMmTSP). The distinguishing features of the proposed problem statement is that first of all the initial depots and their corresponding assigned number of robots are not prespecified. Secondly, the cost function to be minimized is total travel time of robots as opposed to the travel distance or waiting time of the salesmen at the visited nodes for a given TSP with time windows (TSPTW).