Schedulazione di più veicoli di deposito

Question

Ho giocato con algoritmi e ILP per il problema di scheduling di veicoli a singolo deposito (SDVSP) e ora desidero estendere le mie conoscenze al problema di scheduling multipot Depot (MDVSP), come vorrei utilizzare questa conoscenza in un mio progetto.

Per quanto riguarda la domanda, ho trovato e implementato diversi algoritmi per MDSVP. Tuttavia, una domanda che mi interessa molto è come determinare la quantità di depositi necessari (e le posizioni in misura maggiore). Tristemente non sono stato in grado di trovare risorse realmente che non presuppongono/richiedono che i depot siano impostati. Quindi la mia domanda sarebbe: come potrei avvicinarmi a un MDVSP in cui posso determinare la quantità e le posizioni dei depositi?

(Edit) per chiarire: Assumere ci viene data una serie di viaggi di T , T ... T _n come di solito in uno SDVSP o MDVSP. È possibile guidare più volte in successione prima di tornare in un deposito. L'uscita e il ritorno ai depositi di solito avvengono solo all'inizio e alla fine della giornata. Ma come estensione dei normali problemi, ora possiamo determinare l'ammontare e le posizioni dei nostri depositi, contrariamente ad avere i depot impostati.

L'obiettivo è trovare una soluzione in cui tutti i viaggi siano guidati con il minimo costo. Il costo è costituito dalla quantità di deadhead (la distanza che l'auto deve percorrere tra i viaggi e da e verso i depositi), un costo fisso K per auto e un costo fisso C per depositi.

Spero che questo chiarisca un po 'la domanda.

Answer 1

L'approccio standard prevede l'aggiunta di | V | variabili binarie in ILP, una per ogni nodo dove x_i = 1 se v_i è un depot e 0 altrimenti.

Tuttavia, il modo in cui la domanda è attualmente articolata, tutti i valori x_i saranno pari a zero, poiché non vi è alcun "vantaggio" nel rendere il nodo un deposito e il costo totale = (altri fattori di costo) + sum_i (x_i) * FIXED_COST_PER_DEPOT.

Forse la domanda deve essere aggiornata con qualche altro vincolo sulla gamma dell'auto. Ad esempio, una macchina può solo andare così e così miglia prima di tornare a un deposito.