One of the most important problems concerning the toll roads is the setting of an appropriate cost for traveling through private arcs of a transportation network. The purpose of this paper is to consider this problem by stating it as a bilevel programming (BLP) model. At the upper level, one has a public regulator or a private company that manages the toll roads seeking to increase its profits. At the lower level, several companies-users try to satisfy the existing demand for transportation of goods and/or passengers, and simultaneously, to select the routes so as to minimize their travel costs. In other words, what is sought is kind of a balance of costs that bring the highest profit to the regulating company (the upper level) and are still attractive enough to the users (the lower level).
With the aim of providing a solution to the BLP problem in question, a direct algorithm based on sensitivity analysis (SA) is proposed. In order to make it easier to move (if necessary) from a local maximum of the upper level objective function to another, the well-known “filled function (FF)” method is used.
The paper proposes and tests two versions of the heuristic algorithm to solve the toll optimization problem (TOP) based upon SA for linear programming (LP) problems. The algorithm makes use of an SA procedure for the LP problem at the lower level, as well as of the “filled” function technicalities in order to reach the global optimum when “jammed” at some local optimum. Numerical experiments with a series of small and medium dimension test problems show the proposed algorithm’s robustness and decent convergence characteristics.
Numerical experiments with a series of small- and medium dimension test problems show the proposed algorithm’s robustness and reasonable convergence characteristics. In particular, while ceding in efficiency to other algorithms when solving small problems, the proposed method wins in the case of medium (higher dimensional) test models. Because of that, one can expect a serious real-life impact on the TOP when the proposed methods and/or their improved versions are developed further to be applicable in practice in the near future.
The proposed algorithms are original and perform well when solving small and medium test numerical problems. The proposed heuristics aim at filling in a gap in a series of numerical approaches to the solution of TOP problem listed in the Introduction. To the authors knowledge, no systematic attempts to apply the SA tools to the toll assigned problem have been recently made. Moreover, the combination of these powerful tools with the “FFs” techniques brings forward some new global optimization ideas. Exactly these features build up the knowledge this specific paper offers in relation to previous relevant works.
The research activity of the Vyacheslav V. Kalashnikov and the Roberto Carlos Herrera Maldonado was financially supported by the R & D Department (Grupo de Enfoque de Investigación) of the Tecnológico de Monterrey (ITESM, Campus Monterrey), and by the SEP-CONACYT project CB-2013-01-221676, Mexico. The work of the José-Fernando Camacho-Vallejo was supported by the Universidad Autónoma de Nuevo León (UANL) within the Support Program for Scientific Research and Technology (PAICyT) with the Project CE407-10, and by the research group “Programación Binivel y Estadística Aplicada” of the Secretary of Public Education (SEP) within the Strengthening of Academics Groups Program with the project PROMEP/103.5/12/4953. The research activity of the fourth author was financially supported by the National Council of Science and Technology (CONACyT) of Mexico as part of the project CB-2009-01-127691, and by the PAICYT project No. CE250-09. The authors would also like to express their profound gratitude to the anonymous referees whose valuable comments and suggestions have helped them greatly improve the presentation.
Kalashnikov, V., Herrera Maldonado, R., Camacho-Vallejo, J. and Kalashnykova, N. (2016), "A heuristic algorithm solving bilevel toll optimization problems", International Journal of Logistics Management, The, Vol. 27 No. 1, pp. 31-51. https://doi.org/10.1108/IJLM-06-2013-0072Download as .RIS
Emerald Group Publishing Limited
Copyright © 2016, Emerald Group Publishing Limited