Newsgroup: it.discussioni.ingegneria
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


Una tecnica che e' fondamentale nella soluzione di questo tipo di problemi,
e' quella di prendere il libro di testo della materia e studiarlo a fondo.
L'algrotimo che da soluzioni vicine all'ottimo e' quello che ti permette di
processare al meglio le informazioni acquisite sul testo di cui sopra.
--------------------------------
Inviato via 
http://arianna.libero.it/usenet/

 linea).....
Non sono un esperto in materia, ma assomiglia al classico problema del
commesso viaggiatore in cui la funzione costo non e' piu' la distanza totale
ma una sua funzione "pesata" col ritardo delle consegne.
Da profano quale sono proverei con i classici simulated annealing e/o
iterate local search.
Stefano
