Riassunto del primo incontro del ciclo di seminari “ROAR IN AZIONE!” sul servizio di prestito interbibliotecario della Rete Bibliotecaria Bresciana e Cremonese come problema di routing con finestre temporali.

Martedì 01 febbraio si è svolto il primo incontro di “ROAR IN AZIONE!”, dedicato a presentare applicazioni della ricerca operativa e della matematica in generale, per affrontare e risolvere problemi di ottimizzazione emergenti in situazioni reali diverse.

Gli oratori

Protagonisti dell’incontro sono stati Marco Gussago, responsabile dei servizi automatizzati dell’Ufficio Biblioteche della Provincia di Brescia, e Fabio Bazzoli, direttore del Sistema Bibliotecario del Sud Ovest Bresciano. Durante la prima parte del seminario, entrambi hanno dedicato qualche minuto a presentarsi e a illustrare la propria formazione.

Marco Gussago e Fabio Bazzoli.

Marco Gussago, diplomato perito informatico, in passato ha lavorato come sviluppatore software nell’ambito dell’automazione industriale. In seguito, si è laureato in filosofia ed è diventato bibliotecario. Dal 2002 si occupa del sistema informativo della Rete Bibliotecaria Bresciana Cremonese.
Fabio Bazzoli, dopo un diploma in un istituto d’arte, si è laureato in storia ed è diventato bibliotecario nel 1992. Dal 1998 è sia responsabile dell’Area Cultura e Biblioteche del Comune di Chiari (BS) e coordinatore del Sistema Sud Ovest Bresciano.

Quale collegamento può esserci tra delle biblioteche e la ricerca operativa? 

Uno dei servizi principali offerti dalla Rete Bibliotecaria Bresciana e Cremonese è il prestito interbibliotecario, implementato tra le più di trecento biblioteche delle province di Brescia e Cremona. Gussago e Bazzoli si sono concentrati solo sulle biblioteche della provincia di Brescia, riducendo così il numero a circa duecentotrenta.

Biblioteche nella Rete Bibliotecaria Bresciana e Cremonese
© OpenStreetMap contributors.

Quando un utente ha bisogno di una risorsa non posseduta dalla biblioteca locale a cui è iscritto, la sua richiesta può essere soddisfatta da una delle altre biblioteche presenti nella rete che invece l’hanno disponibile. La richiesta viene inserita nel sistema informativo della RBBC e viene quindi soddisfatta da una di queste altre biblioteche. Il libro o il dvd (o un’altra tipologia di esemplari disponibili nella rete) viene preparato dalla biblioteca prestante e viene ritirato da un corriere, che porta l’esemplare in un centro di raccolta, situato nella periferia di Brescia. Appena possibile, nei giorni successivi, la risorsa verrà consegnata da un altro corriere alla biblioteca di destinazione, quella dove l’utente andrà a ritirarla.

Il sistema utilizzato al momento

Chiaramente ogni giorno le richieste degli utenti da gestire sono ben più di una. La Rete Bibliotecaria Bresciana e Cremonese ha un contratto con una ditta esterna che offre servizi di logistica tramite dei corrieri. Il modello attualmente implementato è a stella: le biblioteche sono organizzate in linee fisse (nome ispirato alle linee degli autobus), che i corrieri seguono alcune volte a settimana, in base a una frequenza determinata in base allo storico, e tutte le linee partono dal centro di raccolta.

Le linee in cui sono suddivise le biblioteche pubbliche della provincia di Brescia e il centro di raccolta
(indicato con l’icona della casetta – mappa Google: https://shorturl.at/axEFR).

I corrieri percorrono quindi un certo numero totale di chilometri ogni giorno, seguendo un calendario statico settimanale. Quanto è buono questo approccio? Potrebbe essere migliorabile?

È proprio qui che viene in aiuto la ricerca operativa, come spiegano Marco Gussago e Fabio Bazzoli, modellando il servizio di prestito interbibliotecario come un problema di routing. Infatti, la gestione dei percorsi del prestito bibliotecario può essere ricondotta a uno dei problemi classici studiati in questa disciplina: il Vehicle Routing Problem. In questo caso, parliamo in particolare di una variante che considera sia delle finestre temporali sia operazioni di pickup e delivery.

La formulazione del modello matematico

Consideriamo come orizzonte temporale un giorno. C’è una flotta di corrieri disponibili, ognuno dei quali può trasportare un massimo numero di esemplari e può lavorare un massimo numero di ore massimo. Ogni corriere comincia e termina il suo giro nell’unico deposito presente nella rete (il centro di raccolta).

I vincoli 

Da considerare poi c’è l’insieme delle biblioteche pubbliche da visitare quel giorno. Ogni biblioteca può avere un certo numero di esemplari da consegnare al corriere (operazione di pickup) e/o un numero di esemplari da ricevere dal corriere (operazione di delivery). Tutti gli esemplari da consegnare alle biblioteche si trovano già nel deposito all’inizio del giorno. Viceversa, tutti gli esemplari che vengono ritirati dal corriere nelle biblioteche vengono portati al deposito alla fine del giorno. Ogni biblioteca deve essere visitata da un corriere durante i suoi orari di apertura (per esempio, tra le 9:00 e le 18:00), a meno che il corriere non abbia una copia delle chiavi di quella biblioteca. Questi sono i vincoli principali del problema.

Possiamo pensare al problema come a un grafo dove i punti da raggiungere sono tutte le biblioteche, collegate tra loro attraverso le possibili strade. Per esempio, per spostarsi dalla Biblioteca di Chiari alla Biblioteca di Iseo, il tragitto più corto sarebbe di 21,8 km e richiederebbe 32 minuti.

Percorsi consigliati da Google Maps tra la Biblioteca di Chiari e la Biblioteca di Iseo.

La funzione obiettivo

Lo scopo è quello di minimizzare il numero di chilometri percorsi dai corrieri, assegnando a ognuno di essi un insieme di biblioteche da visitare e definendone la rotta, che parte e termina nel deposito. 

Le variabili

Le decisioni da prendere corrispondono alle variabili del problema: un determinato corriere visiterà una determinata biblioteca? Quali biblioteche dovrà visitare ogni corriere? E in quale ordine? Quali strade dovrà percorrere? A che ora arriverà in una certa biblioteca?

Queste variabili, i vincoli, e la funzione obiettivo costituiscono un modello di programmazione lineare mista intera (alcune variabili potranno assumere valore continuo, altre invece dovranno essere intere o binarie) per rappresentare il prestito interbibliotecario come un problema di routing.

I risultati dei test computazionali

Una volta formulato il modello e dopo averlo implementato (per esempio, con un linguaggio di modellazione algebrica come AMPL o usando librerie come gurobipy per Python), esso può essere dato in pasto a un solver, un software in grado di restituire una soluzione ottima. Se il tempo richiesto per determinare l’ottimo sarebbe più di quanto concesso, il solver restituirà la soluzione migliore trovata fino a quel momento. La soluzione ottima indicherà i valori da assegnare a tutte le variabili, tali da soddisfare tutti i vincoli e minimizzare la funzione obiettivo.

Sfruttando il solver Gurobi per risolvendo tutte le istanze giornaliere ricavate dal database dei prestiti avvenuti nell’intero anno solare 2019, si dimostra che ricorrere a un tale modello porterebbe a diminuire il numero totale di chilometri annuali di circa il 19%.

Tra la teoria e la pratica

Ciò nonostante, adottare un tale modello potrebbe non essere così conveniente in pratica. Appoggiarsi a un calendario settimanale statico di visite e percorrere ogni giorno le stesse rotte può essere più utile per i bibliotecari e per i corrieri per organizzare le attività o per avere più familiarità con le strade (per esempio, evitando alcuni tratti trafficati in orari di punta). Se ogni giorno le rotte cambiassero, si perderebbero questi vantaggi e il servizio in sé potrebbe subire rallentamenti. Il modello di programmazione lineare mista intera proposto offre sì una buona rappresentazione del problema reale, ed è un ottimo strumento per analizzare e valutare il sistema corrente. Tuttavia tralascia, purtroppo, alcune circostanze reali.

C’è ancora lavoro da fare. Come ha concluso Marco Gussago, riportando un detto, “la differenza tra la pratica e la teoria è più grande in pratica che in teoria.”

Qui potete visionare tutto il seminario sul prestito interbibliotecario della RBBC analizzato come problema di routing:

 

Il prossimo incontro di “ROAR IN AZIONE!”

Il prossimo seminario è in programma lunedì 14 febbraio alle ore 11:00. Il relatore sarà Leonardo Drahorad (Amazon), che parlerà dell’ottimizzazione geospaziale delle consegne. Per poter seguire il seminario su Zoom, anche con un’eventuale classe di studenti, contattatemi via e-mail.