Newsgroup: it.scienza.informatica
Titolo: Algoritmo cervellotico

Ho il seguente algoritmo da risolvere per una esercitazione:
Devo pianificare le consegne di prodotti su 6 giorni a svariati clienti
dislocati in modo casuale in un area quadrata ampia.
I clienti sono identificati dalla coppia di coordinate X,Y e devo
immaginare di poterli raggiungerli in modo lineare (tracciando una
linea)
Ho un numero determinato di mezzi per fare le consegne ma non sono
sufficienti per esaurire le consegne secondo le scadenze.
Ogni mezzo può trasportare lo stesso quantitativo di merce e ha lo
stesso costo di percorrenza.
Ho una lista di questo tipo:
Giorno Consegna Xcliente Ycliente Quantità scadenza
0      c0       100      200      1,5      -2        (è scaduta da 2
giorni)
0      c1       70       300      3        1         (scade domani)
1      c2       600      70       2        0         (scade oggi)
1      c3       500      120      2,5      1
2      c4       300      200      1,8      3         (scade tra 2 giorni
a partire dal secondo giorno di inizio consegne)
...   ...       ...      ..       ....     ...
So inoltre che se non riesco a consegnare entro la data le penali
aumentano in modo esponenziale rispetto al ritardo in giorni.
So inoltre che non è accettabile consegnare troppo in anticipo (esempio
se consegno gelati il cliente ha il frigo pieno)
Devo trovare i carichi ottimali da fare con i vari mezzi affinchè possa
avere il costo minimo.
Il costo per semplicità coincide con la traiettoria che fa il mezzo ma
va sommato alle eventuali penali dei clienti per i quali sono in
ritardo.
Le traiettorie vanno immaginate sugli assi cartesiani prive di qualsiasi
ostacoli per cui da un cliente con coordinate 100,200 e un'altro 200,300
calcolo il percorso con Pitagora non considerando ostacoli o strade
intermedie.
Un algoritmo che ho visto, ma non produce soluzioni ottimali, prevede
l'individuazione della consegna più in ritardo e la determinazione di
una retta
passante per tale cliente e l'origine degli assi cartesiani. Dopo di che
si individuano tutti i clienti disposti sull'intorno della retta con
un'angolo definito.
Poi quando il mezzo è quasi pieno si vanno a vedere i clienti
all'interno di un certo raggio e si satura il mezzo.
Questa tecnica pero' non è vicina all'ottimale per cui , scambiando i
clienti non serviti, con qualche cliente servito per un certo mezzo, ci
si accorge che
il costo è minore.
Avete altre idee o tecniche da proporre ? conoscete degli algoritmi che
possano dare soluzioni vicine all'ottimo ?
 
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 
Mi sembra un problema di ottimizzazione combinatoria (a vederlo cosi`, 
anche tosto), per cui un algoritmo greedy come quello che hai visto 
rischia di essere lontano dalla soluzione ottima. Ci sono molte tecniche 
per risolvere questo tipo di problemi, fra cui:
. Constraint Programming
. Integer Linear Programming
. Local Search (hill climbing, tabu search, simulated annealing, ...)
Le prime due sono complete (cioe` trovano sempre l'ottimo), mentre local 
search cerca di avvicinarsi velocemente alla soluzione ottima ma non e` 
detto che riesca a raggiungerla.
Ciao,
Marco
--
http://www.ing.unife.it/docenti/MarcoGavanelli/