Pianificazione dei veicoli/pianificazione dell'algoritmo delle risorse

Question

Il mio primo post qui - sperando che tu possa aiutarmi a progettare un algoritmo che ho preso in considerazione per un po 'di tempo - non so quale approccio adottare (VRPTW o pianificazione delle risorse o altro interamente !?)

Per metterlo in un vero e proprio esempio di parola, abbiamo un sacco di rifiuti di giardino in un piccolo numero di luoghi (in genere meno di 5). I rifiuti devono essere trasportati in altri luoghi entro determinati intervalli di tempo. Per spostare i rifiuti del giardino abbiamo rimorchi, che devono essere rimorchiati dalle auto. I rifiuti del giardino possono essere lasciati cadere nel deposito rifiuti in determinati orari (finestre temporali). In alcuni siti possiamo lasciare il trailer per essere riempiti o svuotati da persone lì, ma in altri luoghi il conducente dell'auto deve farlo da solo e l'auto deve rimanere lì. Tutti i tempi possono essere calcolati (cioè tempi di carico/scarico, tempi di transito ecc.). Le auto possono spostarsi tra i siti senza un rimorchio, i rimorchi possono essere rimorchiati vuoti, ma i rimorchi non possono spostarsi da un luogo all'altro.

Il nostro obiettivo è quello di garantire tutti i carichi del rimorchio dei rifiuti trasportati, mentre

• riducendo al minimo il numero di rimorchi e macchine in uso
• incontro tutte le finestre temporali per cadere rifiuti
• “bilanciamento” del rimorchi - vale a dire alla fine della giornata abbiamo tanti rimorchi in ogni luogo com'erano all'inizio del giorno

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

Un altro metodo che ho considerato era considerare prima le auto. Potrei quindi selezionare il primo compito e creare un grafico di tutte le attività possibili dopo questo. Se poi ho scelto il percorso più lungo attraverso il grafico che 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à sono state servite. Dovrei quindi eseguire questo elenco di carichi di rimorchio per calcolare il numero di rimorchi richiesti.

Qualsiasi idea di approccio sarebbe apprezzata!

Answer 1

Sono d'accordo con Jiri ...vuoi un algoritmo euristico che sia ragionevolmente vicino a una soluzione accettabile rapidamente e poi raffini da lì.

Ho lavorato in aziende che avevano software di instradamento delle consegne e l'approccio che hanno adottato è stato quello di utilizzare un algoritmo genetico per risolvere problemi molto simili, benché su scala molto più ampia. Prendi un look here se non hai familiarità con l'approccio. Da quel sito:

1. [Start] Genera popolazione casuale di n cromosomi (soluzioni adeguate per il problema)
2. [Fitness] valutare le f Fitness (x) di ciascun cromosoma x nella popolazione

3. [nuovo popolazione] Creare una nuova popolazione ripetendo seguenti operazioni fino a quando la nuova popolazione è completa

   [Selezione] Selezionare due cromosomi genitore da una popolazione in base alla loro forma fisica (la forma fisica migliore, la più grande possibilità di essere selezionati)

   012.

   [Crossover] Con una probabilità di attraversamento incrociare i genitori per formare una nuova progenie (bambini). Se non è stato eseguito alcun crossover, la prole è una copia esatta dei genitori.

   [Mutazione] Con una probabilità di mutazione si modifica la nuova discendenza in ciascun locus (posizione nel cromosoma).

   [Accettare] Mettere nuova progenie in una nuova popolazione

4. [Sostituire] Utilizzare nuova popolazione generato per un ulteriore periodo di algoritmo
5. [Test] Se la condizione finale è soddisfatta, si fermano, e restituire il migliore soluzione in popolazione attuale
6. [loop] Andare al punto 2

il trucco per questo è la codifica dei vincoli in un "cromosoma" e scrivendo la funzione "fitness". La funzione fitness deve prendere input dei risultati di una potenziale soluzione e sputare un punteggio di quanto sia buona una soluzione o lanciarla se viola uno dei vincoli.

Come accennato da Jiri, il vantaggio di questa soluzione è che fornisce una soluzione praticabile, anche se forse non la migliore, molto rapidamente e più a lungo si lascia correre, migliore è la soluzione.

Answer 2

Stiamo parlando di un algoritmo NP completo di sicuro, al di là di un certo numero di automobili e rimorchi, questo non sarà un compito in cui si otterrebbe la migliore soluzione da tutte le possibili soluzioni e quindi si può scartarla e andare di nuovo per evitare il percorso più lungo come suggerisci. Se progettate il vostro algoritmo in questo modo, è molto probabile che un giorno aggiungerete un po 'più macchine e rimorchi e non finirà mai di calcolare la soluzione.

Probabilmente vorrai andare con un algoritmo che possa generare abbastanza velocemente 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 un po 'di% entro il quale desideri che la tua soluzione provenga da una soluzione ideale e semplicemente prendi la prima soluzione che ha la metrica entro i limiti. Questo ha il vantaggio aggiunto che se questo algoritmo impiega troppo tempo per essere calcolato e lo si interrompe, è comunque possibile utilizzare la soluzione con la metrica calcolata più bassa, anche se non è nei limiti previsti.

Non sono sicuro di quale approccio adottare per risolvere il problema stesso. Suggerirei di leggere alcuni articoli dopo aver cercato su acm portal. Direi che UPS e Fedex probabilmente hanno problemi simili, se li aggiungi come parole chiave a una ricerca su google, potresti ottenere risultati più utili.

Answer 3

Sono tendenzialmente d'accordo con Robert. Questo mi sembra un ottimo candidato per una tecnica di ottimizzazione evolutiva come l'implementazione dell'algoritmo genetico che descrive.

Ho avuto anche molto successo su alcuni problemi con l'ottimizzazione delle particelle (PSO). Fondamentalmente, si può pensare a ciascun genoma come una particella in uno spazio multi-dimensionale. Le coordinate della particella sono i parametri per il calcolo (funzione fitness). Ogni particella viene avviata a caso con una velocità casuale. Per ogni iterazione della simulazione, aggiorni la posizione di ogni particella con il suo vettore di corsa corrente, e poi aggiungi componenti di altri vettori come: direzione della particella migliore fino a quel momento, direzione della migliore particella di sempre, direzione verso un gruppo locale meglio ecc ...

All'inizio può sembrare piuttosto scoraggiante implementare un GA o un PSO ma vi assicuro che è facile scrivere un piccolo framework che astrae 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, di solito inizio con un problema con 2 parametri (probabilmente una semplificazione del tuo problema, o posizioni X e Y su un'immagine), in modo che io possa facilmente visualizzare e modificare l'algoritmo in modo da ottenere buon comportamento brulicante. Quindi lo ridimensiono a più dimensioni.

Mi piace questo approccio perché mi consente di ottimizzare facilmente i problemi che hanno parti piuttosto complesse e complesse rispetto all'affermazione del problema reale (come le auto ei rimorchi).

Inoltre, perché le tecniche evolutive sono attraenti è perché è possibile dedicare una parte fissa del tempo alla simulazione e ottenere la risposta migliore fino a quando si decide di interrompere.

In base alla mia esperienza, si tende a dedicare più tempo a modificare i parametri su GA o PSO (una volta implementata) come si scriverebbe una soluzione euristica codificata, ma il vantaggio è quello di modificare la strategia per la ricerca della soluzione richiede in genere 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 fatemi un grido se avete bisogno di una guida sulla progettazione dei framework generici per uno dei due algoritmi. Devo precisare che ci sono anche molti buoni framework gratuiti di terze parti. A volte mi piace codificare il mio perché capisco ogni aspetto dell'algoritmo e so dove posso adattare la strategia.

Answer 4

Approccio generale:

Dal momento che il problema è piccolo, vorrei suggerire un approccio in cui si aggiungono le automobili e rimorchi fino ad ottenere una soluzione fattibile, piuttosto che cercare di ridurre al minimo le automobili e rimorchi.

Solving:

Ho avuto meno successo a gas con vincoli e ancor meno successo sul gas con vincoli sulle variabili intere (ad esempio il numero di rimorchi in una posizione). Può essere che la programmazione dei vincoli sia un approccio migliore poiché si desidera generare una soluzione fattibile per un dato numero di automobili e rimorchi piuttosto che cercare di ridurre al minimo la distanza percorsa.

Osservazione:

Sei risolvere il problema su una rete in cui le ultime mosse possono essere a trasferirsi un rimorchio vuoto.

Buona fortuna!

Answer 5

Ricerca locale sono un'alternativa agli algoritmi genetici. Nel Concorso internazionale di orari ,, gli algoritmi di ricerca locale (come la ricerca tabu e la ricottura simulata) battono chiaramente le voci dell'algoritmo genetico (da 1 a 4 per LS rispetto a 5o per GA nella traccia 1 su circa 80 concorrenti IIRC).

Inoltre, date un'occhiata ad alcune delle librerie là fuori, come ad esempio OptaPlanner (Tabu Search, Simulated Annealing, Late Acceptance, open source, java), JGap (algoritmi genetici, open source, java), OpenTS (Tabu Ricerca, ...