Generalised formulations for minimum distance trajectory in patrolling problems

Abstract

In this study, three general formulations are presented for trajectory optimisation in patrolling problems. In the traditional patrolling problem, some basic assumptions are made (often implicitly). For example, it is known how many robots and how many starting depots exist. Furthermore, the starting depots are assumed to be pre‐specified. Each of the three formulations provided here relaxes some (or all) of these assumptions, hence generalising the patrolling problem. A group of robots are supposed to travel through a number of nodes (viewpoints) in such an order so that the total travel distance is minimised. This problem is, in fact, a variant of the Travelling Salesman Problem and is called Multidepot multiple Travelling Salesman Problem. The effectiveness of the approach is demonstrated by comparing the results with those in the literature.