Algoritmo di filiale e prezzo

Question

Il ramo e il prezzo possono essere un buon approccio risolutivo per un problema di instradamento con la funzione obiettivo min-max? Ad esempio, riducendo al minimo la lunghezza massima di qualsiasi percorso del veicolo in un VRP.

In letteratura, non ho mai visto che questo approccio risolutivo sia stato utilizzato per risolvere un problema del genere. Per quanto ne so, questo approccio viene utilizzato per risolvere i VRP riducendo al minimo il costo totale.

Answer 1

Essere un approccio buono o cattivo dipenderà da diversi fattori, ad esempio:

• la dimensione delle istanze
• tempo disponibile per trovare una soluzione (questo tende a essere una questione importante nelle applicazioni di instradamento dei veicoli)
• potenza di calcolo
• quale livello di qualità della soluzione si qualifica come sufficientemente buono

Guarda questo lavoro di Yu, Nagarajan e Shen sul VRP di makepan minimo con vincoli di compatibilità, poiché è un problema simile che è stato studiato prima di utilizzare il branch-and-price come approccio per risolvere una variante VRP di makepan. Ha funzionato abbastanza bene. Si noti che nel loro caso, hanno progettato un algoritmo di approssimazione per accelerare il tempo di esecuzione di B&P.

Suggerisco il seguente esperimento:

Primo passo: seguendo la risposta di @ RobPratt alla tua precedente domanda sulla minimizzazione del makepan in VRP :

Permettere $d_i$ essere la domanda per il cliente $i\in N$, permettere $V=\{1,\dots,K\}$ sia l'insieme dei veicoli, e lascia $P$ essere l'insieme delle colonne, dove ogni colonna corrisponde ad un sotto-giro ammissibile a partire dal deposito, con variabili d'arco $x_{i,j}$ e variabili nodo $y_i$. Permettere$z$essere il makepan. Il problema principale è finito$z$ e $\lambda$è la seguente, con due variabili tra parentesi: \ begin {align} & \ text {minimizza} & z \\ & \ text {soggetto a} & z - \ sum_ {p \ in P} \ left (\ sum_ {i, j } c_ {i, j} x_ {i, j} ^ p \ right) \ lambda ^ p_v & \ ge 0 && \ text {for$v\in V$} && (\ pi_v \ ge 0) \\ && \ sum_ {v \ in V} \ sum_ {p \ in P} y_i ^ p \ lambda ^ p_v & \ ge 1 && \ text {per $i\in N$} &&(\testo{$\alpha_i \ge 0$}) \\ && - \ sum_ {p \ in P} \ lambda ^ p_v & \ ge -1 && \ text {per $v\in V$} &&(\testo{$\beta_v \ge 0$}) \\ && \ lambda ^ p_v & \ ge 0 && \ text {per $v\in V$ e $p\in P$} \ end {align}

Il sottoproblema di generazione della colonna è finito $x$ e $y$ per ciascuno $v\in V$ è quindi ridurre al minimo il costo ridotto di $\lambda^p_v$. Cioè, minimizza$$\pi_v \sum_{i,j} c_{i,j} x_{i,j} - \sum_{i \in N} \alpha_i y_i + \beta_v$$ soggetto a $(x,y)$ formando un subtour fattibile a partire dal deposito, con $\sum_i d_i y_i \le L$, dove $L$ è la capacità di ogni veicolo.

Come indicato qui, il sottoproblema può essere riformulato come percorso elementare più breve: dividere il depot in una sorgente e un sink e spostare i pesi dei nodi sugli archi: $\pi_v c_{i,j}−\alpha_i$ per il peso dell'arco $(i,j)$ nel sottoproblema elementare del cammino minimo.

Secondo: implementare il metodo sopra. Consiglio di provare a usare VRPy, come suggerito da Kuifje qui . In questo modo non dovrai implementare da zero tutte le operazioni di filiale e di prezzo. Passaggi dettagliati:

1. Dai un'occhiata alla documentazione del progetto.
2. Dai un'occhiata al codice in GitHub.
3. Crea un fork o scarica il progetto come .zip, in modo da poter apportare modifiche localmente.
4. Modificare il codice relativo al problema secondario , in modo che il depot venga suddiviso come spiegato sopra.
5. Esegui gli esperimenti, puoi seguire le istanze di esempio dalla documentazione come qui e qui .
6. Facci sapere come ha funzionato. E ricorda di riconoscere VRPy e i suoi sviluppatori nel tuo lavoro (che si tratti di un rapporto di progetto, tesi, pubblicazione, ecc.), Oltre a rispettare i termini della licenza della libreria rispetto alle modifiche.

Answer 2

VRPy (v0.3.0) ora supporta questa opzione: tutto ciò che devi fare è impostare l' minimize_global_spanopzione su Truequando istanziare l' VehicleRoutingProblemoggetto:

prob = VehicleRoutingProblem(G, num_vehicles=2, minimize_global_span=True)
prob.solve()

Ovviamente il tuo grafico $G$ deve essere ben definito in primo luogo.

Viene implementata la formulazione proposta da @RobPratt. Se giochi con qualche problema di giocattolo, vedrai che la formulazione è debole rispetto a quella classica (senza il makepan). È facile vedere che il vincolo$$ z - \sum_{p\in P} \left(\sum_{i,j} c_{i,j}x_{i,j}^p\right) \lambda^p_v \ge 0 \quad \text{ for $v \ in V$} $$ è responsabile di questo.

Puoi anche provare il seguente approccio alternativo:

1. Risolvi il problema senza l'opzione min_max

2. Interroga l'intervallo più grande

3. Risolvi di nuovo senza min_max, ma limita il problema in modo tale che ogni route abbia uno span inferiore a quello più grande interrogato in 2.

4. Se impossibile, fermarsi, altrimenti andare al passaggio 2.

Tutto questo è semplice con l'ecosistema di VRPy. Divertiti.