Algorithmic contributions to bilevel location problems with queueing and user equilibrium : exact and semi-exact approaches

Bien que la littérature sur le problème d'emplacement soit vaste, la plupart des publications considèrent des modèles simples, dans lesquels une autorité centrale assigne les utilisateurs aux installations les plus proches. Des caractéristiques plus réalistes, telles que le comportement des usagers, la compétition et la congestion, sont souvent négligées, peut-être en raison de leur nature hautement non-linéaire «compliquée». Quelques articles ont incorporé ces traits, mais uniquement de facon séparée, et seulement des approches heuristiques ont été proposées comme méthodes de résolution. Le problème d'emplacement d'installations consiste à localiser un ensemble d'installations de manière optimale afin de répondre à une demande donnée. Dans un environnement congestioné où les usagers ont le choix, les installations sont généralement modélisées sous la forme de files d'attente. Les utilisateurs sélectionnent les installations à fréquenter en fonction de leur utilité perçue, qui est généralement écrite comme une combinaison linéaire de la distance de déplacement, du temps d'attente dans les installations, etc. En résulte un modèle dit "à deux niveaux" appartenant à la classe des programmes mathématiques à contraintes d'équilibre (MPEC en anglais), où l'équilibre peut être exprimé sous la forme d'une inéquation variationnelle. Notre travail est axé sur le problème d'emplacement d'installations où les usagers ont le choix (CC-FLP en anglais) et nous fournissons un certain nombre de contributions importantes. Du point de vue de la modélisation, nous proposons différents modèles qui capturent les principales caractéristiques du CC-FLP. Pour ces programmes non-linéaires, discrets, et NP-difficiles, nous avons conçu des algorithmes exactes et d'approximation, ainsi que des heuristiques sur-mesure. Notre travail couvre trois articles. Dans le premier article, nous considérons différents modèles qui intègrent l'abandon aux centres de services, en raison des places limitées dans la file d'attente, tandis que le comportement des utilisateurs peut être déterministe ou stochastique. Dans ce dernier cas, le comportement des usagers correspond au principe d'équilibre de Wardrop, tandis que dans le premier cas, les clients se distribuent entre les établissements selon un modèle de choix d'utilité aléatoire Logit. Au-delà de l'analyse des propriétés théoriques du modèle, nous concevons une heuristique menée par les usagers et un algorithme d'approximation linéaire pour lequel nous prouvons une borne d'erreur de l'approximation, dans le cas d'une file d'attente M/M/1. Le second article est consacré à la conception d'un nouvel algorithme de `Branch and Bound' (B&B) pour résoudre une sous-classe plus générale des MPEC. L'algorithme est implémenté et évalué sur un CC-FLP. L'idée est de traiter virtuellement chaque nœud de l'arbre B& B comme un problème d'optimisation distinct, afin de tirer parti de la puissance des solveurs MILP et de leur prétraitement fort au niveau de la racine. Notre approche algorithmique est basée sur une combinaison de programmation linéaire à nombres entiers et mixtes (MILP en anglais), de techniques de linéarisation et de la résolution itérative de sous-problèmes convexes, et nécessite une gestion d’arbre sophistiquée. Dans le troisième article, nous incorporons les prix dans le CC-FLP. Le prix est une variable de décision continue, tout comme la localisation et le niveaux et de service, et les utilisateurs l'intègrent dans leur utilité. Les concepts de tarification du réseaux et de CC-FLP étant fusionnés en un seul modèle, le problème devient extrêmement difficile, également en raison de la présence de variables de localisation et de niveau de service, ainsi que de délais d'attente bidimensionnels. Pour ce programme à deux niveaux non-convexe, nous avons conçu un algorithme basé sur des approximations linéaires emprunté à la fois à la littérature sur la localisation et à la tarification du réseau.

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.