Giovanni Righini scrive... Caro prof e cari alunni delle due squadre, complimenti!
State andando davvero alla grande!
Ovviamente non posso "aiutarvi" nel vero senso della parola, ma vi indico
qualche spunto per indirizzare i vostri pensieri nella direzione più
proficua.
1) I dati del problema. Così come sono, vi siete accorti, i dati non sono
nel formato "utile" (ho fatto apposta: era per farvi toccare con mano il
fatto che i dati che vengono forniti al ricercatore operativo non sono quasi
mai quelli che lui vorrebbe; è quasi sempre necessario qualche passaggio
intermedio per elaborarli e ricavare i "veri" dati del problema di
ottimizzazione). Avete capito che ciò che serve è avere una matrice di
distanze da ogni punto ad ogni altro: questi sono i "veri" dati del
problema. Avete capito che la metrica da usare per ricavarli non è quella
Euclidea ma è simile a quella "Manhattan" o "taxi". Però nel nostro caso,
avete notato, c'è una piccola complicazione in più, dovuta al fatto che il
grafo è orientato: l'arco (i,j) e l'arco (j,i) vanno trattati diversamente.
Quindi in generale la distanza da i a j e la distanza da j a i sono diverse
(cosa che invece non accade con la metrica "taxi"). Si tratta quindi di
trovare un semplice metodo che dati due punti (descritti dalle tre
coordinate "strane" con cui sono descritti gli indirizzi) permetta di
ricavare subito la distanza. Forse la vostra idea dello "spin" è proprio il
tassello mancante: provate a formalizzarla meglio (e verificate se funziona
sempre).
2) Nella slide 14 è scritto "tenendo conto di possibili coincidenze". Cosa
significa esattamente?
Mettiamola così: se voi non vi accorgeste che due clienti sono coincidenti
potreste per questo sbagliare nel calcolare i tempi?
Se la risposta è "sì", allora dovete senz'altro "tenere conto di possibili
coincidenze"; se la risposta è "no" siete autorizzati a trattare sempre gli
utenti come se fossero distinti, senza pericolo di sbagliare per questo. (Io
ho cercato di semplificarvi la vita: state attenti a non complicarvela
voi...).
3) Vincoli sui tempi di consegna. Li avete descritti bene a parole: ora
dovreste formalizzarli matematicamente come avete già fatto (magnificamente)
per tutto il resto del problema. Occhio alla slide 12, c'è un indice
sbagliato: vi è scappato un t(j,j) invece di t(i,j). Il tempo trascorso si
accumula lungo il percorso, come il carico distribuito. La differenza è che
il carico dipende dagli utenti visitati, mentre il tempo dipende anche dai
cammini percorsi da utente a utente. Ma le vostre variabili z rappresentano
proprio il fatto che venga percorso un cammino da utente a utente, quindi
esprimere il tempo trascorso dovrebbe essere persino più facile che
esprimere il carico distribuito.
4) Il modello matematico. Il modello della slide 13 è da applausi. Dovreste
solo perfezionare la definizione delle variabili z(i,j,k) nella slide 11,
perché nella definizione manca il riferimento al significato degli indici i
e j. Potrebbe esserci ancora un problema, però. Per adesso non vi dico
quale, perché dipende da come completerete il modello. Vi suggerisco solo
una parola su cui eventualmente riflettere: "sottocicli"!
5) Per la gara ho visto che volete usare AMPL. Ok. Il linguaggio MathProg
di GLPK è proprio un derivato di AMPL. Dovreste essere già in grado di
risolvere il sottoproblema Bin Packing, trovando i valori ottimi del primo
obiettivo. Volete davvero unificare i due sottoproblemi in un modello unico?
Sì, si può fare, ormai avete quasi tutto quello che vi serve. Però anche
risolverli in due fasi successive va bene lo stesso. Quindi adesso, se fossi
in voi, non dedicherei tempo a unificare i due modelli, ma piuttosto a
completare il secondo.
6) Per la gara B cercate risultati con algoritmi
euristici e utilizzate algoritmi "tabu search" per trovarne di
migliori. Magnifico! Finalmente qualcuno che sceglie l'euristica giusta! Di
solito tutti si fanno abbindolare da "algoritmi genetici" e "formiche
ottimizzatrici" e altre cose che sembrano spettacolari ma in realtà
funzionano male. Voi invece avete puntato proprio sulla "tabu search", il
metodo che finora ha fornito i risultati migliori su questo tipo di
problemi. Mi farebbe piacere conoscere le soluzioni che trovate,
per metterle on-line sul sito della gara (e fare invidia alle altre
squadre...). Posso preparare esempi più grandi, allora? Lo faccio subito...!
Complimenti e buon lavoro!
Ovviamente non posso "aiutarvi" nel vero senso della parola, ma vi indico
qualche spunto per indirizzare i vostri pensieri nella direzione più
proficua.
1) I dati del problema. Così come sono, vi siete accorti, i dati non sono
nel formato "utile" (ho fatto apposta: era per farvi toccare con mano il
fatto che i dati che vengono forniti al ricercatore operativo non sono quasi
mai quelli che lui vorrebbe; è quasi sempre necessario qualche passaggio
intermedio per elaborarli e ricavare i "veri" dati del problema di
ottimizzazione). Avete capito che ciò che serve è avere una matrice di
distanze da ogni punto ad ogni altro: questi sono i "veri" dati del
problema. Avete capito che la metrica da usare per ricavarli non è quella
Euclidea ma è simile a quella "Manhattan" o "taxi". Però nel nostro caso,
avete notato, c'è una piccola complicazione in più, dovuta al fatto che il
grafo è orientato: l'arco (i,j) e l'arco (j,i) vanno trattati diversamente.
Quindi in generale la distanza da i a j e la distanza da j a i sono diverse
(cosa che invece non accade con la metrica "taxi"). Si tratta quindi di
trovare un semplice metodo che dati due punti (descritti dalle tre
coordinate "strane" con cui sono descritti gli indirizzi) permetta di
ricavare subito la distanza. Forse la vostra idea dello "spin" è proprio il
tassello mancante: provate a formalizzarla meglio (e verificate se funziona
sempre).
2) Nella slide 14 è scritto "tenendo conto di possibili coincidenze". Cosa
significa esattamente?
Mettiamola così: se voi non vi accorgeste che due clienti sono coincidenti
potreste per questo sbagliare nel calcolare i tempi?
Se la risposta è "sì", allora dovete senz'altro "tenere conto di possibili
coincidenze"; se la risposta è "no" siete autorizzati a trattare sempre gli
utenti come se fossero distinti, senza pericolo di sbagliare per questo. (Io
ho cercato di semplificarvi la vita: state attenti a non complicarvela
voi...).
3) Vincoli sui tempi di consegna. Li avete descritti bene a parole: ora
dovreste formalizzarli matematicamente come avete già fatto (magnificamente)
per tutto il resto del problema. Occhio alla slide 12, c'è un indice
sbagliato: vi è scappato un t(j,j) invece di t(i,j). Il tempo trascorso si
accumula lungo il percorso, come il carico distribuito. La differenza è che
il carico dipende dagli utenti visitati, mentre il tempo dipende anche dai
cammini percorsi da utente a utente. Ma le vostre variabili z rappresentano
proprio il fatto che venga percorso un cammino da utente a utente, quindi
esprimere il tempo trascorso dovrebbe essere persino più facile che
esprimere il carico distribuito.
4) Il modello matematico. Il modello della slide 13 è da applausi. Dovreste
solo perfezionare la definizione delle variabili z(i,j,k) nella slide 11,
perché nella definizione manca il riferimento al significato degli indici i
e j. Potrebbe esserci ancora un problema, però. Per adesso non vi dico
quale, perché dipende da come completerete il modello. Vi suggerisco solo
una parola su cui eventualmente riflettere: "sottocicli"!
5) Per la gara ho visto che volete usare AMPL. Ok. Il linguaggio MathProg
di GLPK è proprio un derivato di AMPL. Dovreste essere già in grado di
risolvere il sottoproblema Bin Packing, trovando i valori ottimi del primo
obiettivo. Volete davvero unificare i due sottoproblemi in un modello unico?
Sì, si può fare, ormai avete quasi tutto quello che vi serve. Però anche
risolverli in due fasi successive va bene lo stesso. Quindi adesso, se fossi
in voi, non dedicherei tempo a unificare i due modelli, ma piuttosto a
completare il secondo.
6) Per la gara B cercate risultati con algoritmi
euristici e utilizzate algoritmi "tabu search" per trovarne di
migliori. Magnifico! Finalmente qualcuno che sceglie l'euristica giusta! Di
solito tutti si fanno abbindolare da "algoritmi genetici" e "formiche
ottimizzatrici" e altre cose che sembrano spettacolari ma in realtà
funzionano male. Voi invece avete puntato proprio sulla "tabu search", il
metodo che finora ha fornito i risultati migliori su questo tipo di
problemi. Mi farebbe piacere conoscere le soluzioni che trovate,
per metterle on-line sul sito della gara (e fare invidia alle altre
squadre...). Posso preparare esempi più grandi, allora? Lo faccio subito...!
Complimenti e buon lavoro!
Nessun commento:
Posta un commento