Benchmark Instances for the Bilevel Optimization of the Toll Pricing Problem

Resumo

The Toll Pricing Problem (TPP) seeks to optimize tolls in a network by maximizing profit while minimizing the travel cost of users. Bilevel optimization emerges as a suitable way for modeling this problem, as it allows the regulatory authority to anticipate users' responses to the toll policy. Due to the complexity of the problem, metaheuristics are frequently employed. The development of new metaheuristics requires a rigorous investigation process, involving the testing of different search strategies and parameter settings. Moreover, comparative evaluations between methods are essential to validate progress and guide improvements in bilevel optimization techniques. We propose a benchmark suite comprising 192 instances for a bilevel toll optimization problem. In this setting, the upper-level objective is to maximize the toll manager's profit, while the lower level seeks to minimize the total travel cost for routing a set of commodities across a network. The benchmark includes instances ranging from 10 to 60 nodes and 5 to 40 commodities, with tolls applied to 20%-40% of edges in smaller instances (up to 15 nodes) and 5%-20% in larger instances (up to 60 nodes). A bilevel algorithm with multiple followers was used to generate reference results, which are provided for future benchmarking. The dataset includes the best-obtained toll values and their corresponding routing costs.