Blog divulgativo sulla matematica applicata

Supermercati, traffico e statistica: la TEORIA DELLE CODE

La fila accanto è sempre più veloce

Da romana quale sono, una delle prima cose che mi viene in mente quando penso a Roma è...il traffico! @_@

Ci avete mai fatto caso a tutte quelle situazioni (per esempio stare in coda nel traffico) in cui "perdiamo" tempo? In fila alle poste, al bar, in cassa al supermercato, al bagno nei ristoranti, al casello, al pronto soccorso, ...

L'elenco è potenzialmente infinito. E' un dato di fatto che le code sono parte integrante della nostra vita di tutti i giorni (e non mi riferisco alla coda, cito vocabolario: "appendice del corpo dei vertebrati, opposta alla testa" ;-) ).

long queue of people, back view

Il comportamento che mostriamo in coda assume diverse sfumature: c’è chi attende tranquillamente il proprio turno, c’è chi comincia a inveire verso gli impiegati dello sportello e c’è chi, avendone la possibilità, cambia la sua fila d’attesa. Dover aspettare non è solo un disagio della singola persona: il tempo che la popolazione di una nazione perde aspettando in coda è uno dei principali fattori sia nella qualità della vita sia nell'efficienza dell'economia di un Paese.

Mi spiace rendere pubblica questa verità, ma al contrario di dicerie popolari, le code non sono regolate dalle leggi di Murphy (“La fila accanto è sempre più veloce”), ma da leggi matematiche ben precise, nelle quali trova larga applicazione, per esempio, la distribuzione di Poisson. In matematica e nelle scienze applicate la CODA viene definita come una fila ordinata di utenti in attesa del proprio turno per ottenere un servizio. Gli utenti possono essere persone, oggetti fisici o dati in un sistema informatico; il servizio può essere quello fornito da uno sportello o da un negozio, può essere il transito da un varco o l'ingresso in un mezzo di trasporto in un luogo pubblico o in una strada, una elaborazione dei dati in informatica, la trasmissione di un pacchetto nelle telecomunicazioni.

Una coda ha una teoria dietro?! O.o

La teoria delle code è considerata una branca della c.d. Ricerca Operativa e permette di formalizzare modelli di code tramite i quali è possibile rappresentare i vari tipi di sistemi di fila d'attesa che sorgono nella pratica. Le formule che si ricavano indicano come i relativi sistemi dovrebbero operare, e la quantità media di attesa che si verifica nelle varie circostanze. Tali modelli risultano molto utili per stabilire come agisce un sistema di fila d'attesa e come potrebbe essere ottimizzato. Le problematiche d'interesse generalmente riguardano i costi. Se si fornisce un'elevata capacità di servizio il gestore del sistema incorrerebbe in costi eccessivi, ma se non se ne fornisce abbastanza si potrebbe verificare un'attesa molto lunga, percepita come costo da parte del cliente. I modelli di teoria delle code permettono di determinare un giusto equilibrio tra il costo del servizio e il tempo d'attesa (definito come costo dall'utente).

queuing-theory-7-728

Gli elementi che permettono di definire completamente un sistema d’attesa sono:

  • la popolazione dei clienti: insieme dei potenziali clienti
  • il processo d'arrivo: modo secondo cui i clienti si presentano e solitamente rappresentato tramite un processo stocastico definito in termini della distribuzione dell'intertempo d'arrivo, cioè dell'intervallo di tempo che intercorre tra l'arrivo di due clienti successivi
  • la coda (in senso stretto): formata dai clienti in attesa di essere serviti
  • i servitori: punti di erogazione del servizio
  • il processo di servizio: solitamente anch'esso un processo stocastico il quale definisce il tempo in cui il servizio viene erogato
  • la disciplina di servizio:  specifica quale sarà il prossimo cliente servito fra quelli in attesa al momento in cui si libera un servitore. Le discipline di servizio usualmente considerate sono: 1) FCFS - First Come First Served; 2) FIFO - First In First Out; 3) LCFS - Last Come First Served; 4) LIFO - Last In First Out; 4) SIRO - Service In Random Order.

"Rappresentare" una coda: la notazione di Kendall

La c.d. notazione di Kendall riporta tutti gli elementi fondamentali grazie ai quali è possibile definire una coda: A/B/c/K/m/Z

  • A: distribuzione del processo d'arrivo;
  • B: distribuzione del processo di servizio;
  • c: numero di servitori;
  • K: capacità del sistema (default: infinita);
  • m: dimensione della popolazione (default: infinito);
  • Z: disciplina di servizio (default: FCFS);

Dal punto di vista dinamico una coda è costituita essenzialmente da due processi stocastici: il processo d'arrivo dei clienti (lettera A) e il processo di servizio (lettera B). In particolare ad A e B possono essere sostituite le seguenti lettere:

  • M : distribuzione esponenziale (Markoviana)
  • D : distribuzione costante (Degenere)
  • Ek : distribuzione di Erlang di ordine k
  • G : distribuzione generica
  • GI : distribuzione generica di eventi indipendenti (per gli arrivi)

Ad esempio M/M/1 sta per M/M/1/∞/∞/FCFS: coda con processo degli arrivi e dei servizi
markoviani, con un servitore, con capacità del sistema infinita, con arrivi provenienti da una popolazione infinita, serviti su base FCFS.

Esempio di un problema reale

Supponiamo di essere in un supermarket in cui entrano 10 clienti al minuto, e supponiamo che ogni cassa smaltisca un cliente ogni 2 minuti. Quante casse devo predisporre affinché il tempo medio di attesa totale (attesa in coda + più servizio in cassa) sia inferiore ai 5 minuti?

Fila

Definiamo:

  • μ=2 : tasso medio di servizio ⇒ 1/μ=0.5 : tempo atteso di servizio
  • λ=10 : tasso medio di arrivo  ⇒  1/λ=0.1 : tempo atteso tra due arrivi
  • incognita: s  numeri di serventi

A questo punto è fondamentale definire il cosiddetto fattore di utilizzazione 

ρ=λ/(sμ) 

il quale esprime il rapporto tra il tempo medio di servizio e il tempo medio tra due arrivi. Un sistema viene detto stabile se in media ha la potenzialità di servire i clienti più velocemente di quanto essi non arrivino. Da cui si ricava la cosiddetta condizione di stabilità: ρ<1.

Pertanto:

Se deve essere (10/s*0.5)<1

⇒ s=20

Quindi con 20 casse a disposizione avrei la certezza di avere un sistema in grado di smaltire la coda,  ma non di garantirmi che il tempo medio di attesa sia inferiore ai 5 minuti.

Il tempo medio di attesa in un sistema con s servitori è uguale a:

Ws = s/(μ*s-λ)

Imponendo il vincolo:

Ws < 5 ⇒ s/(0.5*s-10) < 5 ⇒ s > 33.33

Quindi, dati questo tempo medio di arrivo dei clienti e questo tempo medio di servizio, il numero di casse che garantisce un tempo di permanenza medio nel sistema inferiore ai 5 minuti è 34.

Non so voi...io 34 casse attive in un supermercato non le ho mai viste. E infatti direi che il tempo medio di permanenza in coda è nettamente superiore ai 5 minuti! :-P

E sperando almeno sul finale di avervi strappato un sorriso ;-) al prossimo post!

KEEP IN TOUCH! :-)

CC BY-NC-SA 4.0
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Similar posts

Nessun commento ancora

Lascia una risposta

L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *

È possibile utilizzare questi tag ed attributi XHTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Canale Telegram dedicato alla Matematica

Iscriviti sul nostro canale Telegram

MIA15 - Nomination

Rimani aggiornato sui più interessanti articoli di divulgazione matematica e non solo!

Iscriviti alla nostra newsletter

Resta aggiornato sui nostri post e su quello che facciamo.

Seguici su Twitter

Tag Cloud

Grazie per il sostegno ai #MIA2015

Grazie a tutti per averci votato ai "Macchia Nera Awards 2015" nella categoria "Miglior Sito Tecnico-Divulgativo".

Siamo arrivati in finale grazie al vostro sostegno!

MIA15 - Nomination