Haering, T., Torres, F., and Bierlaire, M.

Fast Algorithms for Capacitated Continuous Pricing with Discrete Choice Demand Models

Speaker: Haering Tom

2nd EPFL Symposium on Transportation Research, EPFL

February 05, 2024

This research introduces the Breakpoint Exact Algorithm with Capacities (BEAC) and the Breakpoint Heuristic Algorithm (BHA), both of which offer substantial advancements in solving the choice-based pricing problem (CPP) with and without capacity constraints. The BEAC, enhancing the Breakpoint Exact Algorithm (BEA) with a capacity management strategy, outperforms the state-of-the-art mixed-integer linear programming (MILP) approach by 20 times in computational speed. The BHA, employing a coordinate descent method, excels in high-dimensional scenarios, showing remarkable efficiency in both capacitated and uncapacitated cases. Notably, it outpaces the MILP by a factor of 100 to 5000 for the capacitated case, and the state-of-the-art Branch and Benders Decomposition approach by several orders of magnitude for the uncapacitated case, while maintaining an average optimality gap of less than 0.2\%. The dynamic line search extension of the BHA succeeds in identifying the global optimum in all tested instances, albeit with a significant speed reduction. For future research, other extensions of the BHA to escape local optima should be considered.