Scegliere una coda anziché un’altra può cambiare il tempo d’attesa. Ma c’è una strategia migliore? La matematica suggerisce la risposta. Ce ne parla Marco Menale.

I nuovi stili di vita richiedono sempre più efficienza nell’organizzazione quotidiana. Gli orari di lavoro ci costringono a gestire in modo ottimale le incombenze di casa. Succede quando siamo al supermercato per la spesa. Dopo aver riempito il carrello, arriviamo alle case per il momento “ora, quale coda scelgo?”. Meglio una scelta a caso oppure guardare un po’ nei vari carrelli rispetto alla lunghezza delle code? La matematica può aiutarci in questa scelta.

Ci rifacciamo ai risultati di un lavoro del 2006. Si tratta dell’articolo “On the maximum queue length in the supermarket model” di Malwina J. Luczak e Colin McDiarmid, pubblicato su The Annals of Probability. Usando un modello probabilistico che simula il comportamento di clienti davanti a più code, l’obiettivo è capire come evolvono le code alle casse in base alle scelte dei clienti.

Si considera un sistema costituito da $n$ casse, con $n>1$, ciascuna con la propria coda. I clienti arrivano nel tempo secondo una distribuzione di Poisson di parametro $\lambda$. L’intensità della clientela alle case è $\lambda n$, ossia proporzionale al numero di casse $n$. Si suppone che ciascun cliente non osservi tutte le code, ma solo un gruppo $d$ casuale, con $d\geq 1$ intero positivo fissato. Il funzionamento del processo è così definito: un cliente arriva alle casse, seleziona $d$ code e sceglie quella con meno persone tra queste. In caso di parità, si sceglie ancora casualmente tra quelle più corte.

A questo punto i due autori usano strumenti di calcolo delle probabilità, come le catene di Markov a tempo continuo, per capire, tra gli altri, come il valore del parametro $d$ influenzi l’evoluzione del sistema. Dimostrano che se $d=1$, ossia ogni cliente sceglie una coda a caso, allora la coda più lunga del supermercato cresce in lunghezza come $\ln n$. Invece, già passando a $d=2$, ossia ciascun cliente guarda almeno due code, la lunghezza della coda più lunga cresce più lentamente, infatti va come $\ln \ln n$. Essendo quest’ultima funzione (se la vediamo come funzione \ln \ln x) più lenta nella crescita di $\ln x$ (Figura 1), si nota come migliora la situazione delle code.

Figura 1. Confronto tra $\ln(x)$ e $\ln(\ln(x))$.

Più precisamente, gli autori mostrano che le code si distribuiscono in modo altamente regolare: quasi tutte hanno una lunghezza simile, e la coda più lunga è confinata in un intervallo molto ristretto. In un certo senso, il sistema si auto-organizza in modo efficiente grazie a decisioni individuali parziali, ma intelligenti, con tutte le sfumature di questa parola. Non serve conoscere tutto: osservare solo due code già migliora le cose, malgrado l’impressione di trovarci sempre nella fila più lenta.

I risultati di questo lavoro vanno oltre la coda al supermercato. Lo stesso principio è applicato nei data center, nei server distribuiti, nei sistemi di traffico e in altri contesti. Quindi, la prossima volta al supermercato, al momento della scelta della cassa, tra carrello e orologio che ci suggerisce fretta, meglio guardare almeno due code per una scelta migliore.

Marco Menale