Vehicle routing problem
Il Vehicle routing problem (VRP) è una classe di problemi nell'ambito della ricerca operativa. Questi problemi trattano tutti gli aspetti della gestione di una flotta dei veicoli nell'ambito della logistica.
Generalità del VRP
Il VRP tratta la gestione di veicoli idelamente da ogni punto di vista. Questi classe di problemi comprende una casistica molto varia: questo motivo fa sì che tali problemi siano difficilmente risolubili all'ottimo. Il caso più generale prevede la pianificazione del percorso di veicoli in presenza di:
- consegne multiple
- più veicoli.
Ogni veicolo:
- può avere più clienti.
- ha capacità di trasporto limitata
Ogni cliente:
- ha una domanda di un certo prodotto.
Obiettivo:
- minimizzare un costo associato al percorso del veicolo (distanza, tempo, ecc.)
Questi metodi devono:
- assegnare un certo insieme di clienti ad ogni veicolo.
- elaborare per ogni veicolo un percorso.
Problema del commesso viaggiatore
Un caso particolare di VRP è il famoso problema del commesso viaggiatore. In quasto caso si ipotizza:
- un solo veicolo
- capacità infinta del veicolo
È possibile:
- estendere i metodi di soluzione del TSP al VRP (vedi paragrafi seguenti)
- decomporre il VRP in più sottoproblemi TSP
Metodi euristici per il VRP
La grande complessità dei problemi di VRP rende molto difficile, o al limite impossibile, il calcolo della soluzione ottima. Perciò, si usa procedere attraverso euristiche, proprio come nel più semplice caso del TSP. È possibile applicare al VRP:
- euristiche costruttive: costruiscono un set valido di soluzioni ampliato ad ogni passo dell'algoritmo
- euristiche iterative: costruiscono un set completo di soluzioni che viene migliorato iterativamente ad ogni passo dell'algoritmo
Algoritmo di Clarke & Wright
È un metodo costruttivo per la soluzione di VRP base; esso è chiamato anche metodo dei risparmi, proprio perché l'obiettivo è massimizzare il risparmio dei costi ottenuto dal collasso di più percorsi.
Rifermenti
[1] Toth, P.; Vigo, D.; The Vehicle Routing Problem. Monographs on Discrete Mathematics and its Applications, SIAM,(2002).