A Scatter Search Algorithm for Solving a Bilevel Optimization Model for Determining Highway Tolls

Abstract

The problem of determining the optimal tolls established on a subset of the arcs in a multicommodity capacitated transportation network is presented. The problem is formulated as a bilevel optimization problem where the upper level consists of an administrator who establishes the tolls in some arcs of the network, while the lower level is represented by a group of users who travel along the shortest paths with respect to a travel cost. The objective is not only to increase the tolls, but also to maintain an optimal flow on the arcs of the network in order to maximize the leader’s profit. If the leader sets very high toll values, the followers will be discouraged from using the tolled arcs, so the profit obtained from that decision is not going to be convenient for the leader. A methodology to solve this problem using an optimization software at the lower level and the metaheuristic Scatter Search at the upper level is proposed.