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[modifica | modifica wikitesto]
Il VRP tratta la gestione di veicoli idealmente da ogni punto di vista. Questa 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[modifica | modifica wikitesto]
Un caso particolare di VRP è il famoso problema del commesso viaggiatore. In questo caso si ipotizza:
- un solo veicolo
- capacità infinita del veicolo
È possibile:
- estendere i metodi di soluzione del TSP al VRP
- decomporre il VRP in più sottoproblemi TSP
Il problema è risolvibile in tempi polinomiali solamente per un massimo di due nodi, uno di partenza e uno di destinazione.
Se si chiede al calcolatore l'itinerario più breve/economico per collegare numerose località, la soluzione non può arrivare in tempi umani, causa l'assenza di un algoritmo per risolvere efficacemente il problema.
Metodi euristici per il VRP[modifica | modifica wikitesto]
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[modifica | modifica wikitesto]
È un metodo costruttivo per la soluzione di VRP base; esso è chiamato anche metodo dei risparmi (savings), proprio perché l'obiettivo è massimizzare il risparmio dei costi ottenuto dal collasso di più percorsi.
Bibliografia[modifica | modifica wikitesto]
- Toth, P.; Vigo, D.; The Vehicle Routing Problem. Monographs on Discrete Mathematics and its Applications, SIAM,(2002).