文献类型：期刊文献

英文题名：A Cardinality-Constrained Approach to Combinatorial Bilevel Congestion Pricing

作者：Guo, Lei[1]; Li, Jiayang[2]; Nie, Yu[3]; Xie, Jun[4]

机构：[1] School of Business, East China University of Science and Technology, China; [2] Department of Data and Systems Engineering, The University of Hong Kong, Hong Kong; [3] Department of Civil and Environmental Engineering, Northwestern University, United States; [4] School of Transportation and Logistics, Southwest Jiaotong University, China

年份：2024

外文期刊名：arXiv

收录：EI(收录号：20240519933)

语种：英文

外文关键词：Approximation algorithms - Integer programming

摘要：Combinatorial bilevel congestion pricing (CBCP), a variant of the mixed (continuous/discrete) network design problems, seeks to minimize the total travel time experienced by all travelers in a road network, by strategically selecting toll locations and determining toll charges. Conventional wisdom suggests that these problems are intractable since they have to be formulated and solved with a significant number of integer variables. Here, we devise a scalable local algorithm for the CBCP problem that guarantees convergence to an approximate Karush-Kuhn-Tucker point. Our approach is novel in that it eliminates the use of integer variables altogether, instead introducing a cardinality constraint that limits the number of toll locations to a user-specified upper bound. The resulting bilevel program with the cardinality constraint is then transformed into a block-separable, single-level optimization problem that can be solved efficiently after penalization and decomposition. We are able to apply the algorithm to solve, in about 20 minutes, a CBCP instance with up to 3,000 links. To the best of our knowledge, no existing algorithm can solve CBCP problems at such a scale while providing any assurance of convergence. Copyright ? 2024, The Authors. All rights reserved.