Algoritmo di generazione della colonna

Question

Voglio risolvere un VRP con un algoritmo di generazione di colonne. L'obiettivo del problema è la minimizzazione del panorama. ma c'è un punto nel calcolare l'ora di arrivo del veicolo in ogni nodo. il veicolo deve essere sincronizzato con un'altra modalità di trasporto come un treno il cui percorso è predeterminato prima di risolvere il suddetto VRP. il treno può passare da alcuni nodi che il veicolo passerà e in questi nodi l'orario di arrivo è massimo dell'orario di arrivo del treno e del veicolo. Voglio sapere come dovrei risolvere il sottoproblema dei prezzi?

Answer 1

Se ho capito bene il tuo problema, l'unica differenza con la versione iniziale (senza il treno) è che la funzione tempo non è additiva.

Ad esempio, supponiamo che il treno passi attraverso il nodo $j$ all'ora (data) $t_j$e stai calcolando un percorso $p$ il cui ultimo nodo è $i$. Il tempo totale accumulato su questo percorso è indicato da$\tau_p(i)$. $\Delta t_{ij}$ indica il tempo impiegato dal veicolo per passare $i$ per $j$. Se vuoi estendere il percorso e aggiungere node$j$, quindi il tempo totale accumulato per il percorso $p$, $\tau_p$, è aumentato come segue: $$ \tau_p(j) := \max\{ t_j, \tau_p(i) + \Delta t_{ij} \} $$

Se il treno arriva prima del veicolo, il tempo totale accumulato assume valore $\tau_p(i) + \Delta t_{ij}$, altrimenti, prende valore $t_j$.

Nota che è come avere finestre temporali sui nodi del treno, con solo un limite inferiore: puoi semplicemente aggiungere finestre temporali $[t_j, +\infty[$ sul nodo $j$ ed esegui il tuo algoritmo del percorso più breve con finestre temporali (se ne hai una a portata di mano).

In altre parole, la funzione di estensione della risorsa (tempo) non è additiva. Questo è gestito ad esempio da cspy , una grande libreria python che calcola i percorsi più brevi con vincoli di risorse, dove puoi inserire la tua regola di estensione delle risorse personalizzata (controlla i documenti in cui viene fornito un esempio di questo tipo). VRPy , una libreria python VRP per VRP si basa su cspy per calcolare i suoi percorsi più brevi per la generazione di colonne. Dato che VRPy gestisce le finestre temporali, ti sei procurato un buon punto di partenza!