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 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
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 (vedi paragrafi seguenti)
- 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
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
à
Bibliografia
- Toth, P.; Vigo, D.; The Vehicle Routing Problem. Monographs on Discrete Mathematics and its Applications, SIAM,(2002).