Consider a three-level non-capacitated location/pricing problem: a firm first decides which facilities to open, out of a finite set of candidate sites, and sets service prices with the aim of revenue maximization; then a second firm makes the same decisions after checking competing offers; finally, customers make individual decisions trying to minimize costs that include both purchase and transportation. A restricted two-level problem can be defined to model an optimal reaction of the second firm to known decision of the first. For non-metric costs, the two-level problem corresponds to Envy-free Pricing or to a special Network Pricing problem, and is APX-complete even if facilities can be opened at no fixed cost. Our focus is on the metric 1-dimensional case, a model where customers are distributed on a main communica- tion road and transportation cost is proportional to distance. We describe polynomial-time algorithms that solve two- and three-level problems with opening costs and single 1st level facility. Quite surprisingly, however, even the two-level problem with no opening costs becomes N P-hard when two 1st level facilities are considered.

Competitive location and pricing on a line with metric transportation costs

Arbib C.
;
PINAR, MUSTAFA CELEBI;TONELLI, MASSIMO
2019-01-01

Abstract

Consider a three-level non-capacitated location/pricing problem: a firm first decides which facilities to open, out of a finite set of candidate sites, and sets service prices with the aim of revenue maximization; then a second firm makes the same decisions after checking competing offers; finally, customers make individual decisions trying to minimize costs that include both purchase and transportation. A restricted two-level problem can be defined to model an optimal reaction of the second firm to known decision of the first. For non-metric costs, the two-level problem corresponds to Envy-free Pricing or to a special Network Pricing problem, and is APX-complete even if facilities can be opened at no fixed cost. Our focus is on the metric 1-dimensional case, a model where customers are distributed on a main communica- tion road and transportation cost is proportional to distance. We describe polynomial-time algorithms that solve two- and three-level problems with opening costs and single 1st level facility. Quite surprisingly, however, even the two-level problem with no opening costs becomes N P-hard when two 1st level facilities are considered.
File in questo prodotto:
File Dimensione Formato  
EOR_16017.pdf

solo utenti autorizzati

Descrizione: Articolo principale
Tipologia: Documento in Pre-print
Licenza: Creative commons
Dimensione 1.16 MB
Formato Adobe PDF
1.16 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11697/138649
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 13
social impact