The Orienteering Problem

Risoluzione tramite algoritmo genetico

Repository per il progetto d'esame di Algoritmi di Ottimizzazione Combinatoria e su Rete (UNINA)

Lo scopo del progetto consiste nell'implementare un algoritmo genetico adatto a risolvere il problema di orienteering (OP), nella fattispecie il lavoro si è concentrato sulla variante del problema con starting point differente dall'ending point (OP with Mandatory Visits) e l'algoritmo è stato realizzato sfruttando la libreria DEAP. Le soluzioni ottenute vengono poi confrontate con quelle ottime fornite dall'algoritmo esatto, implementato tramite la libreria Gurobi come problema di PLI, con formulazione MTZ per i subtour elimination constraints. I risultati ottenuti sono esposti all'interno della documentazione fornita (OP_GA_vs_MTZ); il codice dell'algoritmo genetico e dell'algoritmo esatto si trovano rispettivamente nelle cartelle op_ga e op_mtz.