Optimization Online


A biased random-key genetic algorithm for road congestion minimization

L.S. Buriol(buriol***at***inf.ufrgs.br)
M.J. Hirsch(mjh8787***at***ufl.edu)
P.M. Pardalos(pardalos***at***ufl.edu)
T. Querido(tania***at***linearoptions.com)
M.G.C. Resende Resende(mgcr***at***research.att.com)
M. Ritt(marcus.ritt***at***inf.ufrgs.br)

Abstract: One of the main goals in transportation planning is to achieve solutions for two classical problems, the traffic assignment and toll pricing problems. The traffic assignment problem aims to minimize total travel delay among all travelers. Based on data derived from the first problem, the toll pricing problem determines the set of tolls and corresponding tariffs that would collectively benefit all travelers and would lead to a user equilibrium solution. Obtaining high-quality solutions for this framework is a challenge for large networks. In this paper, we propose an approach to solve the two problems jointly, making use of a biased random-key genetic algorithm for the optimization of transportation network performance by strategically allocating tolls on some of the links of the road network. Since a transportation network may have thousands of intersections and hundreds of road segments, our algorithm takes advantage of mechanisms for speeding up shortest-path algorithms.

Keywords: Transportation planning, system optimal, user equilibrium, traffic assignment, toll booth placement, dynamic shortest paths, genetic algorithm.

Category 1: Applications -- OR and Management Sciences (Transportation )

Category 2: Combinatorial Optimization (Meta Heuristics )

Category 3: Combinatorial Optimization

Citation: AT&T Labs Research Technical Report, AT&T Labs Research, Florham Park, NJ 07932 USA, July 2010.

Download: [PDF]

Entry Submitted: 07/26/2010
Entry Accepted: 07/26/2010
Entry Last Modified: 07/26/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society