nexact restoration method to solve the demand adjustment problem

LOTITO, PABLO ANDRÉS; MANCINELLI, E.M.; PARENTE LISANDRO A.; JORGELINA WALPEN

Tandil

Workshop; V LAWOC 2016; 2016

CONICET-UNCPBA-ANPCyT

The problem of estimating the origin-destination matrix(DAP: demand adjustment problem) in a congested transportnetwork, can be dealt as a Mathematical Program withEquilibrium Constraints (MPEC), where the equilibriumconstraint is precisely, the user?s deterministicequilibrium formulated by Wardrop (DUE: deterministic userequilibrium). Under certain assumptions over the net it canbe proved that equilibrium solutions coincide with thesolutions of a convex optimization problem (TAP: trafficassignment problem). Consequently, DAP can be rewritten asa bilevel optimization problem.An inexact restoration method for nonlinear bilevel problemshas been studied and adapted in order to test its performanceover DAP. Under certain hypothesis convergence is proved in[1] for the original version of the method. So far, we havestudied and proposed in [5] and in [3], heuristics that dealwith the reformulation of DAP as a single level problem. Incontrast, the proposal of this work is interesting as ittakes into account and profits from the structure of theproblem of the lower level, the TAP. The original motivationfor studying this method is associated with this lastobservation, as there exist plenty of algorithms with veryacceptable performance that solve TAP and that can be usedin an implementation of the inexact restoration method tosolve DAP.The Inexact Restoration Method deals separately withfeasibility and optimality at each iteration. In thefeasibility stage, called restoration phase, it seeks for amore feasible point considering the original objectivefunction and constraints. In the optimality phase it looksfor a trial point that reduces sufficiently the value of aLagrangian defined by the original data, in a tangent setthat approximates the feasible region, within a trust regioncentered at the point obtained in the feasibility phase.Sufficient decrease of a merit function that balancesfeasibility and optimality determines the acceptance of thetrial point obtained in the optimization phase. If the trialpoint is not accepted, the size of the trust region isreduced. For the adapted version to solve DAP, the algorithmsimplemented in [2] are used to solve the assignments in therestoration phase of the method and for the optimizationphase a minimization procedure inspired in the work ofMartinez [4] is used.The approach of this work is also interesting in the sensethat it represents a tangible application of the inexactrestoration method.Numerical results are presented.