Volume 22, No 3, 2015, P. 36-54
UDC 519.87+519.854
Kochetov Yu. A., Panin A. A., Plyasunov A. V.
Comparison of metaheuristics for the bilevel facility location and mill pricing problem
Abstract:
We consider the bilevel nonlinear facility location and pricing problem.We assume that facilities can charge different prices and the objective is to maximize the total revenue. It is known that the problem is NP-hard in the strong sense even for the given facility location. We show that it belongs to class Poly-APX. We present two hybrid algorithms based on local search: variable neighborhood descent and genetic local search. Being compared with previously known algorithms and CPLEX software, these algorithms show their competitiveness. Computational experiments were conducted on instances from the benchmark library «Discrete Location Problems».
Tab. 2, bibliogr. 30.
Keywords: bilevel problem, location, pricing, VND metaheuristic, genetic local search metaheuristics, two level metaheuristics.
DOI: 10.17377/daio.2015.22.480
Yury A. Kochetov 1,2
Artem A. Panin 1
Alexander V. Plyasunov 1,2
1. Sobolev Institute of Mathematics
4 Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: jkochet@math.nsc.ru, arteam1897@gmail.com, apljas@math.nsc.ru
Received 14 March 2015
Revised 6 April 2015
References
[1] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979. Translated under the title Vychislitel’nye mashiny i trudnoreshaemye zadachi, Mir, Moscow, 1982.[2] I. A. Davydov, Yu. A. Kochetov, N. Mladenović, D. Urošević, Fast metaheuristics for the discrete (r|p)-centroid problem, Avtom. Telemekh., No. 4, 106–119, 2014. Translated in Autom. Remote Control, 75, No. 4, 677–687, 2014.
[3] V. T. Dement’ev and Yu. V. Shamardin, The problem of price selection for production under the condition of obligatory satisfaction of demand, Diskretn. Anal. Issled. Oper., Ser. 2, 9, No. 2, 31–40, 2002.
[4] Yu. A. Kochetov and A. V. Plyasunov, A polynomially solvable class of two-level linear programming problems, Diskretn. Anal. Issled. Oper., Ser. 2, 1, No. 2, 23–33, 1997.
[5] Yu. A. Kochetov and A. V. Plyasunov, Genetic local search the graph partitioning problem under cardinality constraints, Zh. Vychisl. Mat. Mat. Fiz., 52, No. 1, 164–176, 2012. Translated in Comput. Math. Math. Phys., 52, No. 1, 157–167, 2012.
[6] A. A. Panin and A. V. Plyasunov, On complexity of the bilevel location and pricing problems, Diskretn. Anal. Issled. Oper., 21, No. 5, 54–66, 2014. Translated in J. Appl. Ind. Math., 8, No. 4, 574–581, 2014.
[7] A. V. Plyasunov and A. A. Panin, The pricing problem. Part I: Exact and approximate algorithms, Diskretn. Anal. Issled. Oper., 19, No. 5, 83–100, 2012. Translated in J. Appl. Ind. Math., 7, No. 2, 241–251, 2013.
[8] R. Aboolian, O. Berman, and D. Krass, Competitive facility location model with concave demand, Eur. J. Oper. Res., 181, No. 2, 598–619, 2007.
[9] R. Aboolian, O. Berman, and D. Krass, Optimizing pricing and location decisions for competitive service facilities charging uniform price, J. Oper. Res. Soc., 59, No. 11, 1506–1519, 2008.
[10] N. Adler and K. Smilowitz, Hub-and-spoke network alliances and mergers: Price-location competition in the airline industry, Transp. Res., Part B, 41, No. 4, 394–409, 2007.
[11] M. J. Attallah, ed., Algorithms and Theory of Computation Handbook, CRC Press, Boca Raton, 1998.
[12] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti- Spaccamela, and M. Protasi, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer-Verlag, Berlin, 1999.
[13] M. Bouhtou, A. Grigoriev, S. van Hoesel, A. F. van der Kraaij, F. C. R. Spieksma, and M. Uetz, Pricing bridges to cross a river, Naval Res. Logist., 54, No. 4, 411–420, 2007.
[14] A. Dasci and G. Laporte, Location and pricing decisions of a multistore monopoly in a spatial market, J. Reg. Sci., 44, No. 3, 489–515, 2004.
[15] S. Dempe, Foundations of Bilevel Programming, Kluwer Acad. Publ., Dordrecht, 2002.
[16] Z. Diakova and Yu. A. Kochetov, A double VNS heuristic for the facility location and pricing problem, Electron. Notes Discrete Math., 39, No. 4, 29–34, 2012.
[17] Z. Drezner, ed., Facility Location: A Survey of Applications and Methods, Springer-Verlag, New York, 1995.
[18] T. Drezner and H. A. Eiselt, Consumers in competitive location models, in Z. Drezner and H. W. Hamacher, eds., Facility Location: Applications and Theory, pp. 151–178, Springer-Verlag, Berlin, 2004.
[19] H. A. Eiselt, G. Laporte, and J.-F. Thisse, Competitive location models: A framework and bibliography, Transp. Sci., 27, No. 1, 44–54, 1993.
[20] H. A. Eiselt and V. Marianov, Foundations of Location Analysis, Springer, New York, 2011 (Int. Ser. Oper. Res. Manag. Sci.; Vol. 155).
[21] A. Grigoriev, J. van Loon, M. Sviridenko, M. Uetz, and T. Vredeveld, Optimal bundle pricing with monotonicity constraint, Oper. Res. Lett., 36, No. 5, 609–614, 2008.
[22] P. Hanjoul, P. Hansen, D. Peeters, and J.-F. Thisse, Uncapacitated plant location under alternative spatial price policies, Manag. Sci., 36, No. 1, 41–57, 1990.
[23] P. Hansen and N. Mladenović, Variable neighborhood search, Eur. J. Oper. Res., 130, No. 3, 449–467, 2001.
[24] H. Hotelling, Stability in competition, Econ. J., 39, No. 153, 41–57, 1929.
[25] Yu. A. Kochetov, E. V. Alekseeva, T. V. Levanova, and M. A. Loresh, Large neighborhood local search for the p-median problem, Yugosl. J. Oper. Res., 15, No. 1, 53–63, 2005.
[26] Ph. J. Lederer and J.-F. Thisse, Competitive location on network under delivered pricing, Oper. Res. Lett., 9, No. 3, 147–153, 1990.
[27] E. W. Leggett Jr. and D. J. Moore, Optimization problems and the polynomial hierarchy, Theor. Comput. Sci., 15, No. 3, 279–289, 1981.
[28] A. Lüer-Villagra and V. Marianov, A competitive hub location and pricing problem, Eur. J. Oper. Res., 231, No. 3, 734–744, 2013.
[29] D. Serra and Ch. ReVelle, Competitive locations and pricing on networks, Geogr. Anal., 31, No. 2, 109–129, 1999.
[30] X. Vives, Oligopoly Pricing: Old Ideas and New Tools, MIT Press, Cambridge, 2001.
