I problemi di instradamento (VRP - Vehicle Routing Problems) sono una tematica di rilievo nella gestione logistica sia nel settore privato che pubblico. Essi consistono nel determinare le rotte ottimali per i veicoli, data una serie di vincoli. I vincoli più comuni impongono che il carico trasportato da un singolo veicolo non sia superiore alla sua capacità totale, che la durata totale della rotta non ecceda un dato limite e che vengano rispettate le finestre temporali di servizio associate ad ogni nodo da visitare.
I problemi di instradamento su vaste aree geografiche prevedono che ai veicoli venga assegnata un'attività alla volta; su aree ridotte, le attività sono di durata inferiore (più brevi di un turno lavorativo) e una rotta è costruita come sequenza di attività.
Esistono differenti tipologie di problemi che devono essere risolti in tempo reale. Si elencano le applicazioni principali che motivano la nostra ricerca in campo VRP.

Gestione dinamica delle flotte
Alcune applicazioni su larga scala richiedono che i mezzi vengano impiegati per raccogliere o consegnare beni. Ottimizzare queste operazioni può condurre a un risparmio considerevole.

Sistemi di distribuzione vendor-managed
Nei sistemi vendor-managed le compagnie di distribuzione stimano i livelli di inventario del cliente in modo tale da rifornirlo prima dell'esaurimento scorte. La domanda è quindi nota a priori ed è considerata statica. In ogni caso, siccome la domanda è incerta, alcuni clienti (in genere una percentuale ridotta) possono esaurire le loro scorte e necessitare di forniture urgenti.

Corrieri
I corrieri che percorrono lunghe distanze devono raccogliere i colli in uscita prima di portarli presso un terminal remoto e consolidare i carichi. Allo stesso modo i carichi provenienti dai terminal remoti devono essere distribuiti localmente. Molte richieste sono dinamiche e devono essere soddisfatte nella stessa giornata, laddove possibile.

Compagnie di soccorso e riparazione
Alcune compagnie forniscono servizio di soccorso e riparazione (soccorso auto in avaria, riparazione dispositivi, ecc.).

Sistemi a chiamata
I sistemi di trasporto a chiamata forniscono servizio a persone attraverso coppie origine-destinazione. Gli utenti possono prenotare una corsa con almeno un giorno di anticipo (caso off-line) oppure con pochi minuti di anticipo (caso real-time).

Servizi di emergenza
I servizi di emergenza comprendono la polizia, i vigili del fuoco e le ambulanze. Per definizione tutti i clienti sono dinamici. Inoltre la frequenza della domanda è bassa e perciò i veicoli attraversano frequenti periodi di fermo macchina. In questo contesto è molto importante riposizionare i veicoli fuori servizio in modo tale da anticipare eventuali domande future ed evitare ore di punta e traffico..

Servizio taxi
In ogni servizio taxi la maggior parte degli utenti è dinamica. Così come nei servizi di emergenza, la ricollocazione dei mezzi fuori servizio è molto importante.