Algoritmi euristici per il VRP, Giuseppe Bruno « Ricerca Operativa II « Ingegneria

Argomenti della lezione

Definizioni generali
Algoritmi costruttivi
Algoritmi migliorativi
Algoritmi Cluster First-Route Second
Algoritmi Route First-Cluster Second

Definizioni generali

Rappresentazione su grafo

Si consideri un grafo G=(V,A) con

V={v₁,..,v_n}insieme di n nodi rappresentativo di località, A={(v_i,v_j): v_i,v_j∈V} insieme archi che identificano i possibili collegamenti tra località.
A ciascun arco è associato un costo c_ijche può indicare la lunghezza del collegamento, il tempo o il costo per coprirlo.

Si parla di problemi a

copertura dei nodi (node covering) se i servizi si intendono localizzati in corrispondenza dei nodi;
copertura di archi (arc covering) se i servizi si immagino distribuiti sugli archi.

Obiettivo: individuare un insieme di itinerari che visitino i nodi o gli archi presso i quali sono presenti i servizi.

Definizioni generali (segue)

Complessità del problema

Il VRP appartiene alla classe dei problemi NP-hard per i quali, cioè, non esiste un algoritmo in grado di risolvere il problema in tempo polinomiale.

Anche per il VRP una soluzione ammissibile è rappresentata da una permutazione del tipo

d-A-C-F-d-B-D-E-d-G-H

essendo d il nodo deposito.

Definizioni generali (segue)

Algoritmi euristici per il VRP

Si possono distinguere

Algoritmi costruttivi
- Algoritmo nearest neighbour
- Algoritmi di inserimento
- Algoritmi di Cluster-First Route Second
- Algoritmi di Route First-Cluster Second
Algoritmi migliorativi
Metaeuristiche

Algoritmi costruttivi per il VRP

Metodi orientati alla individuazione (costruzione) di una soluzione ammissibile.

Passi fondamentali di un algoritmo costruttivo:

1. Inizializzazione
Si sceglie un elemento di partenza per la costruzione della soluzione parziale S.

2. Selezione nuovo elemento da aggiungere alla soluzione
Si individua il criterio di selezione di un nuovo elemento da aggiungere alla soluzione parziale S.

3. Criterio di arresto
Se S è completa e, quindi, ammissibile la procedura si interrompe altrimenti si ritorna al passo 2.

Algoritmi costruttivi per il VRP (segue)

Gli algoritmi costruttivi per il VRP (nearest neighbour – algoritmi di inserimento – algoritmo di saving) possono essere considerati degli adattamenti degli stessi algoritmi per il TSP in modo da poter considerare i vincoli di capacità.

Essi possono essere implementati in modo:

Sequenziale se si provvede alla costruzione di un circuito alla volta;
Parallelo se si provvede alla costruzione di più circuiti alla volta.

Algoritmi costruttivi per il VRP (segue)

Algoritmo nearest neighbor (vicino più vicino)

È un algoritmo sequenziale che funziona in modo simile alla versione illustrata per il TSP.

A partire dal deposito, si costruisce un circuito alla volta aggiungendo, alla generica iterazione, il nodo ammissibile* più vicino all’ultimo nodo inserito nel circuito;

Quando non esistono più nodi ammissibili, si unisce l’ultimo nodo al deposito e si riprende la costruzione di un nuovo circuito.
(*) si intende per nodo ammissibile un nodo non ancora inserito in alcun circuito, la cui aggiunta al circuito in costruzione non viola il vincolo sulla capacità Q.

Algoritmi costruttivi per il VRP (segue)

Algoritmi di inserimento

Nella versione sequenziale funzionano come nel TSP: a partire dal deposito, si costruisce un circuito alla volta scegliendo un nodo ammissibile (selezione) ed inserendolo nel circuito in costruzione (inserimento). In assenza di nodi ammissibili, si unisce l’ultimo nodo al deposito e si riprende la costruzione di un nuovo circuito.

Nella versione parallela si costruiscono contemporaneamente m‘ circuiti attraverso l’inserimento di un nuovo nodo in uno dei circuiti in costruzione; quindi si seleziona un nodo non appartenente ad alcuno dei circuiti (selezione) e lo si inserisce in una posizione all’interno di uno dei circuiti in costruzione (inserimento).

Anche in questo caso è possibile distinguere tra algoritmi:

Nearest insertion;
Cheapest insertion;
Random insertion.

Algoritmi costruttivi per il VRP (segue)

Algoritmi Cluster First Route Second

Si basano sulla scomposizione del problema in due fasi successive.
La prima fase di clustering individua gruppi di nodi (clusters) tali che la somma delle domande associate ai nodi di ciascun gruppo non ecceda la capacità dei veicoli.
Nella fase di routing si risolve un TSP per ciascuno dei clusters di nodi individuato con l’aggiunta del deposito.

L’algoritmo sweep di Gillet e Miller risolve un VRP in cui i nodi sono posizionati in un piano e le distanze tra essi siano euclidee.

Se il deposito d corrisponde all’origine di un sistema di coordinate polari (ρ, θ), posta a caso una direzione θ=0, ad ogni nodo i è associabile una coppia (ρ_i, θ_i).

Algoritmi costruttivi per il VRP (segue)

Algoritmi Route First Cluster Second

Si basano, al contrario, su una prima fase di routing nella quale si risolve un TSP con riferimento a tutti i nodi domanda. In questo modo si individua un circuito (giant tour) che non rispetta il vincolo sulla capacità.

La seconda fase di clustering riguarda la scomposizione del giant tour al fine di soddisfare i vincoli di capacità. A tale scopo si considera un verso di percorrenza arbitrario e si sceglie a caso un nodo di riferimento i*. A partire da i* e secondo il verso di percorrenza, si raggruppano i nodi in modo tale che la somma delle domande associate a questi nodi non ecceda la capacità dei veicoli.

Infine si cancellano gli archi che collegano nodi di gruppi differenti e si chiudono i percorsi collegando i nodi estremi direttamente al deposito, formando così un insieme di circuiti.

Algoritmi costruttivi per il VRP (segue)

Algoritmi migliorativi per il VRP

Si basa sulla procedura di saving per il TSP, con la differenza che due nodi estremi possono essere uniti se il nuovo circuito che si viene a creare sia tale da non violare il vincolo sulla capacità Q.

Poiché la soluzione iniziale a stella è una soluzione ammissibile, l’algoritmo rappresenta, in pratica, una procedura migliorativa.