Car patrolling problem: models and algorithms for a practical application

Abstract

This Ph.D. thesis addresses a Car Patrolling Problem derived from a real-world application faced by a large Italian service provider through the development of optimization algorithms. In summary, the car patrolling problem that we face is a generalization of the well-known team orienteering problem. A set of customers requires a variety of security-related services that they want to be performed in their properties according to a weekly planning. On the basis of the customers’ demands, the company deploys patrols that will perform the requested services. The goal of the research is to optimize and improve the service provision using algorithmic methods, possibly improving both customers satisfaction and reducing company costs. The research was conducted sequentially as requirements appeared during its development, and hence, the overall original problem was divided into three problems. The first problem addresses patrol routing within their original territories, modeled as a deterministic variant of the team orienteering problem, where not all vertices need to be visited, while visiting them may yield profit. It was formalized using integer linear programming, and a metaheuristic algorithm based on Iterated Local Search (ILS) was developed to effectively solve the company’s real-world instances. Next, we addressed territory division, extending the previous problem by proposing new customer partitions to improve patrol routing. We explored methods based on clustering algorithms and Mixed Integer Linear Programming (MILP) models to generate alternative territory divisions. For each clustering solution, routing was performed using variants of the MILP model and clustering algorithms with the ILS from the first problem. Computational results showed that adjusting territory configurations can enhance customer satisfaction and reduce costs. The third problem introduces stochastic elements in the form of alarm triggers within the patrolling operation. By employing a two-phase stochastic modeling approach, scenarios are generated based on an extensive historical alarm database to design resilient routes. The problem is addressed using both MILP and a heuristic method, delivering a comprehensive solution that enhances decision-making efficiency for managers. Overall, this thesis has positively addressed a very general real-world problem with numerous practical challenges, providing efficient optimization algorithms and leading to improved problem solutions. Keywords: car patrolling problem; team orienteering problem; iterated local search; mixed-integer linear programming; scenario-based stochastic optimizationEsta tese de doutorado aborda um Problema de Patrulhamento com Viaturas (Car Patrolling Problem) derivado de uma aplicação real enfrentada por um grande prestador de serviços italiano, por meio do desenvolvimento de algoritmos de otimização. Em síntese, o problema de patrulhamento com viaturas considerado é uma generalização do conhecido Problema de Orienteering em Equipe (Team Orienteering Problem). Um conjunto de clientes requer uma variedade de serviços relacionados à segurança, que desejam que sejam executados em suas propriedades de acordo com um planejamento semanal. Com base nas demandas dos clientes, a empresa aloca patrulhas que realizarão os serviços solicitados. O objetivo desta pesquisa é otimizar e aprimorar a prestação do serviço por meio de métodos algorítmicos, buscando, simultaneamente, aumentar a satisfação dos clientes e reduzir os custos da empresa. A pesquisa foi conduzida de forma sequencial, conforme novos requisitos surgiam ao longo do desenvolvimento e, portanto, o problema original geral foi dividido em três problemas. O primeiro problema trata do roteamento das patrulhas dentro de seus territórios originais, modelado como uma variante determinística do problema de orienteering em equipe, na qual nem todos os vértices precisam ser visitados, embora sua visita possa gerar lucro. Ele foi formalizado por meio de Programação Linear Inteira (Integer Linear Programming — ILP), e foi desenvolvido um algoritmo metaheurístico baseado em Busca Local Iterada (Iterated Local Search — ILS) para resolver de forma eficaz as instâncias reais da empresa. Em seguida, abordamos a divisão de territórios, estendendo o problema anterior ao propor novas partições de clientes para melhorar o roteamento das patrulhas. Investigamos métodos baseados em algoritmos de agrupamento (clustering) e modelos de Programação Linear Inteira Mista (Mixed Integer Linear Programming — MILP) para gerar divisões alternativas de territórios. Para cada solução de agrupamento, o roteamento foi realizado usando variantes do modelo MILP e algoritmos de clustering em conjunto com o ILS desenvolvido no primeiro problema. Os resultados computacionais mostraram que ajustar as configurações territoriais pode aumentar a satisfação dos clientes e reduzir custos. O terceiro problema introduz elementos estocásticos na forma de disparos de alarmes durante a operação de patrulhamento. Ao empregar uma abordagem de modelagem estocástica em duas fases, cenários são gerados com base em uma ampla base histórica de alarmes, a fim de projetar rotas resilientes. O problema é tratado tanto por MILP quanto por um método heurístico, fornecendo uma solução abrangente que aumenta a eficiência da tomada de decisão por parte dos gestores. De modo geral, esta tese aborda de forma positiva um problema real bastante geral, com numerosos desafios práticos, oferecendo algoritmos de otimização eficientes e resultando em soluções aprimoradas para o problema. Palavras-chave: problema de patrulhamento com viaturas; problema de orienteering em equipe; busca local iterada; programação inteira mista; otimização estocástica baseada em cenários