A Scatter Search Algorithm for Solving a Bilevel Optimization Model for Determining Highway Tolls

José Luis González Velarde; José Fernando Camacho Vallejo; Gabriel Pinto Serrano

Ayuda

A Scatter Search Algorithm for Solving a Bilevel Optimization Model for Determining Highway Tolls

José Luis González Velarde ^[1] ; José-Fernando Camacho-Vallejo ^[2] ; Gabriel Pinto Serrano ^[1]
1. [1] Instituto Tecnológico y de Estudios Superiores de Monterrey
  
  Instituto Tecnológico y de Estudios Superiores de Monterrey
  
  México
2. [2] Universidad Autónoma de Nuevo León
  
  Universidad Autónoma de Nuevo León
  
  México
Localización: Computación y Sistemas (CyS), ISSN 1405-5546, ISSN-e 2007-9737, Vol. 19, Nº. 1, 2015, págs. 5-16
Idioma: inglés
DOI: 10.13053/CyS-19-1-1916
Enlaces
- Texto completo
Resumen
- The problem of determining optimal tolls established on a subset of arcs in a multicommodity capacitated transportation network is presented. The problem is formulated as a bilevel optimization problem where the upper level consists of an administrator who establishes tolls in some arcs of a network, while the lower level is represented by a group of users who travel along the shortest paths with respect to the travel cost. The objective is not only to increase the tolls, but also to maintain an optimal flow on the arcs of the network in order to maximize the leader's profit. If the leader sets very high toll values, the followers will be discouraged from using the tolled arcs, so the profit obtained from that decision is not going to be convenient for the leader. A methodology to solve this problem using optimization software at the lower level and the metaheuristic Scatter Search at the upper level is proposed.
Referencias bibliográficas
- Button, K.. (2004). Road Pricing. Center for Transportation Policy Operations and Logistics. Fairfax.
- Mong-Sim, K.,Hong-Sun, W.. (2003). Ant colony optimization for routing and load-balancing: survey and new directions. IEEE Transactions on...
- Patriksson, M.. (1994). The Traffic Assignment Problem: Models and Methods. VSP International Science Publishers.
- Bergendor, P.,Hearn, D.,Ramana, M.. (1997). Congestion in Toll Pricing of Traffic Networks. Center for Applied Optimization. Gainesville^eFL...
- Cropper, M.,Oates, W.. (1992). Environmental economics: a survey. Journal of Economic Literature. 30. 675-740
- Button, K.. (2010). Transport Economics. MPG Books Group.
- Labbé, M.,Marcotte, P.,Savard, G.. (1998). A bilevel model of taxation and its application to optimal highway pricing. Management Science....
- Roch, S.,Savard, G.,Marcotte, P.. (2005). An approximation algorithm for Stackelberg network pricing. Networks. 46. 57-67
- Didi-Biha, M.,Marcotte, P.,Savard, G.. (2006). Optimization with Multivalued Mappings Theory: Theory, Applications and Algorithms. Springer....
- Kalashnikov, V.,Camacho, F.,Askin, R.,Kalashnikova, N.. (2010). Comparing various algorithms performance: application to bilevel toll setting...
- Brotcorne, L.,Cirinei, F.,Marcotte, P.,Savard, G.. (2012). A tabu search algorithm for the network pricing problem. Computers & Operations...
- Dimitriou, L.,Tsekeris, T.,Stathopoulos, A.. (2008). Applications of Evolutionary Computing. Springer.
- Laguna, M.,Martí, R.. (2003). Scatter Search: Methodology and Implementations. Kluwer Academic Publishers.
- Zadeh, N.. (1973). A bad network problem for the simplex method and other minimum cost flow algorithms. Mathematical Programming.
- Edmonds, K.. (1972). Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM. 19. 248-264
- Anandalingam, G.,Friesz, T.. (1992). Hierarchical optimization. Annals of Operations Research. 34. 1-11
- Bard, J.F.. (1998). Practical Bilevel Optimization. Kluwer Academic Publishers.
- Chandler, W.,Norton, R.. (1977). Multi-Level Programming and development policy. World Bank.
- Dempe, S.. (2003). Bilevel Programming: A survey. University Bergakademie. Freiberg.
- Colson, B.,Marcotte, P.,Savard, G.. (2007). An overview of bilevel optimization. Annals of Operations Research. 153. 235-256
- Calvete, H.I.,Galé, C.. (2010). A Multiobjective Bilevel Program for Production-Distribution Planning in a Supply Chain: Multiple Criteria...
- Candler, W.. (1988). A linear bilevel programming algorithm: A comment. Computers & Operations Research. 15. 297-298
- Clarke, P.,Westerberg, A.. (1988). A note on the optimality conditions for the bilevel programming problem. Naval Research Logistics Quarterly....
- Haurie, A.,Savard, G.,White, D.. (1990). A note on: an efficient point algorithm for a linear two-stage optimization problem. Operations Research....
- Marcotte, P.,Savard, G.. (1991). A note on the Pareto optimality of solutions to the linear bilevel programming problem. Computers & Operations...
- Glover, F.. (1998). Artificial Evolution: Third European Conference. Springer. Heidelberg.
- Martí, R.,Laguna, M.. (2003). Scatter Search: Basic Design and Advanced Strategies. Inteligencia Artificial, Revista Iberoamericana de Inteligencia...
- Moscato, P.. (2000). Handbook of Applied Optimization. Oxford University Press.
- Nelder, J.A.,Mead, R.. (1965). A simplex algorithm for function minimization. The Computer Journal. 7. 308-313
- González-Velarde, J.L.,Martí, R.. (2008). Adaptive memory programing for the robust capacitated international sourcing problem. Computers...
- González-Velarde, J.L.,Alvarez, A.M.,De Alba, K.. (2005). Grasp Embedded Scatter Search for the Multicommodity Capacitated Network Design...
- Camacho-Vallejo, J.F.,Cordero, A.E.,González-Ramírez, R.G.. (2014). Solving the Bilevel Facility Location Problem under Preferences by a Stackelberg...