J'habite dans une tour. Si. Un grand immeuble de presque 30 étages, qui dispose de quatre cabines d'ascenseur pour les desservir. Deux sont consacrés aux étages 18 à 29 (ils partent quand même du rez-de-chaussée ...), deux autres s'occupant des étages 0 à 18. Or j'ai constaté que ces deux-là (je n'ai pas fait attention au comportement des deux autres, ne les utilisant pas) se (re)placent assez systématiquement chacun à une "extrémité" de leur parcours. Je ne sais pas au bout de combien de temps d'inactivité ils prennent cette initiative, mais le fait est que le soir, à une heure où ils sont peu utilisés, il y en a toujours un au rdc et un autre au dix-septième (pourquoi pas le dix-huitième, ma foi, c'est un premier mystère mais pour lequel je n'aurai sans doute jamais de réponse).

Intuitivement je m'étais dit que cette stratégie n'était pas forcément pire qu'une autre, mais après réflexion c'est sûrement faux. La position optimale (dans le sens où elle minimise les temps d'attente moyens) pour un ascenseur unique dans un immeuble de n étages consiste à se placer (au bout d'un certain temps) à l'étage n/2 (les comiques du fond de la classe me feront grâce du cas où n est impair ...).
Un petit exemple simple pour se convaincre ? Un immeuble de trois étages (hors rdc ...), avec un seul habitant par étage. Si l'ascenseur part systématiquement de l'étage "médian" (le deuxième, donc, puisque (n+1)/2 est la réponse au cas impair), l'occupant du deuxième n'attendra pas, alors que celui du troisième attendra une seconde (oui, c'est un ascenseur rapide à un étage par seconde, mais vous pouvez prendre l'unité-étage-temps que vous voulez), ainsi que celui du premier (qui aurait mieux fait de prendre l'escalier, mais ca complique la démonstration). Attente totale : 2 secondes. Attente moyenne par individu : 2/3 secondes.
Si l'ascenseur part du troisième, l'occupant de cet étage y gagne, mais celui du 2e patiente une seconde, et celui du 1er étage deux secondes. Attente totale : 3 secondes. Attente moyenne par habitant : 1 seconde.

En généralisant à n étages, si l'acenseur part systématiquement du dernier les temps d'attente cumulés seront de 1+2+...+(n-1), dont la somme vaut n(n-1)/2. Si au contraire il part systématiquement de l'étage k=n/2, les temps d'attente cumulés seront de (1+2+...+k) pour les habitants des étages k+1 à n, et (1+2+...+(k-1)) pour les occupants des étages k-1 à 1. Soit au total : k(k+1)/2 + k(k-1)/2 = k^2 = n^2/4.

Pour n grand le choix de cette deuxième stratégie est donc deux fois plus intéressant. Ce raisonnement peut également être étendu au cas de deux ascenseurs. La stratégie actuellement utilisée par ceux de mon immeuble est moins efficace que celle qui consiste à en placer un au cinquième, c'est-à-dire à mi-chemin des étages 1 à 9, et l'autre au 14è, à mi-chemin du tronçon 10-18. La rentabilité (en termes énergétiques) d'un replacement systématique à l'étage médian est en outre fortement dépendante du temps moyen d'inactivité. Lors des pics de fréquentation, disons 7h-9h le matin et 17-19h le soir, l'attente est clairement nettement plus économique que le replacement. Lorsque la fréquentation est faible, en revanche, ça mérite davantage de réflexion.

Todo-list : un petit modèle dynamique discret, avec deux gaussiennes pour représenter les taux d'utilisation des ascenseurs matin et soir, un générateur de nombres aléatoires pour dire si c'est Madame Rombier du 3ème ou Monsieur Plantard du 17è qui descendra le premier le matin, et zou, let the code roll pour voir ce que ça dit. Je me demande si le sujet est susceptible d'intéresser grand monde à la prochaine réunion de copros ...