Haering, T., Legault, R., Torres, F., and Bierlaire, M. (2024)

Fast Algorithms for Capacitated Continuous Pricing with Discrete Choice Demand Models

24th Swiss Transport Research Conference, Ascona, Switzerland

We introduce the Breakpoint Exact Algorithm with Capacities (BEAC), based on the state-of-the-art Breakpoint Exact Algorithm (BEA) to address the choice-based pricing problem (CPP) with capacity constraints, together with the Breakpoint Heuristic Algorithm (BHA) for both uncapacitated and capacitated instances. For capacity management, an approach based on an exogenous priority queue, as well as a supplier-controlled queuing strategy to generate maximal or minimal profit for robust optimization is developed. The BHA leverages a coordinate descent method, which we propose to extend with a dynamic line search (DLS) to escape local optima. Our results show that for the capacitated case, the BEAC reports runtimes up to 20 times faster than the state-of-the-art mixed-integer linear programming (MILP) approach, while the BHA performs from 100 to 5000 times faster than the MILP. For the uncapacitated case, the BHA outspeeds the BEA as well as the current state-of-the-art Branch & Benders Decomposition (B&BD) approach by multiple orders of magnitude, especially for high-dimensional instances. The average gap in optimality between the solution reported by the BHA and the global optimum was less than 0.2%, with the extension via DLS finding the global optimum in all tested instances, albeit at a significant computational cost.