Comparison of metaheuristics for the bilevel facility location and mill pricing problem

Yu. A. Kochetov ; A. A. Panin ; A. V. Plyasunov

Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 3, pp. 36-54.

Résumé

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.

Détail

Keywords: bilevel problem, location, pricing, VND metaheuristic, genetic local search metaheuristics, two level metaheuristics.

Bibliographie

[1] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, 1979 | MR | MR | Zbl

[2] I. A. Davydov, Yu. A. Kochetov, N. Mladenović, D. Urošević, “Fast metaheuristics for the discrete $(r|p)$-centroid problem”, Autom. Remote Control, 75:4 (2014), 677–687 | DOI | MR | Zbl

[3] V. T. Dement'ev, 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:2 (2002), 31–40 | MR | Zbl

[4] Yu. A. Kochetov, A. V. Plyasunov, “A polynomially solvable class of two-level linear programming problems”, Diskretn. Anal. Issled. Oper., Ser. 2, 4:2 (1997), 23–33 | MR

[5] Yu. A. Kochetov, A. V. Plyasunov, “Genetic local search the graph partitioning problem under cardinality constraints”, Comput. Math. Math. Phys., 52:1 (2012), 157–167 | DOI | MR | Zbl

[6] A. A. Panin, A. V. Plyasunov, “On complexity of the bilevel location and pricing problems”, J. Appl. Ind. Math., 8:4 (2014), 574–581 | DOI | MR | Zbl

[7] A. V. Plyasunov, A. A. Panin, “The pricing problem. Part I: Exact and approximate algorithms”, J. Appl. Ind. Math., 7:2 (2013), 241–251 | DOI | MR

[8] Aboolian R., Berman O., Krass D., “Competitive facility location model with concave demand”, Eur. J. Oper. Res., 181 (2007), 598–619 | DOI | MR | Zbl

[9] Aboolian R., Berman O., Krass D., “Optimizing pricing and location decisions for competitive service facilities charging uniform price”, J. Oper. Res. Soc., 59 (2008), 1506–1519 | DOI | Zbl

[10] Adler N., Smilowitz K., “Hub-and-spoke network alliances and mergers: price-location competition in the airline industry”, Transp. Res. Part B, 41 (2007), 394–409 | DOI

[11] Attallah M., Algorithms and theory of computation handbook, CRC Press LLC, Boca Raton, 1998, 1312 pp. | MR

[12] Ausiello G., Crescenzi P., Gambosi G., Kann V., Marchetti-Spaccamela A., Protasi M., Complexity and approximation: combinatorial optimization problems and their aproximability properties, Springer-Verl., Berlin, 1999, 524 pp. | MR

[13] Bouhtou M., Grigoriev A., Van Der Kraaij A. F., Van Hoesel S., Spieksma F., Uetz M., “Pricing bridges to cross a river”, Nav. Res. Logist., 54:4 (2007), 411–420 | DOI | MR | Zbl

[14] Dasci A., Laporte G., “Location and pricing decisions of a multistore monopoly in a spatial market”, J. Region Sci., 44 (2004), 489–515 | DOI

[15] Dempe S., Foundations of bilevel programming, Kluwer Acad. Publ., Dordrecht, 2002, 320 pp. | MR | Zbl

[16] Diakova Z., Kochetov Yu., “A double VNS heuristic for the facility location and pricing problem”, Electron. Notes Discrete Math., 39 (2012), 29–34 | DOI | MR | Zbl

[17] Drezner Z., Facility location: A survey of applications and methods, Springer-Verl., New York, 1995, 572 pp. | MR

[18] Drezner T., Eiselt H. A., “Consumers in competitive location models”, Facility location: Applications and theory, Springer-Verl., Berlin, 2004, 151–178 | MR

[19] Eiselt H. A., Laporte G., Thisse J.-F., “Competitive location models: A framework and bibliography”, Transp. Sci., 27:1 (1993), 44–54 | DOI | MR | Zbl

[20] Eiselt H. A., Marianov V., Foundations of location analysis, Int. Ser. Oper. Res. Manag. Sci., 155, Springer-Verl., New York, 2011, 510 pp. | DOI | MR

[21] Grigoriev A., van Loon J., Sviridenko M., Uetz M., Vredeveld T., “Optimal bundle pricing with monotonicity constraint”, Oper. Res. Lett., 36:5 (2008), 609–614 | DOI | MR | Zbl

[22] Hanjoul P., Hansen P., Peeters D., Thisse J.-F., “Uncapacitated plant location under alternative spatial price policies”, Manage Sci., 36:1 (1990), 41–57 | DOI | MR | Zbl

[23] Hansen P., Mladenovic N., “Variable neighborhood search”, Eur. J. Oper. Res., 130:3 (2001), 449–467 | DOI | MR | Zbl

[24] Hotelling H., “Stability in competition”, Econom. J., 39:153 (1929), 41–57

[25] Kochetov Yu., Alekseeva E., Levanova T., Loresh M., “Large neighborhood local search for the $p$-median problem”, Yugosl. J. Oper. Res., 15:1 (2005), 53–63 | DOI | MR | Zbl

[26] Lederes Ph. J., Thisse J.-F., “Competitive location on network under delivered pricing”, Oper. Res. Lett., 9:3 (1990), 147–154 | DOI | MR

[27] Leggett E. W., Moore D. J., “Optimization problems and the polynomial hierarchy”, Theor. Comput. Sci., 15:3 (1981), 279–289 | DOI | MR | Zbl

[28] Marianov V., Lüer-Villagra A., “A competitive hub location and pricing problem”, Eur. J. Oper. Res., 231:3 (2013), 734–744 | DOI | MR | Zbl

[29] Serra D., ReVelle Ch., “Competitive location and pricing on networks”, Geograph. Anal., 31:2 (1999), 109–129 | DOI | MR

[30] Vives X., Oligopoly pricing: old ideas and new tools, MIT Press, Cambridge, MA, 2001, 441 pp.