Algoritmo di raggruppamento

8

Abbiamo sviluppato un algoritmo che, a seconda del momento del check-in di alcuni lavoratori e del loro luogo di vita, calcola il modo di raggrupparli in alcuni veicoli e il percorso che deve essere seguito dai veicoli per trasportarli sul luogo di lavoro . Questo è stato realizzato utilizzando l'algoritmo TSP (Traveling Salesman Problem) e alcune altre personalizzazioni.

Vogliamo andare oltre e migliorarlo. Per il momento, la capacità dei posti dei veicoli è fissata a 4 (5 posti ma uno occupato dal conducente) e vogliamo rendere questa variabile "variabile". In altre parole, vogliamo, prima dell'esecuzione dell'algoritmo principale, determinare le combinazioni di veicoli (e i loro posti liberi) che potrebbero essere necessari. È importante sapere che quando parlo di veicoli parlo di tipi di veicoli, ad es. Il veicolo A è di 4 posti, il veicolo B è di 7 posti e così via. Quindi non sto parlando di avere una Audi A8 da 5 posti, Seat Ibiza da 5 posti, un Bus da 20 posti, per esempio.

Finora, quello che ho pensato è il seguente:

  1. Determina i gruppi di lavoratori.
  2. Determina quanti veicoli saranno necessari e i loro posti (gratuiti). Questo è quello che sto chiedendo in questa domanda [a].
  3. L'utente seleziona la combinazione preferita e continua.
  4. Applica l'algoritmo che è già stato sviluppato utilizzando la combinazione di veicoli e vedi se raggiunge una soluzione fattibile.

La mia domanda è come sviluppare l'algoritmo [a]. Il seguente esempio ti mostrerà il risultato dell'esecuzione di [a]:

Immagina di avere le seguenti persone da raggruppare in veicoli di 4, 7, 10 posti gratuiti.

Dopo l'esecuzione di [a], avremo come risultato:

  • G3 (2 lavoratori): un veicolo di 4 posti liberi (i veicoli con più posti liberi vengono scartati).
  • G2 (2 lavoratori): un veicolo di 4 posti liberi (i veicoli con più posti liberi vengono scartati).
  • G1 (9 lavoratori):

    • Opzione A: 3 veicoli di 4 posti.
    • Opzione B: 1 veicolo di 4 posti e un altro di 7.
    • Opzione C: 2 veicoli di 7 posti.
    • Opzione D: un veicolo di 10 posti.

Ho pensato ad un'approssimazione:

  • Crea i tipi di veicoli e aggiungili a una lista ordinata (i criteri di classificazione devono essere i posti).
  • Per ogni gruppo di lavoratori, fai:
    • Calcola le combinazioni [b].
  • Stampa i risultati sullo schermo.

Quindi il problema principale è come sviluppare [b].

Qualche suggerimento? Scusa se mi sono spiegato male.

    
posta russellhoff 13.08.2015 - 13:59
fonte

1 risposta

2

Ho trovato una soluzione possibile: usa il Problema di Soddisfazione dei Vincoli per risolverlo.

Ci sarà un vincolo per Gruppo, come segue:

importo dei lavoratori del gruppo < = somma per ogni veicolo (importo del veicolo X posti del veicolo)

L'unica variabile è la quantità del veicolo, il resto sono costanti. Quindi, nel mio esempio ci sarebbero i seguenti punti di contatto:

9 < = 4x + 7y + 10z
2 < = 4a + 7b + 10c
2 < = 4j + 7k + 10i

Ho trovato diverse librerie (JaCoP, Drools e OptaPlanner) e attualmente sto usando il primo. Ma non so come definire correttamente questi vincoli ...

    
risposta data 17.08.2015 - 10:25
fonte

Leggi altre domande sui tag