A smoothing approach for solving transportation problem with road toll pricing and capacity expansions. (English) Zbl 1344.49052
Summary: In this paper, we establish a bi-level optimization model for the equilibrium transportation problem concerning both capacity expansion and road toll pricing under the user equilibrium conditions. The bi-level optimization problem is reformulated as a Mathematical Programming problem with Complementarity Constraints (MPCC), which fails to satisfy the Mangasarian-Fromovitz Constraint Qualification (MFCQ). We adopt a smoothing approach to overcome the lack of constraint qualifications in the MPCC problem. Under mild conditions, it is proved that the sequence of the global optimal solutions generated by solving corresponding smoothing subproblems converges to an optimal solution of the original MPCC problem. Numerical experiments show that the proposed method is practical in solving user equilibrium transportation problems with capacity expansion combining road toll pricing.
MSC:
| 49M30 | Other numerical methods in calculus of variations (MSC2010) |
| 90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |
| 90C90 | Applications of mathematical programming |
| 90B06 | Transportation, logistics and supply chain management |
| 65K05 | Numerical mathematical programming methods |
| 49J40 | Variational inequalities |
Keywords:
bi-level optimization; complementarity constraints; perturbation approach; Fischer-Burmeister function; road toll pricing; capacity expansionReferences:
| [1] | von Stackelberg, H: The Theory of the Market Economy. Oxford University Press, New York (1952) |
| [2] | Bracken, J, McGill, J: Mathematical programs with optimization problems in the constraints. Oper. Res. 21(1), 37-44 (1973) · Zbl 0263.90029 · doi:10.1287/opre.21.1.37 |
| [3] | Lv, YB, Wan, Z: A solution method for the optimistic linear semivectorial bi-level optimization problem. J. Inequal. Appl. (2014). doi:10.1186/1029-242X-2014-164 · Zbl 1380.90245 · doi:10.1186/1029-242X-2014-164 |
| [4] | Vicente, L, Calamai, P: Bilevel and multilevel programming: a bibliography review. J. Glob. Optim. 5(3), 291-306 (2004) · Zbl 0822.90127 · doi:10.1007/BF01096458 |
| [5] | Dempe, S: Foundation of Bilevel Programming: Nonconvex Optimization and Its Applications. Kluwer Academic, Dordrecht (2002) · Zbl 1038.90097 |
| [6] | Colson, B, Marcotte, P, Savard, G: An overview of bilevel optimization. Ann. Oper. Res. 153(1), 235-256 (2007) · Zbl 1159.90483 · doi:10.1007/s10479-007-0176-2 |
| [7] | Salmoron, J, Wood, K, Baldick, R: Analysis of electric grid security under terrorist threat. IEEE Trans. Power Syst. 19(2), 905-912 (2004) · doi:10.1109/TPWRS.2004.825888 |
| [8] | Fampa, M, Barroso, L, Candal, D, Simonetta, L: Bilevel optimization applied to strategic pricing in competitive electricity markets. Comput. Optim. Appl. 39(2), 121-142 (2008) · Zbl 1147.90392 · doi:10.1007/s10589-007-9066-4 |
| [9] | Lim, C, Smith, J: Algorithm for discrete and continuous multicommodity flow network interdiction problems. IIE Trans. 39(1), 15-26 (2007) · doi:10.1080/07408170600729192 |
| [10] | Bianco, L, Caramia, M, Giordani, S: A bilevel flow model for hazmat transportation network design. Transp. Res., Part C, Emerg. Technol. 17(2), 175-196 (2009) · doi:10.1016/j.trc.2008.10.001 |
| [11] | Scheel, S, Scholtes, S: Mathematical programs with complementarity constraints: stationary, optimality and sensitivity. Math. Oper. Res. 25(1), 1-22 (2000) · Zbl 1073.90557 · doi:10.1287/moor.25.1.1.15213 |
| [12] | Ayoishi, E, Shimizu, K: Hierarchical decentralized systems and its new solution by a barrier method. IEEE Trans. Syst. Man Cybern. 11, 444-449 (1981) · doi:10.1109/TSMC.1981.4308712 |
| [13] | Bard, J, Moore, J: A branch and bound algorithm for the bilevel program problem. SIAM J. Sci. Stat. Comput. 11(2), 281-292 (1990) · Zbl 0702.65060 · doi:10.1137/0911017 |
| [14] | Hussein, E, Kamalabadi, I: Taylor approach for solving nonlinear bilevel programming problem. Adv. Comput. Sci., Int. J. 3(5), 91-97 (2014) |
| [15] | Lv, YB, Hu, T, Wang, G, Wan, Z: A neural network approach for solving nonlinear bilevel programming problem. Comput. Math. Appl. 55(12), 2823-2829 (2007) · Zbl 1142.65363 · doi:10.1016/j.camwa.2007.09.010 |
| [16] | Fletcher, R, Leyffer, S: Numerical experience with solving MPECs as NLPs. Tech. report NA-210, University of Dundee, Dundee, Scotland, UK (2002) |
| [17] | Fan, W, Gurmu, Z: Combined decision making of congestion pricing and capacity expansion: genetic algorithm approach. J. Transp. Eng. 140(8), 04014031 (2014) · doi:10.1061/(ASCE)TE.1943-5436.0000695 |
| [18] | Zhang, X, van Wee, B: Enhancing transportation network capacity by congestion pricing with simultaneous toll location and toll level. Eng. Optim. 44(4), 477-488 (2012) · doi:10.1080/0305215X.2011.584534 |
| [19] | Gao, Z, Wu, H, Sun, H: Solution algorithm for the bi-level discrete network design problem. Transp. Res., Part B, Methodol. 39(6), 479-495 (2005) · doi:10.1016/j.trb.2004.06.004 |
| [20] | Marcotte, P: Network design problem with congestion effects: a case of bilevel programming. Math. Program. 34(2), 142-162 (1986) · Zbl 0604.90053 · doi:10.1007/BF01580580 |
| [21] | Suh, S, Kim, TJ: Toward developing a national transportation planning model: a bilevel programming approach for Korea. Ann. Reg. Sci. 22(2), 65-80 (1992) |
| [22] | Friesz, T, Tobin, R, Cho, HJ, Mehta, N: Sensitivity analysis based heuristic algorithms for mathematical problems with variational inequality constraints. Math. Program. 48(2), 265-284 (1986) · Zbl 0723.90070 |
| [23] | LeBlanc, JL, Boyce, DE: A bilevel programming algorithm for exact solution of the network design with user optimal flows. Transp. Res., Part B, Methodol. 20(3), 259-265 (1986) · doi:10.1016/0191-2615(86)90021-4 |
| [24] | Lawphongpanich, S, Hearn, D: An MPEC approach to second-best toll pricing. Math. Program. 101(1), 33-55 (2004) · Zbl 1076.90009 · doi:10.1007/s10107-004-0536-5 |
| [25] | Sheffi, Y: Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods. Prentice Hall, Englewood Cliffs (1985) |
| [26] | Patriksson, M: The Traffic Assignment Problem: Models and Methods. VSP, Utrecht (1994) · Zbl 0828.90127 |
| [27] | Aarts, EH, Korst, JH: Simulated Annealing and Boltzmann Machines. Wiley, Chichester (1988) |
| [28] | Yin, Y: Genetic algorithm based approach for bi-level programming models. J. Transp. Eng. 126(2), 115-120 (2000) · doi:10.1061/(ASCE)0733-947X(2000)126:2(115) |
| [29] | Doringo, M, Stutzle, T: Ant Colony Optimization. MIT Press, Cambridge (2004) · Zbl 1092.90066 · doi:10.1007/b99492 |
| [30] | Chiou, S.; Griffths, JD (ed.), Bilevel formulation for equilibrium traffic flow and signal settings, 59-68 (1998), Amsterdam |
| [31] | Verhoef, ET: Second-best congestion pricing in general networks. Heuristic algorithm for finding second best optimal toll levels and toll points. Transp. Res., Part B, Methodol. 36(8), 707-729 (2002) · doi:10.1016/S0191-2615(01)00025-X |
| [32] | Shepherd, SP, Sumalee, A: A genetic based algorithm based approach to optimal toll level and location problems. Netw. Spat. Econ. 4(2), 161-179 (2004) · Zbl 1079.90082 · doi:10.1023/B:NETS.0000027771.13826.3a |
| [33] | Zhang, L, Sun, J: A dual based heuristic for optimal cordon pricing design. J. Transp. Eng. 139(11), 1105-1116 (2013) · doi:10.1061/(ASCE)TE.1943-5436.0000591 |
| [34] | Bell, MGH, Iida, Y: Transportation Network Analysis. Wiley, Chichester (1997) · doi:10.1002/9781118903032 |
| [35] | Luo, ZQ, Pang, JS, Ralph, D: Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge (1996) · Zbl 0898.90006 · doi:10.1017/CBO9780511983658 |
| [36] | Facchinei, F, Jiang, H, Qi, L: A smoothing method for mathematical programs with equilibrium constraints. Math. Program. 85, 107-134 (1999) · Zbl 0959.65079 · doi:10.1007/s101070050048 |
| [37] | Fukushima, M.; Pang, JS; Théra, M. (ed.); Tichatschke, R. (ed.), Convergence of a smoothing continuation method for mathematical problems with complementarity constraints, No. 477, 105-116 (1999), Berlin · doi:10.1007/978-3-642-45780-7_7 |
| [38] | Scholtes, S: Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim. 11, 918-936 (2001) · Zbl 1010.90086 · doi:10.1137/S1052623499361233 |
| [39] | Lin, GH, Fukushima, M: A modified relaxation scheme for mathematical programs with complementarity constraints. Ann. Oper. Res. 133, 63-84 (2005) · Zbl 1119.90058 · doi:10.1007/s10479-004-5024-z |
| [40] | Rockafellar, RT, Wets, RJB: Variational Analysis. Springer, New York (1998) · Zbl 0888.49001 · doi:10.1007/978-3-642-02431-3 |
| [41] | Braess, D, Nagurney, A, Wakolbinger, T: On a paradox of traffic planning. Transp. Sci. 39(4), 446-450 (2005) · doi:10.1287/trsc.1050.0127 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
