Optimization and equilibrium problems with discrete choice models

Abstract

Many transportation markets are characterized by oligopolistic competition. In these markets customers, suppliers and regulators make decisions that are influenced by the preferences and the decisions of all other agents. In particular, capturing and understanding demand heterogeneity is key for suppliers and regulators to develop optimal strategies and policies. A state-of-the-art approach to model demand at a disaggregate level is discrete choice modeling. This thesis deals with the integration of discrete choice models into optimization and equilibrium problems by means of simulation. First, we analyze a deregulated competitive market. When a disaggregate heterogeneous demand is considered, there is no theoretical guarantee that a market equilibrium solution exists, nor it is possible to rely on derivative-based methods to find one. Therefore, we propose a simulation-based heuristic to find approximate equilibrium solutions. Numerical experiments show that the proposed algorithm can approximate the results of an exact method that finds a pure equilibrium in the case of logit demand with single-product offer and homogeneous customers. Furthermore, the algorithm succeeds at finding approximate equilibria for two transportation case studies featuring more complex discrete choice models, heterogeneous demand, multi-product offer by supplies, and price differentiation, for which no analytical approach exists. Then, the framework is extended to the case of a regulated competitive market. The objective of the regulator is to find optimal price-based policies which affect the behavior of all other agents towards welfare-maximizing outcomes. In transport markets, economic instruments might target specific alternatives, to reduce externalities such as congestion or emissions, or specific segments of the population. A mixed-integer linear optimization model is presented which finds optimal policies subject to supply's profit maximization and demand's utility maximization constraints. This model is included into an adapted version of the simulation-based heuristic framework developed for deregulated competition. Numerical experiments on an intercity travel case study show how the regulator can optimize taxes and subsidies for different objective functions and scenarios. Finally, a deeper analysis is conducted on the choice-based optimization model that represents a fundamental block, and the most computationally expensive one, of the choice-based equilibrium framework. Because of simulation, the problem has a block-diagonal structure that makes it suitable to the use of mathematical decomposition techniques. Specifically, it is shown that a formulation in which all the decision variables of the supplier are discrete is amenable to the use of Benders decomposition. Under this assumption, a Benders decomposition scheme is derived and implemented within a branch-and-cut approach to solve an uncapacitated facility location and pricing problem with disaggregate demand. Numerical experiments that compare this approach with a black-box solver show that the black-box solver is faster at solving small instances, while Benders decomposition is faster on larger instances. The possibility to achieve speed-ups through enhancements available in the literature and to tackle large problems with more complex structures should motivate further investigation of Benders and other decomposition techniques for other classes of choice-based optimization problems.