README.md

---
title: Tour Generator GA
emoji: 🚀
colorFrom: red
colorTo: purple
sdk: docker
pinned: false
license: apache-2.0
---

# tour_ga — Generatore di tour turistici con NSGA-II e TOP-TW

Progetto Python per la generazione automatica di tour personalizzati in città (Roma come caso di studio) tramite un algoritmo genetico multi-obiettivo. Il problema è modellato come **Team Orienteering Problem with Time Windows (TOP-TW)** e risolto con una variante di **NSGA-II** (Non-dominated Sorting Genetic Algorithm II, Deb et al., 2002).

---

## Indice

1. [Il problema: TOP-TW](#1-il-problema-top-tw)
2. [Fondamenti teorici: NSGA-II](#2-fondamenti-teorici-nsga-ii)
3. [Struttura del progetto](#3-struttura-del-progetto)
4. [Modello dati](#4-modello-dati)
5. [Profilo turista (TouristProfile)](#5-profilo-turista-touristprofile)
6. [Funzione fitness multi-obiettivo](#6-funzione-fitness-multi-obiettivo)
7. [Operatori genetici](#7-operatori-genetici)
8. [Riparazione genetica (Repair Engine)](#8-riparazione-genetica-repair-engine)
9. [Greedy Seeding](#9-greedy-seeding)
10. [Modello di trasporto realistico](#10-modello-di-trasporto-realistico)
11. [Configurazione e avvio](#11-configurazione-e-avvio)
12. [Risultati di esempio](#12-risultati-di-esempio)
13. [Riferimenti](#13-riferimenti)

---

## 1. Il problema: TOP-TW

Il **Team Orienteering Problem with Time Windows** è una generalizzazione del Travelling Salesman Problem in cui:

- Esiste un insieme di **Punti di Interesse (PoI)** con uno score di attrattività, una durata di visita stimata e una finestra temporale di apertura `[open, close]`.
- Non tutti i PoI possono essere visitati entro il **budget di tempo** giornaliero.
- L'obiettivo è selezionare e ordinare un sottoinsieme di PoI in modo da **massimizzare lo score totale** rispettando i vincoli temporali.

In questo progetto il problema viene esteso con tre obiettivi competitivi simultanei:

| Obiettivo | Direzione | Significato |
|-----------|-----------|-------------|
| `total_score` | Massimizza | Interesse culturale/gastronomico del tour |
| `total_distance` | Minimizza | Fatica e costi di spostamento |
| `time_penalty` | Minimizza | Sforamento del budget giornaliero |

La natura multi-obiettivo rende la ricerca di un'unica soluzione ottima impossibile: esistono molteplici soluzioni di compromesso (fronte di Pareto) tra le quali il turista sceglie in base alle proprie preferenze.

---

## 2. Fondamenti teorici: NSGA-II

L'algoritmo NSGA-II (Deb, Pratap, Agarwal, Meyarivan — *IEEE Transactions on Evolutionary Computation*, Vol. 6, No. 2, 2002) risolve i tre limiti principali del suo predecessore NSGA:

1. **Complessità computazionale** — Il sorting non-dominato originale era O(MN³). NSGA-II lo riduce a **O(MN²)** con un algoritmo di conteggio della dominanza.
2. **Mancanza di elitismo** — NSGA-II combina popolazione corrente e figli in un pool di 2N individui e seleziona i migliori N: le soluzioni eccellenti non vengono mai perse.
3. **Parametro di sharing** — Sostituito dalla **crowding distance**, una metrica parameter-free che misura la densità delle soluzioni nell'intorno di un individuo nello spazio degli obiettivi.

### 2.1 Fast Non-Dominated Sorting

Per ogni individuo `i` si calcolano:
- `dom_count[i]`: numero di individui che dominano `i`
- `dom_set[i]`: insieme degli individui dominati da `i`

Un individuo `A` **domina** `B` se è migliore o uguale su tutti gli obiettivi e strettamente migliore su almeno uno. Gli individui con `dom_count = 0` formano il **Fronte 1** (Pareto front). Rimuovendo il fronte 1 e ripetendo si ottengono i fronti successivi. La complessità totale è **O(MN²)**.

### 2.2 Crowding Distance

Per ogni fronte, la crowding distance di un individuo `i` è la somma delle distanze normalizzate tra i vicini immediati lungo ciascun obiettivo:

```
CD(i) = Σ_m  |f_m(i+1) - f_m(i-1)| / (f_m_max - f_m_min)
```

Gli individui agli estremi del fronte ricevono distanza infinita. La crowding distance alta indica un individuo in una regione poco affollata — preferito nella selezione per mantenere diversità.

### 2.3 Crowded-Comparison Operator

Nella selezione a torneo, un individuo `A` è preferito a `B` se:
- `rank(A) < rank(B)` (rango Pareto migliore), oppure
- `rank(A) == rank(B)` e `crowd(A) > crowd(B)` (regione meno affollata)

### 2.4 Ciclo evolutivo principale

```
Inizializzazione popolazione P (greedy seeding + casuale riparato)
        ↓
Valutazione fitness (3 obiettivi)
        ↓
Fast non-dominated sort → assegna rank e crowding distance
        ↓
┌─────────────────────────────────────────────────────────┐
│  Selezione torneo (crowded-comparison)                  │
│  Crossover (OX | PoI-aware, prob cx_prob)               │
│  Mutazione (swap | insert | reverse | add-remove)       │
│  Riparazione (categoria → TW → budget → cap → pasto)   │
│  → popolazione figli Q (size N)                         │
└─────────────────────────────────────────────────────────┘
        ↓
Unione R = P ∪ Q  (size 2N)
        ↓
Non-dominated sort su R → seleziona migliori N → nuova P
        ↓
Criterio di stop? (max generazioni | stagnazione)
        ↓ NO                              ↓ SÌ
     (loop)                     Restituisce Fronte 1
```

### 2.5 Adattamenti al TOP-TW

L'NSGA-II standard opera su cromosomi di lunghezza fissa con variabili continue. Per il TOP-TW sono stati introdotti:

- **Cromosomi a lunghezza variabile** — lista ordinata di PoI (sottoinsieme del pool, non permutazione completa)
- **Repair-before-evaluation** — ogni individuo viene riparato dopo ogni operatore genetico, prima della valutazione fitness
- **Gene Jolly** (via `add_remove_mutation`) — placeholder che viene sostituito con il PoI più conveniente disponibile
- **Penalità dinamica sulle attese** — scoraggia tour con buchi temporali lunghi

---

## 3. Struttura del progetto

```
tour_generator_ga/
├── core/
│   ├── models.py       # PoI, Individual, TourSchedule, FitnessScore
│   ├── distance.py     # DistanceMatrix (Haversine × 1.3)
│   ├── fitness.py      # FitnessEvaluator multi-obiettivo
│   └── profile.py      # TouristProfile + modello trasporto realistico
├── ga/
│   ├── operators.py    # crossover (OX, PoI-aware), mutation, selection
│   ├── repair.py       # RepairEngine: 7 step di riparazione
│   └── seeding.py      # GreedySeeder: costruzione iniziale α-greedy
├── data/               # (placeholder per loader OSM/CSV)
├── solver.py           # NSGA2Solver: ciclo evolutivo completo
├── demo_rome.py        # Demo con dataset Roma e confronto profili
└── README.md
```

---

## 4. Modello dati

### `PoI`

```python
@dataclass
class PoI:
    id:             str
    name:           str
    lat, lon:       float
    score:          float           # attrattività [0, 1]
    visit_duration: int             # minuti di visita
    time_window:    TimeWindow      # (open, close) in minuti dalla mezzanotte
    category:       PoICategory     # MUSEUM | MONUMENT | RESTAURANT | BAR | GELATERIA | PARK | VIEWPOINT
    tags:           list[str]       # es. ["arte", "antico", "fotogenico"]
```

### `Individual` (cromosoma)

```python
class Individual:
    genes:    list[PoI]       # sequenza ordinata del tour
    fitness:  FitnessScore    # calcolata dopo evaluate()
    _schedule: TourSchedule   # cache dello schedule decodificato
```

La rappresentazione come lista ordinata permette di codificare naturalmente sia l'insieme dei PoI visitati sia l'ordine di visita, senza vincoli di lunghezza fissa.

### `TourSchedule`

Output della decodifica del cromosoma: per ogni PoI vengono calcolati orario di arrivo, attesa all'apertura e orario di partenza. Il campo `total_wait` traccia i minuti di attesa cumulati e contribuisce alla penalità fitness.

### `PoICategory`

```
MUSEUM | MONUMENT | RESTAURANT | BAR | GELATERIA | PARK | VIEWPOINT
```

La distinzione tra `RESTAURANT` (pasto formale) e `BAR`/`GELATERIA` (sosta breve) permette al `RepairEngine` di applicare vincoli differenziati per tipo di sosta alimentare.

---

## 5. Profilo turista (TouristProfile)

Il `TouristProfile` è l'oggetto centrale che attraversa l'intero pipeline e determina il comportamento di ogni componente.

```python
@dataclass
class TouristProfile:
    transport_mode:      TransportMode     # WALK | CAR | TRANSIT | MIXED
    mobility:            MobilityLevel     # NORMAL | LIMITED
    allowed_categories:  list[str]         # categorie PoI ammesse
    want_lunch:          bool              # richiede sosta pranzo
    want_dinner:         bool              # richiede sosta cena
    lunch_time:          int               # orario preferito pranzo (minuti)
    dinner_time:         int               # orario preferito cena (minuti)
    meal_window:         int               # flessibilità ±minuti attorno all'orario
    max_bar_stops:       int = 1           # max soste bar nel tour
    max_gelateria_stops: int = 1           # max soste gelateria nel tour
    tag_weights:         dict[str, float]  # boost per tag di interesse
    max_entry_fee:       float | None      # budget biglietti per PoI
    group_size:          int = 1           # persone (influenza durata visite)
```

**Profili predefiniti disponibili:**

| Factory | Modalità | Categorie | Pasti |
|---------|----------|-----------|-------|
| `profile_cultural_walker()` | WALK | museum, monument, viewpoint, restaurant | pranzo |
| `profile_foodie_transit()` | TRANSIT | restaurant, bar, gelateria, monument, viewpoint | pranzo + cena |
| `profile_family_mixed()` | MIXED / LIMITED | monument, park, viewpoint, restaurant | pranzo |
| `profile_art_lover_car()` | CAR | museum, monument | pranzo |

**Effetti sul pipeline:**

- `DistanceMatrix` — usa `profile.travel_time_min(km)` per i tempi di percorrenza
- `GreedySeeder` — filtra `allowed_pois` per categoria; usa `effective_score()` (con boost tag)
- `RepairEngine` — filtra categorie, applica cap ristoranti/snack, garantisce slot pasto
- `FitnessEvaluator` — calcola score con boost da `tag_weights`; penalizza pasti mancanti

---

## 6. Funzione fitness multi-obiettivo

La fitness è calcolata in `FitnessEvaluator.evaluate()` e comprende tre componenti separate per NSGA-II e uno scalare aggregato per confronti rapidi (tournament selection):

### Score effettivo con boost

```python
effective_score(poi) = min(poi.score × Π(1 + tag_weight - 1), 1.5)
```

I `tag_weights` del profilo amplificano i PoI tematicamente rilevanti (es. `arte × 1.4` per un turista culturale). Il cap a 1.5 evita distorsioni eccessive.

### Scalare aggregato

```
scalar = w_score × norm(total_score)
       - w_dist  × norm(total_distance)
       - time_over_penalty     # solo sullo sforamento, non sull'uso del budget
       - wait_penalty          # penalizza attese cumulate > 5 min
       - meal_penalty          # penalizza slot pasto non coperti
```

La scelta deliberata di **non penalizzare l'uso del budget** (solo lo sforamento) evita che il GA produca tour brevissimi per minimizzare il tempo. Un tour di 10 ore che rispetta il budget di 11 ore non è peggio di uno da 3 ore.

### I tre obiettivi Pareto

| Obiettivo | Misura | Direzione |
|-----------|--------|-----------|
| `total_score` | score effettivo cumulato | Massimizza |
| `total_distance` | km percorsi (Haversine × 1.3) | Minimizza |
| `total_time` | minuti totali del tour | Minimizza |

La dominanza Pareto è implementata in `FitnessScore.dominates()`:

```python
def dominates(self, other) -> bool:
    better_or_equal = (score ≥ and dist ≤ and time ≤)
    strictly_better = (score > or dist < or time <)
    return better_or_equal and strictly_better
```

---

## 7. Operatori genetici

### Selezione

**Tournament selection** con `k=3` candidati casuali. Con `use_pareto=True` (default) preferisce rango Pareto basso e crowding distance alta, implementando l'operatore crowded-comparison di NSGA-II.

### Crossover

**Order Crossover (OX) adattato** — Preserva l'ordine relativo dei PoI condivisi tra i genitori senza duplicati. Adattato al TOP-TW per gestire cromosomi a lunghezza variabile (sottoinsiemi, non permutazioni complete).

```
Genitore A: [Trevi, Navona, Pantheon, Pranzo, Colosseo]
Genitore B: [Colosseo, Pranzo, Borghese, Trevi, Castel]

Segmento da A (pos 1-2): [Navona, Pantheon]
Riempimento da B (escl. duplicati): [Colosseo, Pranzo, Trevi, Castel]
Figlio: [Colosseo, Navona, Pantheon, Pranzo, Trevi, Castel]
```

**PoI-aware Crossover** — Scambia interi blocchi per categoria (es. tutti i musei da A, tutti i ristoranti da B). Preserva la "nicchia tematica" del genitore e mantiene la coerenza del profilo turista.

### Mutazione

Quattro operatori applicati con probabilità adattiva:

| Operatore | Effetto | Caso d'uso |
|-----------|---------|------------|
| `swap_mutation` | Scambia 2 PoI nella sequenza | Esplorazione locale |
| `insert_mutation` | Rimuove e reinserisce un PoI | Fix ordinamento temporale |
| `reverse_segment_mutation` | Inverte un sottosegmento | Elimina crossing geografici |
| `add_remove_mutation` | Aggiunge/rimuove un PoI dal pool ammesso | Modifica lunghezza tour |

La `add_remove_mutation` opera **solo sul pool filtrato** per le categorie del profilo — non può mai inserire un ristorante nel tour di un turista che li ha esclusi.

---

## 8. Riparazione genetica (Repair Engine)

Ogni individuo viene riparato dopo ogni operatore genetico, prima della valutazione fitness. La pipeline di riparazione ha **7 step in sequenza**:

```
1. _filter_allowed_categories   → rimuove PoI di categorie non ammesse
2. _sort_by_earliest_deadline   → riordina per orario di apertura (EDF)
3. repair_time_windows          → rimuove PoI con TW violata o attesa > max_wait_min
4. repair_budget                → rimuove PoI a minor score/durata finché budget rispettato
5. _cap_restaurants             → limita ristoranti formali al numero di slot pasto
6. _cap_snacks                  → limita bar e gelaterie ai massimi del profilo
7. _ensure_meal_slots           → garantisce un ristorante per ogni slot pasto richiesto
```

### Step 3: max_wait_min

Il parametro `max_wait_min` (default 30) definisce la massima attesa tollerata per qualsiasi PoI. Un ristorante che apre alle 12:00 e a cui si arriva alle 9:30 viene **rimosso** — non ha senso aspettare 2 ore e mezza. L'eccezione è `_ensure_meal_slots`, che tolera fino a 45 minuti di attesa per garantire la sosta pranzo/cena.

### Step 7: strategia di inserimento/sostituzione

Quando deve garantire un pasto, `_ensure_meal_slots` prova due strategie:

1. **Inserimento diretto** — aggiunge il ristorante nella posizione temporalmente corretta senza sforare il budget.
2. **Sostituzione** — se non c'è spazio, rimuove il PoI con il peggior rapporto score/durata e lo sostituisce con il ristorante. Questo evita che tour a budget pieno perdano la garanzia del pasto.

---

## 9. Greedy Seeding

La popolazione iniziale è costruita con una strategia mista 20/20/60:

| Quota | Strategia | Scopo |
|-------|-----------|-------|
| 20% | Greedy puro (`alpha=0`) | Massima qualità iniziale, convergenza rapida |
| 20% | α-greedy perturbato (`alpha` da 0.15 a 0.50) | Varietà controllata vicino all'ottimo |
| 60% | Casuale riparato | Massima diversità genetica |

### Criterio greedy: ratio score/overhead

```python
ratio = effective_score(poi) / (travel_min + wait_min + visit_duration)
```

Dove `effective_score` include già i boost da `tag_weights` del profilo. Il criterio seleziona il PoI che massimizza il valore per minuto di tempo investito (spostamento + attesa + visita).

### Restricted Candidate List (GRASP-like)

Con `alpha > 0`, invece di scegliere sempre il candidato migliore, si sceglie **casualmente tra il top 20%** per ratio. Questo produce soluzioni diverse ma ancora di buona qualità, avvicinandosi alla strategia GRASP (Greedy Randomized Adaptive Search Procedure).

Tutti gli individui iniziali (greedy inclusi) passano per `repair.repair()` per garantire la coerenza con i vincoli del profilo fin dalla prima generazione.

---

## 10. Modello di trasporto realistico

Il calcolo dei tempi di percorrenza in `profile.travel_time_min(km)` usa un modello che riflette la realtà urbana:

### WALK

```
t = km / v_walk
```
- `v_walk_normal = 4.5 km/h`, `v_walk_limited = 3.0 km/h`

### TRANSIT (bus + metro)

```
if km < 0.40:          # soglia: prendere il mezzo non conviene
    t = km / v_walk
else:
    t = km / 20.0 + 10 min   # 10 min overhead (attesa + fermata)
```

L'overhead fisso di 10 minuti per tratta modella la realtà di Roma: frequenza media bus 8-12 minuti, metro 4-5 minuti, più il cammino alle fermate.

### CAR / TAXI

```
t = km / 25.0 + 5 min   # 5 min overhead parcheggio
```

### MIXED

Per distanze sotto `600 m` si usa `v_walk`; oltre si usa la velocità transit con overhead.

---

## 11. Configurazione e avvio

### Requisiti

```
Python ≥ 3.10   (per syntax X | None nei type hint)
Nessuna dipendenza esterna (stdlib only)
```

### SolverConfig

```python
from tour_ga.solver import SolverConfig

config = SolverConfig(
    pop_size         = 80,      # dimensione popolazione
    max_generations  = 300,     # generazioni massime
    cx_prob          = 0.85,    # probabilità crossover
    mut_prob         = 0.20,    # probabilità mutazione
    tournament_k     = 3,       # candidati per torneo
    stagnation_limit = 50,      # early stop per stagnazione
    start_time       = 540,     # 09:00 (minuti dalla mezzanotte)
    budget           = 480,     # 8 ore di tour
    start_lat        = 41.896,  # coordinate punto di partenza
    start_lon        = 12.484,
    max_wait_min     = 30,      # attesa massima tollerata per PoI
    w_score          = 0.50,    # peso obiettivo score
    w_dist           = 0.20,    # peso obiettivo distanza
    w_time           = 0.30,    # peso penalità tempo
)
```

### Avvio base

```python
from tour_ga.core.models import PoI, PoICategory, TimeWindow
from tour_ga.core.distance import DistanceMatrix
from tour_ga.core.profile import profile_cultural_walker
from tour_ga.solver import NSGA2Solver, SolverConfig

pois = [...]   # lista di PoI
profile = profile_cultural_walker()

dm = DistanceMatrix(pois, profile=profile)
dm.build()     # calcola matrice distanze (una volta sola)

solver = NSGA2Solver(pois, dm, config, profile=profile)
pareto_front = solver.solve()  # restituisce lista di Individual

# Selezione della soluzione consigliata dal fronte
best = max(pareto_front, key=lambda x: x.fitness.scalar)
schedule = solver.evaluator.decode(best)
print(schedule.summary())
```

### Profilo custom

```python
from tour_ga.core.profile import TouristProfile, TransportMode

profile = TouristProfile(
    transport_mode     = TransportMode.TRANSIT,
    allowed_categories = ["monument", "viewpoint", "bar"],
    want_lunch         = False,
    want_dinner        = False,
    max_bar_stops      = 2,
    tag_weights        = {"fotogenico": 1.5, "panorama": 1.3},
)
```

### Callback di monitoraggio

```python
def progress(gen, pareto_front, stats):
    print(f"Gen {gen}: pareto={stats['pareto_size']}, "
          f"best={stats['best_scalar']:.4f}, "
          f"feasible={stats['feasible_pct']:.0f}%")

front = solver.solve(callback=progress)
```

### Demo completa

```bash
python tour_ga/demo_rome.py
```

---

## 12. Risultati di esempio

Configurazione: `budget=660 min` (11h), `start_time=570` (09:30), `pop_size=60`, `max_generations=200`, Roma.

### Profilo gastronomico con mezzi (TRANSIT, pranzo + cena)

```
09:42–10:12  Fontana di Trevi
10:24–10:54  Piazza di Spagna
11:08–11:53  Piazza Navona
11:56–12:16  Sant'Eustachio il Caffè         ← bar pomeridiano
12:27–13:27  Osteria del Rione               ← pranzo garantito
13:41–15:11  Castel Sant'Angelo
15:24–16:24  Pantheon
16:37–18:07  Foro Romano
18:21–18:41  Fatamorgana                     ← gelateria pomeridiana
19:00–20:20  Ristorante San Pietro           ← cena garantita (attesa 4 min)
Totale: 650 min, 10.9 km, attese 4 min
Composizione: 1×bar, 1×gelateria, 4×monument, 2×restaurant, 2×viewpoint
```

### Profilo culturale a piedi (WALK, solo pranzo)

```
09:39–10:09  Fontana di Trevi
10:18–10:48  Piazza di Spagna
11:06–11:51  Piazza Navona
12:00–13:00  Osteria del Rione               ← pranzo (attesa 3 min)
13:05–14:05  Pantheon
14:21–15:51  Foro Romano
16:01–18:01  Colosseo
18:32–20:02  Trastevere
Totale: 632 min, 8.1 km, attese 3 min
```

### Profilo custom: solo viste, nessun pasto

```
09:39–10:09  Fontana di Trevi
10:18–10:48  Piazza di Spagna
11:06–11:51  Piazza Navona
11:54–12:14  Sant'Eustachio il Caffè
12:16–13:16  Pantheon
13:33–15:03  Castel Sant'Angelo
15:14–15:34  Fatamorgana
Totale: 364 min, 5.5 km
```

---

## 13. Riferimenti

### Articolo scientifico principale

Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). **A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II**. *IEEE Transactions on Evolutionary Computation*, 6(2), 182–197.
[https://www.cse.unr.edu/~sushil/class/gas/papers/nsga2.pdf](https://www.cse.unr.edu/~sushil/class/gas/papers/nsga2.pdf)

Il paper introduce tre contributi fondamentali qui implementati: il fast non-dominated sorting O(MN²) tramite conteggio della dominanza (implementato in `solver.py::_fast_non_dominated_sort`), la crowding distance come meccanismo di diversità parameter-free (implementato in `_assign_crowding_distance`), e il crowded-comparison operator per selezione a torneo (in `operators.py::tournament_select`).

### Riferimento divulgativo

Non-Dominated Sorting Genetic Algorithm 2 (NSGA-II) — GeeksforGeeks.
[https://www.geeksforgeeks.org/deep-learning/non-dominated-sorting-genetic-algorithm-2-nsga-ii/](https://www.geeksforgeeks.org/deep-learning/non-dominated-sorting-genetic-algorithm-2-nsga-ii/)

### Problema di riferimento

Vansteenwegen, P., Souffriau, W., & Van Oudheusden, D. (2011). **The Orienteering Problem: A Survey**. *European Journal of Operational Research*, 209(1), 1–10.

Chao, I. M., Golden, B. L., & Wasil, E. A. (1996). **The Team Orienteering Problem**. *European Journal of Operational Research*, 88(3), 464–474.

### Calcolo distanze

Formula di Haversine per la distanza geodetica tra due coordinate GPS, con fattore correttivo 1.3 per approssimare il percorso urbano reale rispetto alla linea d'aria.