Trovare una soluzione per un problema di assegnazione / instradamento di un mondo reale

2

Attualmente sto lavorando con una società di pulizia delle finestre che utilizza il proprio set di euristica per pianificare il suo piccolo set di pulitori per i lavori, in pratica un enorme foglio di calcolo con date e codici locali assegnati. Ho stupidamente detto che può essere fatto meglio.

Condizioni:

  • I lavori hanno una data di "ultima pulizia" e una regolarità della quale vengono puliti (mensilmente, ogni due mesi, ... ogni sei mesi). Questo dà una finestra di tempo in cui devono essere puliti (la loro data pianificata).
  • I lavori devono essere completati entro 3 giorni +/- dalla data prevista.
  • I lavori hanno un costo associato per eseguire il lavoro, che si traduce approssimativamente nel tempo necessario per completare il lavoro.

Nel complesso, l'obiettivo è di ridurre al minimo il tempo impiegato tra i lavori per più addetti alle pulizie, assicurandosi al tempo stesso che tutti i lavori vengano puliti entro le condizioni sopra indicate.

La società è già operativa e i clienti devono essere puliti. Mi piacerebbe essere in grado di utilizzare un metodo che lentamente convalida la pianificazione delle pulizie verso l'ottimale (cioè assumere lavori in anticipo / in ritardo in modo da adattarsi meglio a un programma ottimale) poiché imporlo dall'inizio comprometterebbe il loro funzionamento.

Ho cercato Strumenti di ottimizzazione di Google per suggerimenti. È simile a un problema di routing del veicolo, ma è difficile sapere quali lavori devono essere scelti per far parte del percorso in un particolare giorno. Se i lavori sono ordinati per data pianificata e poi estratti dalla coda, il sistema non migliorerà mai più di prima.

Qualsiasi suggerimento verso ulteriori letture o metodi proposti sarebbe molto apprezzato!

    
posta Louis JA 09.01.2018 - 10:22
fonte

2 risposte

6

HaHa :) suo NP-Hard

link

Ma il tuo problema principale sono gli umani coinvolti, che andranno in vacanza, si ammaleranno e cambieranno i turni a orari scomodi.

La soluzione migliore è dimenticarsi dell'ottimizzazione e andare per facilità d'uso. Automatizza i calcoli che le persone fanno nella loro testa per capire quale lavoro assegnare a chi, ad esempio ordinare gli elenchi in base alla distanza dall'ultimo lavoro, fare in modo che le cose diventino rosse se non ci sono abbastanza persone da girare, Lascia che l'utente trascini qualcosa e mostra il tempo di viaggio ecc.

Fai in modo che l'utente giochi e mostri loro i costi piuttosto che tentare di calcolare l'optimum e poi costringerli a cambiarlo perché non puoi tener conto dei fattori umani

    
risposta data 09.01.2018 - 11:10
fonte
1

Hai dato un'occhiata a genetica / algoritmi evolutivi , o ricottura simulata ? Oppure ottimizzazione delle colonie di formiche ? Oppure ottimizzazione degli sciami di particelle ?

Come ha trovato @Ewan, il problema è NP-difficile. Ma a quanto pare, molti problemi NP-hard possono essere risolti con risultati eccellenti usando questi algoritmi che approssimano solo la soluzione ottimale invece di trovare il vero optimum.

Sono abbastanza sicuro che troverai qualche algoritmo che trova una soluzione veramente eccellente per il tuo problema, anche se non è la soluzione ottimale. Richiederà molto lavoro. Non hai a che fare con il più semplice dei problemi di ingegneria del software qui.

Oh, ea seconda della complessità del problema, potrebbe essere necessario gettare un sacco di CPU al problema e attendere ancora un lungo periodo di tempo per il completamento dei calcoli. Questi algoritmi differiscono in quanto sono facili da parallelizzare. La ricottura simulata è difficile da parallelizzare, mentre gli algoritmi genetici ed evolutivi sono facili da parallelizzare.

    
risposta data 09.01.2018 - 14:28
fonte

Leggi altre domande sui tag