Optimizing Patrolling Operations with Multiple Traveling Salesmen Problem: A Formulation and Simulation Approach

Abstract

Integer optimization program is a useful tool for solving realistic problems especially in assigning tasks problems. Traveling salesman (TSP) problem is one of the most classic subjects under integer program. This paper mainly focuses on the multiple traveling salesmen (MTSP) problem, which introduces two ways of formulations for the MTSP problem. The first program is formulated by tracking the traveling direction for each ‘salesperson’ when they are visiting different locations. On the contrary, the second program does not track the moving direction for salesmen and instead, which only tracks which edge between two locations is assigned to a certain salesperson. The two formulations do share some similarities and have some differences. This study briefly compares the complexity of the two models by counting the number of constraints for two formulations as well. In addition to a simulation test based on the two formulated optimization program, the limitations regarding the two formulations are discussed. According to the analysis, TSP is a classic problem under optimization, hence MTSP is meaningful for companies especially in assigning multiple tasks to workers or machines.