verticale

Pianificazione ed ottimizzazione dei percorsi nella logistica dei magazzini industriali

Panoramica sulla logistica e focus sui magazzini industriali nelle loro caratteristiche principali. Illustrazione del software riguardante la pianificazione e l’ottimizzazione dei percorsi e applicazione del software realizzato in uno scenario di magazzino reale, osservandone i risultati e analizzandone le prestazioni in termini di tempi di calcolo.

Scarica il PDF Scarica il PDF
Aggiungi ai preferiti Aggiungi ai preferiti


Articoli tecnico scientifici o articoli contenenti case history
Tesi di Laurea, Università degli Studi di Bologna, Anno Accademico 2011- 2012

Pubblicato
da Alessia De Giosa
VerticaleSegui aziendaSegui




Settori: 


Estratto del testo
ALMA MATER STUDIORUM UNIVERSIT ` A DI BOLOGNA Seconda Facolt`a di Ingegneria - Sede di Cesena Corso di Laurea Magistrale in Ingegneria Informatica PIANIFICAZIONE ED OTTIMIZZAZIONE DEI PERCORSI NELLA LOGISTICA DEI MAGAZZINI INDUSTRIALI Elaborata nel corso di: Metodi e Modelli per il Supporto alle Decisioni LM Tesi di Laurea di : MANUEL FABBRI Relatore : Prof. DANIELE VIGO Correlatore : Ing. CLAUDIO GAMBETTI ANNO ACCADEMICO 2011''2012 SESSIONE III PAROLE CHIAVE Logistica Industria Magazzino Pianificazione Percorso Indice Introduzione ix 1 Il sistema logistico e i magazzini industriali 1 1.1 Introduzione alla logistica . . . . . . . . . . . . . . . . 1 1.2 Il sistema logistico . . . . . . . . . . . . . . . . . . . . . 2 1.2.1 Supply chain management . . . . . . . . . . . 3 1.2.2 Caratteristiche di un sistema logistico . . . . . 5 1.2.3 Funzionamento di un sistema logistico . . . . 7 1.2.4 Gestire un sistema logistico . . . . . . . . . . . 10 1.3 I magazzini industriali . . . . . . . . . . . . . . . . . . 12 1.3.1 Gestione del magazzino . . . . . . . . . . . . . 13 1.3.2 Struttura interna . . . . . . . . . . . . . . . . . 14 1.3.3 Mezzi di immagazzinamento . . . . . . . . . . 15 1.3.4 Approcci per stoccaggio e recupero merce . . . 19 1.3.5 Magazzini automatici . . . . . . . . . . . . . . 19 1.3.6 Criteri di allocazione dei prodotti . . . . . . . 22 1.3.7 Movimentazione interna . . . . . . . . . . . . . 24 1.4 In sintesi . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2 Pianificazione e ottimizzazione dei percorsi 27 2.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . 27 2.2 Modellazione del magazzino . . . . . . . . . . . . . . 29 2.2.1 Panoramica sulla modellazione . . . . . . . . . 29 2.2.2 Generazione del modello . . . . . . . . . . . . 31 2.3 Ottimizzazione dei percorsi . . . . . . . . . . . . . . . 32 2.3.1 Introduzione al calcolo dei percorsi . . . . . . 32 2.3.2 Vehicle routing problem . . . . . . . . . . . . . 33 v 2.3.3 Travelling salesman problem . . . . . . . . . . 35 2.3.4 Road travelling salesman problem . . . . . . . 35 2.3.5 Algoritmi euristici . . . . . . . . . . . . . . . . 39 2.3.6 Algoritmi meta-euristici . . . . . . . . . . . . . 42 2.3.7 Algoritmi per cammini minimi . . . . . . . . . 46 2.4 Un possibile sistema . . . . . . . . . . . . . . . . . . . 48 2.5 In sintesi . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3 Un software per la pianificazione e ottimizzazione di per-
corsi
55 3.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . 55 3.1.1 Problema . . . . . . . . . . . . . . . . . . . . . . 56 3.1.2 Visione . . . . . . . . . . . . . . . . . . . . . . . 56 3.1.3 Obiettivi . . . . . . . . . . . . . . . . . . . . . . 56 3.2 Requisiti . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.3 Analisi dei requisiti . . . . . . . . . . . . . . . . . . . . 58 3.3.1 Glossario . . . . . . . . . . . . . . . . . . . . . . 58 3.3.2 Casi d''uso . . . . . . . . . . . . . . . . . . . . . 60 3.3.3 Modello del dominio . . . . . . . . . . . . . . . 68 3.4 Analisi del problema . . . . . . . . . . . . . . . . . . . 68 3.4.1 Architettura logica . . . . . . . . . . . . . . . . 70 3.4.2 Piano di collaudo . . . . . . . . . . . . . . . . . 73 3.4.3 Piano di lavoro e analisi dei rischi . . . . . . . 73 3.5 Progetto . . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.5.1 Scelta tecnologica . . . . . . . . . . . . . . . . . 76 3.5.2 Il pattern Model-View-ViewModel . . . . . . . 78 3.5.3 Algoritmo di generazione del modello . . . . . 81 3.5.4 Algoritmo di generazione del percorso . . . . 85 3.5.5 Scelte per visualizzazione e interazione utente 87 3.5.6 Architettura . . . . . . . . . . . . . . . . . . . . 88 3.6 Esecuzione . . . . . . . . . . . . . . . . . . . . . . . . . 89 3.7 In sintesi . . . . . . . . . . . . . . . . . . . . . . . . . . 100 4 Risultati 105 4.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . 105 4.2 Analisi dei tempi . . . . . . . . . . . . . . . . . . . . . 105 4.3 Uno scenario reale . . . . . . . . . . . . . . . . . . . . . 107 vi 4.4 In sintesi . . . . . . . . . . . . . . . . . . . . . . . . . . 109 5 Conclusioni 113 vii viii Introduzione Nell''ambito della logistica industriale, un problema di base riguar-
da la necessit`a di gestire i flussi di merci in entrata e in uscita dagli
impianti; una componente fondamentale di questo problema con-
cerne la pianificazione e l''ottimizzazione dei percorsi all''interno di
un magazzino industriale. Si `e voluto a ffrontare parte di questo vasto argomento median- te un''esperienza di tirocinio presso Onit Group s.r.l., una software
house di Cesena che dal 1996 svolge la propria attivit`a nel settore del-
le tecnologie informatiche e della consulenza mirata al management
e alla organizzazione aziendale. Il tirocinio, dal titolo Algoritmi di pianificazione percorsi consentiti indoor e calcolo distanze, ha a ffrontato la seguente necessit`a aziendale: la tendenza a modificare sempre pi `u frequentemente, in base alle
mutevoli esigenze del mercato, le modalit`a di utilizzo degli spazi
negli impianti di stoccaggio rende determinante pianificare in ma-
niera ottima e automatica i percorsi di movimentazione interna. La
pianificazione dei percorsi deve essere eseguita per determinare il
viaggio di un lavoratore o di una macchina all''interno di un''area,
evitando gli ostacoli. Attraverso l''attivit`a di tirocinio `e stato pos-
sibile esaminare direttamente questo contesto di realt`a aziendale,
visitando gli stabilimenti della societ`a cooperativa agricola Orogel
di Cesena e osservando sul campo i processi di carico e scarico merci,
lavorazione, produzione, confezionamento e stoccaggio per la linea
dei prodotti surgelati. Una volta analizzato tale dominio applicativo, nel quale si inten- de agire, l''obiettivo della tesi `e di studiare algoritmi di pianificazio-
ne e ottimizzazione dei percorsi, all''interno di ambienti complessi,
e implementarne una soluzione software valutandone le prestazio- ix ni all''interno di uno scenario reale, per fornire uno strumento che
possa essere di supporto in questo ambito. Il progetto appena descritto `e stato sviluppato con il supporto della business unit industria di Onit, che opera negli ambiti della
progettazione e ottimizzazione dei processi produttivi, qualitativi e
di logistica. La tesi `e organizzata come segue: nel capitolo 1 si presenta una panoramica generale del contesto lavorativo, introducendo i vari
tipi di magazzini industriali e il dominio in cui si collocano. Questa
conoscenza `e necessaria come premessa delle fasi seguenti. Nel secondo capitolo ci si focalizza sul prodotto dell''attivit`a di ricerca bibliografica riguardante la modellazione dei magazzini e gli
algoritmi di ottimizzazione dei percorsi. Si riportano quelli ritenuti
pi `u rilevanti, sui quali `e stata prodotta una sintesi. Il capitolo successivo tratta della soluzione software sviluppata, a fronte dei requisiti del problema, dell''analisi e del progetto. Inoltre,
si pone l''attenzione anche sulla tecnologia utilizzata, mediante uno
sguardo generale sul framework .NET 4.0. Nel capitolo 4 si descrivono i risultati ottenuti, mediante un test del software applicato ad un caso reale, commentando anali-
si e simulazioni applicate a scenari produttivi inerenti all''azienda
Orogel. Si termina, infine, con una sezione conclusiva sull''attivit`a svolta. x Capitolo 1 Il sistema logistico e i
magazzini industriali
In questo capitolo si introduce il concetto di sistema logistico, per
inquadrare l''ambito nel quale si colloca il magazzino industriale. Si
inizia con una panoramica sulla logistica, per poi focalizzarsi sulle
principali caratteristiche di un sistema logistico, infine di presentano
le categorie principali dei magazzini industriali. 1.1 Introduzione alla logistica Con il termine logistica si intende la pianificazione e il controllo
dei flussi di materiale e informativi nelle organizzazioni. L''obiettivo
della logistica `e portare beni o servizi nel giusto luogo, con tempi
certi e nelle condizioni volute, a costo minimo e a profitto maggiore. `E una delle chiavi dell''economia moderna. L''espansione dei mercati industriali a livello globale ha genera- to una forte competizione e, allo stesso tempo, la disponibilit`a di
prodotti alternativi ha creato un tipo di clientela molto esigente, che
richiede continuamente la disponibilit`a istantanea di nuovi modelli.
Ai fornitori delle attivit`a logistiche, quindi, `e richiesto di svolgere
pi `u transazioni, in meno tempo, a costi minori e con grande accura-
tezza; per di pi `u, la tendenza a una personalizzazione di massa dei
prodotti porter`a a una intensificazione di questo tipo di domanda. 1 2 CAPITOLO 1. IL SISTEMA LOGISTICO E I MAGAZZINI INDUSTRIALI I ritmi accelerati e l''ambito maggiore su cui le operazioni logistiche
deve agire hanno portato e portano tuttora ad un cambiamento nel
modello di pianificazione logistica aziendale. Data la quantit`a di denaro coinvolto e l''incremento dei requisi- ti operativi, la pianificazione e il controllo dei sistemi logistici ha
attirato maggior attenzione sia in ambito lavorativo che accademi-
co. Per massimizzare il valore in un sistema logistico, vi sono un
gran numero di decisioni di pianificazione da prendere, che vanno
dalla scelta del sistema di stoccaggio, a quale elemento prelevare
in successione per riempire l''ordine di un cliente fino alle decisioni
aziendali di alto livello di investire sulla costruzione di un nuovo
impianto. Esiste una grande quantit`a di letteratura e di strumenti di sup- porto software che si focalizzano su ogni singolo ambito dei sistemi
logistici. Da questa premessa, si pu `o comprendere l''importanza
della catena logistica nel mondo attuale e come le aziende siano in-
teressate a possibili miglioramenti in uno qualunque dei suoi tanti
aspetti. 1.2 Il sistema logistico Il sistema logistico `e l''insieme delle infrastrutture, delle attrezzature,
delle risorse e delle politiche operative che permettono il movimento
del flusso delle merci e delle relative informazioni, dall''acquisizione
delle materie prime e dei materiali ausiliari attraverso la produzione,
fino alla distrubuzione dei prodotti finiti ai clienti [3]. Le tre attivit`a principali di cui si occupa ogni sistema logistico sono: ' processamento degli ordini; ' gestione dello stoccaggio; ' trasporto della merce. Le prime due hanno come obiettivo di garantire la fruibilit`a del prodotto o bene, in modo che sia disponibile quando richie-
sto (valore temporale) e la terza ne deve garantire l''accessibilit`a
(valore spaziale). 2 CAPITOLO 1. IL SISTEMA LOGISTICO E I MAGAZZINI
INDUSTRIALI 3 Si noti che ben il 10% del costo del prodotto `e influenzato dall''a- spetto logistico; al suo interno, il costo del trasporto incide solamen-
te per 1 /3! Gli altri costi pi `u rilevanti sono relativi allo stoccaggio, all''inventario e all''amministrazione [2]. Come detto, la logistica si occupa di integrare tutte quelle attivit`a di fornitura, gestione magazzino, gestione trasporti, eccetera, che
contenute in un''azienda, con lo scopo di portare maggior valore
temporale e spaziale. Per fare ci `o, essa si serve di una supply chain
managament
. 1.2.1 Supply chain management La supply chain managament (SCM) `e un complesso sistema logi-
stico che definisce l''integrazione di tutte le attivit`a associate con il flusso
e la trasformazione di beni, dalle materie prime all''utente finale, allo stesso
modo dei flussi informativi, mediante il miglioramento delle inter-relazioni
presenti, per far raggiungere un vantaggio sostenibile e competitivo all''a-
zienda [1]. Rappresenta un complesso sistema logistico nel quale le
materie prime sono trasformate in prodotti finiti da distribuire agli
utenti finali. Un possibile percorso di questo tipo `e rappresentanto in
figura 1.1: i materiali grezzi sono portati dai fornitori (supplier) agli
impianti di produzione (manufacturing plant), che creano componen-
ti o parti semi-lavorate, mentre i prodotti finiti vengono assemblati
in uno stabilimento di fferente (assembly plant). Anche la distribu- zione `e suddivisa in due passi: due centri di distribuzione centra-
li (CDC) che riforniscono diversi centri di distribuzione regionali
(RDC). Ovviamente, al seconda del tipo di prodotto e di doman-
da, verr`a realizzata la catena pi `u adatta, eliminando o aggiungendo
impianti e collegamenti fra le varie fasi. Questi ultimi, inoltre, pos-
sono essere pi `u o meno complessi e andare da una semplice linea di
trasporto con camion a una rete pi `u articolata che coinvolge diversi
sistemi e compagnie di trasporto. Gli ambiti aziendali coinvolti dalla supply chain sono vari: marke- ting, vendite, ricerca e sviluppo, previsioni, produzione, acquisti, logistica,
sistemi informativi, finanza, servizio cliente. I flussi principali che la supply chain deve gestire sono riguar- danti: prodotti (in entrata e in uscita), servizi (in entrata e in uscita), 3 4 CAPITOLO 1. IL SISTEMA LOGISTICO E I MAGAZZINI INDUSTRIALI Figura 1.1: Una esempio di supply chain (fonte: Ghiani, Laporte,
Musmanno) informazioni (in entrata e in uscita), risorse finanziarie (in entrata e in
uscita), domanda (in entrata), previsioni (in uscita). Tutto ci `o per raggiungere gli obiettivi desiderati a proposito di: ' soddisfazione del cliente; ' valore; ' redditivit`a; ' vantaggio competitivo. La SCM non `e sempre stata quella odierna, ma si `e evoluta nel tempo. Negli anni ''60, nell''ambito dell''industria, c''erano u ffici fram- mentati per le diverse attivit`a da svolgere; nei seguenti 40 anni, si `e andati verso un''integrazione della logica, per aree di competenza (stoccaggio, produzione, trasporto), dove ogni area `e progettata a
seconda delle proprie peculiarit`a. Questo ha portato a un migliora-
mento nell''e fficienza del processo produttivo e a un contenimento dei costi, in quanto un singolo ambito tiene conto di pi `u aspetti nel
processo di decisione, interagendo con gli altri. Si crea la logistica
inbound (per flussi in entrata) e outbound (in uscita) dell''azienda. 4 CAPITOLO 1. IL SISTEMA LOGISTICO E I MAGAZZINI
INDUSTRIALI 5 1.2.2 Caratteristiche di un sistema logistico Ci sono varie dimensioni che caratterizzano un sistema logistico; di
seguito vengono analizzate le pi `u comuni: 1. Sistemi pull o push: ' Push (make-to-stock): il sistema `e orientato alla produzio- ne. Si ha la struttura distributiva tradizionale a di ffusione capillare sul territorio: dal sistema produttivo ai depositi
centrali, passando per quelli periferici, fino ai punti ven-
dita. `E prioritaria la capacit`a di stoccaggio rispetto alla
distribuzione. La produzione `e basata sulle previsioni e
la domanda `e anticipata; si hanno alti costi di magazzino
e pi `u bassi costi di trasporto, in quanto si possono ag-
gregare maggiormente i flussi delle forniture, rispetto ai
sistemi pull. ' Pull (make-to-order): i prodotti sono realizzati solo su ri- chiesta dei clienti; il magazzino del produttore `e basso o
nullo e si hanno alti costi di trasporto. Questa logica di
sistema `e stata ideata parallelamente all''evoluzione del-
la SCM; per cercare un vantaggio competitivo, mediante
l''eccellenza del servizio con bassi livelli di scorte, i magaz-
zini centrali si trasformano in centri di distribuzione (CEDI),
e diminuiti di numero; i magazzini periferici si trasfor-
mano in punti di transito, che operano solo smistamento
e distribuzione. Si ha una struttura distributiva snella.
Le informazioni risalgono a ritroso, dai punti vendita ai
punti di transito, fino ai CEDI, gli ordini vengono conso-
lidati e poi spediti. Viene data la priorit`a alla capacit`a di
smistamento e distribuzione. ' Mixed (make-to-assembly): `e un sistema misto fra i due; si accumulano parti di approvvigionamento (push), per poi
essere e fficienti nella distribuzione ai clienti (pull) a fronte di un ordine. 2. Supply chain a integrazione verticale o con logistica di terze parti : 5 6 CAPITOLO 1. IL SISTEMA LOGISTICO E I MAGAZZINI INDUSTRIALI ' Integrazione verticale: in questo caso tutti i componenti (sorgenti di materie prime, stabilimenti, trasporti) appar-
tengono alla stessa azienda. Pi `u frequentemente, diverse
e indipendenti compagnie operano in una supply chain.
Vantaggioso in un mercato stabile. ' Logistica di terze parti: parte della logistica viene a ffi- data a terzi (i.e., operatori specializzati). In questo caso,
l''azienda ha un basso o nullo costo di investimento su
infrastrutture e si riducono gli e ffetti negativi dei periodi con bassa domanda, ma rischia la perdita di contatto con
il cliente e i costi logistici unitari sono in genere maggiori. 3. Magazzino a gestione del dettagliante o a gestione del ven- ditore : ' A gestione del dettagliante: egli controlla il suo magaz- zino e decide quando e quanto rifornirsi; in questo caso
si ha una logica di tipo pull per la distribuzione. ' A gestione del venditore: egli monitora i magazzini dei clienti rivenditori e decide quando e quanto rifornirli; la
distribuzione a valle `e decisa dal punto a monte. Questa
modalit`a si `e sviluppata solo di recente ed `e realizzabile
in accordo fra le due parti o in caso di forte leadership del
mercato del venditore. Quest''ultimo ha maggiori rispar-
mi dovuti ad una miglior coordinazione della logistica,
mentre i clienti non sono tenuti ad investire nel controllo
del magazzino. Come si osserva nella figura 1.2, i prodotti seguono il flusso della supply chain (eccetto per quelli obsoleti, danneggiati o non funzio-
nanti che devono ritornare alla sorgente), al contrario le informazioni
seguono il percorso inverso, dai consumatori ai fornitori. In un si-
stema pull, ad esempio, gli ordini fatti dai clienti finali vengono presi
in carico dai venditori e trasmessi al produttore, che li trasforma in
ordini per i fornitori. Analogamente, nei sistemi pull, le vendite
storicizzate sono usate per fare previsioni future sulla domanda di
prodotto e la relativa richiesta di materiali. 6 CAPITOLO 1. IL SISTEMA LOGISTICO E I MAGAZZINI
INDUSTRIALI 7 Figura 1.2: Flusso dei prodotti e delle informazioni (fonte: Ballou,
2004) Facendo riferimento al caso reale in Orogel, un''azienda manu- fatturiera che lavora sul prodotto fresco, opera in modalit`a push.
Lo stoccaggio dei prodotti ha un forte impatto sui costi, necessi-
tando la presenza di diverse celle di immagazzinamento, presenti
sia a gestione manuale, sia automatica. Ognuno di questi impianti
pu `o arrivare a contenere migliaia di posti pallet, soprattutto gra-
zie alla grande capienza fornita da quelli a movimentazione interna
automatica, da ci `o se ne deduce che, nel caso della linea di prodot-
ti surgelati, il consumo di energia risulta particolarmente oneroso,
dovendo mantenere temperature di gran lunga sotto lo 0. Il ritmo
della produzione, ovvero la trasformazione del prodotto fresco in
surgelato, `e dettato dal calendario dei raccolti di campagna, men-
tre le operazioni di confezionamento sono basate sulle previsioni di
vendita. 1.2.3 Funzionamento di un sistema logistico Riprendendo le tre attivit`a principali facenti parte di un sistema lo-
gistico accennate prima, si descrive, in breve, il suo funzionamento. 7 8 CAPITOLO 1. IL SISTEMA LOGISTICO E I MAGAZZINI INDUSTRIALI Fase 1 - gestione degli ordini: questo compito `e a grande dispen-
dio di tempo (fino al 70% dell''intero tempo di ciclo dell''ordine [5]);
qui si collega il flusso delle informazioni con il flusso dei prodotti.
A fronte di una richiesta, se ne verifica la disponibilit`a, si produce o
estrae dal magazzino il prodotto e infine si spedisce, mantenendo le
informazioni sullo stato dell''ordine a disposizione del cliente. Ad
ogni modo, il ricorso a supporti elettronici e informatici hanno ac-
celerato di molto questa fase, nel corso degli ultimi anni. Fase 2 - gestione dello stoccaggio: riguarda l''immagazzinamento sia
delle materie prime da manifatturare, che dei prodotti semilavora-
ti (o componenti da assemblare) e dei prodotti finiti da vendere.
I magazzini sono utili per gestire la richiesta di tipo stagionale o
tamponare quella casuale di un prodotto, per migliorare il livello
di servizio (riducendo i tempi di consegna, se il magazzino `e pi `u
vicino al bacino della clientela), per sfruttare le economie di scala
nel trasporto. In una logica di tipo push si pu `o reagire alla variabilit`a
della domanda e tamponare eventuali ine fficienze a monte. D''altro canto, il mantenimento di un magazzino pu `o risultare molto costoso
per varie ragioni: la propriet`a incorre in un costo di opportunit`a,
rappresentato dal ritorno di investimento che avrebbe realizzato se
il denaro fosse stato meglio investito. Secondo, deve essere soste-
nuto il costo della struttura, privata, pubblica o in a ffitto che sia. L''obiettivo della gestione di magazzino `e determinare il livello di
stoccaggio per minimizzare i costi operativi totali, soddisfacendo i
requisiti di livello di servizio dei clienti. Fase 2 /3 - strategie di stoccaggio/trasporto: le politiche di stoc- caggio e di trasporto sono fortemente collegate. Come viene rap-
presentato in figura 1.3, ce ne possono essere tre tipologie principali: ' Spedizione diretta dal produttore all''utente finale. Il lead-time (i.e. l''intervallo di tempo fra il momento dell''ordine e di arrivo
del prodotto) `e ridotto e si risparmia sui costi dell''utilizzo
di un magazzino. Non `e conveniente se le spedizioni sono
piccole e i clienti sparsi, perch´e si avrebbe una flotta di veicoli 8 CAPITOLO 1. IL SISTEMA LOGISTICO E I MAGAZZINI
INDUSTRIALI 9 Figura 1.3: Strategie di stoccaggio /trasporto (fonte: Ghiani, Laporte, Musmanno) semivuoti. `E comune in caso di richieste di camion pieni o per
beni degradabili che non consentono aggregazione. ' Immagazzinamento: strategia intermedia. Il magazzino rice- ve i beni in ingresso, li stocca, e a fronte di ordini li spedisce. Se
ne pu `o avere uno singolo centralizzato oppure vari regionali
decentralizzati. Con questa strategia si riduce il lead-time, ma
aumentano i costi di gestione. ' Crossdocking: avviene la cosiddetta distribuzione appena in tempo, dalla fabbrica al magazzino e da esso al cliente. Il ma-
gazzino diventa una piattaforma logistica nella quale i prodot-
ti rimangono per tempi brevi; le merci vengono trasferite da
trasporti sulla lunga distanza a trasporti sulla corta distanza.
Si ha una minor gestione dello stoccaggio, ma si introduce la
complessit`a di sincronizzare le fasi di ingresso e uscita. Questa
strategia richiede volumi di beni elevati, a bassa variabilit`a, e
facilmente maneggiabili, con la coordinazione dei flussi che
avviene mediante un supporto informativo. Fase 3 - trasporto della merce: il trasporto delle merci gioca un ruo-
lo chiave nell''economia odierna. Consente, infatti, che il consumo
avvenga lontano dalla produzione, espandendo il raggio d''azione 9 10 CAPITOLO 1. IL SISTEMA LOGISTICO E I MAGAZZINI INDUSTRIALI dei mercati, stimolando la competizione diretta fra aziende produt-
trici di paesi diversi e incoraggiando le compagnie a sfruttare le
economie di scala. Si ha, cos`ı, la disponibilit`a globale di certi pro-
dotti e si migliora la fruibilit`a dei beni degradabili. Il trasporto pu `o
avvenire con mezzi privati, con terzisti che lavorano in esclusiva
per l''azienda oppure con corrieri. Di seguito, se ne analizzano le
principali caratteristiche: ' Canale di distribuzione: identifica il percorso seguito dal pro- dotto, con la presenza di possibili intermediari tra il produttore
e il cliente (broker, grossista e dettagliante). In genere, i beni
industriali sono distribuiti al massimo mediante i primi due in-
termediari, mentre i beni di consumo possono utilizzare anche
il terzo. ' Aggregazione della merce: l''aggregazione pu `o avvenire me- diante un''apposita infrastruttura (consolidando spedizioni sin-
gole in certi nodi della rete di trasporto), in modalit`a multi-stop
(le spedizioni singole verso la destinazione finale passano per
un percorso che pu `o servire diversi clienti) oppure con consoli-
damento temporale (le spedizioni vengono ritardate o anticipate
per riuscire a spedire grandi quantit`a). ' Modalit`a di trasporto: pu `o avvenire con aereo, camion, tre- no, nave, condutture o in maniera inter-modale. La scelta
dipende dal tipo di merce (se consolidata in pallet o container),
dallo stato del materiale (solido, liquido) e dalla deperibilit`a.
Bisogna inoltre considerare i tempi di consegna che si deside-
rano rispettare, le distanze da percorrere e i costi del tipo di
trasporto. 1.2.4 Gestire un sistema logistico Ci sono vari obiettivi da tenere presente nella definizione di una
strategia logistica, di cui i principali sono: la riduzione degli inve-
stimenti da compiere (scegliendo, ad esempio, fra logistica interna
o esternalizzata), la riduzione dei costi operativi e il miglioramento del
livello di servizio. Quest''ultimo dipende dal lead-time e pu `o essere: 10 CAPITOLO 1. IL SISTEMA LOGISTICO E I MAGAZZINI
INDUSTRIALI 11 ' molto breve, se `e stato richiesto un prodotto disponibile al
dettaglio, ' breve, se il prodotto deve essere ordinato dai centri di disribu-
zione regionali o dal magazzino centrale, e ' lungo, se il prodotto `e terminato e deve ancora essere creato. Il lead-time, o order cycle time, viene rappresentata come una varia-
bile casuale con distribuzione di probabilit`a multinomiale, basata
sui tre eventi di cui sopra. `E necessario scegliere un compromesso fra costi e i livello di servizio, tenendo presente che vi `e anche una relazione tra quest''ultimo e le ven-
dite. Il livello di servizio ottimale `e quello che garantisce il massimo
delle entrate, nel punto in cui `e massima la di fferenza fra vendite e costi. Ci sono tutta una serie di decisioni da intraprendere nel progetto di un sistema logistico e che riguardano: strutture, materiali, moda-
lit`a, rifornimenti, trasporti, eccetera. Esse si possono raggruppare
in 3 principali macro-aree: ' Decisioni strategiche: hanno un orizzonte di diversi anni, basate su dati imprecisi o incompleti, e sono prese dai vertici
aziendali. Esse riguardano la dimensione, la configurazione e
la locazione delle strutture. ' Decisioni tattiche: hanno un orizzonte temporale fino al mas- simo di un anno, basate su dati disaggregati e sono prese
dai dirigenti di medio livello. Esse riguardano l''allocazio-
ne delle risorse e la pianificazione della produzione e della
distribuzione. ' Decisioni operative: hanno un orizzonte di giorni, basate su dati precisi e prese dai dirigenti di basso livello. Esse riguar-
dano, ad esempio, la presa in carico di ordini e lo smistamento
dei veicoli. In quest''ambito, si possono utilizzare dei supporti alle decisio- ni, come, ad esempio, l''analisi quantitativa. Essa `e essenziale per
prendere decisioni intelligenti e pu `o essere svolta in diversi modi: 11 12 CAPITOLO 1. IL SISTEMA LOGISTICO E I MAGAZZINI INDUSTRIALI mediante il benchmarking (si valuta un sistema esistente comparato
ad uno standard industriale), la simulazione (valutazione di alterna-
tive specifiche applicate ad un modello) e l''ottimizzazione (di una
certa configurazione rispetto a un valore di prestazioni). Come `e immaginabile, data la vastit`a e l''importanza che l''ar- gomento ricopre tuttora, esistono molti pacchetti software nell''area
della logistica, ma la loro trattazione esula dallo scopo di questa tesi. 1.3 I magazzini industriali Come descritto sopra, il sistema logistico comprende anche i siste-
mi di stoccaggio e di distribuzione, per congiungere produttori e
consumatori. Il magazzino, quindi, eroga un servizio logistico (ren-
dere disponibile il prodotto nel posto, al momento e al costo giusto),
collocato nella supply chain. Il sistema distributivo `e formato da due
strutture distinte: ' il canale logistico: rappresenta la rete distributiva per il con- centramento, la selezione, lo smistamento e il trasporto del-
le merci. Di queste funzioni, le prime tre sono svolte nei
magazzini. ' il canale commerciale: costituito dalle strutture atte alla vendita del prodotto. Il magazzino pu `o essere visto come contenitore e trasformatore dei flussi di materiali che riceve, operando sia sulla quantit`a che sulla
quantit`a dei beni. Esso `e importante sia in ottica temporale, in quanto
consente di realizzare economie legate ad approvvigionamenti e di
ottimizzare la produzione, sia in ottica qualitativa, rendendo possibile
il consolidamento dei carichi, con conseguente riduzione dei costi
di trasporto. I magazzini vengono principalmente suddivisi in base alla po- sizione in cui sono collocati nella supply chain. Ci sono, dunque, i
magazzini di produzione e i magazzini di distribuzione. Nei primi
si hanno grandi quantit`a gestite e sono suddivisi in magazzini di
materie prime (provenienti dai fornitori), interoperazionali (posti fra 12 CAPITOLO 1. IL SISTEMA LOGISTICO E I MAGAZZINI
INDUSTRIALI 13 due fasi del processo produttivo, contenenti prodotti semi-lavorati
o componenti) e di prodotti finiti (con prodotto in attesa di essere
venduto). I magazzini di distribuzione, invece, hanno una grande
variet`a di prodotti e sono suddivisi in centralizzati o periferici /regionali, classificati a seconda della dimensione del proprio bacino di utenza: ' Magazzini centralizzati: consentono un immagazzinamento di
grandi quantit`a di materiali, con l''obiettivo di massimizzare
l''e fficienza nella ricezione, stoccaggio, estrazione e spedizione dei beni. Si hanno flussi separati per ogni linea di prodotti. ' Magazzini regionali: questi centri sono pi `u vicini alla distribu-
zione finale. Si hanno grandi quantit`a in ingresso, ricevute
e immagazzinate, mentre le spedizioni sono pi `u piccole e as-
semblate. Si formano gli ordini in maniera coordinata fra di-
verse attivit`a, con prodotti provenienti da diversi flussi (con la
necessaria sincronizzazione). L''unit`a di movimentazione del bene (anche detta unit`a di carico o semplicemente UdC), che spesso `e un pallet o un altro tipo di
contenitore, pu `o dipendere dal cliente o dal livello logistico in cui ci
si trova. L''ordine, di solito, riguarda UdC di diversi prodotti. Inoltre, bisogna tenere presente che nel costo del magazzino, la manipolazione della merce incide, all''incirca, per il 50%, mentre la
ricezione, la spedizione, lo stoccaggio incidono per il restante 50%,
in parti uguali. La spedizione e la ricezione sono fasi di fficili da automatizzare, mentre la manipolazione dipende dalla tecnologia
di immagazzinamneto e recupero usata. 1.3.1 Gestione del magazzino Per ogni punto di stoccaggio, lungo la supply chain, `e necessario
dicedere la quantit`a e il periodo delle ordinazioni di prodotti, in
modo da minimizzare il costo totale nel raggiungimento di un certo
livello di servizio. I costi pi `u rilevanti riguardano: ' approvvigionamento, che comprende i costi di processamento
degli ordini, di acquisto, di lavoro e di trasporto dei prodotti; 13 14 CAPITOLO 1. IL SISTEMA LOGISTICO E I MAGAZZINI INDUSTRIALI ' mantenimento dei magazzini; ' perdite a causa di vendite mancate o di ritorno degli ordini; ' obsolescenza. La gestione del magazzino pu `o essere classificata in base a diver- si parametri, come, ad esempio, l''utilizzo di modelli deterministici
oppure stocastici (nei quali la domanda non `e sempre soddisfatta),
la movimentazione veloce o lenta dei materiali, a domanda statica o
dinamica nel tempo, con punti di stoccaggio singoli o multipli (pi `u
di fficile) e a rifornimento istantaneo o non istantaneo. A seconda delle assunzioni scelte che meglio si adattano alle esigenze aziendali, fra le alternative elencate sopra, si utilizzeranno
modelli diversi, pi `u o meno complessi, per gestire la logistica nel
magazzino. 1.3.2 Struttura interna La struttura interna di un magazzino riflette le operazioni che de-
vono essere svolte al suo interno, mirando a minimizzare i costi di
movimentazione; essa dipende da tre fattori primari: ' le caratteristiche fisiche dei prodotti da stoccare; ' il numero dei prodotti da immagazzinare; ' i volumi di prodotto manipolati in ingresso e in uscita. Tipicamente, in ogni magazzino ci sono: ' una o pi `u zone di ricezione dove la merce in ingresso `e scaricata e controllata; ' una zona di immagazzinamento dove le unit`a di carico sono stoccate; ' una o pi `u zone di spedizione dove sono assemlati gli ordini dei clienti e caricati i veicoli in uscita. 14 CAPITOLO 1. IL SISTEMA LOGISTICO E I MAGAZZINI
INDUSTRIALI 15 Figura 1.4: Magazzino con una zona di immagazzinamento (fonte:
Ghiani, Laporte, Musmanno) Nel magazzino di figura 1.4, la quantit`a di merce in entrata `e pressoch´e simile alla quantit`a di merce in uscita. A volte, invece,
in magazzini in cui la rotazione delle merci `e pi `u elevata, la zona
di immagazzinamento `e suddivisa in ingresso in una zona di riserva,
che riceve grandi quantit`a di imballo, le quali vengono separate in
unit`a di lavoro e in uscita in una zona di inoltro, dove si ha una
suddivisione pi `u fine. Se ne pu `o vedere un esempio in figura 1.5. 1.3.3 Mezzi di immagazzinamento La scelta della tipologia del mezzo di immagazzinamento da adot-
tare deriva fortemente dalle caratteristiche del bene da stoccare e
dal numero medio di elementi di ogni prodotto che compongono
l''ordine di un cliente. Per ogni tipologia si valutano tre parametri
di riferimento, che sono: ' la ricettivit`a della merce, ovvero la capacit`a totale di stoccag- gio, ' la selettivit`a, che `e pari al numero delle UdC direttamente accessibili diviso la ricettivit`a, 15 16 CAPITOLO 1. IL SISTEMA LOGISTICO E I MAGAZZINI INDUSTRIALI Figura 1.5: Magazzino con zona di riserva e zona di inoltro (fonte:
Ghiani, Laporte, Musmanno) ' e la potenzialit`a di movimentazione, cio`e il numero di UdC movimentabili in un''ora. Considerando lo stoccaggio di beni di tipo solido, le alternative principali di immagazzinamento sono tre: ' Pile: gli elementi sono posti in cartoni o pallettizzati e orga- nizzati in pile (o cataste), ovvero stoccando le UdC una sopra
l''altra. Questo metodo necessita un investimento di capitali
pressoch´e nullo ed `e adatto per immagazzinare beni a bassa do-
manda. Si ha un alto coe fficiente di sfruttamento volumentrico e superficiale dello spazio disponibile e il layout `e altamente
riconfigurabile, data l''assenza di strutture fisse. D''altra parte,
l''organizzazione a cataste `e caratterizzata da una bassa seletti-
vit`a (dato che solo le UdC poste in cima sono immediatamente
accessibili) e da una ridotta potenzialit`a di movimentazione. ' Sca ffali: in questo caso gli elementi da stoccare sono posti in sca ffali metallici, mediante scatole o pallet. Essi hanno il van- taggio di poter stoccare anche unit`a di carico non sovrapponi-
bili, di consentire un accesso pi `u facile agli elementi contenuti e
di poter allocare contenitori anche eterogenei nella forma. Un 16 CAPITOLO 1. IL SISTEMA LOGISTICO E I MAGAZZINI
INDUSTRIALI 17 esempio di questo sistema si pu `o vedere nella figura 1.6. Inol-
tre, l''impiego degli sca ffali d`a la possibilit`a di automatizzare i processi di deposito e recupero, mediante apposite macchine
descritte in seguito, ottimizzando lo spazio disponibile nella
struttura. In tal modo, infatti, `e possibile raggiungere un''al-
tezza massima pi `u alta rispetto alla modalit`a di stoccaggio
a pila e restringere la larghezza dei corridoi, aumentando la
capacit`a totale di stoccaggio. Per contro, essi richiedono un
investimento di capitali superiore rispetto alle altre tipologie.
I magazzini a sca ffalatura possono essere di tipo drive in o drive through ; la di fferenza fra i due `e che nel primo caso si ha una gestione LIFO (last in first out) delle merci, in quan-
to l''immissione e l''estrazione delle unit`a di carico avvengono
dallo stesso lato dello sca ffale, mentre nel secondo si ha una gestione FIFO (first in first out) delle merci, quindi le unit`a di
carico vengono immesse da un lato dello sca ffale e prelevate dall''altro. La selettivit`a di questa tipologia rimane comunque
bassa; per aumentarla, si pu `o fare ricorso a sca ffalature di tipo bifrontali, che raddoppiano l''accessibilit`a agli elementi. Fino
adesso si sono considerati solo magazzini statici, nei quali `e
solo l''operatore a muoversi e a movimentare le merci al suo in-
terno; i magazzini dinamici estendono questa capacit`a anche
alla struttura e quindi al materiale. Alcuni esempi sono rap-
presentati dagli sca ffali traslanti (o magazzino compattabile), dal live storage e dai canali in contropendenza. I primi consentono
un''elevata utilizzazione superficiale e volumetrica, ma `e im-
portante considerare il tempo necessario allo scorrimento delle
sca ffalature e della selettivit`a ridotta. I magazzini live storage forniscono una gestione LIFO delle unit`a di carico, mediante
sca ffalature inclinate costituite, in genere, da un piano di scor- rimento a rulli. Infine, i canali in contropendenza consentono
una gestione FIFO delle unit`a. Questi ultimi due metodi di
immagazzinamento sono convenienti se si considera la seletti-
vit`a a livello di gruppo e non di singola unit`a di carico, perch´e,
in genere, ad ogni canale corrisponde una linea d''ordine; in
caso contrario la selettivit`a risulta piuttosto bassa. 17 18 CAPITOLO 1. IL SISTEMA LOGISTICO E I MAGAZZINI INDUSTRIALI Figura 1.6: Un sistema di immagazzinamento a sca ffali (fonte: Ghiani, Laporte, Musmanno) ' Cassettiere: questa tipologia consiste nel disporre di piccoli sca ffali o cassettiere, per stoccare elementi di piccole dimen- sioni con semplice accesso da parte dell''uomo. In genere ven-
gono collocati nell''area di spedizione, nella quale si e ffettuano operazioni di picking. Anche in questo caso, si pu `o optare
per due ulteriori categorie di stoccaggio, con magazzini sta-
tici, anche detta operatore verso materiali o picker-to-product,
che utilizzano i media di stoccaggio appena presentati, o con
magazzini dinamici, anche detta materiali verso operatore o
order-to-picker. Questi ultimi sono pi `u convenienti quando si
deve assicurare una potenzialit`a di movimentazione elevata
e quando gli oggetti non hanno dimensioni particolarmente
grandi. Con l''utilizzo di caroselli o minitraslo si eliminano i
tempi persi nello spostamento dell''operatore, che costituisco-
no la maggior parte del tempo totale di prelievo nei magazzini
statici. 18 CAPITOLO 1. IL SISTEMA LOGISTICO E I MAGAZZINI
INDUSTRIALI 19 1.3.4 Approcci per stoccaggio e recupero merce I magazzini sono spesso classificati in base al metodo utilizzato
per stoccare e recuperare la merce. La scelta del tipo di accesso
da e ffettuare `e molto importante, in quanto da essa dipende la de- finizione ottimale del layout su cui modellare il magazzino, basata
sull''obiettivo di minimizzare i tempi delle operazioni. La gestione
manuale, ad esempio, richiede spazi di manovra maggiori rispetto
alla gestione automatizzata. Come accennato, si possono avere si-
stemi picker-to-product, dove gli ordini sono recuperati e assemblati
da operatori umani, o order-to-picker, i quali automatizzano il proces-
so. A partire da questi due, sono possibili ulteriori classificazioni.
Un primo esempio `e costituito dalla versione ibrida, vale a dire dai
sistemi picker-to-belt, dove gli elementi sono recuperati da uomini e
poi, mediante un nastro trasportatore, giungono alla fase di assem-
blaggio. Oppure, nei sistemi picker-to-product, gli operatori possono
viaggiare alle locazioni di stoccaggio mediante dispositivi automati-
ci, che in genere ricoprono un singolo corridoio (quindi, al massimo
due lati, appartenenti a due sca ffali diversi); essi prendono il nome di person-aboard automated storage /retrieval systems (AS/RSs). Nel caso in cui gli operatori si spostino a piedi o mediante carrelli, potendo
visitare pi `u corridoi, il sistema prende il nome di walkride and pick
systems (W /RPSs). I sistemi order-to-picker pi `u popolari sono gli AS /RSs (di cui si illustra una sua rappresentazione in figura 1.7; questi magazzini
automatici
consistono in una serie di corridoi di stoccaggio, ognuno dei quali `e servito da una singola macchina di deposito e prelievo
(e.g., trasloelevatore). Ogni corridoio, inoltre, `e dotato alla fine di
una stazione di carico e trasporto, accessibile in comune con il sistema
di gestione esterno (rulliera, nastro trasportatore o navetta). 1.3.5 Magazzini automatici I magazzini automatici rientrano nell''approccio per stoccaggio e re-
cupero merce di tipo order-to-picker. In Orogel si sono potuti analiz-
zare diversi impianti automatici con molteplici sistemi di trasporto.
Primo fra tutti, si `e potuto osservare un trasloelevatore all''opera: 19 20 CAPITOLO 1. IL SISTEMA LOGISTICO E I MAGAZZINI INDUSTRIALI Figura 1.7: Rappresentazione di un AS /RS (fonte: Ghiani, Laporte, Musmanno) posto in un corridoio, esso pu `o agire lungo i due lati di due sca ffali diversi, avendo la capacit`a di spostarsi lungo tre assi, in altezza,
larghezza e profondit`a. La comunicazione fra i vari corridoi avvie-
ne mediante una o pi `u navette, dotate di un sistema di traslazione
che permette loro di spostarsi lungo una sola direzione; inoltre, lo
scambio di materiale fra i trasloelevatori e le navette, avviene tra-
mite apposite rulliere che fungono da bu ffer, per rendere asincrona l''interazione fra le due macchine. Data l''altezza di questi impianti,
spesso sono suddivisi in piani, ognuno dei quali pu `o interagire con
l''esterno mediante appositi ingressi e uscite; per spostarsi in altezza,
vengono utilizzati degli elevatori. Un altro tipo di sistema di movimentazione visto in funzione, in una cella automatica pi `u piccola, `e formato da una coppia di
carroponti : essi, con il meccanismo di moto fissato al so ffitto, sono in grado di movimentare la merce dall''alto, spostandosi lungo tre
assi. In tal modo, riescono ad avere un raggio d''azione sull''intera
superficie della cella, con l''unico vincolo di non sovrapporsi. Questi sistemi riducono il tempo di percorrenza (che costitui- sce circa il 70% del tempo della gestione manuale dei prelievi nel
magazzino [2]), sono caratterizzati da bassi costi di esercizio, assi-
curando elevate prestazioni per quel che riguarda potenzialit`a di
movimentazione, ricettivit`a e tracciabilit`a (la possibilit`a di avere il 20 CAPITOLO 1. IL SISTEMA LOGISTICO E I MAGAZZINI
INDUSTRIALI 21 controllo su tutti i movimenti riguardanti una certa unit`a di carico).
La gestione automatica tramite computer ottimizza le variabili di
processo, come ad esempio l''ordine con il quale svolgere le opera-
zioni di prelievo o deposito e i percorsi da compiere. Per costruire
un tale sistema, per `o, `e necessario sostenere un elevato costo riguar-
do la struttura del magazzino e la struttura di movimentazione e
di controllo. Tali spese, perci `o, sono da considerarsi accettabili solo
a fronte di requisiti elevati su ricettivit`a e potenzialit`a, valutando
anche il fatto che una struttura di tale tipo `e fortemente vincolata e
non consente economiche riconfigurazioni. In Orogel si `e potuto osservare come funzioni quali la giacenza puntuale , la tracciabilit`a del prodotto e lo stoccaggio automatico siano svolte interamente via software, con la supervisione di diver-
si addetti e operatori, mediante un apposito warehouse management
system (WMS), chiamato On.Plant. Oltre a questo, inoltre, ogni im-
pianto automatico dispone di un software a s´e stante che consente
la supervisione dello stesso, controllando la correttezza delle ope-
razioni di movimentazione degli elementi e che permette, in caso
di problemi, un tempestivo intervento da parte degli operatori. Ad
ogni pallet in ingresso viene associata una precisa locazione di depo-
sito, calcolata con appositi algoritmi, che tengono conto, ad esempio,
della conformazione, del tipo di articolo, eccetera. Una volta porta-
to all''entrata dell''impianto di destinazione (o manualmente da un
carrellista oppure mediante altri impianti automatici di trasporto),
esso, comandato dal software, si attiva per condurre l''elemento nel
punto di deposito assegnato. Analogamente, in caso di vendita, tutti
gli articoli necessari sono portati all''uscita automaticamente, dopo-
dich´e un operatore, servendosi di un carrello elevatore, si occupa di
caricare i pallet sul camion. Si `e notato come questo tipo di gestione automatizzata del ma- gazzino permetta di minimizzare i percorsi da compiere al suo
interno, massimizzare gli spazi a disposizione, poter gestire in
maniera agevole la scadenza dei prodotti, il tutto rispondendo
tempestivamente alle esigenze di ricezione e spedizione delle merci Inoltre, in Orogel si `e visto come gli impianti automatici non sono solo utilizzati per la movimentazione interna, ma anche per
mettere in comunicazione i vari impianti di stoccaggio fra loro. `E 21 22 CAPITOLO 1. IL SISTEMA LOGISTICO E I MAGAZZINI INDUSTRIALI presente, infatti, un sistema automotore che collega due stabilimenti
(collocati su due lati opposti di una strada) e che trasporta pallet da
una struttura ad un''altra. Esso `e costituito da parti fisse (guide) e da
parti mobili (scambi) che analogamente ad una ferrovia guidano e
alimentano altri componenti mobili (bilancelle) lungo tutto il tragitto
da compiere. Un software consente di controllare lo stato dell''intero
impianto e di inviare comandi alle bilancelle. In questo ambito `e stato possibile aumentare personamente l''e- sperienza diretta, grazie ad attivit`a in Onit che sono seguite al ti-
rocinio. Il coinvolgimento in prima persona nell''implementazione
del software di supervisione di nuovi impianti automatici per il
transito della merce e di interfacciamento con l''automotore, ha per-
messo di conoscere e di comprendere pi `u a fondo l''ampio dominio
dell''automazione industriale. 1.3.6 Criteri di allocazione dei prodotti L''allocazione dei prodotti nell''area di stoccaggio `e una delle decisioni
operazionali pi `u importanti, in quanto influisce sulla pianificazione dei
depositi e dei prelievi. Queste due fasi, infatti, sono da e ffettuare in real-time; in un ambiente dinamico quale il magazzino, il sistema
non dispone a priori di tutte le informazioni, formate anche da una
componente casuale, riguardanti gli ordinima le ha solo al momento. Per ottimizzare le movimentazioni `e necessario, dunque, proget- tare adeguatamente le aree di stoccaggio, seguendo precisi criteri
per quel che riguarda l''allocazione dei prodotti nei media di imma-
gazzinamento; a tale scopo, si valutano le scelte basandosi su vari
parametri di movimentazione: ' Indice di rotazione: indica il grado di sostituzione delle scorte
su un certo periodo di tempo. Dato un generico prodotto i,
l''indice di rotazione `e definito da: IRi = Fui ¯ Gi =  1 T  dove Fui `e il flusso in uscita del prodotto i nel periodo T e ¯ Gi `e la giacenza media del prodotto i. Ipotizzando due prodotti a e 22 CAPITOLO 1. IL SISTEMA LOGISTICO E I MAGAZZINI
INDUSTRIALI 23 b con IRa > IRb, si deduce che il prodotto a, dal punto di vista della movimentazione, `e pi `u importante b. ' Indice di movimentazione: valuta il numero di movimenti ef-
fettuati mediamente nel periodo T; per un generico prodotto
i: IMi = Mi T =  1 T  dove IMi `e pari alle unit`a di carico del prodotto i movimen-
tante nel periodo T. Analogamente a prima, un prodotto
con IM maggiore di un altro risulta pi `u importante per la
movimentazione. ' Indice di accesso: calcola il numero di accessi nell''unit`a di tempo
alla cella del magazzino dedicata al prodotto i-esimo. Dato un
prodotto i, vale: IAi = IMi n 'cellei =  accessi T · vano  dove n 'celle `e pari al numero di celle dedicate al prodotto i, se esistono, oppure `e la giacenza media del prodotto; in
quest''ultimo caso vale IRi = IAi. Esso sintetizza la probabilit`a di accesso alla cella in questione sul periodo di tempo T. Sulla base di questi parametri si sceglie, di conseguenza, la politica di stoccaggio pi `u adatta, la quale pu `o essere di vari tipi: ' Dedicata: si assegna ad ogni prodotto un numero definito di
celle dedidate, fissandone la massima potenzialit`a ricettiva.
Questo metodo facilita la tracciabilit`a e la ricerca, ma si rischia
un sottoutilizzo della capacit`a complessiva. Si segue la di-
sposizione dei prodotti per indice di accesso decrescente, se si
vogliono ottimizzare i tempi di percorrenza, oppure per aree
merceologiche se si vuole facilitarne la ricerca. ' Basato su classi: si suddivide il magazzino in zone dedicate a
classi di prodotti e ogni articolo `e stoccato (casualmente) nella
zona della sua classe. Il tempo medio di accesso si riduce 23 24 CAPITOLO 1. IL SISTEMA LOGISTICO E I MAGAZZINI INDUSTRIALI all''aumentare del numero di classi individuate, ma con esse
aumenta anche la complessit`a gestionale. In genere, viene
valutato come 3 o 4 il numero di classi che consentono un
buon compromesso [4]. ' Casuale: questo tipo di politica ha l''approccio opposto a quella
dedicata: l''allocazione di un prodotto `e decisa dinamicamente,
in base all''occupazione corrente e alla previsione della doman-
da. Questo metodo consente la migliore utilizzazione della
capacit`a e quindi di superficie richiesta, ma il tempo medio di
accesso `e pari alla media dei tempi di accesso a tutti i vani. Le ultime due poliche necessitano l''utilizzo di supporti informa- tici per tenere traccia della locazione e degli spostamenti dei singoli
prodotti. Un ulteriore accorgimento `e relativo a come disporre gli articoli rispetto ai punti di ingresso e di uscita del magazzino; pi `u vicina `e la
collocazione dei prodotti a questi punti, infatti, minore `e la somma
dei tempi di stoccaggio e di prelievo. Perci `o risulta pi `u vantaggioso
disporre gli articoli a partire dai vani pi `u velocemente accessibili,
secondo un ordine decrescente degli indici di accesso. 1.3.7 Movimentazione interna La movimentazione interna si suddivide nella fase di deposito e in
quella di prelievo. Nella prima, una volta assegnata la posizione
ai prodotti, avviene l''allocazione vera e propria; specularmente a
questa, nella fase di prelievo, note le ubicazioni degli articoli, si
attua l''operazione di picking. Generalmente, la merce in ingresso
al magazzino presenta una maggior omogeneit`a, al contrario di
quella in uscita: infatti, gli ordini dei clienti dettaglianti coinvolgono,
spesso, un insieme di prodotti a maggior eterogeneit`a rispetto a
quelli provenienti dai fornitori. La parte di picking risulta, di solito,
pi `u dispendiosa di quella di deposito, in termini di locazioni diverse
da visitare e quindi di percorsi da compiere, perch´e richiede l''accesso
a pi `u classi diverse di prodotti. Le considerazioni presentate di
seguito valgono anche per i depositi, ma si preferisce focalizzarsi 24 CAPITOLO 1. IL SISTEMA LOGISTICO E I MAGAZZINI
INDUSTRIALI 25 sulla fase di prelievo, ritenuta, per l''appunto, pi `u significativa in
termini di complessit`a. Ogni ordine di vendita e spedizione, si traduce nella seguente serie di operazioni: 1. la formazione dei batch, ovvero l''insieme delle missioni di prelievo, 2. il calcolo dell''ordine di prelievo, 3. l''eventuale schedulazione della macchina, 4. e il caricamento dei veicoli. Nel primo punto gli ordini sono formati in batch (lotti); essi pos- sono essere combinati in un certo numero di modi, a seconda che
il magazzino sia suddiviso in zone oppure no. Nel primo stadio si
stima la dimensione ottima del batch (d'') che bilancia gli sforzi di
picking e di ordinamneto. Nel secondo stadio i batch sono creati
con la politica first come first served, aggregando d'' ordini consecuti-
vi. Il dimensionamento dei batch mira a minimizzare il calcolo di
lavoro totale, dato dalla somma dei tempi di picking e di ordina-
mento; il calcolo di d'' pu `o avvenire utilizzando modelli pi `u o meno
complessi, a seconda dei requisiti. Nel W /RPS, dove gli operatori si spostano a piedi o mediante carrelli motorizzati e visitano pi `u corridoi, il secondo punto `e uno
dei pi `u dispendiosi fra i quattro, richiedendo pi `u del 70% del tempo
[2]. Il routing sulla la scelta e l''ordinamento dei percorsi da prendere
fa parte di una classe pi `u grande di problemi di ottimizzazione nota
come VPR (vehicle routing problem), o come RTSP (road travelling
salesman problem) nel caso di operatore singolo. Si possono utilizzare
semplici algoritmi euristici per ottenere il compromesso voluto fra
tempi di calcolo e qualit`a della soluzione. Infine, il carico dei veicoli avviene impacchettando i prodotti, spesso in pallet o container. I primi sono adatti per essere traspor-
tati via camion, mentre i secondi via treno o nave. L''obiettivo, per
minimizzare i costi, `e rendere minimo il numero di contenitori neces-
sari per racchiudere gli oggetti: ci `o si traduce in ulteriori problemi
(di tipo geometrico) con pi `u o meno vincoli, ad esempio a seconda 25 26 CAPITOLO 1. IL SISTEMA LOGISTICO E I MAGAZZINI INDUSTRIALI che gli oggetti siano sovrapponibili, e a vari gradi di complessit`a, in
base al numero di dimensioni da prendere in considerazione. 1.4 In sintesi In questo capitolo si sono volute introdurre le principali tematiche
del dominio a cui ci si `e trovati di fronte all''inizio dell''attivit`a di
tirocinio. Partendo da una panoramica sulla logistica, per poi en-
trare nelle principali caratteristiche di un sistema logistico e infine
terminare con un breve dettaglio sui magazzini industriali, si `e no-
tato come le problematiche da a ffrontare, nella costruzione e nella gestione di un sistema logistico, si estendano a tutti i livelli della
catena e riguardino problemi della pi `u diversa natura: si va dalle
decisioni strategiche riguardo le strutture logistiche da inserire nella
supply chain, passando per la modellazione dei layout dei magazzini,
alla politica di stoccaggio e prelievo nel singolo impianto di depo-
sito merce. Questa `e la premessa su cui si basa l''attivit`a di studio
presentata nel capitolo seguente. 26 Capitolo 2 Pianificazione e ottimizzazione
dei percorsi
In questo capitolo si riporta il lavoro di studio e ricerca bibliografica,
con la formulazione di una sintesi adatta al problema della piani-
ficazione e ottimizzazione dei percorsi, nell''ambito dei magazzini
industriali presentati al capitolo precedente. Dopo una introduzione all''argomento, si descrive la parte di mo- dellazione del magazzino, enfatizzando l''importanza di una rap-
presentazione formale della sua struttura e dello spazio, che `e la
premessa necessaria alla successiva elaborazione algoritmica. Nella sezione seguente si delinea come poter ottimizzare i per- corsi a partire dal modello creato al passo precedente, presentando
algoritmi che possono essere utilizzati allo scopo. Infine si mostra uno schema che modella i possibili sistemi che realizzano queste funzioni, riportato dalla letteratura. 2.1 Introduzione La pianificazione dei percorsi all''interno dei magazzini industriali
riguarda tutta l''attivit`a di modellazione, progettazione ed esecuzione atta
ad ottimizzare i movimenti degli operatori (umani o macchine) al loro
interno, generalmente durante la fase di spostamento della merce. 27 28 CAPITOLO 2. PIANIFICAZIONE E OTTIMIZZAZIONE DEI PERCORSI Come `e stato introdotto nel capitolo precedente, la movimenta- zione degli elementi avviene principalmente per stoccare la merce in
ingresso o per prelevare quella in uscita (ad esempio per la vendita o
per l''asservimento a linee di produzione). Pianificare il pi `u possibile
gli spostamenti degli operatori risulta di fondamentale importanza
per ottimizzare i tempi e i costi di lavoro in un magazzino, dimo-
doch´e si possano evadere gli ordini nella maniera pi `u veloce e meno
costosa possibile. Questi due parametri dipendono principalmente
dalla distanza che `e necessario percorrere durante lo svolgimento
di una particolare operazione. `E necessario, dunque, recuperare tutte le informazioni a dispo- sizione: a partire dalla struttura di un magazzino, ipotizzando la
presenza di una serie di sca ffali, e data la relativa metodologia per spostarsi al suo interno, `e utile derivarne un modello che riassuma
le informazioni necessarie alla pianificazione e ottimizzazione dei
percorsi. Questo modello deve essenzialmente sintetizzare i punti
accessibili dagli operatori durante gli spostamenti, ovvero tutte le
varie locazioni degli sca ffali, e gli spazi utilizzabili per raggiunger- li, fermo restando i vincoli strutturali, come la presenza di corridoi
percorribili solo in un senso di marcia o eventuali ostacoli. Tutte queste informazioni sono definite a priori e possono essere sfruttate in fase di configurazione dei percorsi, la prima volta per
tutte, fino ad un eventuale cambiamento di una delle condizioni
sopraelencate. Le variabili su dove e come organizzare le merci nel
magazzino non sono argomento di studio di questa tesi, per cui, non
sapendo con certezza quali articoli e quali locazioni riguarderanno i
prossimi ordini, non `e possibile calcolare il percorso per recuperare
i prodotti, una volta per tutte. In base a quanto detto, questa fase deve necessariamente essere svolta al momento, solo quando si hanno tutte le informazioni sul-
l''ordine. Una buona pianificazione dei percorsi deve, quindi, saper gestire
depositi e prelievi di un insieme di locazioni scelte casualmente e dare solu-
zioni accettabili, in termini di tempi e costi, in tutti questi possibili insiemi.
Essa `e necessaria ad una movimentazione e fficace della merce. 28 CAPITOLO 2. PIANIFICAZIONE E OTTIMIZZAZIONE DEI
PERCORSI 29 2.2 Modellazione del magazzino Il primo passo nella pianificazione e ottimizzazione dei percorsi `e
di avere un modello formale del magazzino; com''`e noto, questo
artefatto consente di semplificare la realt`a, evidenziando solamente
le informazioni ritenute essenziali e interessanti, in base all''obiettivo
che si vuol perseguire, e di poter essere elaborato da una macchina. Di seguito si descrivono brevemente una serie di idee riferite a implementazioni di sistemi esistenti, ognuno costruito sulle proprie
peculiarit`a; avere una visione d''insieme, documentadosi su soluzio-
ni gi`a presenti, `e un passo utile per decidere le scelte migliori da
adottare in seguito. 2.2.1 Panoramica sulla modellazione Usualmente la pianificazione dei percorsi si svolge per determina-
re il viaggio che deve compiere un lavoratore o una macchina (ad
esempio, un robot) attraverso un''area, la quale `e anche riferita come
spazio gestito. Un percorso pianificato pu `o essere calcolato basan-
dosi su dati che descrivono lo spazio che deve essere gestito (un
magazzino, in questo caso). I metodi tradizionali della pianificazio-
ne determinano dove sono posti gli ostacoli all''interno dello spazio
(muri, macchinari, sca ffalature, eccetera) e cercano di identificare un percorso che li aggiri. Tali metodi sono computazionalmente molto
costosi e spesso non forniscono il risultato voluto; ad esempio, si
potrebbe voler determinare la distanza del percorso calcolato, che
non `e possibile fare sempre con questo tipo di sistemi. Al contrario, esistono metodi che determinano i percorsi in uno spazio gestito basati sul modello del layout che definisce le tratte
possibili: invece di definire lo spazio in termini di ostacoli (cio`e
dove non pu `o esserci un percorso), si pu `o rappresentare l''insieme
delle aree discrete all''interno delle quali `e possibile spostarsi [6]. Il
modello del layout definisce le tratte percorribili come una rete di nodi , i quali indicano i punti dove iniziano e finiscono le tratte e le loro intersezione. Quando una certa operazione richiede di spo-
starsi lungo lo spazio, il sistema di pianificazione pu `o generare un
percorso dal punto di partenza alla locazione di destinazione ba- 29 30 CAPITOLO 2. PIANIFICAZIONE E OTTIMIZZAZIONE DEI PERCORSI sandosi sul modello del layout. Inoltre, questo tipo di definizione
permette una maggior flessibilit`a nella specifica dei percorsi, au-
mentando l''e fficacia nella gestione. Un miglioramento significativo riguarda l''abilit`a di calcolare la distanza del percorso, potendo cos`ı
derivare anche una stima del tempo atteso per completare una certa
operazione. Le locazioni all''interno dello spazio possono essere connesse ai possibili percorsi basandosi sulle loro coordinate. Ogni elemento o
area di lavoro pu `o dunque essere associata, in base alle sue coor-
dinate, a una particolare tratta; la determinazione dei percorsi pu `o
essere prima elaborata sui percorsi associati alle locazioni da rag-
giungere e poi relativa alla singola tratta, ordinando le specifiche
destinazioni ad essa collegate. Il concetto di percorso migliore spesso si traduce in quello pi `u breve . Infatti, di frequente `e richiesto che il viaggio da intraprendere fra le locazioni desiderate sia anche quello pi `u corto; per fare ci `o,
di solito si impiegano algoritmi euristici, che includono la ricerca
depth first, breadth first oppure una combinazione di esse [6]. Pu `o
anche essere necessario dover considerare dei vincoli aggiuntivi,
come l''obbligo di dover utilizzare un particolare macchinario (ad
esempio, un certo carrello elevatore) per svolgere il compito. Il calcolo della distanza pu `o essere eseguito sia per obiettivi di pianificazione, ad esempio per determinare quanto tempo pu `o im-
piegare un compito, e /o di valutazione, individuando se un compito sia stato svolto nei tempi attesi. Molti processi all''interno di un ma-
gazzino otterrebbero dei benefici dalla conoscenza della distanza
fra due locazioni e, di conseguenza, dalla distanza totale compiuta
relativa a un ordine di picking. Oltre a ci `o, in altre implementazioni, si svolge un controllo di funzionalit`a per stabilire la completezza e la consistenza del mo-
dello del layout, cio`e se `e possibile viaggiare da un qualsiasi nodo a
un altro della rete, potendo raggiungere tutte le locazioni mediante
essi. Generalmente, questo controllo viene fatto prima di memoriz-
zare la rete di nodi come modello, durante la generazione del layout
model; in altro modo, pu `o essere svolto contemporaneamente alla
pianificazione di percorsi, determinando se un cammino `e possibile
o meno. 30 CAPITOLO 2. PIANIFICAZIONE E OTTIMIZZAZIONE DEI
PERCORSI 31 2.2.2 Generazione del modello La generazione del modello del layout, per derivare lo spazio gestito,
richiede i dati di anagrafica del magazzino, che includono l''indica-
zione delle coordinate (x, y) di ogni elemento strutturale presente
al suo interno, sia esso un ostacolo, una stazione di lavoro, o altro.
Una rappresentazione a griglia dello spazio gestito pu `o indicare
quali aree sono occupate e quali no, cos`ı, invece di rappresentare un
modello di pianificazione dello spazio in termini di ostacoli, il siste-
ma pu `o determinare quali sono le aree libere e definire i possibili
percorsi per attraversarle. Questi ultimi sono rappresentati come
segmenti di linea delimitati da una coppia di coordinate della rap-
presentazione a griglia, con associata una misura della lunghezza.
Il sistema poi identifica le intersezioni (sovrapposizioni fra le linee)
e genera la rete di nodi; essa viene utilizzata come modello per pia-
nificare i viaggi attraverso il magazzino. In tal modo, si pu `o anche
avere l''informazione riguardante la distanza complessiva sostenuta
attraverso la percorrenza di un insieme di tratte. In un approccio a percorsi possibili si pu `o identificare l''inizio e la fine di uno sca ffale di un corridoio, calcolando la lunghezza di quest''ultimo, e si pu `o tracciare una freccia o una linea che raggiunge
tutte le locazioni dello sca ffale lungo il corridoio. Mediante una ul- teriore freccia si pu `o stabilire la connessione al corridoio successivo,
e cos`ı via. La lunghezza di tali segmenti `e determinabile basandosi
sui dati di anagrafica del magazzino. Il risultato di questa serie di
operazioni `e un insieme di lati e frecce che definiscono la rete, dove
ogni segmento indica un possibile percorso. Si pu `o anche tenere conto di informazioni aggiuntive da salvare assieme al modello. Ad esempio, ogni percorso pu `o essere associa-
to a un vincolo di percorrenza, come la larghezza della tratta e la
dimensione della risorsa che pu `o o meno attraversarla, la direzione
obbligatoria di passaggio oppure la sua suddivisione in corsia de-
stra e corsia sinistra. In sintesi, qualsiasi tipo di vincolo operativo `e
quindi associabile ai percorsi, sia di natura arbitraria che derivante
da caratteristiche intrinseche della struttura. 31 32 CAPITOLO 2. PIANIFICAZIONE E OTTIMIZZAZIONE DEI PERCORSI 2.3 Ottimizzazione dei percorsi In questa sezione vengono esposte alcune comuni soluzioni nel cal-
colo dei percorsi per la fase di movimentazione interna di un magaz-
zino. Anche in questo ambito la letteratura `e molto vasta, quindi si
riporta una sintesi sulla teoria che ha ispirato il capitolo successivo. Spesso i riferimenti fatti dalla letteratura su questo genere di algoritmi sono raccontati mediante metafore su mappe stradali,
ma possono valere allo stesso modo se riportati in un contesto di
movimentazione interna nei magazzini. 2.3.1 Introduzione al calcolo dei percorsi Come accennato precedentemente, si possono utilizzare alcune eu-
ristiche per calcolare il miglior tragitto attraverso lo spazio gestito
del magazzino. Una combinazione di queste pu `o impiegare una ve-
loce ricerca depth first per trovare una prima soluzione ammissibile,
per poi modificarla mediante una ricerca breadth first per ottenere
miglioramenti alla soluzione iniziale. In aggiunta, si pu `o fare ricorso a criteri di stop, che indicano soglie numeriche superate le quali si intende fermare l''algortimo;
ad esempio, si possono applicare per limitare la ricerca breadth fir-
st ad un numero di nodi da visitare pari a quello della soluzione
iniziale. Questi criteri possono non portare ad alcun beneficio in
termini di qualit`a, ma servono per limitare l''intensit`a computazio-
nale del calcolo del percorso, come in caso di requisiti temporali da
soddisfare. In aggiunta a questi algoritmi, si possono utilizzare ulteriori me- triche per la generazione dei percorsi, ad esempio decidere se im-
piegare il calcolo della distanza Euclidea, Manhattan o una loro
combinazione. La prima considera il tratto fra due punti come una
linea retta, vista come l''ipotenusa di un triangolo rettangolo tra le
due coordinate di un punto di inizio e un punto di fine. La distanza
Manhattan considera il tratto fra due punti come definito in due
segmenti, il primo che si sposta solo lungo l''asse X e il secondo solo
lungo l''asse Y, fra le coordinate dei punti di start e di stop. In questo
modo, tutti i percorsi sono composti da soli angoli retti. 32 CAPITOLO 2. PIANIFICAZIONE E OTTIMIZZAZIONE DEI
PERCORSI 33 Nelle sottosezioni seguenti si riportano delle categorie di proble- mi e soluzioni note che modellano viaggi da ottimizzare in una rete
di percorsi. 2.3.2 Vehicle routing problem Il vehicle routing problem, o VRP, consiste nel determinare i percorsi
per una flotta di veicoli che devono raggiungere un insieme di utenti.
Il VRP pu `o essere definito su di un grafo G = (V, A, E), dove V `e l''insieme dei vertici, A `e l''insieme degli archi e E `e l''insieme dei lati.
Il vertice 0 rappresenta il punto di deposito, nel quale sono collocati
gli m veicoli, mentre i sottoinsiemi dei vertici richiesti U '' V e degli
archi e lati richiesti R '' A ' E rappresentano gli utenti. L''obiettivo
del VRP `e determinare l''insieme degli m tour a costo minimo che
attraversano il deposito, i vertici, gli archi e i lati richiesti. In una rappresentazione a grafo, gli archi e i lati corrispondono a tratte percorribili e i vertici a intersezioni fra esse. Utenti singoli
sono rappresentati da un vertice richiesto, mentre i sottoinsiemi di
clienti distribuiti in maniera quasi continua in un insieme di utenti
sono modellati come archi o lati richiesti. All''interno di un magazzino, la rappresentazione pratica sarebbe quella di un insieme di risorse (i veicoli) che devono essere utiliz-
zate al meglio per trasportare la merce e raggiungere i punti di
deposito /prelievo (i clienti) previsti, attraverso il grafo dei percorsi. Se R = '', il VRP `e chiamato node routing problem (NRP), mentre se U = '' `e chiamato arc routing problem (ARP). I problemi NRP sono stati studiati pi `u approfonditamente degli ARP e sono usualmente
riferiti direttamente come VRP. Se vale m = 1 e in assenza di vincoli particolari, il NRP diventa il classico travelling salesman problem (TSP),
che consiste nel determinare un singolo circuito su tutti i vertici di
G, mentre l''ARP diviene il rural postman problem (RPP), che mira a
trovare un singolo circuito che include gli archi e i lati di R. Il RPP
si riduce al Chinese postman problem (CPP) se ogni arco o lato deve
essere attraversato (R = A ' E). I pi `u comuni vincoli operazionali sono: 33 34 CAPITOLO 2. PIANIFICAZIONE E OTTIMIZZAZIONE DEI PERCORSI ' il numero di veicoli m pu `o essere fissato o essere una variabi- le decisionale, eventualmente soggetta a un vincolo di limite
massimo; ' la merce totale trasportata da un veicolo, in ogni istante, non deve eccedere la sua capacit`a; ' la durata di ogni tratta non deve eccedere la durata del turno di lavoro; ' alcuni clienti devono essere serviti entro un intervallo di tempo prestabilito; ' il servizio di un cliente deve essere svolto da un singolo veicolo o da un insieme di essi; ' i clienti sono soggetti a relazioni di precedenza. Quando `e necessario prendere in considerazione esplicitamente vincoli di tempo, nella formazione delle tratte, il VRP `e spesso riferito
come vehicle routing and scheduling problem (VRSP). Vincoli di precedenza appaiono nel caso in cui i beni debbano essere trasportati fra specifiche coppie di punti di carico e scarico
merci. In questo caso, ogni coppia deve essere servita dallo stesso
veicolo e ogni punto di carico deve essere visitato prima del punto
di scarico a lui associato. Simili relazioni di precedenza vengono
imposte quando i veicoli devono prima eseguire un certo numero
di consegne e in seguito una serie di carichi. Ipotizzando l''assegnazione di un costo di attraversamento per ogni arco e lato, l''obiettivo pi `u comune `e quello di minimizzare i
costi totali nella percorrenza del grafo, sommati ai costi fissi relativi
all''uso dei veicoli. Nella risoluzione di questo tipo di problemi si fa spesso ricorso a euristiche, per due motivi principali: innanzitutto, gli algoritmi
esatti per il VRP sono spesso funzioni ricorsive piuttosto comples-
se, che permettono di risolvere solo piccole istanze del problema;
inoltre, soluzioni ammissibili devono spesso essere generate in un
breve, ragionevole, lasso di tempo. 34 CAPITOLO 2. PIANIFICAZIONE E OTTIMIZZAZIONE DEI
PERCORSI 35 2.3.3 Travelling salesman problem In assenza di vincoli operativi, esiste sempre una soluzione ottimale
al NRP nel quale si usa un solo veicolo [5]. Quindi, il NRP si riduce
a travelling salesman problem, che consiste nel trovare il tour a costo
minimo che visita tutti i vertici e il deposito. In ogni soluzione am-
missibile del TSP su un grafo G, ogni vertice U ' {0} compare almeno
una volta e due vertici successivi sono collegati da un percorso a
costo minimo. Come conseguenza, il TSP pu `o essere riformulato
su un grafo ausiliario direzionato completo G 0 = (V0, A0), dove V 0 = U ' {0} `e l''insieme dei vertici e A0 `e l''insieme degli archi. Ad ogni arco (i , j) '' A0 `e associato un costo cij pari a quello del percorso di costo minimo da i a j in G. Tali costi soddisfano la disuguaglianza
triangolare: cij ' cik + ckj, ''(i , j) '' A0, ''k '' V0, k , i, j Data questa propriet`a, esiste una soluzione ottimale del TSP che `e un tour Hamiltoniano in G 0, ovvero un circuito nel quale ogni vertice in V 0 appare esattamente una volta. Se cij = cji per ogni coppia di vertici distinti i, j '' V0, allora il TSP `e detto simmetrico (STSP), altrimenti `e detto asimmetrico (ATSP). Ovviamente, le soluzioni ottenute sull''ATSP sono ammissibili anche
per il STSP, anche se `e un approccio spesso poco e fficiente [5]. Queste premesse sono utili per anticipare il modello del road travelling salesman problem. 2.3.4 Road travelling salesman problem Come anticipato nel capitolo 1, il problema della scelta del percorso
da compiere per raggiungere un insieme di locazioni del magazzino `e noto come order picker routing. Il road travelling salesman problem (RTSP) `e una variante del classico TSP, che consiste nel determinare
il tour di costo minimo su un sottoinsieme dei vertici del grafo G,
per un singolo veicolo (m = 1). Il RTSP ha complessit`a NP-hard, ma nel caso dei magazzini `e spesso risolvibile in tempo polinomiale a causa delle particolari ca-
ratteristiche della rete dei percorsi. Facendo riferimento alla figura 35 36 CAPITOLO 2. PIANIFICAZIONE E OTTIMIZZAZIONE DEI PERCORSI Figura 2.1: Esempio di order picker routing (fonte: Ghiani, Laporte,
Musmanno) 2.1, nel caso in cui ogni corridoio abbbia un solo ingresso, la tratta
a percorrenza pi `u breve `e data visitando prima le locazioni di stoc-
caggio raggiungibili dai corridoi della parte alta della figura e poi
visitando quelli nella parte bassa. Se invece i corridoi hanno pi `u interruzioni (ad esempio per la presenza di pi `u corridoi trasversali), il problema pu `o essere risolto
all''ottimo utilizzando l''algoritmo di programmazione dinamica di
Ratli ff e Rosenthal, il cui caso peggiore di complessit`a computazionale `e dato da una funzione lineare sul numero dei lati dei corridoi. In ogni modo, alla presenza di diversi corridoi ortogonali, il numero
di stati e transizioni aumenta rapidamente e l''uso delle procedure
dinamiche di programmazione diviene non praticabile. Per questi
motivi, vengono utilizzate due semplici euristiche: ' Euristica S-shape: ogni corridoio che contiene almeno un ele- mento che deve essere recuperato viene attraversato intera-
mente. I corridoi che non includono elementi da prelevare
sono saltati. ' Euristica largest gap: in questo contesto, il gap `e la distanza fra due elementi adiacenti che devono essere recuperati in un 36 CAPITOLO 2. PIANIFICAZIONE E OTTIMIZZAZIONE DEI
PERCORSI 37 Figura 2.2: Euristica s-shape (fonte: Ghiani, Laporte, Musmanno) corridoio, o la distanza fra l''ultimo elemento che deve essere
prelevato in un corridoio e il corridoio trasversale pi `u vicino.
L''operatore si posizione dal lato del corridoio pi `u vicino alla
porta di ingresso /uscita, andando verso quello che include al- meno un elemento da recuperare. Dopodich´e egli attraversa
il corridoio interamente, mentre entra ed esce nei rimanenti
corridoi una o due volte, sempre dallo stesso lato, a seconda
del gap maggiore del corridoio. I percorsi generati in questa
maniera possono risultare problematici all''atto pratico della
movimentazione; le inversioni a U nelle corsie sono potenzial-
mente pericolose e poco pratiche in un magazzino con corridoi
a larghezza ridotta. Basandosi su una mappa che prevede di prelevare degli elementi, nelle due figure riportate si applica in un caso l''euristica s-shape 2.2
e nell''altro l''euristica largest gap 2.3. In alternativa, come per il TSP, anche l''ATSP pu `o essere riformu- lato su un sottografo ausiliario direzionato completo G 00 = (V00, A00), 37 38 CAPITOLO 2. PIANIFICAZIONE E OTTIMIZZAZIONE DEI PERCORSI Figura 2.3: Euristica largest gap (fonte: Ghiani, Laporte, Musmanno) 38 CAPITOLO 2. PIANIFICAZIONE E OTTIMIZZAZIONE DEI
PERCORSI 39 dove V 00 = U0 ' {0} `e l''insieme dei vertici, con U0 '' U sottoinsieme dei vertici da visitare, e A 0 `e l''insieme degli archi. Come nella defini- zione precedente, ad ogni arco (i , j) '' A0 `e associato un costo cij pari a quello del percorso di costo minimo da i a j in G, che soddisfano
la disuguaglianza triangolare. Per questo esiste una soluzione ottimale dell''ATSP che `e un tour Hamiltoniano in G 00, ovvero un circuito nel quale ogni vertice in V00 appare esattamente una volta. All''interno dei magazzini pu `o essere utile adottare il modello dell''ATSP per rappresentare i percorsi all''interno, in quanto molto
spesso le tratte sono direzionate per la presenza di corridoi o corsie
a sensi unici di attraversamento. 2.3.5 Algoritmi euristici Gli algoritmi euristici accennati in precedenza garantiscono di cal-
colare una soluzione che approssima l''ottimo. Il loro obiettivo `e
determinare una soluzione ammissibile di buona qualit`a in un tem-
po di calcolo accettabile, ottenendo un bound della soluzione ottima.
Essi si dividono in due categorie:
Algoritmi euristici costruttivi : partono da una soluzione vuota e determinano iterativamente nuovi elementi fino a una soluzione
completa. Essi seguono un criterio di espansione per scegliere quale
elemento aggiungere in soluzione, in alcuni casi pre-ordinandoli.
Per il TSP si possono applicare nell''espansione di un cammino o di
un ciclo, fino alla soluzione completa. Si di fferenziano per la scelta del ciclo o del vertice iniziale, per il criterio di selezione del vertice da
inserire e per il criterio di inserzione (ovvero, dove inserire il vertice).
Alla generica iterazione h si ha un ciclo o cammino che coinvolge
S '' V vertici; termina quando S ' V. Fra questo tipo di algoritmi `e importante ricordare il nearest neighbor e il cheapest insertion. Il primo sceglie il vertice iniziale in maniera arbitraria e poi procede con l''espansione di un cammino,
scegliendo il vertice pi `u vicino e aggiungendolo in fondo. Cos`ı
facendo, per `o, spesso l''arco di chiusura risulta lungo e la soluzione
dipende molto dal verdice iniziale. 39 40 CAPITOLO 2. PIANIFICAZIONE E OTTIMIZZAZIONE DEI PERCORSI Di seguito, viene riportato l''algoritmo nearest neighbor sotto for- ma di pseudo-codice: it : = 1; s(1) : = i; while it < n do determina k : cs(it),k :=min{cs(it),j : j < S};
s(it + 1) := k; it : = it + 1; end while ; Descrivendo singolarmente le variabili: ' i `e il vertice iniziale, scelto arbitrariamente; ' it `e il contatore delle iterazioni; ' n `e il numero di vertici totali; ' S `e l''insieme dei vertici in soluzione; ' s(i) indica il vertice in posizione i fra quelli inseriti nella solu-
zione s; ' ci,j indica il costo dell''arco che collega i vertici i e j. La complessit`a risultante `e O(n2), dipendente dal numero dei vertici. L''algoritmo cheapest insertion procede per espansione di ciclo. La coppia iniziale `e composta da un vertice arbitrario e dal quello a
lui pi `u distante, dopodich´e si procede ad ogni passo selezionando
il vertice per cui `e minimo il costo di inserzione in S (insieme dei
vertici presenti in soluzione). L''inserzione del vertice k tra i vertici
in soluzione Si e Si+1 comporta una variazione di costo data da: δ(k, i) = cS i,k + ck,Si +1 '' cS i,Si +1 , i '' S , k < S Per ogni vertice che non appartiene ad S si pu `o definire: µ ( j) = argmin{δ(j, i) : i '' S} 40 CAPITOLO 2. PIANIFICAZIONE E OTTIMIZZAZIONE DEI
PERCORSI 41 Questi valori si definiscono in tempo O(n2) e sono aggiornabili in tempo O(n). Inoltre, il punto di inserzione in tal modo `e definito
univocamente, nella posizione successiva a µ(k). Algoritmi euristici di ricerca locale : partono da una soluzio- ne (anche non ammissibile) e cercano iterativamente di migliorarla
e ffettuando semplici modifiche (mosse). Queste ultime possono es- sere, ad esempio, scambi di elementi fra quelli in soluzione e quelli
che non lo sono. Tali algoritmi hanno termine quando non esistono
pi `u modifiche che migliorano la selezione corrente. Tra i miglioramenti applicabili, si pu `o scegliere se eseguire il pri- mo scambio migliorante (first improvement) o il migliore tra quelli
disponibili (best improvement). L''insieme delle soluzioni ottenibili
dalla soluzione corrente mediante le mosse si chiama intorno o nei-
ghborhood (vicinato) e sono ottenute applicando una neighborhood
function
alla soluzione corrente. Le ricerche locali hanno applicabilit`a generale e flessibilit`a, ri- chiedono un valutatore di soluzioni, la verifica dell''ammissibilit`a,
una funzione che genera il vicinato e una esplorazione del neighbo-
rhood e fficiente. Il problema centrale risiede nella definizione del vicinato, che `e fortemente dipendente dal problema. Un metodo
generale `e quello del neighborhood basato sugli scambi di sequenze
o partizioni degli elementi presenti nella soluzione. Applicando questo concetto al TSP, per generare un nuovo vicino si possono rimuovere k archi dalla soluzione, aggiungendone altret-
tanti non selezionati in precedenza. La cardinalit`a del vicinato di-
pende, quindi, dal valore di k scelto, in quanto gli archi rimossi pos-
sono essere ricombinati in modi sempre pi `u diversi all''aumentare
di k. La qualit`a dell''ottimo (locale) raggiunto da questo tipo di algo- ritmi dipende molto dalla soluzione iniziale e dal vicinato, perci `o si
possono attuare alcuni miglioramenti, come la tecnica multi-start:
essa genera diverse soluzioni iniziali (con perturbazioni casuali) e
procede con una ricerca locale per ognuna. Le prestazioni di un euristico sono valutabili sia sperimentalmente, osservando la qualit`a delle soluzioni su istanze di test, sia basandosi
sul caso peggiore, in maniera analitica, misurando il massimo errore
ottenibile rispetto alla soluzione ottima. 41 42 CAPITOLO 2. PIANIFICAZIONE E OTTIMIZZAZIONE DEI PERCORSI Una loro evoluzione `e rappresentata dagli algoritmi meta-euristici: essi implementano algoritmi di ricerca locale che usano tecniche per
uscire dai minimi locali, evitando il verificarsi di cicli, per cercare
una soluzione migliore al di fuori di essi. 2.3.6 Algoritmi meta-euristici Le tecniche meta-euristiche sono algoritmi di ricerca locale con meto-
di per uscire da minimi locali, che cercano di evitare i cicli durante
la loro evoluzione. In generale sono molto e fficaci e di facile imple- mentazione, ma richiedono tempi di esecuzione molto pi `u elevati
rispetto agli euristici di prima [8]. Il primo che si presenta `e il tabu search: esso rappresenta una generalizzazione della ricerca locale che consente l''accettazione di
mosse peggiorative della soluzione. Viene utilizzata una memoria
a breve termine, detta tabu list, per evitare di ritornare nelle ultime
soluzioni visitate. La lunghezza di tale memoria `e un parametro
dell''algoritmo, d''ora in poi chiamato t. Ipotizzando un problema di minimizzazione della funzione obiet- tivo, se ne riporta il funzionamento mediante pseudo-codice: soluzione iniziale s di valore z(s)
s '' : = s; k : = 1; T = {s}; while not STOP CRITERION do genera il neighborhood non tabu N(s) \ T
trova la migliore soluzione s 0 '' N(s) \ T rispetto a z(·) if z(s 0) < z(s) then s'' := s; kbest := k s : = s0; k : = k + 1; inserisci s 0 in T al posto della soluzione pi `u vecchia end while ; Descrivendo singolarmente le variabili: ' s `e la soluzione attuale, aggiornata ad ogni iterazione; 42 CAPITOLO 2. PIANIFICAZIONE E OTTIMIZZAZIONE DEI
PERCORSI 43 ' z(s) `e il valore della funzione obiettivo della soluzione s; ' k `e il contatore delle iterazioni; ' N(s) `e l''insieme del vicinato della soluzione s; ' T `e l''insieme delle soluzioni tabu; ' s 0 `e la migliore soluzione trovata nell''insieme del vicinato, meno le soluzioni tabu, ad ogni iterazione; ' s '' `e la migliore soluzione trovata attualmente, aggiornata ad s0 solo `e migliore di s; ' kbest `e il numero dell''iterazione nella quale si `e trovata l''ultima
s ''; ' s(i) indica il vertice in posizione i fra quelli inseriti nella solu-
zione s; ' ci,j indica il costo dell''arco che collega i vertici i e j; ' STOP CRITERION: sono i criteri di arresto dell''algoritmo e ce ne possono essere di diversi: '' N (s) \ T = '': se l''insieme del vicinato meno le soluzioni tabu `e uguale all''insieme vuoto; '' se k > kmax, ovvero se si `e raggiunti un certo limite di iterazioni kmax; '' se si `e raggiunti un tempo limite nell''elaborazione; '' se k '' kbest > knon improving ovvero se la soluzione non viene migliorata da un numero di iterazioni knon improving; '' se si `e trovata s '' ottima, ad esempio uguale ad un lower bound. L''aspetto critico riguarda la tabu list, infatti memorizzare T so- luzioni pu `o essere oneroso, in quanto ognuna `e un vettore di n
elementi; verificare se una soluzione `e tabu ha complessit`a O(n · |T|).
Per porre rimedio a questi calcoli dispendiosi si possono memo-
rizzare solamente delle caratteristiche delle soluzioni, invece delle 43 44 CAPITOLO 2. PIANIFICAZIONE E OTTIMIZZAZIONE DEI PERCORSI soluzioni intere, oppure ricordare nella tabu list le mosse applicate,
anche se in tal modo si proibisce un numero di soluzioni maggiore.
Per fare ci `o si ricorre all''utilizzo di una TI che memorizza le mosse
inverse delle ultime utilizzate, per evitare di ritornare nel punto di
prima. Come detto, questa TI `e molto pi `u restrittiva ti T, ma non ga-
rantisce comunque che non si abbiano cicli di periodo ' |TI|. Questa
tabu list `e chiamata memoria di breve periodo, siccome `e possibile
utilizzare anche dei criteri di aspirazione, ovvero: per sopperire alle
condizioni troppo restrittive della tabu list, le mosse tabu possono
essere comunque e ffettuate se conducono ad una buona soluzione. Per fare ci `o si impiega una memoria di lungo periodo che con-
sente sia intensificazione, preferendo mosse simili a quelle recenti,
senza spostarsi troppo dalla regione attuale, che diversificazione, an-
dando verso zone inesplorate. La lunghezza t della tabu list viene
aggiornata dinamicamente in tal modo: ' se s '' `e migliorata: t = max{tmin, t '' 1} = intensificazione; ' se s '' `e immutata: t = min{tmax, t + 1} = diversificazione. Si possono ora immaginare diversi tipi di tabu list da applicare al travelling salesman problem, ad esempio: ' `e tabu muovere il vertice i per t iterazioni: '' si pu `o salvare la lista dei vertici tabu, '' o salvare l''iterazione in cui `e stato mosso il vertice; ' basandosi su un neighborhood 2-opt, nel quale ogni vicino `e ottenuto sostituendo una coppia di archi con una incrociata: '' T pu `o contenere il lato pi `u corto rimosso (Glover 86); '' T pu `o contenere le coppie di archi pi `u costose rimosse (Knox 94). Infine, se il problema `e fortemente vincolato la cardinalit`a del vicinato `e molto piccolo; in questo caso si possono rilassare dei vin-
coli, riportarne le violazioni inserendo delle penalit`a nella funzione 44 CAPITOLO 2. PIANIFICAZIONE E OTTIMIZZAZIONE DEI
PERCORSI 45 obiettivo, regolandole in maniera dinamica; ad esempio, se da molte
iterazioni le soluzioni risultano tutte inammissibili, si aumentano le
penalit`a delle violazioni per riportarsi su zone ammissibili. Un altro tipo di algoritmo meta-euristico molto noto `e il simu- lated annealing , basato sull''utilizzo di una componente casuale nel movimento sul neighborhood. Esso funziona su questo principio:
data s la solzione corrente, se esiste una soluzione migliorante s 0, appartenente al vicinato, la si esegue, altrimenti si applicano mosse
peggioranti s 00 con una probabilit`a che dipende da un parametro decrescente T, detto temperatura. Si `e dimostrato che questo metodo `e asintoticamente esatto, convergendo teoricamente all''ottimo globale [8]. Il simulated annealing si suddivide in una versione non omogenea, nella quale la temperatura diminuisce ad ogni mossa, ed in una
omogenea, dove si mantiene T uguale fino ad un raggiungimento di
uno stato di equilibrio. L''algoritmo termina quando: ' non si migliora la soluzione da p iterazioni; ' non si accettano mosse da q iterazioni; Una sua prima variante `e formulata dal reannealing, che consiste nel memorizzare alla prima esecuzione il valore di T0 col quale
si `e trovata la soluzione migliore, dopodich´e avviare una seconda
esecuzione di ricerca locale pi `u accurata con T = T0. Una seconda variante `e formulata dal restricted neighborhood, dove non si considerano le mosse che di fficilmente producono buone soluzioni; ad esempio, nel TSP si userebbero mosse che collegano
solo vertici vicini. Sintetizzando, nel tabu search le mosse peggioranti sono consen- tite solo quando si `e in un ottimo locale ed esso `e poco basato sulla
casualit`a, mentre il simulated annealing permette mosse peggioranti
in qualunque momento ed `e fortemente basato sulla casualit`a. In conclusione, gli algoritmi meta-euristici forniscono schemi ge- nerali che necessitano di essere particolarizzate per i singoli proble-
mi, per questo spesso non sono competitivi al confronto di algoritmi 45 46 CAPITOLO 2. PIANIFICAZIONE E OTTIMIZZAZIONE DEI PERCORSI sviluppati ad-hoc. I tempi di sviluppo sono per `o inferiori e i risul-
tati sono normalmente migliori delle ricerche locali di base, anche
se in tempi di calcolo superiori. Possono per `o diventare complessi
e dipendenti da numerosi parametri. 2.3.7 Algoritmi per cammini minimi Il problema dei cammini a costo minimo, o shortest path problem
(SPP), rientra nella teoria dei grafi. Dato un grafo orientato G = (V , A), pesato sugli archi con costi cij, e due vertici s, t '' V, si vuole determinare il cammino semplice di costo minimo dal vertice s al
vertice t. Se i costi degli archi sono qualsiasi, il SPP `e NP-hard [9]. Esistono casi in cui il problema `e a complessit`a polinomiale; ad esempio,
se vale cij ' 0 per ogni (i , j) '' A, si pu`o utilizzare l''algoritmo di Djikstra , a complessit`a O(n2) - O(n · log n). Si dimostra che se i costi degli archi sono non negativi, il cammino di costo minimo `e semplice ed elementare. Inoltre, se il cammino minimo da vi a vj passa per vk, allora esso `e formato dal cammino minimo da vi a vk concatenato dal cammino minimo da vk a vj. Per formulare matematicamente questo problema si pu `o ricorre- re ad un modello di programmazione lineare intera, con funzione
obiettivo: min X (i ,j)''A cijxij e vincoli: X (h ,j)'''+(h) xhj '' X (i ,h)'''''(h) xih = ( 1 se h = s ''1 se h = t 0 se h '' V \ {s , t} X (i ,j):i,j''S xij ' |S| '' 1 '' S '' V , S , '' 0 ' xij ' 1 intero(i , j) '' A 46 CAPITOLO 2. PIANIFICAZIONE E OTTIMIZZAZIONE DEI
PERCORSI 47 Un arco che va dal vertice i al vertice j ha costo cij ed `e considerato in soluzione se xij = 1, 0 altrimenti. La funzione obiettivo definisce una miminizzazione del costo totale degli archi in soluzione che
formano il cammino. Il primo vincolo impone che la di fferenza fra il numero totale di archi entranti ( '+(h)) in un vertice h e il numero di archi uscenti ( '''(h)) da quel vertice sia pari a 1, se j `e il vertice iniziale, ''1 se h `e il vertice finale, e pari a 0 se h `e un vertice interno al
cammino. Il secondo vincolo, invece, impone che per ogni possibile
sottoinsieme di vertici, il numero di archi selezionati, presenti in
esso, sia minore o uguale al numero dei vertici del sottoinsieme
meno 1. In particolare, nel caso in cui i costi siano tutti non negativi,
il secondo vincolo risulta ridondante e pu `o dunque essere eliminato. Questo problema `e stato risolto e fficientemente dall''algoritmo di Dijkstra (1959). Partendo dalle seguenti strutture dati: ' W `e l''insieme dei vertici raggiunti in modo permanente dalla
soluzione s, ' L(v) `e il costo del cammino minimo da s a v passante solo per j '' W, ' pred(v) `e il vertice che precede v nel cammino da s a v, e dato il seguente
Teorema : se L(v '') =minv''V\W{L(v)} il cammino minimo da s a v'' `e lungo L(v ''), se ne descrive la definizione in pseudo-codice: W : = {s}; L(s) : = 0; pred(s) : = 0; for each v '' V \ {s} do L(v) : = c(s, v); pred(v) : = s; while | W| < n do trova v '' '' V \ W : L(v'') = min v''V\W{L(v)}; W : = W ' {v''}; for each v '' V \ W do if L(v'') + c(v'', v) < L(v) then 47 48 CAPITOLO 2. PIANIFICAZIONE E OTTIMIZZAZIONE DEI PERCORSI L(v) : = L(v'') + c(v'', v); pred(v) : = v''; end while Nel ciclo while si svolgono n '' 1 iterazioni e per ogni iterazione
si ha un numero di operazioni proporzionale a |V \ W|; in termini
temporali, la complessit`a risulta O(n2). Inizialmente solo il vertice iniziale `e compreso in S; le etichette da assegnare ai vertici comprendono due informazioni: il predecessore
e il costo totale per giungere a tale vertice. Quelli non raggiungibili
da S hanno costo uguale a infinito, mentre quelli raggiungibili han-
no costo pari all''arco di costo minimo che li connette ad S pi `u il costo
del vertice predecessore. Ad ogni iterazione si include in S il vertice
che ha etichetta con costo minore e la sua diventa di assegnazione
permanente. Dopodich´e si aggiornano solo le etichette dei vertici
che sono raggiungibili da S con un arco diretto, ma solo se il nuovo
costo migliora quello precedente. Una volta trovato il percorso dal
vertice iniziale a quello finale, le etichette ricostruiscono il cammino
minimo. L''algoritmo `e sviluppabile anche in forma tabellare: una
colonna indica la componente connessa, n '' 1 colonne rappresen-
tanti i vertici (tranne quello iniziale) indicano il costo del cammino
minimo per arrivare a tale vertice e altre n '' 1 colonne indicano i
vari predecessori. Ogni riga rappresenta un''iterazione e per ognu-
na si include in S il vertice con costo minore, aggiornando quella
successiva eventualmente con i nuovi costi (se migliori) e i relativi
predecessori, fino a connettere il vertice iniziale con quello finale. Questo algoritmo pu `o essere usato per calcolare i cammini mini- mi fra le varie coppie di vertici di una rete di percorsi, per costruire
quel grafo ausiliario che consente di riformulare l''ATSP, applicando
poi un algoritmo (meta-)euristico di ricerca locale. 2.4 Un possibile sistema Dopo aver analizzato la letteratura, nei sistemi descritti emergono
due tematiche: la generazione del modello e la generazione dei percorsi.
Esse possono essere implementate anche in sistemi separati, non ne- 48 CAPITOLO 2. PIANIFICAZIONE E OTTIMIZZAZIONE DEI
PERCORSI 49 cessariamente compresi nello stesso apparato di gestione magazzino
e in entit`a software e hardware diverse. In figura 2.4 si pu `o osservare un diagramma a blocchi di una implementazione hardware e software di un sistema di gestione
magazzino. Esso comprende un generatore di modello della strut-
tura che definisce una rete di nodi indicante le possibili tratte e un
generatore di percorsi che rappresenta un tragitto basandosi sulla
rete di nodi. Prima di tutto, `e necessario definire il layout del magazzino me- diante le sue caratteristiche strutturali: esse includono le coordinate
dei vari elementi presenti nello spazio e possono essere, ad esempio,
relative a dati di anagrafica del magazzino. Possono inoltre indicare
informazioni aggiuntive, come la direzione di viaggio in una par-
ticolare tratta, la larghezza di un corridoio, eccetera. Questi dati
possono anche essere inseriti nel modulo di gestione magazzino da
un utente, per modificare i percorsi identificati. Ad esempio, in figura 2.5 `e presentato un esempio grafico di un layout di un magazzino; esso descrive un modello di spazio
gestito
, citato in precedenza. Si pu `o notare come il modello sia formato da diversi elementi: due serie di sca ffali (una verticale e una orizzontale) separate da muri divisori visti come ostacoli, e un
insieme di aree di lavoro. Questa `e la parte che va a comporre i dati
di anagrafica della struttura. Ritornando alla figura 2.4, si ha il layout analizer, che permette al generatore di modello di ricevere in input i dati delle caratteristiche
strutturali, processarli e generare un modello dello spazio gestito.
Il suo compito `e analizzare il layout, identificandone le strutture e i
percorsi, per poi passare tali informazioni al modulo successivo. Il pathway definition module si basa sulle informazioni che ri- ceve dal blocco precedente per definire i possibili percorsi, mentre il
node identifier esegue un''analoga operazione, ma atta all''identifi- cazione e definizione dei nodi. I punti estremi di ogni tratta possono
essere riconosciuti come nodi e la lunghezza del percorso pu `o esse-
re considerata come la distanza fra i due nodi. Inoltre, si possono
identificare i nodi determinando i punti nei quali si intersecano i per-
corsi. Questi due moduli possono essere scambiati di ordine oppure
eseguiti in concorrenza fra loro, a seconda delle implementazioni. 49 50 CAPITOLO 2. PIANIFICAZIONE E OTTIMIZZAZIONE DEI PERCORSI Figura 2.4: Un esempio di sistema di gestione magazzino (WMS)
(fonte: Mandel et al., 2009) 50 CAPITOLO 2. PIANIFICAZIONE E OTTIMIZZAZIONE DEI
PERCORSI 51 Figura 2.5: Esempio di layout di un magazzino (fonte: Mandel et
al., 2009) 51 52 CAPITOLO 2. PIANIFICAZIONE E OTTIMIZZAZIONE DEI PERCORSI A seguito di queste fasi avviene la generazione della rete di nodi nel node network generator, che memorizza un modello con
le informazioni sui nodi, sui percorsi e sui vincoli. I nodi sono
organizzati in una rete che indica le relazioni di connessione fra di
essi con le informazioni per determinare: dove sono posti i nodi
all''interno di una griglia, rappresentante lo spazio gestito, dove
sono presenti i possibili percorsi e come possono essere attraversati.
Questo modello viene memorizzato come model data; esso contiene
tutte le informazioni necessarie alla pianificazione dei percorsi. Nella figura 2.5 sono inoltre riportati anche i nodi e i percorsi riconosciuti dal generatore di modello. Si nota come i nodi (nume-
ro 130) siano il risultato di intersezioni fra i percorsi o considerati
come estremi di una tratta. Si osserva che i percorsi, rappresentati
da frecce, possono essere unidirezionali o bidirezionali e con M ed E
sono indicate le due tipologie di metodi per il calcolo della distan-
za compiuta in un viaggio attraverso varie locazioni: Manhattan o
Euclidea. Il path generator `e lanciato da un task, il quale `e inteso come un''operazione che richiede la generazione di un percorso. I resource
data
sono dati che descrivono le varie risorse presenti che possono essere assegnate nello svolgimento di un compito. Il generatore di
percorsi, basandosi su di essi, valuta le risorse da usare a seconda
dei vincoli imposti dal compito. Esso pu `o essere composto di diversi moduli, fra i quali il pri- mo `e il layout analizer: questo riceve la rete di nodi calcolata in
precedenza e si occupa di identificare le informazioni sui possibili
percorsi da inviare al modulo successivo. La sua presenza garanti-
sce la possibilit`a di disaccoppiare funzionalmente il path generator
dal model generator. L''algorithm determiner fornisce la capacit`a di utilizzare uno o pi `u algoritmi euristici nella determinazione del percorso, come
descritto in precedenza. Si utilizzano gli euristici in quanto il cal-
colo di una soluzione ottima ideale in questo ambito pu `o essere
impraticabile [6]. Il path calculator applica gli algoritmi selezionati, identificando un percorso per il task. Questa soluzione pu `o poi essere migliorata,
entro certi dati limiti di soglia. 52 CAPITOLO 2. PIANIFICAZIONE E OTTIMIZZAZIONE DEI
PERCORSI 53 2.5 In sintesi In questo capitolo sono state riassunte diverse fonti di letteratu-
ra sullo stato dell''arte, riguardo la modellazione dei magazzini e
l''ottimizzazione dei percorsi. Nella prima parte si sono tratti spunti su come poter rappresen- tare in modo formale la struttura e lo spazio da gestire per arrivare
ad avere una rete di percorsi che si colleghi con le locazioni presenti
negli sca ffali del magazzino. Nella seconda parte si sono recuperati gli algoritmi che possono essere usati allo scopo di ottimizzare gli spostamenti nel raggiungi-
mento di un certo insieme di locazioni. Tali informazioni saranno alla base dell''analisi e del progetto software al capitolo seguente. 53 54 CAPITOLO 2. PIANIFICAZIONE E OTTIMIZZAZIONE DEI PERCORSI 54 Capitolo 3 Un software per la
pianificazione e ottimizzazione
di percorsi
Questo capitolo illustra il processo di sviluppo che ha porta-
to alla realizzazione del software riguardante la pianificazione e
l''ottimizzazione dei percorsi. Seguendo i principi dell''ingegneria del software [10], si descri- vono i passi della creazione del progetto: dopo un''introduzione, si
passa alla definizione dei requisiti e alla loro successiva analisi, per
poi esaminare il problema derivante. Infine, si descrivono il pro-
getto, i pattern e la tecnologia utilizzati e si mostra un esempio di
esecuzione del sistema. 3.1 Introduzione Dopo aver analizzato, nel capitolo 1, gli aspetti logistici che deter-
minano l''importanza dei magazzini industriali nella gestione della
supply chain e a seguito della ricerca bibliografica sulla modellazione
e sugli algoritmi, riportata nel secondo capitolo, l''attivit`a di tiroci-
nio si `e focalizzata sulla creazione di un progetto software, che si
approcciasse al problema della pianificazione e ottimizzazione dei
percorsi, portando una possibile soluzione. 55 56 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E OTTIMIZZAZIONE DI PERCORSI Il progetto si `e svolto mediante un processo di sviluppo a spirale: a partire da certi requisiti iniziali, definiti in comune accordo con
il tutor aziendale Claudio Gambetti, essi si sono via via ra ffinati, aggiunti o modificati, in base ai risultati dei prototipi presentati di
volta in volta e a seguito di confronti e scambi di idee sui possibili casi
d''uso da comprendere. In maniera analoga, interazioni di questo
tipo avvengono fra committenti e software house, nello sviluppo di
prodotti applicativi. Durante questo periodo, i componenti dela business unit industria di Onit sono stati disponibili a seguito di richieste di consigli o
suggerimenti sia riguardo il modo in cui a ffrontare il problema, sia sull''utilizzo specifico delle tecnologie Microsoft che non rientravano
nella mia diretta conoscenza. 3.1.1 Problema Come anticipato, il problema che ci si pone riguarda l''ottimizzazione
dei percorsi da compiere durante le operazioni di movimentazione
interna in un magazzino, per raggiungere un insieme di locazioni
coprendo la minore distanza possibile. Si vuole considerare il con-
testo in cui un singolo operatore in movimento `e un uomo che si
sposta a piedi o a bordo carrello e che deve e ffettuare una serie di depositi /prelievi dalle locazioni di stoccaggio degli scaffali. 3.1.2 Visione La visione principale nello sviluppo di questo come di un qualsiasi
altro sistema software `e che non c''`e codice senza progetto, non c''`e proget-
to senza analisi del problema, non c''`e problema senza requisiti. Partendo
da questi presupposti, il primo passo da a ffrontare `e la definizio- ne dei requisiti principali da soddisfare in un prototipo, per poi
ra ffinarli ripetendo l''operazione sino ad un risultato soddisfacente. 3.1.3 Obiettivi L''obiettivo di questo progetto `e di sintetizzare le conoscenze ac-
quisite durante l''attivit`a di tirocinio e di sfruttare le compentenze 56 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E
OTTIMIZZAZIONE DI PERCORSI 57 pregresse fornite in ambito accademico per produrre una soluzione
software che funga da prototipo aziendale per la pianificazione e
l''ottimizzazione dei percorsi nei magazzini industriali. 3.2 Requisiti Si vuole avere uno strumento mediamente interattivo che agevoli
l''utente nella fase di configurazione dei percorsi e che provveda a
fornire una successione di tratte da percorrere necessarie allo svolgi-
mento di movimentazioni interne, che devono raggiungere un certo
insieme di locazioni negli sca ffali. Dunque, come prima fase, si delineano i requisiti del sistema software, definiti in accordo con il tutor aziendale: 1. Avere la possibilit`a di modellare graficamente il layout di un magazzino, disponendo gli sca ffali in uno spazio bidimensionale. 2. Avere la possibilit`a di definire, all''interno dello stesso spazio, una mappa principale dei corridoi percorribili dagli operatori
nel magazzino, che si muovono a piedi o a bordo carrello. 3. Tale layout deve essere riconfigurabile in ogni momento, ci `o comporta il prevedere (a) l''aggiunta, modifica o eliminazione degli sca ffali, e (b) l''aggiunta, modifica o eliminazione delle tratte dei corridoi. 4. Gli sca ffali devono essere modificabili nelle loro propriet`a di codice identificativo, lunghezza, profondit`a, tipo (mono-fronte
o bi-fronte), orientamento, posizione (coordinate x e y). 5. Le campate degli sca ffali devono essere modificabili singolar- mente nelle loro propriet`a di codice identificativo, lunghezza
e profondit`a. 6. Le tratte devono poter rappresentare il senso di percorrenza. 57 58 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E OTTIMIZZAZIONE DI PERCORSI 7. A partire dagli sca ffali e dalla mappa principale dei corridoi deve essere possibile generare una mappa dettagliata che col-
lega ogni campata di sca ffale alla tratta del corridoio da cui `e accessibile. 8. Questa mappa dettagliata deve essere modificabile nei percorsi. 9. A partire dalla mappa dettagliata, deve essere possibile se- lezionare un insieme di campate e un punto di deposito, e
generare un percorso (circuito) che ne descriva l''ordine di per-
correnza, in maniera quanto pi `u ottimizzata, considerando un
ragionevole tempo di calcolo. 10. Deve essere possibile evidenziare ogni tratta che collega due punti consecutivi, riportandone il costo in distanza percor-
sa, e visualizzare il percorso completo, anche in questo caso
riportandone la distanza totale compiuta. 11. Tale operazione deve essere ripetibile pi `u volte, selezionado o deselezionando diverse campate e deposito. 12. Si prevedono due tipi di utenti: il configuratore del layout, che si occupa di configurare il layout del magazzino e il pianifica-
tore delle operazioni, che si occupa di gestire le operazioni di
movimentazioni da svolgere all''interno. 3.3 Analisi dei requisiti Questa fase `e necessaria perch´e i requisiti sono espressi in linguag-
gio naturale, il quale `e ambiguo; l''obiettivo dell''analisi `e definire i
termini in maniera pi `u chiara e univoca possibile. 3.3.1 Glossario Il glossario contiene un elenco delle definizioni dei termini presenti
nei requisiti, espresse in linguaggio naturale. 58 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E
OTTIMIZZAZIONE DI PERCORSI 59 ' Magazzino: contenitore di sca ffali, rappresentato da un layout. ' Layout: particolare disposizione degli elementi (sca ffali, corridoi) che compongono il magazzino. ' Sca ffale: mezzo di immagazzinamento degli oggetti presenti nel magazzino. Da un''ottica bidimensionale dall''alto, appare
come un rettangolo. Pu `o essere di tipo mono-fronte (una sola
fila di campate, accessibile da entrambi i lati dello sca ffale) o di tipo bi-fronte (due file di campate adiacenti, ognuna delle quali `e accessibile da un solo lato dello sca ffale). ' Lunghezza dello sca ffale: misura del lato dello scaffale che consente l''accesso agli elementi che contiene. ' Profondit`a dello sca ffale: misura del lato dello scaffale ortogonale alla lunghezza. ' Posizione dello sca ffale: coordinate cartesiane rispetto a un punto di riferimento. ' Orientamento: angolo che forma il vettore normale di un elemento rispetto un asse di riferimento. ' Campata: sezione verticale di uno sca ffale, delimitata da mon- tanti, comprendente pi `u piani lungo la sua altezza. Unit`a dello
sca ffale raggiungibile da un percorso. ' Operatore: risorsa che movimenta le merci nel magazzino. ' Corridoio: spazio disponibile compreso tra due sca ffali conse- cutivi o tra uno sca ffale e un generico ostacolo (ad esempio un muro) che pu `o essere attraversato da un operatore. ' Tratta: `e un segmento compreso fra due punti, su ognuno dei quali pu `o terminare o congiungersi con altre tratte. La lun-
ghezza del segmento rappresenta il costo di attraversamento
della tratta. ' Percorso: `e formato da una tratta o una successione di tratte. 59 60 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E OTTIMIZZAZIONE DI PERCORSI ' Circuito: `e una successione di tratte che inizia e termina sullo stesso punto. ' Mappa, o rete, dei percorsi: rappresentazione grafica dei per- corsi riconosciuti nel magazzino. Pu `o essere principale (inseri-
ta dall''utente) o dettagliata (calcolata dal programma, a partire
da quella principale e dal layout). ' Senso di percorrenza : pu `o essere bidirezionale o unidirezionale. ' Distanza: la distanza di un percorso `e calcolata come somma dei costi di attraversamento delle tratte che lo compongono. ' Deposito: punto di inizio e punto di fine del circuito. 3.3.2 Casi d''uso Il modello dei casi d''uso `e un catalogo delle funzionalit`a del sistema
descritte usando UML. Ogni caso d''uso rappresenta una singola inte-
razione ripetibile attuata da un utente (uomo o macchina) durante
l''utilizzo del sistema, enfatizzando la prospettiva dell''utente, e ne
definisce i requisiti funzionali. Tipicamente, un caso d''uso include uno o pi `u scenari che descrive le interazioni che avvengono tra un attore e il sistema, e documenta
il risultato e le eccezioni che possono avvenire. I casi d''uso possono includerne altri come parte di un pi `u grande pattern di interazione e possono essere estesi da altri casi d''uso. Descrizione dei requisiti presenti in figura 3.1: 60 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E
OTTIMIZZAZIONE DI PERCORSI 61 Figura 3.1: Casi d''uso 61 62 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E OTTIMIZZAZIONE DI PERCORSI Campo Descrizione Nome Aggiungi sca ffale Descrizione Il configuratore del layout vuole aggiun-
gere uno sca ffale. Attori Configuratore layout, Path planner. Precondizioni - Scenario principale L''utente vuole aggiungere uno sca ffale al layout del magazzino. Scenari alternativi - Postcondizioni Lo sca ffale viene aggiunto al layout del magazzino. Campo Descrizione Nome Modifica sca ffale Descrizione Il configuratore del layout vuole modifi-
care uno sca ffale. Attori Configuratore layout, Path planner. Precondizioni Lo sca ffale deve essere gi`a presente nel layout. Scenario principale L''utente vuole modificare uno sca ffale al layout del magazzino. Scenari alternativi - Postcondizioni Lo sca ffale viene modificato nelle sue propriet`a. Campo Descrizione Nome Cancella sca ffale Descrizione Il configuratore del layout vuole cancel-
lare uno sca ffale. Attori Configuratore layout, Path planner. Precondizioni Lo sca ffale deve essere gi`a presente nel layout. Scenario principale L''utente vuole cancellare uno sca ffale dal layout del magazzino. Scenari alternativi - Postcondizioni Lo sca ffale viene rimosso dal layout del magazzino. 62 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E
OTTIMIZZAZIONE DI PERCORSI 63 Campo Descrizione Nome Aggiungi tratta Descrizione Il configuratore del layout vuole aggiun-
gere una tratta. Attori Configuratore layout, Path planner. Precondizioni - Scenario principale L''utente vuole aggiungere una tratta dal
layout del magazzino. Scenari alternativi - Postcondizioni La tratta viene aggiunta al layout del
magazzino. Campo Descrizione Nome Modifica tratta Descrizione Il configuratore del layout vuole modifi-
care una tratta. Attori Configuratore layout, Path planner. Precondizioni La tratta deve essere gi`a presente nel
layout. Scenario principale L''utente vuole modificare una tratta dal
layout del magazzino. Scenari alternativi - Postcondizioni La tratta viene modificata nelle sue
propriet`a. Campo Descrizione Nome Cancella tratta Descrizione Il configuratore del layout vuole cancel-
lare una tratta. Attori Configuratore layout, Path planner. Precondizioni La tratta deve essere gi`a presente nel
layout. Scenario principale L''utente vuole cancellare una tratta dal
layout del magazzino. Scenari alternativi - Postcondizioni La tratta viene cancellata dal layout del
magazzino. 63 64 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E OTTIMIZZAZIONE DI PERCORSI Campo Descrizione Nome Visualizza mappa percorsi dettagliata Descrizione Il configuratore del layout vuole vi-
sualizzare graficamente la mappa dei
percorsi dettagliata. Attori Configuratore layout, Path planner. Precondizioni La mappa dei percorsi dettagliata non `e
visualizzata. Deve essere possibile ac-
cedere al caso d''uso Genera percorsi da
campate a mappa percorsi principali. Scenario principale L''utente vuole cancellare visualizzare la
mappa dei percorsi dettagliata, che non `e quella attualmente visualizzata dal sistema. Scenari alternativi - Postcondizioni La mappa dei percorsi dettagliata viene
visualizzata. Campo Descrizione Nome Genera percorsi da campate a mappa
percorsi principali Descrizione Genera i percorsi che collegano ogni
campata di sca ffale ai relativi corri- doi presenti nella mappa dei percorsi
principali. Attori Path planner. Precondizioni Nel layout deve essere presente almeno
un elemento. Scenario principale Per visualizzare la mappa dei percor-
si dettagliata, devono essere generati i
percorsi. Scenari alternativi - Postcondizioni I percorsi che collegano le campate alla
mappa principale vengono generati. 64 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E
OTTIMIZZAZIONE DI PERCORSI 65 Campo Descrizione Nome Seleziona campata Descrizione Il pianificatore delle operazioni vuole
selezionare una campata. Attori Pianificatore operazioni, Path planner. Precondizioni La campata deve essere collegata alla al-
la mappa dei percorsi dettagliata. La campata non deve essere selezionata. Scenario principale Il pianificatore delle operazioni sele-
ziona una campata da raggiungere
in un''operazione di movimentazione
interna. Scenari alternativi - Postcondizioni La campata viene selezionata. Campo Descrizione Nome Deseleziona campata Descrizione Il pianificatore delle operazioni vuole
deselezionare una campata. Attori Pianificatore operazioni, Path planner. Precondizioni La campata deve essere selezionata. Scenario principale Il pianificatore delle operazioni desele-
ziona una campata da non raggiunge-
re in un''operazione di movimentazione
interna. Scenari alternativi - Postcondizioni La campata viene deselezionata. 65 66 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E OTTIMIZZAZIONE DI PERCORSI Campo Descrizione Nome Seleziona deposito Descrizione Il pianificatore delle operazioni vuole
selezionare il punto deposito. Attori Pianificatore operazioni, Path planner. Precondizioni Deve essere presente almeno una tratta.
Non deve essere selezionato alcun punto
deposito. Scenario principale Il pianificatore delle operazioni seleziona
il punto di deposito per un''operazione di
movimentazione interna. Scenari alternativi - Postcondizioni Il punto deposito viene selezionato. Campo Descrizione Nome Deseleziona deposito Descrizione Il pianificatore delle operazioni vuole
deselezionare il punto deposito. Attori Pianificatore operazioni, Path planner. Precondizioni Il punto deposito deve essere seleziona-
to. Scenario principale Il pianificatore delle operazioni desele-
ziona il punto di deposito. Scenari alternativi - Postcondizioni Il punto deposito viene deselezionato. 66 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E
OTTIMIZZAZIONE DI PERCORSI 67 Campo Descrizione Nome Visualizza circuito deposito - campate Descrizione Il pianificatore delle operazioni vuole vi-
sualizzare il circuito deposito - campate
calcolato dal sistema. Attori Pianificatore operazioni, Path planner. Precondizioni Deve essere stato calcolato il circuito
deposito - campate. Scenario principale Il pianificatore delle operazioni vuo-
le visualizzare il circuito da percorrere
per un''operazione di movimentazione
interna del magazzino. Scenari alternativi - Postcondizioni Il circuito deposito - campate viene
visualizzato. Campo Descrizione Nome Visualizza tratte punto a punto del
circuito Descrizione Il pianificatore delle operazioni vuole vi-
sualizzare le singole tratte fra deposito
e campata o fra campata e campata del
circuito calcolato dal sistema. Attori Pianificatore operazioni, Path planner. Precondizioni Deve essere stato calcolato il circuito
deposito - campate. Scenario principale Il pianificatore delle operazioni vuo-
le visualizzare il circuito da percorrere
per un''operazione di movimentazione
interna del magazzino. Scenari alternativi - Postcondizioni La singola tratta punto a punto fra depo-
sito - campata o campata - campata viene
visualizzata. 67 68 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E OTTIMIZZAZIONE DI PERCORSI Campo Descrizione Nome Calcola circuito deposito - campate Descrizione Il sistema deve calcolare il circuito
deposito - campate. Attori Path planner. Precondizioni Deve essere selezionato un punto depo-
sito e almeno una campata da raggiunge-
re. La mappa dettagliata dei percorsi de-
ve essere fatta in modo da rendere possi-
bile la raggiungibilit`a di tutte le campate
selezionate dal deposito. Scenario principale Il sistema richiede di calcolare il circuito
deposito - campate. Scenari alternativi Se manca una delle precondizioni, il
sistema notifica il tipo di errore Postcondizioni Il circuito deposito - campate viene
calcolato. 3.3.3 Modello del dominio Il modello del dominio `e un modello concettuale di alto livello che
cattura le informazioni essenziali riguardo le entit`a evocate nei re-
quisiti; `e una vista sugli oggetti che hanno a che fare con l''area di
interesse e le loro relazioni. Esso viene utilizzato per rappresentare
gli oggetti significativi all''interno di un dominio. Il modello `e rappresentato in figura 3.2. 3.4 Analisi del problema L''analisi del problema `e essenziale per valutare la complessit`a e i
rischi, pianificare il lavoro e decidere i team di progettazione e svi-
luppo. Lo scopo primario `e valutare la qualit`a del problema, se `e
gestibile facilmente o meno, per sapere come organizzare l''attivit`a. `E la fase pi `u qualificante del processo di produzione e nella quale la dimensione dell''interazione assume notevole importanza fra quelle
da analizzare, in quanto `e quella che ha impatto maggiore sull''ar- 68 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E
OTTIMIZZAZIONE DI PERCORSI 69 Figura 3.2: Modello del dominio chitettura del sistema. Dunque come prima cosa bisogna pensare
e simulare il sistema, senza focalizzarsi sul come, ma sul cosa deve
fare. Grazie all''esperienza formulata nel capitolo 1 e alla letteratura sintetizzata nel secondo capitolo, si ritiene di avere una su fficiente conoscenza per a ffrontare il problema, giudicato risolvibile median- te i concetti della programmazione orientata agli oggetti e facendo
uso di una delle tante piattaforme esistenti che si basano su questo
paradigma. I punti rilevanti del problema riguardano la manipolazione delle entit`a del layout per arrivare, in una prima fase, ad ottenere una
mappa completa dei percorsi fra tutti i punti considerati raggiun-
gibili e, in una seconda fase, al sottoporre questa entit`a ai calcoli
necessari per generare i percorsi richiesti dall''utente. Una scelta importante che ricadr`a in fase di progetto sar`a quella di adottare degli algoritmi appositi per la fase di calcolo dei percorsi,
facendo riferimento alla letteratura riportata nel capitolo 2. 69 70 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E OTTIMIZZAZIONE DI PERCORSI Figura 3.3: Architettura logica 3.4.1 Architettura logica L''architettura logica `e una mappa del cosa: indica come si collocano
le varie parti all''interno del sistema complessivo, in modo da poter
assemblare i vari componenti sviluppati indipendentemente; `e ci `o
che rimane di un sistema quando non si pu `o pi `u togliere nulla,
continuando a comprenderne la struttura e il funzionamento. `E
logica perch´e, a di fferenza di quella di progetto, osserva il problema in s´e, non proietta la soluzione, visualizza la criticit`a dello stesso
e dovrebbe essere abbastanza univoca rispetto al problema. Viene
espressa in un linguaggio non ambiguo e che sia comprensibile a
tutti. Per rappresentare l''architettura logica `e stato scelto il linguag- gio UML. Il modello `e suddiviso nelle tre dimensioni di struttura,
comportamento e interazione, 3.3. La struttura logica del sistema `e riportata in figura 3.4. Essa `e rappresentata mediante il pattern boundary-control-entity; questo ap-
proccio suddivide un sistema software nelle parti di visualizzazione,
di implementazione e di dati associati. La parte di entity descrive gli oggetti che rappresentano la seman- tica delle entit`a nel dominio applicativo, mettendo in luce quelle che
sono state riconosciute in fase di analisi e le loro inter-relazioni, men-
tre la parte di control descrive gli oggetti che percepiscono gli eventi
generati dall''utente e controllano l''esecuzione del processo di busi-
ness e rappresenta un supporto per le operazioni e le attivit`a. Infine
la parte di boundary descrive gli oggetti che rappresentano l''inter-
faccia tra un attore ed il sistema; identifica la parte di confine fra il 70 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E
OTTIMIZZAZIONE DI PERCORSI 71 Figura 3.4: Struttura sistema e l''utente. Il diagramma UML delle entit`a `e riportato in figura 3.5. Si so- no riconosciute due entit`a principali che sono il ModelGenerator e
il PathGenerator. La prima contiene il riferimento al magazzino
(Warehouse), il quale ha una lista di sca ffali (Shelf), a loro volta composti da un insieme di campate (Bay). Queste ultime due entit`a
hanno anche il riferimento alla loro posizione (Coordinates) nello
spazio. Il magazzino, inoltre, contiene anche due di fferenti tipi di reti di percorsi (Network); la prima `e quella che viene definita dall''utente
MainPathsNetwork ), mentre la seconda (DetailedPathsNetwork) `e quella generata dal sistema (e che l''utente pu `o comunque modifica-
re). La classe Network `e definita da una lista di punti (Node), con la
relative posizioni, che rappresentano gli estremi delle tratte (Link).
Le campate si collegano concettualmente ai percorsi mediante un
tipo di nodo pi `u specifico, chiamato LocationNode, il quale ha il
riferimento a una specifica campata. La parte di control, rappresentata dal PathPlannerControl, `e ulteriormente suddivisa in ModelGeneratorControl e PathGeneratorControl ; ognuno che fornisce le rispettive funzionalit`a, come mostrato in figura 3.6. Mediante un diagramma delle attivit`a si `e rappresentata la di- mensione del comportamento del sistema 3.7. Come si pu `o notare,
l''esecuzione comincia con il settaggio del layout del magazzino (con
l''input dell''utente) per poi far generare il modello completo dei per-
corsi al sistema. Nella fase di pianificazione successiva, l''utente 71 72 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E OTTIMIZZAZIONE DI PERCORSI Figura 3.5: Entity Figura 3.6: Dettaglio di PathPlannerControl 72 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E
OTTIMIZZAZIONE DI PERCORSI 73 seleziona le campate e il deposito e il sistema esegue la generazione
del percorso. A questo punto, se `e stata trovata una soluzione, essa
viene visualizzata, altrimenti si passa nello stato di visualizzazione
dell''errore. Infine, si riporta il diagramma delle interazioni 3.8. Si nota co- me sia il control a gestire il flusso di controllo, prendendo gli in-
put dell''utente, svolgendo le operazioni richieste ed aggiornando la
visualizzazione. 3.4.2 Piano di collaudo Il piano di collaudo `e necessario alla definizione della semantica
delle operazioni fornite dalle entit`a scaturite dall''analisi. Per questo
sono stati implementati un insieme di funzioni di test, allegati nella
soluzione del progetto. 3.4.3 Piano di lavoro e analisi dei rischi Durante l''analisi non sono stati evidenziati particolari rischi nella
risoluzione del problema; si procede, dunque, a un piano di lavoro
che prevede lo sviluppo di un primo prototipo quanto prima, che
serva per poter rifinire i requisiti. Ci `o innesca una serie di processi
a spirale che terminano quando il risultato conseguito `e giudicato
soddisfacente da entrambe le parti. 3.5 Progetto Sulla base della specifica dei requisiti prodotta in analisi, il pro-
getto definisce come tali requisiti saranno soddisfatti, entrando nel
merito della struttura che deve essere data al sistema software da
realizzare. La progettazione rimane comunque una fase distinta
dalla programmazione, che corrisponde alla traduzione in un parti-
colare linguaggio di programmazione delle decisioni prese in sede
di progettazione. Una prima scelta progettuale riguarda la specifica piattaforma sulla quale implementare la soluzione al problema analizzato nella 73 74 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E OTTIMIZZAZIONE DI PERCORSI Figura 3.7: Behaviour 74 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E
OTTIMIZZAZIONE DI PERCORSI 75 Figura 3.8: Interaction 75 76 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E OTTIMIZZAZIONE DI PERCORSI sezione precedente: la decisione `e ricaduta sul framework Micro-
soft .NET e l''utilizzo delle librerie WPF, implementandole mediante
linguaggio Visual C#. Le tecnologie Microsoft sono fortemente
sfruttate da Onit nello sviluppo dei suoi prodotti, dunque questa
scelta `e stata anche dettata dal fatto di poter imparare pi `u a fondo,
sia singolarmente che con il supporto della BU industria, questo tipo
di strumenti. Una seconda scelta progettuale, fortemente collegata alla prima, `e sul pattern architetturale che si `e deciso di utilizzare nel modellare il sistema. Infine, un''altra scelta importante riguarda gli specifici algoritmi da utilizzare nella generazione del modello e nella generazione dei
percorsi. Si descrivono queste decisioni in dettaglio nelle seguenti sotto- sezioni. 3.5.1 Scelta tecnologica Come anticipato, si sceglie di realizzare la soluzione utilizzando il
framework .NET 4.0. Esso `e un componente di Windows che sup-
porta la compilazione e l''esecuzione di applicazioni o servizi Web;
tale framework fornisce un ambiente di programmazione coerente
orientato agli oggetti, un ambiente di esecuzione gestito, sviluppo
e distribuzione semplificati e l''integrazione con vari linguaggi di
programmazione. `E formato da due componenti principali: il Common Language Runtime (CLR) e la libreria di classi .NET framework. Il primo `e un
agente che gestisce il codice a run time, fornendo un ambiente con
servizi di base quali gestione della memoria, thread, servizi remoti,
sicurezza, ed e fficienza, mentre il secondo `e un insieme completo object-oriented di tipi riutilizzabili nello sviluppo, di cui fanno parte
ADO.NET , ASP.NET, Windows Form e Windows Presentation Foundation. All''interno di questo framework si sceglie di utilizzare Windo- ws Presentation Foundation (WPF), ovvero un sistema di presentazione
per applicazioni client Windows automonome o su browser, sottoin-
sieme dei tipi .NET. Contiene un set di funzionalit`a che includono
Extensible Application Markup Language (XAML), controlli, binding ai 76 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E
OTTIMIZZAZIONE DI PERCORSI 77 Figura 3.9: Associazione ai dati (fonte: MSDN) dati, layout, grafica 2D e 3D, eccetera. Si ha la possibilit`a di sviluppa-
re applicazioni usando sia un linguaggio di markup che code-behind.
Il primo `e realizzato da XAML, un linguaggio basato su XML, per im-
plementare l''aspetto in modo dichiarativo, mediante una struttura
di elementi ad albero. Il code-behind, al contrario, implementa le
funzionalit`a in risposta a interazioni utente, gestione di eventi, chia-
mata alla logica di business e accesso ai dati. L''associazione ai dati
pu `o avvenire mediante la classe Binding, per relazionare la pro-
priet`a di dipendenza di un controllo di destinazione a una propriet`a
di un oggetto dati di origine dell''associazione. In tal modo, mediante
un meccanismo definito dall''interfaccia INotifyPropertyChanged,
il controllo associato alla sorgente viene notificato di aggiornarsi per
presentare l''attuale valore della sorgente. L''oggetto che realizza il binding ha una propriet`a (Mode) per definire la modalit`a dell''associazione, ovvero OneWay, TwoWay,
OneWayToSource e OneTime. Nella modalit`a OneWay, la propriet`a
di dipendenza viene aggiornata da quella sorgente, ma non pu `o ac-
cadere il contrario; ci `o succede, ad esempio, quando la destinazione
dell''associazione `e solo un output per il sistema. Per far aggiornare
anche la sorgente, a fronte di cambiamenti della destinazione (che
possono avvenire, ad esempio, a seguito di un input dell''utente) `e
necessario settare la propriet`a Mode come TwoWay. L''utilizzo di questo meccaniscmo `e facilitato dall''utilizzo dal pattern di progettazione Model-View-ViewModel, che `e stato scelto
per rappresentare il sistema software e che viene presentato nella
sotto-sezione successiva. `E importante dare, inoltre, un accenno al modello di threading di 77 78 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E OTTIMIZZAZIONE DI PERCORSI WPF . Esso `e progettato per evitare il ricorso alle di fficolt`a del threa- ding, quando possibile. Le applicazioni WPF sono in genere avviate
con due thread: uno per la gestione del rendering e l''altro per la
gestione dell''interfaccia utente (user interface, UI). Il primo `e esegui-
to in background, mentre il secondo riceve gli input, gestisce gli
eventi, aggiorna la visualizzazione ed esegue il codice dell''appli-
cazione. Il thread UI accoda gli elementi di lavoro in un oggetto
denominato Dispatcher, che seleziona i task in base alle priorit`a e li
esegue singolarmente fino al completamento. Ogni thread UI deve
presentare almeno un oggetto Dispatcher e ogni oggetto Dispatcher
pu `o eseguire i task esattamente in un thread. Dunque, se `e necessa-
rio svolgere azioni complesse, queste dovranno essere svolte in un
thread separato che lasci quello UI riservato agli elementi in coda
al Dispatcher; al termine, il risultato viene mandato al thread UI per
la visualizzazione. Questo accade perch´e a un elemento grafico in
Windows pu `o accedere solo il thread che l''ha creato; un thread in
background pu `o chiedere a quello UI di eseguire un''operazione per
suo conto, registrando un task sul Dispatcher del thread UI, con una
certa priorit`a (metodi Invoke, BeginInvoke). Si sceglie, infine, di realizzare la soluzione utilizzando il lin- guaggio di programmazione Visual C#, che `e l''implementazione
del linguaggio C# fatta da Microsoft. Per ognuno di questi argomenti si potrebbe dedicare un capitolo, ma la loro approfondita trattazione esce dal contesto di questa tesi,
sebbene il loro studio e apprendimento abbia fatto parte in maniera
significativa dell''attivit`a di tirocinio. 3.5.2 Il pattern Model-View-ViewModel Il Model-View-ViewModel `e un pattern architetturale che nasce come
variazione al Presentation-Model di Martin Fowler (2004), operata nel
2005 da John Gossman (Microsoft). L''approccio Model-View-ViewModel (MVVM) si presta naturalmente a piattaforme di applicazioni XAML, poich´e influenza alcune speci-
fiche capacit`a di WPF, come il data binding, i controlli e il compor-
tamento. Questo pattern separa le responsabilit`a dell''aspetto del
layout dell''interfaccia grafica dalla logica di presentazione, ripren- 78 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E
OTTIMIZZAZIONE DI PERCORSI 79 Figura 3.10: Model-View-ViewModel dendo i concetti dal Presentation Model (che `e nato per avere un''a-
strazione platform-independent), con l''obiettivo di avere un metodo
standard per sfruttare le funzionalit`a chiave di WPF. La view definisce la struttura, il layout e l''apparenza di ci `o che vede l''utente; idealmente, viene definita interamente in XAML, con
un limitato code-behind che non contiene business logic. Il model `e l''implementazione del modello di dominio dell''appli- cazione, che pu `o includere dati del modello con logica di business e
validazione. Spesso include un layer di accesso ai dati. Il view-model `e l''intermediario fra i due ed `e responsabile di gestire la logica della view. Recupera i dati dal model e li rende
disponibili alla view, in modo che siano facili da usare per essa,
eventualmente trasformandoli. Fornisce anche le implementazio-
ni dei comandi che l''utente avvia nella view ed `e anche respon-
sabile dei cambiamenti di stato locale che influenzano aspetti di
visualizzazione. `E importante capire le interazioni fra questi tre componenti, co- me si nota dalla figura 3.10; la view `e consapevole del model che `e
consapevole del model, al contrario il model non conosce il view-model
che `e inconsapevole della view. Tipicamente, il view-model interagisce con il model mediante chia- mate di metodi e quest''ultimo pu `o anche riportare errori o cambia-
menti ai dati sottostanti usando un set standard di eventi a cui il
view-model si sottoscrive. Uno dei benefici del MVVM coinvolge la fase di sviluppo, nella quale i designer e gli sviluppatori possono lavorare in maniera indi-
pendente e concorrente sui componenti; ad esempio, i primi possono
concentrarsi sulla view, mentre i secondi lavorano su componenti di
model e view-model, creando unit`a di test senza usare l''interfaccia
grafica. Inoltre, se la view `e definita in XAML risulta semplice ridi- 79 80 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E OTTIMIZZAZIONE DI PERCORSI Figura 3.11: Interazione fra componenti del MVVM (fonte: MSDN) segnarla senza agire sul resto del codice. I vantaggi riguardano
maggiormente le applicazioni complesse e di lungo ciclo di vita,
che divengono pi `u facili da mantenere, testare, evolvere e riusare,
mentre per applicazioni semplici o pi `u brevi il lavoro addizionale
per implementare il pattern pu `o non valerne lo sforzo. Facendo riferimento alla figura 3.11, la view pu `o aggiorna- re automaticamente i valori visualizzati in risposta a cambia-
menti del VM sottostante, se quest''ultimo implementa l''interfaccia
INotifyPropertyChanged ; inoltre, se la view vuole anche aggiorna- re il VM, il binding deve essere di tipo two-way. In genere, fra V e
VM c''`e una relazione uno a uno. In generale, si possono prevedere comportamenti in risposta a azioni dell''utente, da inserire nel code-
behind, creando un event-handler; nel pattern MVVM la responsabilit`a
di implementare l''azione `e nel view-model, potendo connettere un
controllo a un metodo del VM con un command binding. In alcuni casi, la view pu `o implementare comportamenti visuali nel code-behind che sarebbero di fficili o inefficienti da esprimere in XAML . Essa riferisce il VM mediante la sua propriet`a DataContext. Come detto, il view-model non ha riferimenti alla view o alla sua specifica implementazione, ed implementa propriet`a e comandi ai
quali la V si pu `o collegare, rendendo disponibili le funzionalit`a.
Negli scenari pi `u usuali, il VM converte e manipola i dati del model
dimodoch´e siano pi `u facili da consumare nella V e pu `o anche definire
propriet`a addizionali che non farebbero parte del modello. A volte non `e semplice scegliere dove inserire certe funzionalit`a; la regola generale `e che ogni cosa concernente la specifica apparenza
della interfaccia grafica, che pu `o essere ridisegnata in un secondo
momento, deve rientrare nella view, ed il codice che manipola di- 80 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E
OTTIMIZZAZIONE DI PERCORSI 81 rettamente elementi visuali deve risiedere nel code-behind. Analoga-
mente, le parti di recupero e manipolazione dei dati da visualizzare
dovranno andare nel VM. Infine, il model contiene tutta la logica applicativa che si occupa del recupero e della gestione dei dati, facendo in modo che siano
rispettate le regole di consistenza e validit`a; per massimizzare la
riusabilit`a, non deve contenere casi o task specifici. Esso pu `o im-
plementare direttamente gli strumenti per collegare i dati alla V, ma
nel caso in cui non lo faccia `e il VM che sar`a responsabile di fare
il wrapping delle classi del modello e fornire le propriet`a richieste
all''interfaccia. 3.5.3 Algoritmo di generazione del modello Per quanto riguarda la fase di generazione del modello, ovvero la
parte in cui al sistema `e richiesto di collegare le campate degli scaf-
fali ai percorsi principali inseriti dall''utente, si decide di operare in
questa maniera: dato l''angolo che lo sca ffale forma con l''asse verti- cale del sistema di riferimento, ad ogni campata si associa un vettore
normale, che ha direzione uguale e verso opposto a quella di acces-
so alla locazione. A partire dalla posizione centrale della campata,
si percorre la direzione indicata dal versore, fino ad intersecare (se
presente) il percorso inserito dall''utente. Se non `e presente alcun
percorso lungo quella direzione, o se viene intercettato prima un
altro sca ffale (che `e visto come un ostacolo, in questo caso) la cam- pata rimane non collegata. Si svolgono una serie di iterazioni che
coinvolgono, per ogni campata, tutte le tratte tracciate dall''utente,
andando ad ogni passo a trovare quella raggiungibile che, lungo la
direzione di ricerca, risulta essere la pi `u vicina. Per prima cosa, `e necessario stabilire un sistema di riferimento. Si considera il punto di origine (0,0) quello in alto a sinistra, con le
ascisse cresenti verso destra e le ordinate crescenti verso il basso. Inoltre, come si mostra in figura 3.12, si decide di rappresentare la posizione e l''orientamento di uno sca ffale mediante un versore ap- plicato nell''estremo evidenziato dello sca ffale, con l''angolo relativo a quello formato con l''asse delle y. 81 82 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E OTTIMIZZAZIONE DI PERCORSI Figura 3.12: Sistema di riferimento Posizione e orientamento dello sca ffale si possono rappresentare in vari modi, a seconda del punto di riferimento che si vuole pren-
dere e dell''angolo impostato (figura 3.13). A partire dal versore di
orientamento allo sca ffale, si generano poi tutti i vettori unitari delle campate che contiene (figura 3.14). Dati due punti A(x1 , y1) e B(x2, y2), la distanza calcolata `e quella euclidea: AB = q (x2 '' x1)2 + (y2 '' y1)2 Considerando una data campata e una certa tratta, il problema riguarda l''intersezione fra due rette, pi `u precisamente: ' La prima retta a `e passante per il punto P di posizione della campata e per quello P 0(x2 , y2) ottenuto a partire dalla posizio- ne della campata P(x1 , y1) pi `u uno spostamento infinitesimo lungo l''asse X e Y, dato dalle relative componenti del vettore
normale 'v = (vx, vy): ( x2 = x1 + vx ·  y2 = y1 + vy ·  dove  `e un numero piccolo vicino allo 0. 82 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E
OTTIMIZZAZIONE DI PERCORSI 83 Figura 3.13: Posizione e orientamento di uno sca ffale Figura 3.14: Orientamento delle campate 83 84 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E OTTIMIZZAZIONE DI PERCORSI ' La seconda retta b `e quella passante per i punti estremi della tratta in esame definita dall''utente. Avendo ora ottenuto le due rette a e b, si procede al calcolo della loro intersezione. Data l''equazione implicita della retta: Ax + By + C = 0 e dati i parametri: ( A = y1 '' y2 B = x2 '' x1 C = x1 · y2 '' y1 · x2 dove (x1 , y1) e (x2, y2) sono due generici punti appartenenti alla retta, l''intersezione Pint(xint , yint) fra due rette Ax + By + C = 0 e A 0x + B0y + C0 = 0 vale: ( xint = B 0 (A0C''AC0)''C0(A0B''AB0) A 0 (A0B''AB0) yint = AC 0 ''A0C A 0 B''AB0 La rappresentazione grafica `e riportata in figura 3.15.
A questo punto, l''algoritmo memorizza i valori di distanza fra P e i Pint,n trovati, dove Pint,n `e il punto di intersezione riguardante la
tratta n-esima, andando poi ad inserire e ffettivamente nella rete dei percorsi il collegamento fra la campata e la tratta raggiungibile che
ha il valore di distanza minore (P ''
int ,n). Una tratta risulta non raggiungibile da una campata se il loro collegamento viene intersecato da un altro sca ffale (figura 3.16). Per rilevare gli ostacoli `e stato quindi necessario considerate anche even-
tuali intersezioni fra la retta a e i lati degli sca ffali; se la distanza fra il punto P e P ''
int ,m, dove Pint,m `e il punto di intersezione fra la ret- ta a e il segmento di ostacolo m-esimo, e P ''
int ,m `e quello pi ` u vicino 84 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E
OTTIMIZZAZIONE DI PERCORSI 85 Figura 3.15: Calcolo dell''intersezione fra la retta della campata e del
percorso principale a P, `e minore di P ''
int ,n, allora il punto P della campata risulta non raggiungibile. Trovato un P ''
int ,n, viene inserito nella rete di percorsi un nodo (Node) in tale posizione (se non esiste gi`a), modificando di conse-
guenza la struttura dei Link per collegarlo con il LocationNode in P
e mantenendo coerente le direzioni delle tratte impostate dall''uten-
te. Il nodo in P '' viene poi etichettato come aggiunto dal sistema e per questo non sar`a poi selezionabile come nodo deposito in fase di
pianificazione dei percorsi. In tal modo, vengono collegate tutte le campate possibili con nuove tratte, andando a formare una rete di nodi e collegamenti che
viene utilizzata nel passo successivo. 3.5.4 Algoritmo di generazione del percorso Una volta generato il modello del passo precedente, anch''esso
eventualmente modificabile manualmente dall''utente, esso pu `o es-
sere utilizzato per la generazione del percorso da compiere nel
raggiungere le campate scelte. A questo punto, a partire da questo grafo, si sceglie di far ge- nerare al sistema un grafo ausiliario completo su di esso, ovvero: 85 86 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E OTTIMIZZAZIONE DI PERCORSI Figura 3.16: Calcolo dell''intersezione fra la retta della campata e di
uno sca ffale di ostacolo si produce un grafo che ha un nodo ausiliario (AuxiliaryNode) per
ogni LocationNode e per ogni possibile nodo deposito del grafo
iniziale e che contiene un arco ausiliario (AuxiliaryLink) per ogni
coppia di nodi ausiliari (ove sussistano i requisiti di raggiungibilit`a
fra le coppie). Un arco ausiliario `e formato dagli archi che che rea-
lizzano il percorso di costo minimo fra i nodi ausiliari estremi, pu `o
attraversare pi `u nodi del grafo iniziale e ha per costo la somma dei
costi degli archi che contiene. Un arco (Link) ha infatti associato
un costo pari alla distanza euclidea tra i suoi due nodi estremi. In
tal modo, si ha un grafo che rivela il percorso minimo per andare
da un qualsiasi LocationNode della rete ad un altro. L''algoritmo
per la produzione di questo grafo ausiliario `e relativo al shortest path
problem (2.3.7). Per sviluppare questa funzionalit`a, si implementa una strut- tura dati ulteriore, la classe DijkstraNode, utile allo svolgimento
dell''algoritmo di Dijkstra. Questa `e la parte che risulta pi `u gravosa
dal punto di vista computazionale, coinvolgendo la totalit`a di nodi
della rete e considerando la complessit`a di O(n2). L''algoritmo di
Dijkstra viene svolto per ogni nodo ausiliario; dato n il numero di
questi nodi, ad ogni iterazione si ottengono n '' 1 archi ausiliari che
connettono il nodo in questione a tutti gli altri. A questo punto, disponendo gi`a di tutti i percorsi minimi fra 86 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E
OTTIMIZZAZIONE DI PERCORSI 87 i punti, dato l''insieme delle campate (ovvero, dei LocationNode)
da raggiungere e il nodo deposito, non resta fare altro che mettere
in ordine gli archi ausiliari che collegano i vari nodi, per ottenere
l''esito dell''ottimizzazione richiesta. Questa parte si risolve median-
te l''algoritmo euristico nearest neighbor (2.3.5), di complessit`a O(n2).
Questo algoritmo non opera sulla totalit`a del grafo ausiliario, ma so-
lo sulla parte necessaria, estraendo solo i nodi selezionati dall''utente
e i relativi archi ausiliari. A livello di visualizzazione per l''utente, per visualizzare quale percorso prendere per andare da un punto all''altro, `e su fficiente evidenziare gli archi contenuti da quelli ausiliari, potendo usufruire
sia della distanza complessiva del circuito, sia della distanza di ogni
singola tratta punto a punto. Questo tipo di suddivisione algoritmica consente di avere, a fron- te di una fase di configurazione computazionalmente pi `u pesante
nella costruzione del grafo ausiliario, dei tempi di risposta molto
pi `u brevi nel mostrare il risultato all''utente, una volta inserito l''in-
put delle campate da raggiungere. Infatti, si `e analizzato come il
numero delle riconfigurazioni a livello di layout e di percorsi sia
trascurabile rispetto al numero delle pianificazioni richieste sullo
stesso layout, dunque `e stato considerato ragionevole optare per
una scelta di questo tipo. 3.5.5 Scelte per visualizzazione e interazione utente L''interazione tra software e utente avviene mediante dispositivi di
input e output. L''output avviene mediante lo schermo, rappresen-
tando graficamente il layout del magazzino e la rete di percorsi.
D''altro canto, l''utente invia input al sistema mediante mouse e ta-
stiera: tramite appositi bottoni pu `o impartire varie azioni di input
per inserire i dati del layout (sca ffali e percorsi principali). Per favo- rire la configurazione grafica del magazzino, si decide di sfruttare
il drag-and-drop, dimodoch´e gli oggetti presenti possano essere spo-
stati con il mouse. Per gli sca ffali (e le relative campate), `e prevista una maschera per impostarne le propriet`a in maniera precisa, men-
tre per inserire nodi e percorsi `e prevista solo la modalit`a tramite
mouse. Per aiutare il disegno ortogonale delle tratte, si inserisce una 87 88 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E OTTIMIZZAZIONE DI PERCORSI Figura 3.17: Architettura di progetto Figura 3.18: Structure funzionalit`a che rende perpendicolari le tratte che si discostano di
poco dall''esserlo. Infine, per supportare l''utente nella visualizza-
zione del layout, si sceglie di aggiungere le funzionalit`a di zoom-in
e zoom-out. 3.5.6 Architettura Date tutte le scelte e considerazioni di cui sopra, vengono presentati i
diagrammi UML dell''architettura di progetto. Come per l''architettura
logica, si riporta il modello del progetto sulle tre dimensioni di
struttura, comportamento e interazione (figura 3.17). Per quanto riguarda la struttura, si applica il pattern Model- View-ViewModel, seguendo le considerazioni fatte nella sezione 3.5.1
(figura 3.18). Il model `e rappresentato in figura 3.19. La struttura del modello rimane molto simile a quella dell''analisi, fermo restando le entit`a 88 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E
OTTIMIZZAZIONE DI PERCORSI 89 aggiunte per implementare la soluzione. In figura 3.20 `e presente invece il diagramma del comportamento; anch''esso risulta molto simile a quello creato in fase di analisi, con
in pi `u qualche dettaglio, ad esempio al tipo di algoritmo svolto nella
fase di generazione del percorso. Nel diagramma delle interazioni di figura 3.21 si vogliono rap- presentare solo le macro-interazioni fra View, ViewModel e Model.
Un diagramma completo, in questo contesto, sarebbe stato altrimen-
ti di poca comprensibilit`a. A seguito di un''interazione dell''utente
con la view, si innescano a cascata dei comportamenti a livello del
view-model e infine altri eventuali comportamenti nel model con un
possibile aggiornamento dei dati. Al termine delle operazioni (al
ritorno dalla chiamata a funzione, nel primo caso, oppure al lancio
di un evento del modello, nell''ultimo caso), ci `o comporta la notifica,
da parte del view-model del cambiamento dei dati nel modello alla
view, dimodoch´e essa possa aggiornarsi. Nel caso al centro, dopo
un''interazione utente con la view, vengono invece aggiornati solo i
dati di visualizzazioni appartententi al view-model, senza toccare il
modello. Dopo aver realizzato l''architettura di progetto, si svolge la fase di implementazione mediante l''ambiente di sviluppo Microsoft Visual
Studio 2010 Premium. Nella sezione successiva si riportano una serie
di schermate, come esempio dell''esecuzione del software. 3.6 Esecuzione In questa sezione si riporta una sequenza di immagini che
rappresentano un esempio di esecuzione del sistema software
sviluppato. Dopo aver inserito un insieme di sca ffali, il layout di presenta come in figura 3.22. Selezionando uno (o pi `u) sca ffali, mediante il tasto sinistro del mouse, si aprono altre viste per modificarne le propriet`a (figura
3.23). 89 90 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E OTTIMIZZAZIONE DI PERCORSI Figura 3.19: Model 90 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E
OTTIMIZZAZIONE DI PERCORSI 91 Figura 3.20: Behaviour 91 92 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E OTTIMIZZAZIONE DI PERCORSI Figura 3.21: Interaction 92 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E
OTTIMIZZAZIONE DI PERCORSI 93 Figura 3.22: Layout di magazzino con sca ffali Figura 3.23: Sca ffale selezionato 93 94 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E OTTIMIZZAZIONE DI PERCORSI Figura 3.24: Dati dello sca ffale La vista che mostra le propriet`a di uno sca ffale, tutte modificabili, `e quella nella figura 3.24. Inoltre, `e possibile modificare le propriet`a di ogni campata singolarmente, premendo il bottone Bays editing. I dati e la disposizione degli sca ffali possono essere modificati a piacimento, fino a creare la configurazione desiderata (figura 3.25),
anche sfruttando la funzionalit`a di drag&drop. Inoltre, premendo
il tasto destro del mouse su di uno sca ffale lo si ruota di 90'. Invece, premendo i tasti del o backspace si eliminano dal layout gli elementi
correntemente selezionati. A questo punto, `e possibile aggiungere una serie di tratte princi- pali, inserendo nodi o link singolarmente, oppure direttamente una
loro successione. Selezionando Add path, infatti, alla pressione del
tasto sinistro del mouse si aggiunge un nodo e un link a quello inse-
rito al click precedente (che rimane evidenziato di colore giallo). Per
cambiare il nodo selezionato, al quale verr`a collegato quello inserito, `e su fficiente cliccare su un altro nodo con il tasto destro del mouse. Cliccando con il tasto destro del mouse su di un collegamento fra
nodi gli si cambia il senso di percorrenza, da bidirezionale a mono-
direzionale, scegliendo come orientare la freccia. Anche in questo
caso, alla pressione dei tasti del o backspace si eliminano gli elementi
selezionati. Il risultato `e in figura 3.26. 94 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E
OTTIMIZZAZIONE DI PERCORSI 95 Figura 3.25: Layout di magazzino con sca ffali Figura 3.26: Layout di magazzino con sca ffali e percorsi principali 95 96 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E OTTIMIZZAZIONE DI PERCORSI Figura 3.27: Layout di magazzino con sca ffali e percorsi principali corretti Avendo inserito i percorsi mediante il mouse risulta di fficile di- segnarli in maniera ortogonale; per sopperire a questo problema
si pu `o utilizzare il bottone Orthogonal correction, che rende le tratte
come in figura 3.27. A questo punto, cliccando sul bottone Generate paths to bays si procede alla generazione del modello dei percorsi, che collega ogni
campata alla tratta raggiungibile pi `u vicina. Ogni campata collegata
alla rete di percorsi viene poi evidenziata di verde, mentre viene
colorata di rosso in caso opposto (fig. 3.28). `E ora possibile, dopo altre eventuali modifiche che l''utente pu`o apporre a nodi e tratte, utilizzare questo modello per calcolare i per-
corsi da compiere durante le operazioni di movimentazione interna.
Cliccando sul bottone Save network for path planning viene creato il
grafo ausiliario come descritto nella sezione 3.5.4. Quando il programma ha terminato la fase di calcolo, si presenta la vista che permette di selezionare i nodi delle campate e il nodo
deposito (fig. 3.29). Questa interfaccia mostra tutti gli sca ffali e i possibili nodi selezionabili; si ricorda che `e possibile selezionare
solo un nodo deposito e un numero di locazioni da raggiungere
maggiore di zero. 96 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E
OTTIMIZZAZIONE DI PERCORSI 97 Figura 3.28: Layout dopo la generazione del modello Figura 3.29: Vista per la pianificazione del percorso 97 98 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E OTTIMIZZAZIONE DI PERCORSI Figura 3.30: Campate e deposito selezionati Si selezionano un certo numero di campate e il nodo deposito, come in figura 3.30. Premendo il bottone Launch path planning si avviano i successivi calcoli sulla sequenza di tratte da compiere per attraversare tutte le
locazioni e tornare al nodo deposito, come deciso nella sezione 3.5.4.
In maniera quasi istantanea, il programma restituisce il risultato,
evidenziando le tratte da percorrere, con un etichetta che ne indica
l''ordine e il costo totale del circuito, misurata in metri (fig. 3.31). Premendo i pulsanti Previous path e Next path `e possibile eviden- ziare le singole tratte punto a punto, dalla prima (che ha come nodo
iniziale il nodo deposito) all''ultima (che ha come nodo finale il nodo
deposito). Un esempio `e in figura 3.32. Ora, deselezionando un nodo qualsiasi, `e possibile procedere ad una nuova selezione e calcolo di percorso, oppure si pu `o tornare a
modificare il layout della mappa principale o secondare e ripetere
tutte le operazioni descritte sopra. Si mostra ora il caso in cui non `e possibile collegare certe locazioni alla rete dei percorsi, perch´e le relative tratte sono assenti o intralciate
da altri sca ffali. Partendo dal layout principale di figura 3.33, si genera il modello di rete dei percorsi dettagliato. Il risultato della generazione `e in figura 3.34; le campate del lato 98 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E
OTTIMIZZAZIONE DI PERCORSI 99 Figura 3.31: Risultato del calcolo del percorso Figura 3.32: Tratta punto a punto del risultato 99 100 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E OTTIMIZZAZIONE DI PERCORSI Figura 3.33: Layout di magazzino destro dello sca ffale pi `u a destra risultano non collegate in quanto non `e stata trovata alcuna tratta di fronte ad esse. Invece, le campate
del lato sinistro dello stesso sca ffale, nella parte alta, non sono ac- cessibili in quanto intralciate dallo sca ffale posto in obliquo davanti ad esse. Un altro caso che `e possibile modellare, riguarda quello in cui vi sono sca ffali molto lunghi che sono attraversabili al centro mediante un sottopassaggio. Ci `o `e rappresentabile mediante i percorsi inseriti
nella figura 3.35. Generando la rete dettagliata di percorsi, si ha il risultato di figura 3.36; nel caso in cui le campate sotto le quali vi `e costruito un
passaggio non siano accessibili, `e possibile modificare manualmente
la rete generata, rimuovendo i nodi delle campate inaccessibili e i
relativi collegameti, dimodoch´e non siano selezionabili e utilizzabili
nella fase successiva (vedi figura 3.37). 3.7 In sintesi In questo capitolo si `e riportata la descrizione del processo di svilup-
po che ha portato all''implementazione di un supporto software per
la pianificazione e ottimizzazione dei percorsi all''interno di un ma- 100 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E
OTTIMIZZAZIONE DI PERCORSI 101 Figura 3.34: Rete di percorsi con campate non collegate Figura 3.35: Layout con sottopassaggio 101 102 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E OTTIMIZZAZIONE DI PERCORSI Figura 3.36: Rete di percorsi con sottopassaggio Figura 3.37: Rete di percorsi corretti dall''utente 102 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E
OTTIMIZZAZIONE DI PERCORSI 103 gazzino. A partire dai requisiti del problema, si `e continuato con la
presentazione dell''analisi, definendo i punti cardine del problema,
per poi passare al progetto della soluzione, scegliendo la tecnologia
da usare, e infine alla sua implementazione. Al termine di una serie di processi di sviluppo a spirale `e stato valutato, in accordo col tutor aziendale, di aver raggiunto un risul-
tato accettabile in un prototipo che `e in grado di rappresentare e
soddisfare un insieme su fficiente di casi d''uso. 103 104 CAPITOLO 3. UN SOFTWARE PER LA PIANIFICAZIONE E OTTIMIZZAZIONE DI PERCORSI 104 Capitolo 4 Risultati 4.1 Introduzione In questo capitolo si riportano le analisi e i commenti relativi al-
l''applicazione del software presentato al capitolo precedente, prima
riportando i tempi di calcolo utilizzando layout con un numero di
sca ffali crescente e poi su di un magazzino reale. In particolare, si riporter`a la disposizione degli sca ffali e dei percorsi principali, per poi far generare il modello dettagliato dei percorsi al program-
ma e simulare un''operazione di movimentazione interna, con una
missione di prelievo che coinvolge un certo insieme di locazioni da
raggiungere. 4.2 Analisi dei tempi In questa sezione si vuole riportare l''andamento dei tempi di calcolo
al variare del numero di sca ffali (e quindi di nodi) presenti nella rete. Vengono analizzati i tempi della generazione del modello (di 3.5.3) al variare del numero di campate presenti e degli algoritmi di
Dijkstra e nearest neighbor (di 3.5.4) al cambiare del numero di nodi
della rete su cui agiscono. I tempi impiegati nella generazione del modello sono stati con- siderati come trascurabili, in quanto in tutte le prove e ffettuate sono 105 106 CAPITOLO 4. RISULTATI Figura 4.1: Tempi di esecuzione dell''algoritmo di Dijkstra sempre risultati inferiori al secondo. Stessa considerazione vale per
i tempi di calcolo dell''algoritmo nearest neighbor. La fase pi `u significativa `e invece quella della generazione del grafo completo. Dato m come somma dei LocationNode e dei possi-
bili nodi deposito (ovvero quelli inseriti manualmente dall''utente)
e dato n il numero di nodi totali della rete (n = m+ i nodi aggiuntivi inseriti in fase di generazione del modello), si sono lanciate diverse
esecuzioni che hanno avuto come esito i tempi registrati nei grafici
seguenti. I tempi di calcolo dipendono dal numero di nodi del modello precedente e dall''hardware che esegue il programma. In questo
caso, l''esecuzione `e stata avviata compilando i sorgenti per piatta-
forme x86 e su un sistema con Windows 7, processore Intel Core 2
Duo P8700 2.53 GHz e 4 GB di RAM DDR3. Per calcolare i tempi dell''esecuzione del grafo 4.1 si `e lanciato l''algoritmo su di una rete con numero di nodi presenti nell''asse delle
X per m iterazioni. Il tempo ottenuto `e quello calcolato dalla media
su quello totale. Si nota come, confrontandolo con il grafico 4.2,
l''andamento sia simile; infatti, l''algoritmo di Dijkstra `e a complessit`a
O(n2) 106 CAPITOLO 4. RISULTATI 107 Figura 4.2: O(n2) Per ultimo, si riporta il grafico che rappresenta l''andamento dei tempi nella costruzione del grafo ausiliario; si ricorda che per ela-
borare tale grafo, `e necessario eseguire l''algoritmo di Dijkstra per
m volte, ogni volta su una rete di n nodi. Sull''asse delle ascisse si
riporta il valore di m · n2. 4.3 Uno scenario reale Lo scenario che si vuole prendere in esame `e quello di un magazzino
reale nel quale vengono realizzate missioni di deposito o prelievo su
varie locazioni mediante carrello elevatore. La struttura appartiene
agli stabilimenti di un cliente di Onit ed `e formata da 21 sca ffali per un totale di 271 campate. Come prima cosa si riporta il layout del magazzino nel pro- gramma (fig. 4.4), dopodich´e si inseriscono i percorsi principali nei
corridoi, come in figura 4.5. A questo punto, facendo generare i percorsi alle campate, si ottiene il risultato di figura 4.6. Si aggiunge, inoltre, un nodo in 107 108 CAPITOLO 4. RISULTATI Figura 4.3: Tempi di costruzione del grafo ausiliario completo Figura 4.4: Layout del magazzino di un cliente di Onit 108 CAPITOLO 4. RISULTATI 109 Figura 4.5: Layout del magazzino con percorsi principali alto al centro, da considerarsi quello di ingresso e uscita dopo una
missione di movimentazione nel magazzino (il cosiddetto deposito). Ora si pu `o utilizzare la rete di nodi creata per generare il grafo ausiliario completo necessario al nearest neighbor della fase successi-
va. Cliccando sul bottone Save network for path planning, dopo circa
12 minuti e 30 secondi, appare la schermata di figura 4.7, calcolata
con 266 nodi ausiliari e 409 nodi totali. Procedendo con una selezione di 15 campate e del nodo deposito (fig. 4.8), per un totale di 16 nodi, lanciando la pianificazione del
percorso viene prodotto, quasi istantaneamente, il risultato di figura
4.9, con la sequenza delle tratte punto a punto da percorrere per
portare a termine la missione. 4.4 In sintesi In questo capitolo si sono mostrate alcune analisi sui tempi e ffettuate sul programma realizzato. Si `e mostrato come la fase computazio-
nalmente pi `u onerosa sia quella che calcola il grafo ausiliario com-
pleto sulla rete, come previsto. I tempi di attesa possono comunque 109 110 CAPITOLO 4. RISULTATI Figura 4.6: Layout del magazzino dopo la generazione del modello Figura 4.7: Interfaccia per selezione delle locazioni da visitare e del
deposito 110 CAPITOLO 4. RISULTATI 111 Figura 4.8: Selezione di 15 campate e del nodo deposito Figura 4.9: Risultato della pianificazione del percorso 111 112 CAPITOLO 4. RISULTATI essere compatibili con un utilizzo del programma in uno scenario
reale, in quanto questa fase di configurazione, fatta una volta per
tutte, permette poi di avere dei tempi di risposta istantanei nella
pianificazione vera e propria del singolo percorso. Ci `o `e stato testa-
to anche sul layout di un impianto di stoccaggio reale, con risultati
soddisfacenti. 112 Capitolo 5 Conclusioni Durante l''attivit`a che ha portato alla stesura di questa tesi ho com-
piuto un percorso di apprendimento e di integrazione delle cono-
scenze pregresse, le quali sono state sfruttate per sviluppare il pro-
totipo di un software utile alla pianificazione e ottimizzazione dei
percorsi per la movimentazione interna nei magazzini industriali. Ho svolto questa esperienza grazie a un''opportunit`a di tirocinio per tesi in azienda, svoltasi presso Onit Group s.r.l., mediante la quale
ho potuto frequentare regolarmente l''ambiente di lavoro per circa 3
mesi, dal 25 Giugno 2012 al 12 Settembre 2012, per un complessivo
di circa 345 ore. I capitoli riportati nella tesi hanno ripercorso, a grandi linee, l''ordine cronologico con il quale `e proseguita l''attivit`a di studio,
prima, e di sviluppo software, poi. Nel primo capitolo ho riportato una panoramica sulla logistica, descrivendone l''importanza generale per poi focalizzarmi sui ma-
gazzini industriali nelle loro caratteristiche principali; riguardo que-
sto argomento, ho anche potuto sfruttare esperienze dirette median-
te alcune visite all''azienda Orogel di Cesena, azienda leader in Italia
nella produzione dei surgelati e cliente di Onit, dunque un esempio
importante nell''ambito di studio. Ho potuto cos`ı approfondire la
conoscenza sul dominio del problema. Nel secondo capitolo mi sono focalizzato sulla ricerca di lette- ratura riguardante la modellazione dei magazzini e gli algoritmi di
ottimizzazione dei percorsi. Ho prodotto una sintesi di quelli che 113 114 CAPITOLO 5. CONCLUSIONI ho ritenuto pi `u rilevanti e utili per a ffrontare, in prima battuta, il problema della pianificazione dei percorsi. Dopo aver recuperato e sintetizzato la letteratura riportata ai ca- pitoli precedenti, nel terzo ho illustrato il processo di sviluppo che ha
portato alla realizzazione del software riguardante la pianificazione
e l''ottimizzazione dei percorsi. A partire da un insieme di requisiti
iniziali e a seguito di una serie di confronti con il tutor aziendale
Claudio Gambetti, si `e deciso quali altri requisiti poter aggiungere
e sviluppare, in un processo a spirale, fino al conseguimento di un
risultato soddisfacente. Nel quarto e ultimo capitolo, infine, ho applicato il software rea- lizzato in uno scenario di magazzino reale, osservandone i risultati
e analizzandone le prestazioni in termini di tempi di calcolo. Per
fare questo, ho riportato il layout di un impianto di stoccaggio di un
cliente di Onit nel software per simulare una movimentazione di
merce riguardante diverse locazioni. Ho appurato che il program-
ma, una volta terminata la fase di configurazione, che risulta la pi `u
onerosa, calcola i percorsi in tempi soddisfacenti. Possibili sviluppi futuri possono riguardare sia un''estensione dei casi d''uso risolvibili dal programma, molto numerosi in que-
sto ambito, sia un miglioramento delle parti gi`a presenti, come ad
esempio sfruttare il multi-threading per la fase di calcolo del grafo
completo, oppure ampliare gli algoritmi utilizzabili per la genera-
zione dei percorsi, oltre al nearest neighbor, in funzione della qualit`a
della soluzione che si vuole ottenere. Nel complesso, le fonti di conoscenza dalle quali ho attinto per svolgere la tesi si rifanno principalmente alla ricerca operativa, nei
primi due capitoli, e all''ingegneria del software, nel terzo capitolo.
Inoltre, grazie al periodo di tirocinio in Onit, ho potuto accedere
a tutta una serie di conoscenze collaterali, ad esempio riguardo il
linguaggio Visual C# e l''utilizzo delle librerie di classi WPF appar-
tenenti al Framework .NET. Sebbene non fossi coinvolto nell''imple-
mentazione di un prodotto, ho avuto la possibilit`a di poter osservare
dall''interno la software house. Ci `o mi ha permesso di avere un ri-
scontro sul campo del processo di sviluppo del software nel mondo
lavorativo, osservando le interazioni fra i colleghi e, a volte, quelle
con il cliente. 114 CAPITOLO 5. CONCLUSIONI 115 In conclusione, valuto questa esperienza come positiva per due motivi principali: il primo riguarda il risultato della tesi, cio`e l''aver
realizzato un prototipo da cui si pu `o prendere spunto per integrare
nuove funzionalit`a ad un prodotto di gestione magazzino gi`a esi-
stente. Si noti che l''alternativa all''utilizzo di un programma come
quello che ho sviluppato `e di inserire manualmente a sistema tutti i
nodi e gli archi dei percorsi, il che richiederebbe tempi nettamente
superiori (circa un ordine di grandezza). Il secondo motivo deri-
va dal fatto che questa esperienza mi ha permesso di inserirmi in
maniera stabile in Onit, con un impiego nella business unit automazio-
ne, che `e responsabile degli sviluppi software e della manutenzione
sugli impianti automatici di Orogel. Per queste ragioni, mi auspico che le occasioni di tirocinio in azienda siano maggiormente utilizzate per rendere pi `u natu-
rale il passaggio fra il mondo universitario e quello lavorativo,
diminuendo il divario fra i due. Desidero infine ringraziare il relatore prof. Daniele Vigo, Onit Group per l''opportunit`a concessami e in particolare il correlatore
ing. Claudio Gambetti e tutta l''area industria per la formazione ed il
supporto fornito durante il periodo di svolgimento della tesi. 115 116 CAPITOLO 5. CONCLUSIONI 116 Bibliografia [1] Robert B. Handfield, Ernest L. Nichols : Introduction to supply chain management, 1999, Prentice Hall [2] Daniele Vigo: IT-Based Management of Logistics 2, 2010, Meto- di e Modelli per il Supporto alle Decisioni LM, Universit`a di
Bologna [3] Antonio Comi: Logistica e trasporto delle merci, Universit`a degli Studi di Roma Tor Vergata [4] Prof. Ing. Riccardo De Carlini: Logistica Industriale - Capitolo VI: I Magazzini Industriali, Ingegneria Gestionale, Universit`a degli
Studi di Napoli Federico II [5] Gianpaolo Ghiani, Gilbert Laporte, Roberto Musmanno: In- troduction to Logistics Systems Planning and Control, Wiley,
2004 [6] Alexander Mandel, Jan Kappallo, Wassili Sabelfeld, Chri- stian Reinhardt, Markus Puchta: Method and apparatus for pa-
th planning and distance calculation, 2009, United States, Patent
Application Publication [7] Daniele Vigo: Algoritmi euristici, 2010, Metodi e modelli per il supporto alle decisioni LM, Universit`a di Bologna [8] Daniele Vigo: Algoritmi metaeuristici, 2010, Metodi e modelli per il supporto alle decisioni LM, Universit`a di Bologna [9] Daniele Vigo: Teoria dei grafi - Cammini a costo minimo, 2010, Ricerca operativa LA, Universit`a di Bologna 117 118 BIBLIOGRAFIA [10] Antonio Natali: Ingegneria dei sistemi software LM, 2010, Universit`a di Bologna [11] MSDN Library: .NET Fra- mework 4, http: //msdn.microsoft.com/it- it /library/w0x726c2(v=vs.100).aspx [12] MSDN Library: WPF, http: //msdn.microsoft.com/it- it /library/ms754130(v=vs.100).aspx [13] MSDN Library: Using the Model-View-ViewModel Pattern, http: //msdn.microsoft.com/it-it/library/hh821028.aspx [14] Josh Smith: WPF Apps With The Model-View-ViewModel Design Pattern, http: //msdn.microsoft.com/it-it/magazine/dd419663.aspx 118


© Eiom - All rights Reserved     P.IVA 00850640186