Modello di programmazione lineare intera

[Ushas]

Ciao a tutti,
potreste aiutarmi a linearizzare il vincolo di un modello P.L.I. (il modello è una variante del VRP con vincoli di capacità e distanza)
Vi scrivo il frammento di codice LaTeX, magari torna meglio per capire di cosa sto parlando:

$$K \geq K_{min}=max\{\lceil\frac{\sum_{i\in V} q_i}{C}\rceil,\lceil\frac{\sum_{(i,j)\in A}
d_{ij}.\sum_{k=1}^{K} x_{ijk}}{D}\rceil\}$$

In breve, il numero K di veicoli di cui dispongo deve essere almeno uguale al minimo numero Kmin di veicoli che mi servono per coprire la rotta in termini di capacità massima di ogni veicolo e di km massimi che ogni veicolo può fare, cioè K>=Kmin=max{min numero di veicoli per la capacità; min numero di veicoli per la distanza}.

Se non sbaglio, però, questo vincolo non è lineare: come posso linearizzarlo?

Grazie, spero di essermi spiegata!

[kuarl]

riscrivilo in maniera potabile oppure incolla uno shot del render di latex... così è incomprensibile.

quanto alla presenza di max nel vincolo, solitamente si introduce una nuova variabile nel problema, da sommare alla funzione obiettivo e la si pone >= al vincolo

es:

min y
| y >= x1 + x2


in ogni caso la tua descrizione del problema mi pare assai contorta. Io il VRP lo formulo in maniera differente

[MItaly]

Agevolo lo screenshot LaTeX per gli interessati (sostituendo max con \max ).

[Ushas]

Grazie MItaly per lo screenshot, in effetti non mi era venuto in mente di fare semplicemente così

min y | y >= x1 + x2

Il fatto è che io non voglio minimizzare il numero di veicoli, voglio solo verificare che quelli che ho siano sufficienti.
La mia funzione obiettivo è infatti minimizzare il costo totale, supponendo però che le voci di costo non dipendano dai veicoli utilizzati ma solo dalle rotte percorse.

[kuarl]

te hai le idee parecchio confuse fratello. Il VRP è un problema il cui obiettivo è eseguire tutte le consegne assegnandole al minor numero di veicoli (clustering) e al contempo facendogli fare una rotta di costo minimo (routing).

Per vedere se i tuoi veicoli sono sufficienti, risolvi il problema del VRP, vedi quanti veicoli richiede all'ottimo e vedi se bastano quelli che hai.


In ogni caso il problema del VRP, benché possa essere formulato in termini di programmazione lineare intera, solitamente viene risolto usando tecniche subottime più veloci. Questo perché lo spazio di ricerca esplode letteralmente all'aumentare delle consegne, ed essendo poi un problema intero, il risolutore potrebbe starci dei giorni per trovare una soluzione su un problema reale.

Se il tuo interesse per il problema del VRP non è solo teorico ma intendi usarlo in un caso pratico, valuta l'utilizzo di algoritmi approssimati come il Tabu Route, un algoritmo di ricerca locale basato su tabu search inventato da tre tizi il cui nome al momento mi sfugge

[kuarl]

c'ho riflettuto, rettifico un paio di cose

sia la formulazione in PLI che il tabu route si fanno con un numero di veicoli limitato. In altre parole te imposti il problema col numero di veicoli che hai e glie lo fai risolvere. Se i veicoli non sono sufficienti semplicemente ti dirà che non esiste soluzione.

I tizi del tabu route si chiamano Hertz, Gendreau, Laporte

[Ushas]

Mi serve per una cosa puramente teorica al fine di un esame, addirittura sul calcolatore neanche lo proviamo...

Originariamente inviato da kuarl
sia la formulazione in PLI che il tabu route si fanno con un numero di veicoli limitato. In altre parole te imposti il problema col numero di veicoli che hai e glie lo fai risolvere. Se i veicoli non sono sufficienti semplicemente ti dirà che non esiste soluzione.

Ok, scriverò questo nel progetto! Grazie mille per la disponibilità!

[MDM]

anche a me piace molto il latex

[OZZY IS BACK...]

MDM ti voglio bene