Vehicle routing
Da Wikipedia, l'enciclopedia libera.
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.
Indice |
[modifica] 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.
[modifica] 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 segienti)
- decomporre il VRP in più sottoproblemi TSP
[modifica] 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
[modifica] Algoritmo di Clarke & Wright
E'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.
