The close enough Traveling Salesman Problem: enhanced heuristics, applications and variants

The traveling salesman problem (TSP) is widely studied to model a wide range of problems. The objective is to identify the minimum path to visit each city in a given set and return to the city of departure ("depot"). TSP has several practical applications in planning, logistics, etc. In recent years, generalizations of TSP have been widely treated for logistical purposes, such as the close enough traveling salesman problem (CETSP) and the close enough arc routing problem (CEARP). In CETSP, each target has a range within which it is considered visited. Hence, we are no longer constrained to the exact location but just close enough. We are not bound to a road network in this problem, so we consider Euclidean distances. In contrast, in the case of CEARP, we always have a range around the targets, but we are constrained to a road network (arcs) to define the route. CETSP and CEARP have practical applications in several real-world scenarios, such as reading meters in a neighborhood using radio frequency identification (RFID) systems. In this thesis, we present an in-depth study of CETSP. We have produced a genetic algorithm (GA) for its resolution, which provides better solutions in most considered benchmark cases. In addition, we present two metrics, TSPDegree (TSPD) and OverlappingCenter (OC), for evaluating instances of the problem. We compared our metrics with those already present in the literature, precisely overlap ratio (OR), obtaining that TSPD and OC provide more information about the characteristics of an instance than OR. We identified incorrect values present in the literature and presented the corrected values regarding OR. We present a case study related to solar panel diagnostics. Specifically, we used a drone to check the correct operation of a solar array. The above case was modeled as a CETSP and solved using our algorithm, obtaining excellent results. This work introduces two variants of CETSP, respectively, the mixed constrained generalized routing problem (MCGRP) and the generalized close enough traveling salesman problem (GCETSP). The former is a generalization of CETSP and CEARP in which we introduce the concept of flight zones. We differentiate two of them: one in which the drone can fly freely (FFZ) and one in which the flight is constrained or prohibited (CFZ). The MCGRP has the same goal as CETSP but within the constraints of the flight zones. We have formally defined the problem and examined it in its limiting cases, namely CETSP and CEARP. The latter is a variant of CETSP. Each target has several areas, modeled as concentric disks, each with a premium that decreases as one moves away from the target. The purpose of GCETSP is to identify the minimum cost route that maximizes the difference between the total premium and the route length by visiting one disk per target. With GCETSP, we can model different application scenarios in which we get more benefits by getting closer to the target. We formally defined the problem and its instances and adapted the solving algorithm to this problem. The results show that our approach can solve the problem correctly, providing excellent solutions.

Il traveling salesman problem (TSP) è ampiamente studiato per la sua abilità di modellare un'ampia gamma di problemi. L'obiettivo è identificare il percorso minimo che visiti ogni città di un dato set e tornare alla città di partenza ("deposito"). Il TSP ha diverse applicazioni pratiche riguardanti il planning, la logistica, etc. Negli ultimi anni, generalizzazioni del TSP sono state ampiamente trattate per scopi logistici, come il close enough traveling salesman problem (CETSP) e il close enough arc routing problem (CEARP). Nel CETSP, ogni target ha un raggio d'azione entro il quale è considerato visitato. Da ciò, non siamo più vincolati alla posizione esatta, ma basta andare abbastanza vicino. In questo problema non siamo vincolati ad una rete stradale, quindi consideriamo le distanze euclidee. Invece, nel caso del CEARP, abbiamo sempre un raggio d'azione attorno ai target, ma siamo vincolati ad una rete stradale (archi) per definire la rotta. Il CETSP e CEARP hanno applicazioni pratiche in diversi scenari reali, come ad esempio per la lettura di contatori in un quartiere mediante sistemi a radio frequenza (RFID). In questa tesi, presentiamo uno studio approfondito del CETSP. Abbiamo prodotto un algoritmo genetico (GA) per la sua risoluzione, che fornisce soluzioni migliori nella maggior parte dei casi di benchmark considerati. Inoltre, presentiamo due metriche, TSPDegree (TSPD) e OverlappingCenter (OC), per la valutazione delle istanze del problema. Abbiamo comparato le nostre metriche con quelle già presenti in letteratura, nello specifico overlap ratio (OR), ottenendo che TSPD e OC forniscono maggiori informazioni sulle caratteristiche di un'istanza rispetto a OR. Riguardo OR, abbiamo identificato valori errati presenti in letteratura, e ne presentiamo i valori corretti. Presentiamo un caso di studio relativo alla diagnostica di pannelli solari. Nello specifico, abbiamo utilizzato un drone per controllare il corretto funzionamento di un campo fotovoltaico. Il suddetto caso è stato modellato come un CETSP e risolto mediante il nostro algoritmo, ottenendo ottimi risultati. In questo lavoro, introduciamo due varianti del CETSP, rispettivamente il mixed constrained generalized routing problem (MCGRP) e il generalized close enough traveling salesman problem (GCETSP). Il primo è una generalizzazione di CETSP e CEARP in cui introduciamo il concetto di zone di volo. Ne differenziamo due: una in cui il drone può volare liberamente (FFZ), e una in cui il volo è vincolato o proibito (CFZ). Il MCGRP si pone lo stesso obiettivo del CETSP ma nel rispetto dei vincoli delle zone di volo. Abbiamo formalmente definito il problema e lo abbiamo esaminato nei suoi casi limiti, ossia CETSP e CEARP. Il secondo è una variante del CETSP, in cui ogni target ha diverse aree associate ad esso, modellate come dischi concentrici, ognuna con un premio che decresce all'allontanarsi dal target. Lo scopo del GCETSP è quello di identificare la rotta di costo minimo che massimizza la differenza tra il premio totale e la lunghezza della rotta, visitando un disco per ogni target. Col GCETSP possiamo modellare diversi scenari applicativi in cui otteniamo maggiori benefici avvicinandoci al target. Abbiamo definito formalmente il problema e delle istanze per esso, e abbiamo adattato l'algoritmo risolutivo a questo problema. I risultati mostrano che il nostro approccio è in grado di risolvere il problema correttamente, fornendo eccellenti soluzioni.