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

Abstract

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.

While the location literature is vast, most papers consider simpler models, in which a central authority assigns users to the closest facilities. More realistic traits, such as user behaviour, competition, and congestion are often overlooked, perhaps due to their `complicating' highly non-linear nature. A few papers did incorporate them, but separately, and only heuristic approaches have been proposed as solution methods.

The facility location problem consists in optimally locating a set of facilities in order to satisfy a given demand. In a congested user-choice environment, facilities are typically modeled as queues, and users select the facilities to patronize based on their perceived utility, which is, in general, written as linear combination of travel distance, waiting time at facilities, etc. The resulting bilevel model belongs to the class of mathematical programs with equilibrium constraints (MPECs), where the equilibrium can be expressed as a variational inequality.

Our work is focused on the \emph{competitive congested user-choice facility location problem} (CC-FLP), and we provide a number of strong contributions. From the modeling point of view, we propose various models that capture the key features of CC-FLP. For these NP-hard discrete nonlinear programs we designed exact and approximated algorithms, as well as tailored heuristics. Our work spans three papers. In the first article we consider different models that incorporate balking at facilities, due to limited places in the queue, while user behaviour can be either deterministic or stochastic. In the latter case, user behaviour fits Wardrop's equilibrium principle, while in the former case, customers distribute among facilities according to a Logit random utility choice model. Beyond the analysis of the model's theoretical properties, we design a user-driven heuristic and a linear approximation algorithm, for which we prove a bound on the approximation error, for the M/M/1 queue.

The second paper is dedicated to the design of a novel exact branch-and-bound (B&B) algorithm for solving a more general subclass of MPECs, which is implemented and evaluated on a CC-FLP. The idea is to virtually treat each node of the B&B tree as a separate optimization problem, in oder to leverage the strength of the MILP solvers and their strong preprocessing at the root node. Our algorithmic approach is based on a combination of Mixed-Integer Linear Programming (MILP), linearization techniques and the iterative solution of convex subproblems, and requires a sophisticated tree management.

In the third paper we incorporate mill pricing into the CC-FLP. Price is a continuous decision variable, along with the location and service levels, and user incorporate it into their utility. Since concepts from network pricing and CC-FLP are merged into a single model, the problem becomes extremely challenging, also due to the presence of facility location and service level decision variables, as well as bivariate queueing delays. For this non-convex bilevel program we devise an algorithm based on linear approximations, that borrows from both location and network pricing literature.