Appunti Optimization and data science for management secondo parziale (in italiano)

Secondo parziale

Problema del commesso viaggiatore

Definizione del TSP = (, ),

Dato un grafo orientato con costi associati agli archi, il problema consiste nel determinare un ciclo (permutazione dei nodi) che:

• Inizi da un nodo scelto arbitrariamente come punto di partenza (deposito)
• Ritorni al punto di partenza
• Visiti ogni nodo esattamente una volta
• Abbia costo minimo (somma dei costi degli archi percorsi)

Caso di studio: Bontur a Prague

• Laboratorio specializzato nella produzione artigianale di dolci
• 4 stabilimenti produttivi e un laboratorio che serve la città
• Ogni mattina alle 6:30, una flotta di furgoni trasporta i prodotti di pasticceria dal laboratorio ai punti vendita (supermercati, canè, hotel)
• Il quartiere Vltava è servito da un solo furgone e i costi di trasporto sono assunti proporzionali alle distanze percorse.

Seleziona 8 archi tali che:

• Solo un arco entra in ciascun nodo
• Solo un arco esce da ciascun nodo
• Il costo totale degli archi selezionati sia minimizzato

(, ).

Associamo una variabile a ciascun arco

#! + + + + + + = 1),% ),8 ),' ),? ),%@ ),&) ),&& + + + + + + = 1%,) 8,) ',) ?,) %@,) &),) &&,)

Il costo è pari a 20.8.

Che dire del costo della soluzione ottima? Sarebbe minore o maggiore di 20.8?

Formulazione matematica del TSP

min R #! #!(#,!)∈3R = 1∀ ∈ #!!∈AB(#)R = 1∀ ∈ #!#∈CB(!)̅ ̅ ̅R ≥ 1∀, ⊆ . . ∩ = ∅, ∪ = #!(#,!)∈3(B,B̅) ≥ 0∀(, ) ∈ #!e intero.

Una formulazione alternativa

min R #! #!(#,!)∈3R = 1∀ ∈ #!!∈AB(#)R = 1∀ ∈ #!#∈CB(!) ≥ + 1 − ^1 − _∀(, ) ∈ , ≠ 1! # #!1 ≤ ≤ ∀ ∈ ! ≥ 0∀(, ) ∈ ! ,

Si utilizzano variabili aggiuntive che rappresentano la posizione di un nodo nel tour: si assume che il deposito sia il nodo 1 e che ci siano nodi. I vincoli collegano tra loro le variabili dei e quando = 1).

I nodi questi vengono visitati consecutivamente (Negli altri casi, i #! = . vincoli risultano ridondanti: una scelta ammissibile è Questi vincoli non vengono applicati agli archi che entrano nel deposito; altrimenti non sarebbe possibile chiudere il tour ritornando al deposito.

La struttura del TSP

Vehicle routing problem – VRP

Che cosa? Problemi di pianificazione e gestione che sorgono nella consegna di beni e servizi

Perché? I costi di trasporto rappresentano circa il 10-20% del costo totale di un bene. Esiste un enorme numero di pacchetti commerciali per risolvere il problema.

Il VRP riguarda la pianificazione e la gestione di problemi relativi alla consegna di beni e servizi. Questa è un’area critica per le imprese perché i costi di trasporto rappresentano tipicamente dal 10% al 20% del costo totale di una produzione.

Applicazioni: ritiro e consegna di merci, raccolta dei rifiuti, instradamento degli scuolabus, “dial-a-ride” e carpooling, pulizia stradale, trasporto in ambito sanitario.

Definizione del problema

Dato:

• Un insieme di clienti
• Uno o più depositi
• Un insieme di veicoli basati nei depositi
• Una rete stradale

Il problema richiede di determinare un insieme di percorsi, uno per ciascun veicolo, ciascuno con partenza e arrivo al deposito, tale che ogni cliente appartenga esattamente a un solo percorso (partizione) e il costo totale di trasporto sia minimizzato. Possono essere presenti vincoli aggiuntivi, come capacità, tempi, ecc.

L’obiettivo è determinare un insieme di percorsi, uno per ciascun veicolo, in cui ogni percorso inizia e termina al deposito. Ogni cliente deve essere incluso esattamente in un solo percorso, e l’obiettivo principale è minimizzare il costo totale di trasporto rispettando vincoli aggiuntivi come la capacità del veicolo e i tempi.

Caratteristiche:

1. Rete stradale
2. Clienti
3. Percorsi
4. Flotta di veicoli
5. Conducente
6. Vincoli aggiuntivi
7. Criteri di guida

Rete stradale

La rete stradale è descritta da un grafo, in cui i nodi corrispondono al deposito e alle posizioni dei clienti, agli incroci stradali, … gli archi corrispondono alle strade.

Gli archi possono essere:

1. Orientati (mappa urbana)
2. Non orientati (l’arco può essere percorso in entrambe le direzioni)

Per ogni arco, sono noti il costo e il tempo di percorrenza. Possono essere dinamici, cioè possono dipendere dall’orario di partenza.

Clienti

I clienti sono nodi con requisiti specifici:

1. Ogni cliente corrisponde a un nodo della rete
2. La domanda di ciascun cliente può essere singola o multi-prodotto. I clienti possono richiedere servizi di ritiro, consegna o entrambi.
3. Finestre temporali in cui i clienti possono ricevere il servizio. Periodi specifici in cui possono ricevere il servizio
4. Tempo di servizio: tempo richiesto per caricare/scaricare il veicolo. Può dipendere dal tipo di veicolo
5. Un cliente potrebbe essere visitato da un sottoinsieme di veicoli (vincoli di compatibilità)
6. Costo di penalità se non servito

Percorsi e depositi

• I percorsi iniziano e terminano in un deposito (di solito lo stesso)
• Ogni deposito possiede una flotta di veicoli
• In alcune applicazioni (o per gestire la complessità del problema), i clienti possono essere ripartiti tra i depositi. In questo caso, l’intero problema viene scomposto in tanti sottoproblemi indipendenti quanti sono i depositi.

Flotta di veicoli

• Deposito di appartenenza (o base): a un veicolo può essere consentito terminare il proprio servizio in un deposito diverso dalla sua base
• Capacità: peso o volume massimo che un veicolo può trasportare. I veicoli hanno capacità specifiche (peso o volume) e possono avere compartimenti specializzati o attrezzature di carico. Sono inoltre soggetti a restrizioni stradali, come il divieto di percorrere alcuni archi.
• Possibile suddivisione di un veicolo in compartimenti
• Può essere equipaggiato con specifiche attrezzature per il carico/scarico delle merci
• Divieto di utilizzare alcuni archi
• Costi: unitari, fissi, …

Conducenti

Usiamo questa assunzione: conducenti = veicoli

In generale, possono esserci accordi collettivi e altri vincoli sulla durata di un turno, sul numero e sulla durata delle pause, sulla fidelizzazione (cruciale in alcuni servizi, come i servizi di assistenza domiciliare) → consistenza: mantenere lo stesso conducente per uno specifico cliente per costruire fidelizzazione.

Criteri di guida

Gli obiettivi di ottimizzazione sono spesso in conflitto. I più comunemente utilizzati sono:

• Minimizzazione del costo totale di trasporto (proporzionale al tempo di viaggio o alla distanza) e dei costi fissi associati all’uso dei veicoli
• Minimizzazione del numero di veicoli richiesti per servire tutti i clienti
• Bilanciamento dei percorsi (in termini di tempo di viaggio e/o carico del veicolo)
• Minimizzazione delle penalità derivanti dal mancato soddisfacimento di alcuni clienti
• Combinazione pesata dei criteri precedenti.

Il TSP è un caso speciale del VRP

Il Travelling Salesman Problem (TSP) è un VRP con le seguenti caratteristiche:

• Un solo deposito = 1
• Un solo veicolo (che corrisponde al venditore), E#F%∑ ≥
• Nessun vincolo di capacità sul veicolo (senza capacità), #-
• Nessun altro vincolo aggiuntivo

Sequenziamento dei clienti

In questo scenario semplificato, l’obiettivo si sposta dalla gestione del carico e dall’ottimizzazione della flotta al sequenziamento dei clienti, cioè trovare l’ordine più efficiente in cui visitare tutti i nodi.

Capacitated Vehicle Routing Problem (CVRP)

Ipotesi:

• Clienti richiedono un servizio di consegna e la domanda è mono-prodotto, nota e non frazionabile
• Veicoli veicoli omogenei basati in un deposito centrale
• Vincoli aggiuntivi capacità del veicolo

Questo specifico modello assume una flotta omogenea (tutti i veicoli sono uguali) basata in un deposito centrale. I clienti hanno una domanda nota e non frazionabile per un solo tipo di bene. Il vincolo principale è che nessun veicolo può trasportare più della sua capacità massima.

Notazione

= (, )

• È un grafo completo = {0,1, … , },
• Dove 0 (or “o”) è il deposito
• o {1, }… , L’insieme identifica gli clienti
• o ≥ 0 ∀(, ) ∈ - costo di viaggio da a#!

Nota: nella maggior parte delle applicazioni pratiche, i costi soddisfano la proprietà triangolare.

Costruzione di un’astrazione della rete stradale

1. Fase di preprocessing

Prima di risolvere un VRP, è richiesta una fase di preprocessing per semplificare la rete stradale reale in un modello astratto.

Partendo dalla rete stradale, questa fase di preprocessing calcola la matrice delle distanze/costi tra ogni coppia di clienti e tra deposito e clienti. La matrice delle distanze calcola la distanza o il costo tra ogni coppia di clienti e tra il deposito e i clienti.

Il VRP è definito sulla rete astratta in cui i nodi corrispondono ai clienti e al deposito, e gli archi collegano ogni coppia di nodi (grafo completo).

Notazione: ≥ 0 ∀ ∈ , = 0- domanda del cliente con (domanda fittizia per il deposito)

# ): , ( ≤;- numero di veicoli identici basati nel deposito, ciascuno con capacità #) ∀ ∈ . veicoli

La capacità è il carico massimo per ciascuno dei identici. ≥ - Ipotesi: , dove è il numero minimo di veicoli richiesto per servire tutti i G#E G#E clienti - Un limite inferiore banale (LB) su :G#E 'H * ! ≥ ‰ Š (*)!($G#E I

Costruzione del limite inferiore

La formula del limite inferiore “banale”, che semplicemente divide la domanda totale per la capacità del veicolo e arrotonda per eccesso, può spesso essere imprecisa. Questo perché la formula assume che le domande possano essere suddivise perfettamente, cosa che raramente è possibile nel carico reale.

Il limite inferiore banale (*) può essere impreciso.

Esempio - 5 nodi con domanda: 2 2 3 5 5#=6

• ≥ ⌈17/6⌉ = 3
• Non è sufficiente!

G#E = 4G#E

Perché cambia K nell’esempio? Questo succede perché i pezzi sono troppo grandi per essere combinati tra loro senza superare la capacità di 6. Tuttavia, 3 veicoli non sono sufficienti perché le singole richieste, come i due “5”, non possono essere combinate con le altre senza superare la capacità di 6. In questo caso specifico, sono effettivamente necessari 4 veicoli.

2. Fase di preprocessing

È fornito come soluzione ottima di un problema di Bin Packing 0-1

G#E min R !!∈JR = 1 ∀ ∈ #!!∈JR ≤ ∀ ∈ # #! !#∈K {0,1} ∈ ∀ ∈ ∀ ∈ #! {0,1} ∈ ∀ ∈ ! insieme degli elementi insieme dei contenitori disponibili (illimitati)

ˇ1, se e assegnato a = ’#! 0, altrimenti

ˇ1, se e usato = ’! 0, altrimenti

Enunciato del problema CVRP

Determinare cicli in (ciascuno corrispondente a un veicolo) con costo minimo tali che:

1. Coerenza del deposito: ogni ciclo inizia e termina al deposito
2. Partizionamento dei clienti: ogni cliente appartiene a un solo ciclo (partizione dei clienti)
3. Rispetto della capacità: la domanda totale dei clienti assegnati a un veicolo non supera la capacità

Ipotesi matrice delle distanze asimmetrica

Studieremo i seguenti modelli:

1. Formulazione a due indici
2. Formulazione di flusso a due indici
3. Formulazione set-partitioning
4. Formulazione a tre indici (per CVRP + finestre temporali)

Questi modelli assumono tipicamente una matrice delle distanze asimmetrica, cioè il costo di viaggio dal punto A al punto B potrebbe non essere uguale al costo di viaggio dal punto B al punto A.

Formulazione a due indici

Il modello utilizza le seguenti variabili a due indici:

1, (, )se appartiene a qualche percorso = ’#! 0, altrimenti∀(, ) ∈ .

Esiste una variabile &( ),

Quindi, abbiamo un numero di variabili perché il grafo è completo.

Nota che:

• I vincoli (1), (2), (3) e (4) sono vincoli di conservazione del flusso: per ogni cliente deve arrivare esattamente un veicolo (Backward Star) e deve partire esattamente un veicolo; esattamente veicoli devono lasciare il deposito ed esattamente veicoli devono ritornarvi.
• Quindi, uno di questi vincoli dipende linearmente dagli altri e può essere eliminato.

Questa è la stessa situazione che si verifica nel problema di flusso a costo minimo” () = 0 quando assumiamo .#∈6

• Vincoli di capacità sui tagli (Cut Capacity Constraints, CCC): questi assicurano che tutti i percorsi siano connessi al deposito e che la capacità del veicolo sia rispettata.

I vincoli relativi alla conservazione del flusso nei nodi e nel deposito sono linearmente dipendenti. Questo è simile ai problemi standard di flusso a costo minimo; significa che se il flusso è bilanciato in tutti i nodi tranne uno, l’ultimo nodo è automaticamente bilanciato, permettendo di rimuovere un vincolo dal calcolo.

Esempio ∣ ∣= 9, = 8

Assumiamo e le seguenti domande dei nodi per gli 8 clienti.

Requisito dei veicoli: per trovare il numero minimo di veicoli, usiamo la formula del G#E limite inferiore. = 2 fornisce soluzioni ammissibili.

È considerata una soluzione ammissibile (o feasible) perché soddisfa contemporaneamente i requisiti matematici e logistici del problema CVRP.

Graficamente:

I clienti 1, 2, 3, 5 e 7 sono correttamente collegati al deposito (nodo 0), ma i nodi 4, 6 e 8, formano un ciclo separato, insieme che non è collegato al deposito. Questo è un sottotour.

Una soluzione VRP è valida solo se ogni percorso inizia e termina al deposito.

Vincoli di capacità sui tagli (CCC)

I vincoli (5), chiamati Cut Capacity Constraints, svolgono un duplice ruolo:

1. Garantiscono la connessione con il deposito (vincoli di eliminazione dei sottotour)
2. Garantiscono il vincolo di capacità sui veicoli

() è un parametro (da calcolare nella fase di preprocessing) e rappresenta il numero. () minimo di veicoli necessari per visitare tutti i clienti nell’insieme può essere calcolato risolvendo un problema di Bin Packing 0-1 per ogni (fattibile su istanze VRP di dimensioni reali). (),

Questi vincoli si basano su un parametro chiamato che rappresenta il numero minimo di veicoli necessari per visitare tutti i clienti all’interno di uno specifico sottoinsieme. Questo parametro viene calcolato utilizzando un problema di Bin Packing 0-1 durante la fase di preprocessing.

Esempio CCC ( ∖ , ).

Deve esserci almeno un veicolo che attraversa il taglio. Questo è necessario per servire i clienti in. La soluzione non è ammissibile per il CVRP.

La domanda totale per questo insieme è di 4 unità. Poiché la domanda è inferiore alla () = 1 capacità, (un veicolo è sufficiente). Il vincolo richiede che almeno un veicolo attraversi il “taglio” tra il deposito e questo insieme di clienti. Se i nodi formano un ciclo tra loro “senza” una connessione al deposito, la soluzione non è ammissibile.

CCC vs GSEC

I CCC possono essere sostituiti dagli equivalenti vincoli generalizzati di eliminazione dei sottotour (GSEC): ||R ≤ − () ∀ ⊆ \{}, ≠∅#!(#,!)∈3 0.$. #∈B, !∈B ,

Impongono un limite superiore (al massimo) sul numero di archi all’interno di quindi esiste un limite sul numero di strade utilizzate all’interno del gruppo. Equivalentemente, questo () . significa che almeno archi, cioè veicoli, lasciano l’insieme

Mentre i CCC si concentrano sui veicoli che entrano in un insieme, i GSEC si concentrano sul numero di archi all’interno di un insieme usando la formula precedente.

Esempio … osservare i cicli isolati Per un insieme di 3 () = 1, nodi in cui possono esserci al massimo 2 archi interni; un terzo arco creerebbe un ciclo isolato proibito.

Equivalenza tra CCC e GSEC

CCC GSEC

Consideriamo i vincoli (1) nel CVRP (per ogni nodo il flusso entrante è uguale a uno) ∑ = 1(#,!)∈CB(!) #! ,