Progettazione di algoritmi di routing dei veicoli/pianificazione delle risorse

https://stackoverflow.com/questions/1925439

20-09-2019
|

Domanda

Il mio primo post qui – sperando che tu possa aiutarmi con la progettazione di un algoritmo che sto considerando da un po' di tempo – non sono sicuro di quale approccio adottare (VRPTW o pianificazione delle risorse o qualcos'altro completamente!?)

Per dirla con un esempio concreto, abbiamo un sacco di rifiuti da giardino in un numero limitato di luoghi (di solito meno di 5).I rifiuti devono essere tutti trasportati in altri luoghi entro determinati tempi.Per spostare i rifiuti del giardino disponiamo di rimorchi, che devono essere trainati dalle auto.I rifiuti del giardino possono essere conferiti al deposito rifiuti solo in determinati orari (finestre orarie).In alcuni luoghi possiamo lasciare il rimorchio affinché venga riempito o svuotato da persone presenti, ma in altri luoghi il conducente dell'auto deve farlo da solo e l'auto deve rimanere lì.Tutti i tempi possono essere calcolati (ad es.tempi di carico/scarico, tempi di transito ecc.).Le auto possono spostarsi tra i siti senza rimorchio, i rimorchi possono essere rimorchiati vuoti ma i rimorchi non possono spostarsi da soli tra i luoghi.

Il nostro obiettivo è garantire che tutti i rimorchi carichi di rifiuti vengano trasportati durante il trasporto

riducendo al minimo il numero di rimorchi e automobili in uso
rispettare tutte le finestre temporali per conferire i rifiuti
“bilanciare” i rimorchi – cioèalla fine della giornata abbiamo in ogni luogo tanti trailer quanti ce n'erano all'inizio della giornata

Ho pensato di avvicinarmi a questo come un algoritmo di pianificazione delle risorse, ma non sono sicuro di come gestire il "bilanciamento" dei trailer.

Un altro metodo che ho preso in considerazione è stato quello di considerare prima le auto.Potrei quindi selezionare la prima attività e successivamente creare un grafico di tutte le attività realizzabili.Se poi scegliessi il percorso più lungo attraverso il grafico, servirebbe il numero massimo di carichi del rimorchio.Potrei quindi rimuovere queste attività dall'elenco delle attività e ripetere fino a quando tutte le attività non saranno state eseguite.Dovrei quindi esaminare l'elenco dei carichi del rimorchio per calcolare il numero di rimorchi richiesti.

Qualsiasi pensiero sull'approccio sarebbe apprezzato!

Soluzione

Sono d'accordo con Jiri ... vuoi un algoritmo euristico che si avvicina ragionevolmente con una soluzione accettabile rapidamente e poi si perfeziona da lì.

In precedenza ho lavorato presso le aziende che avevano un software di routing di consegna e l'approccio che adottarono era utilizzare un algoritmo genetico per risolvere un problema molto simile, sebbene molto più ampio. Prendere un guarda qui Se non hai familiarità con l'approccio. Da quel sito:

Avvia] Genera popolazione casuale di n cromosomi (soluzioni adatte per il problema)
Fitness] Valuta il fitness f (x) di ciascun cromosoma x nella popolazione
Nuova popolazione] Crea una nuova popolazione ripetendo i seguenti passaggi fino al completamento della nuova popolazione

Selezione] Seleziona due cromosomi genitori da una popolazione in base alla loro forma fisica (la migliore forma fisica, maggiore è la possibilità di selezionare)

Crossover] Con una probabilità crossover incrociata sui genitori per formare una nuova prole (bambini). Se non è stato eseguito alcun crossover, la prole è una copia esatta dei genitori.

Mutazione] con una probabilità di mutazione muta la nuova prole in ciascun locus (posizione nel cromosoma).

Accettazione] Metti una nuova prole in una nuova popolazione
Sostituisci] Utilizzare una nuova popolazione generata per un'ulteriore serie di algoritmo
Test] Se la condizione finale è soddisfatta, fermarsi e restituire la soluzione migliore nella popolazione attuale
Loop] Vai al passaggio 2

Il trucco è codificare i tuoi vincoli in un "cromosoma" e scrivere la funzione "fitness". La funzione di fitness deve prendere input dei risultati di una potenziale soluzione e sputare un punteggio di quanto sia buona una soluzione o buttarla fuori se viola uno qualsiasi dei vincoli.

Come menzionato da JIRI, il vantaggio di questa soluzione è che viene visualizzato con un lavoro praticabile, anche se forse non il migliore, rispondi molto rapidamente e più a lungo lo lasci correre, migliore è la soluzione.

Altri suggerimenti

Stiamo sicuramente parlando di un algoritmo NP completo qui, al di là di un certo numero di auto e rimorchi questo non sarà un compito in cui otterresti la soluzione migliore tra tutte le soluzioni possibili e poi sarai in grado di scartarla e ricominciare per evitare il percorso più lungo come suggerisci.Se progetti il tuo algoritmo in questo modo, è molto probabile che un giorno aggiungerai un po' più di auto e rimorchi e non finirà mai di calcolare la soluzione.

Probabilmente vorrai utilizzare un algoritmo che possa generare in modo ragionevolmente veloce una soluzione sufficientemente buona del problema.Assicurati di creare una metrica per la qualità della soluzione, ottieni un buon modo per stimare il valore della metrica per una soluzione ideale, quindi imposta una percentuale entro la quale desideri che la tua soluzione provenga da una soluzione ideale e semplicemente prendi la prima soluzione che ha la metrica entro i limiti.Ciò ha l'ulteriore vantaggio che, se l'algoritmo impiega troppo tempo per il calcolo e lo interrompi, puoi comunque utilizzare la soluzione con la metrica calcolata più bassa, anche se non rientra nei limiti previsti.

Tuttavia, non sono sicuro dell'approccio da adottare per risolvere il problema stesso.Suggerirei di leggere alcuni articoli dopo aver effettuato la ricerca portale acm.Presumo che UPS e Fedex abbiano probabilmente problemi simili, se li aggiungi come parole chiave a una ricerca su Google, potresti ottenere risultati più utili.

Tendo ad essere d'accordo con Robert. Questo mi sembra un candidato davvero eccezionale per una tecnica di ottimizzazione evolutiva come l'implementazione dell'algoritmo genetico che descrive.

Ho anche avuto un ottimo successo su alcuni problemi con l'ottimizzazione dello sciame di particelle (PSO) .Basicamente, puoi pensare a ciascun genoma come a una particella in uno spazio multidimensionale. Le coordinate della particella sono i parametri del calcolo (funzione di fitness). Ogni particella viene avviata in modo casuale con una velocità casuale. Per ogni iterazione della simulazione, si aggiorna la posizione di ciascuna particella con il suo vettore di viaggio attuale, quindi aggiungi componenti di altri vettori come: direzione alla migliore particella finora, direzione per la migliore particella di sempre, direzione per un gruppo locale Best ecc ...

All'inizio può sembrare piuttosto scoraggiante implementare un GA o un PSO, ma ti assicuro che è facile scrivere un piccolo framework che estrae l'algoritmo (GA/PSO) dal dominio del problema reale che stai cercando di ottimizzare. Puoi sempre tornare a Wikipedia per i dettagli degli algoritmi.

Una volta che ho un framework, normalmente inizio con un problema di 2 parametri (probabilmente una semplificazione del tuo problema o le posizioni X e Y su un'immagine), in modo da poter visualizzare e modificare facilmente l'algoritmo in modo da ottenere un buon comportamento di sciame. Quindi lo scavo fino a più dimensioni.

Mi piace questo approccio perché mi permette di ottimizzare facilmente per problemi che hanno parti piuttosto complesse e complesse alla dichiarazione del problema reale (come le auto e i rimorchi).

Inoltre, perché le tecniche evolutive sono attraenti è perché puoi dedicare una parte fissa del tempo alla simulazione e prendere la risposta migliore finora quando decidi di fermarti.

Nella mia esperienza, tendi a dedicare tutto il tempo a modificare i parametri a GA o PSO (una volta che hai un'implementazione) in quanto scrivi una soluzione euristica con codice duro, ma il vantaggio è che per cambiare la strategia per trovare la soluzione in genere Richiede solo modifiche ai parametri o lo scambio di algoritmi molto ben definiti con un'altra implementazione, invece di codificare una strategia completamente diversa per risolvere il problema euristicamente da zero.

Per favore, dammi un grido se hai bisogno di una guida sulla progettazione dei quadri generici per uno dei due algoritmi. Devo sottolineare che otterrai anche molti buoni framework di terze parti gratuiti. A volte mi piace codificare il mio perché capisco ogni aspetto dell'algoritmo e so dove posso regolare la strategia.

Approccio generale:

Poiché il problema è piccolo, suggerirei un approccio in cui aggiungi auto e rimorchi fino a ottenere una soluzione fattibile piuttosto che cercare di ridurre al minimo le auto e i rimorchi.

Risoluzione:

Ho avuto meno successo sul gas con vincoli e ancora meno successo sul gas con vincoli sulle variabili intera (ad esempio il numero di rimorchi in una posizione). Può darsi che la programmazione dei vincoli sia un approccio migliore poiché vuoi solo generare una soluzione fattibile per un determinato numero di auto e rimorchi piuttosto che cercare di ridurre al minimo la distanza percorsa.

Osservazione:

Stai risolvendo il problema su una rete in cui le ultime mosse potrebbero essere quella di trasferire un rimorchio vuoto.

Buona fortuna !

Ricerca locale sono un'alternativa agli algoritmi genetici. Nel International TimeTabling Competition 2007, Gli algoritmi di ricerca locali (come la ricerca tabu e la ricottura simulata) hanno chiaramente battuto le voci di algoritmo genetico (1 al 4 ° posto per LS rispetto al 5 ° posto per GA nella traccia 1 su circa 80 concorrenti IIRC).

Inoltre, dai un'occhiata ad alcune delle biblioteche là fuori, come Optaplanner (Ricerca tabu, ricottura simulata, accettazione tardiva, open source, java), jgap (algoritmi genetici, open source, java), opents (tabu search,

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow