An effective bilevel programming approach for the evasive flow capturing location problem. (English) Zbl 1514.90152

Summary: This paper addresses the problem of locating weigh-in-motion (WIM) sensors on a road transportation network to effectively detect and intercept overloaded trucks assuming that truckers quickly find out the locations of WIM facilities, and make an attempt to avoid them by deviating from their predefined shortest paths. We formulate the problem as a bi-level programming (BLP) model and propose two approaches to find its optimal solution: The first approach utilizes the Karush-Kuhn-Tucker (KKT) conditions to provide a single-level reformulation of the BLP model. However, the second one is an exact decomposition-based algorithm that is superior to the KKT-based reformulation in terms of the computational time. The algorithm starts with a relaxed version of the BLP model and adds a family of cuts on the fly, the optimum is obtained within a few iterations. The idea behind our cut generation is novel and it is based on the knowledge of the underlying problem structure. Computational experiments on some randomly generated instances confirm the efficiency of the algorithm.


90B80 Discrete location and assignment
90B06 Transportation, logistics and supply chain management
90C35 Programming involving graphs or networks


Full Text: DOI


[1] Algadhi, Sah, Optimizing truck weigh stations’ locations on the highway network of Saudi Arabia, King Saud Univ, 22, 1-19 (2002)
[2] Ban, X.; Liu, Hx, A link-node discrete-time dynamic second best toll pricing model with a relaxation solution algorithm, Network Spatial Econ, 9, 243-267 (2009) · Zbl 1170.90321 · doi:10.1007/s11067-009-9100-4
[3] Bard, Jf; Moore, Jt, A branch and bound algorithm for the bilevel programming problem, SIAM J Sci Stat Comput, 11, 2, 281-292 (1990) · Zbl 0702.65060 · doi:10.1137/0911017
[4] Bard, Jf; Moore, Jt, An algorithm for the discrete bilevel programming problem, Nav Res Logist, 39, 3, 419-435 (1992) · Zbl 0751.90111 · doi:10.1002/1520-6750(199204)39:3<419::AID-NAV3220390310>3.0.CO;2-C
[5] Bisschop J (2012) AIMMS-Optimization modeling. Paragon Decision Technology, Harlem. http://www.aimms.com
[6] Boccia, M.; Sforza, A.; Sterle, C., Flow intercepting facility location: problems, models and heuristics, J Math Model Algorith, 8, 1, 35-79 (2009) · Zbl 1178.90215 · doi:10.1007/s10852-008-9098-5
[7] Colson, P.; 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
[8] Cottrell Jr BH (1992) The avoidance of weigh stations in Virginia by overweight trucks. Technical report. Virginia Transportation Research Council
[9] Dempe, S., Foundations of bilevel programming (2002), Dordrecht: Springer, Dordrecht · Zbl 1038.90097
[10] Farvaresh, H.; Sepehri, Mm, A branch and bound algorithm for bi-level discrete network design problem, Network Spatial Econ, 13, 1, 67-106 (2013) · Zbl 1332.90351 · doi:10.1007/s11067-012-9173-3
[11] Hansen, P.; Jaumard, B.; Savard, G., New branch-and-bound rules for linear bilevel programming, SIAM J Sci Stat Comput, 13, 5, 1194-1217 (1992) · Zbl 0760.65063 · doi:10.1137/0913069
[12] ILOG (2011) ILOG CPLEX 12.4 User’s manual. http://www.ilog.com/products/cplex
[13] Israeli, E.; Wood, Rk, Shortest-path network interdiction, Networks, 40, 2, 97-111 (2002) · Zbl 1027.90106 · doi:10.1002/net.10039
[14] Jacob, B.; La Beaumelle, Vf, Improving truck safety: potential of weigh-in-motion technology, IATSS Res, 34, 1, 9-15 (2010) · doi:10.1016/j.iatssr.2010.06.003
[15] Jeroslow, Rg, The polynomial hierarchy and a simple model for competitive analysis, Math Program, 32, 2, 146-164 (1985) · Zbl 0588.90053 · doi:10.1007/BF01586088
[16] Lin, Dy; Karoonsoontawong, A.; Waller, St, A Dantzig-Wolfe decomposition based heuristic scheme for bi-level dynamic network design problem, Network Spatial Econ, 11, 1, 101-126 (2011) · Zbl 1213.90254 · doi:10.1007/s11067-008-9093-4
[17] Lu, J.; Han, J.; Hu, Y.; Zhang, G., Multilevel decision-making: a survey, Inf Sci, 346-347, 10, 463-487 (2016) · Zbl 1398.90077 · doi:10.1016/j.ins.2016.01.084
[18] Mahmoudabadi, A.; Seyedhosseini, Sm, Improving the efficiency of weigh in motion systems through optimized allocating truck checking oriented procedure, IATSS Res, 36, 2, 123-128 (2013) · doi:10.1016/j.iatssr.2012.08.002
[19] Marković, N.; Ryzhov, Io; Schonfeld, P., Evasive flow capture: optimal location of weigh-in-motion systems, tollbooths, and security checkpoints, Networks, 65, 1, 22-42 (2015) · Zbl 1390.90373 · doi:10.1002/net.21581
[20] Marković, N.; Ryzhov, Io; Schonfeld, P., Evasive flow capture: a multi-period stochastic facility location problem with independent demand, Eur J Oper Res, 257, 687-703 (2017) · Zbl 1394.90392 · doi:10.1016/j.ejor.2016.08.020
[21] Rahmani, A.; Mirhassani, Sa, Lagrangean relaxation-based algorithm for bi-level problems, Opt Methods Softw, 30, 1-14 (2015) · Zbl 1325.90068 · doi:10.1080/10556788.2014.885519
[22] Sadeghi, S.; Seifi, A.; Azizi, E., Trilevel shortest path network interdiction with partial fortification, Comput Ind Eng, 106, C, 400-411 (2017) · doi:10.1016/j.cie.2017.02.006
[23] Saharidis, Gk; Ierapetritou, Mg, Resolution method for mixed integer bi-level linear problems based on decomposition technique, J Glob Optim, 44, 1, 29-51 (2009) · Zbl 1172.90451 · doi:10.1007/s10898-008-9291-0
[24] Šelmić, M.; Bešinović, N.; Teodorović, D., Locating weigh-in-motion checkpoints in traffic networks using genetic algorithm, E-Soc J, 2, 1, 55-66 (2011)
[25] Shi, C.; Lu, J.; Zhang, G., An extended Kuhn-Tucker approach for linear bilevel programming, Appl Math Comput, 162, 1, 51-63 (2005) · Zbl 1090.90175
[26] Williams, Hp, Model building in mathematical programming (2013), London: Wiley, London · Zbl 1261.90003
[27] Yang, Jun; Zhang, Min; He, Bo; Yang, Chao, Bi-level programming model and hybrid genetic algorithm for flow interception problem with customer choice, Computers & Mathematics with Applications, 57, 11-12, 1985-1994 (2009) · Zbl 1186.90107 · doi:10.1016/j.camwa.2008.10.035
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.