Frank-Wolfe Algorithm Implementation for Traffic Equilibrium Assignment

The Frank-Wolfe algorithm is a classical method for solving convex optimization problems, particularly well-suited for large-scale issues with linear constraints like traffic equilibrium assignment. In transportation engineering, equilibrium assignment aims to rationally distribute travel demand across network paths based on road impedance factors such as travel time, ultimately achieving user equilibrium—where no traveler can unilaterally change routes to reduce their travel cost.

The Frank-Wolfe algorithm approaches optimal solutions through iteration. Its core mechanism involves: calculating the gradient of the objective function (path impedance) using the current solution, solving a linear subproblem (typically all-or-nothing assignment) to generate a descent direction, and determining step size via line search before updating the solution. Implementation advantages include efficient subproblem resolution and memory efficiency—storing only current path flows rather than complete flow patterns—making it suitable for large-scale networks. In code implementations, key functions would include gradient calculation using current impedance values and shortest-path algorithms for the all-or-nothing assignment subproblem.

The algorithmic workflow for traffic equilibrium assignment can be summarized as: Initialization: Typically starting from free-flow conditions (zero traffic) as the initial point; All-or-Nothing Assignment: Computing shortest paths based on current impedance and loading all flow onto these optimal paths using Dijkstra's algorithm or similar methods; Line Search: Finding optimal step size along the new solution direction through techniques like bisection search or golden section search to balance impedance between old and new paths; Termination Criteria: Stopping iterations when flow changes or impedance differences fall below predefined thresholds, often implemented with convergence checks in while-loop structures.

The algorithm demonstrates strong extensibility, allowing integration with heuristic step-size strategies for accelerated convergence or combination with nonlinear impedance models like BPR functions through impedance update functions in each iteration. Its primary limitation lies in slower convergence during later stages, often addressed through hybrid approaches like gradient projection methods that combine Frank-Wolfe's direction finding with more sophisticated step-size optimization techniques.