Vehicle routing problem

Da Wikipedia, l'enciclopedia libera.
Immagine che illustra il 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 sorgente]

Il VRP tratta la gestione di veicoli idealmente 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[modifica | modifica sorgente]

Un caso particolare di VRP è il famoso problema del commesso viaggiatore. In questo 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

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 sorgente]

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 sorgente]

È 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.

Riferimenti[modifica | modifica sorgente]

[1] Toth, P.; Vigo, D.; The Vehicle Routing Problem. Monographs on Discrete Mathematics and its Applications, SIAM,(2002).