×

A heuristic method for the minimum toll booth problem. (English) Zbl 1206.90172

Summary: This paper addresses the toll pricing problem in which the objective is to minimize the number of required toll facilities in a traffic network. The problem is shown to be NP-hard. To obtain a solution in a reasonable time, an effective metaheuristic algorithm is developed. The algorithm uses a local search technique in which the neighborhood function employs the dynamic slope scaling procedure to deal with the fixed charge nature of the objective function. Numerical results from 50 randomly generated and three real networks are reported.

MSC:

90C30 Nonlinear programming
90B20 Traffic problems in operations research
90C59 Approximation methods and heuristics in mathematical programming

Software:

GAMS; CPLEX
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahuja R.K., Magnanti T.L., Orlin J.B.: Network Flows, Theory, Algorithm and Applications. Prentice Hall, Upper Saddle River (1993) · Zbl 1201.90001
[2] Bai L., Hearn D.W., Lawphongpanich S.: Decomposition techniques for the minimum toll revenue problem. Networks 44(2), 142–150 (2004) · Zbl 1055.90009 · doi:10.1002/net.20024
[3] Bai L., Rubin P.A.: Combinatorial benders cuts for the minimum tollbooth problem. Oper. Res. 57(6), 1510–1522 (2009) · Zbl 1226.90122 · doi:10.1287/opre.1090.0694
[4] Bazaraa M.S., Jarvis J.J., Sherali H.D.: Linear Programming and Network Flows. Wiley, Hoboken (1990) · Zbl 0722.90042
[5] Beckmann M., McGuire C., Winston C.: Studies in the Economics of Transportation. Yale University Press, New Haven (1956)
[6] Costa M.C., Létocart L., Roupin F.: Minimal multicut and maximal integer multiflow: a survey. Eur. J. Oper. Res. 126, 55–69 (2005) · Zbl 1132.90306 · doi:10.1016/j.ejor.2003.10.037
[7] CPLEX: CPLEX Optimization Inc., Incline Village (1996)
[8] DeCorla-Souza, P.: Report to the transportation research board joint subcommittee on pricing. In: 82nd Annual Transportation Research Board Meeting, Washington (2005)
[9] Florian M., Guélat J., Spiess H.: An efficient implementation of the PARTAN variant of the linear approximation method for the network equilibrium problem. Networks 17, 319–339 (1987) · Zbl 0647.90098 · doi:10.1002/net.3230170307
[10] Florian M., Hearn D.W.: Network equilibrium models and algorithms. In: Ball, M.O., Magnanti, T.L., Monma, C.L., Nemhauser, G.L. (eds) Handbooks in Operations Research and Management Science, vol. 8: Network Routing, pp. 485–550. North-Holland, New York (1995)
[11] GAMS: General Algebraic Modeling System. GAMS Development Corporation (1995)
[12] Garg, N., Vazirani, V., Yannakakis, M.: Multiway cuts in directed and node weighted graphs. In: Proceedings for the 21st International Colloquium on Automata, Languages, and Programming, pp. 487–498, Jerusalem (1994) · Zbl 1068.68178
[13] Hearn D.W., Lawphongpanich S., Ventura J.: Restricted simplicial decomposition: computation and xtensions. Math. Program. Study 31, 99–118 (1995) · Zbl 0636.90027
[14] Hearn D.W., Ramana M.: Solving congestion toll pricing models. In: Marcotte, P., Nguyen, S. (eds) Equilibrium and Advanced Transportation Modeling, pp. 109–124. Kluwer, Norwell (1998) · Zbl 1067.90508
[15] Kim D., Pardalos P.M.: A solution approach to the fixed charge network flow problem using a dynamic slope scaling procedure. Oper. Res. Lett. 24(4), 195–203 (1999) · Zbl 0947.90017 · doi:10.1016/S0167-6377(99)00004-8
[16] Lawphongpanich S.: Dynamic slope scaling procedure and Lagrangian relaxation with subproblem approximation. J. Glob. Optim. 35, 121–130 (2006) · Zbl 1103.90093 · doi:10.1007/s10898-005-1383-5
[17] LeBlanc L.J., Morlok E.K., Pierskalla W.P.: An efficient approach to solving the road network equilibrium traffic assignment problem. Transp. Res. 9, 309–318 (1975) · doi:10.1016/0041-1647(75)90030-1
[18] Mineta N.Y.: National Strategy to Reduce Congestion on America’s Transportation Network. U.S. Department of Transportation, Washington (2006)
[19] Nahapetyan A., Pardalos P.M.: Adaptive dynamic cost updating procedure for solving fixed charge network flow problems. Comput. Optim. Appl. 39(1), 37–50 (2008) · Zbl 1147.90310 · doi:10.1007/s10589-007-9060-x
[20] Pigou A.C.: The Economics of Welfare. MacMillan, New York (1920)
[21] Schrank, D., Lomax, T.: Urban Mobility Report 2007. Texas Transportation Institute, September 2007. http://mobility.tamu.edu . Accessed 1 May 2008
[22] Todd, J.: Duke Student Math Aims to Alleviate Tollbooth Lines. Duke University News and Communications, June 2005. http://www.dukenews.duke.edu/2005/06/tollbooths.html . Accessed 1 May 2008
[23] Verhoef E.: Second-best congestion pricing in general networks: heuristic algorithms for finding second-best optimal toll levels and toll points. Transp. Res. B. 36, 707–729 (2002) · doi:10.1016/S0191-2615(01)00025-X
[24] Yang H., Zhang X.: Optimal toll design in second-best link-based congestion pricing. J. Transp. Res. Board Transp. Res. Rec. 1857, 85–92 (2003) · doi:10.3141/1857-10
[25] Yildirim M.B., Hearn D.W.: A toll pricing framework for traffic assignment problems with elastic demand. In: Gendreau, M., Marcotte, P. (eds) Current Trends in Transportation and Network Analysis: Papers in honor of Michael Florian, pp. 135–145. Kluwer, Norwell (2002) · Zbl 1048.90067
[26] Yildirim M.B., Hearn D.W.: A first best toll pricing framework for variable demand traffic assignment problems. Transp. Res. B. 39, 659–678 (2005) · doi:10.1016/j.trb.2004.08.001
[27] Zhang X., Yang H.: The optimal cordon-based network congestion pricing problem. Transp. Res. B. 38, 517–537 (2004) · doi:10.1016/j.trb.2003.08.001
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.