1 Introduction

Nowadays, circular economy (CE) is an important and relevant topic (Geissdoerfer et al. 2017). CE dynamically develops due to a significant change in the world's perception of modern environmental problems such as excessive pollution or rapid climate change (Jammeli et al. 2021). Within European Union, the CE is realized through the circular economy package (CEP) (Hughes 2017), which is a CE initiative adopted by the European Commission. CEP sets up a series of milestones, which must be achieved in order to successfully embed CE principles into production cycles. One of the CEP goals lies in a decrease in the amount of utilizable solid waste that is being landfilled as well as in an increase in its material and energy recovery (Hughes 2017). Therefore, the concept of CE is closely connected to effective waste management, which devotes itself to monitoring and regulation of the waste collection, transportation, treatment, and disposal (Amasuono and Baird 2016). Whereas the recyclable waste fits perfectly into the design of CE closed production cycles, the non-recyclable fraction of municipal solid waste (MSW) cannot be utilized in the same way. However, the energy potential of non-recyclable waste can be restored through Waste-to-Energy (WtE) technology (Korhonen et al. 2018). It is expected that WtE plants will play an important role in waste treatment under CEP legislative changes (Mitropoulos et al. 2009). Whereas in the past, incineration of MSW has been a source of substantial pollution, nowadays, due to the continuous development of WtE technology, WtE plants can serve as an environmentally friendly source of energy (Yaman et al. 2020). In Pfadt-Trilling et al. (2021), the WtE environmental impact has been thoroughly studied. The research concluded that the WtE, as a combination of waste management practice and electricity sources, can provide climate change benefits. However, if it is considered a renewable energy source solely, it cannot compete with other sources regarding greenhouse gas emissions. On the other side, it is more stable than wind power or solar energy (Zhang et al. 2021). Thus, the embedment of the WtE plans into cities' smart-energy grids might help to increase the sustainable production of energy and solve the problem of overwhelming energy demand expected in the near future (Trachanas et al. 2020). Expectedly, the actual capacities of already existing waste treatment facilities can be insufficient for efficient waste energy recovery in the future. Therefore, new waste treatment facilities will be needed (Hrabec et al. 2020).

The placement and design of a new WtE plant require a thorough feasibility study of the planned investments based on a reasonable estimate of its potential gate fee. The paper deals with the problematics of the WtE plant's optimal gate-fee setting in a competitive environment under limited capacities. The established task comprehends two distinct steps:

  • A solution of the price-setting bilevel program with one WtE plant, maximizing its revenue on the upper level, and cooperating waste producers, minimizing their total costs on the lower level;

  • A determination of the Nash equilibrium (NE) of the price-setting normal-form game between WtE plants.

Formally, bilevel optimization is defined as a mathematical program with constraints containing another optimization problem. This framework involves convex, non-convex, and mixed-integer programming (MIP) and enables to model of hierarchical situations when the response of lower-level entities impacts the decisions of the upper-level authority. For more details on bilevel optimization, see (Dempe 2002). In order to solve the considered non-trivial instance of the bilevel optimization and to anticipate the optimal gate fee of the WtE plant, a novel heuristic algorithm has been proposed. Then, the equilibrium of gate fees was found using the best-response dynamics. The bilevel programming heuristic has been validated using artificially generated scenarios describing WM networks. The proposed methodology's complete potential has been demonstrated in an exemplary decision-making process problem. The problem describes the optimal capacity design of the newly planned WtE facility. The computational results for the considered real waste management network also highlight the functionality and time efficiency of the proposed heuristic algorithm, being the main methodological contribution of this work. The algorithm's speed is crucial since the search for equilibrium requires the solution of numerous bilevel problems in a reasonable time for each considered capacity design.

To summarize, this work presents comprehensive research on the bilevel programming and application of the developed approach to the exemplary problem motivated by the data obtained from the Ministry of the Environment of the Czech Republic. The results of this work can be used in solving further problems, such as the interaction between cities or route planning in waste management networks. The obtained information can also be used in strategic planning, forecasting of cash flow, and an overall analysis of the waste management network.

The remainder of this paper is organized as follows. Section 1.1 introduces the studied problem, whereas Sect. 1.2 provides its precise mathematical formulation. To provide a better image of the originality of the studied problem, a review of the current state-of-art on the price-setting problems is presented in Sect. 2. Section 2 also highlights currently existing research gaps and summarizes the contribution of this work. Section 3 focuses on developing a heuristic to solve the established problem. It also introduces an instance of bilevel programming that is closely related to the one considered in the paper and describes the algorithm employed to compute the NE between multiple WtE plants. Section 4 is focused on the validation of the proposed bilevel programming algorithm. The heuristic and best-response dynamics are then combined in Sect. 5, which consists of the exemplary case study and the discussion on the performance of the proposed algorithm on the realistic data.

1.1 Problem statement

The placement of a new WtE facility is strongly impacted by the existing infrastructure of the considered region and therefore does not suggest vast space for possible decisions. On the other side, the optimal capacity design brings numerous variants that should be assessed correctly. Such strategical decisions should be taken with the help of suitable decision-making methods. Moreover, it should be supported by a reliable analysis of the current waste management situation since an accurate estimate of potential capacity occupancy and realistic gate fee will make it possible to correctly anticipate a return on investment and the financial feasibility of the whole project. However, in most operational research models employed in waste management (Barbosa-Póvoa et al. 2018), gate fees are assumed to be external fixed parameters that have been set or optimized centrally. Such an assumption neglects individual behaviors of WtE plants management and cannot describe a real conflict of interest in a waste treatment market. Therefore, there is an open problem of efficient establishment of the gate fees, which will realistically reflect the waste management network setting.

The detailed formulation of the considered problem can be described as follows. Consider the already built waste management network. WtE plants with different capacities and waste producers (mainly cities or agglomerations) with different waste productions are presented in an area. Each WtE plant is interested in maximizing its income by setting the optimal gate fee, which will be sufficiently high or/and will attract the most waste producers. WtE plant income is presented as a product of its gate fee and the total amount of waste sent to this WtE plant by waste producers. The main assumption is that landfilling of utilizable waste is substantially limited, according to (Directive (EU) 2018/850). This fact forces waste producers to treat all produced non-recyclable waste using the services of WtE plants. Each waste producer's main interest is to reduce costs for waste treatment. These costs are represented as a product of the amount of waste sent to a particular WtE plant and the sum of gate fees and transportation costs. Another important assumption is that, whereas WtE plants located in an area are individually maximizing their income, waste producers are cooperatively minimizing their total waste treatment costs. The cooperating waste producers reflect the current trend of municipalities creating unions to lower waste treatment costs (Eryganov et al. 2020). The schematic explanation of the revenue maximization by a WtE plant is depicted in Fig. 1, where the entities' objectives are highlighted in bold, and their constraints are highlighted in italics. The exchange of decision variables is depicted using arrows.

Fig. 1
figure 1

WtE plant problem

Full size image

From Fig. 1, it can be seen that setting the optimal gate fee for a particular WtE plant corresponds to solving the bilevel optimization problem, with the WtE plant on the upper level of the hierarchy and waste producers as one entity on the lower level.

The conflict of WtE plants' interests will certainly occur since each plant will operate with its gate fee to obtain a greater part of the fixed total demand (total waste production of the whole region). Plants' capacities and relative locations of WtE plants and waste producers define the market power of WtE plants, i.e., how great a gate fee WtE plant can set without loss of a substantial part of demand. Anticipating the realistic gate fee means that the interest resides in finding some logical gate fee outcome, which will persist. This issue will be solved through game theory since this mathematical apparatus had been originally applied to provide a more realistic insight into market modeling (Migdalas 2002). It was decided to apply a non-cooperative approach to the price-setting problem; cooperation between WtE plants would mean the existence of illegal collusion about the gate fees level. Thus, the considered problem is a classical normal-form game, which is played on the upper-hierarchy level between WtE plants, where optimizing the payoff function of a player leads to a bilevel program. The well-known NE (Owen 2013) is assumed to be the searched stable gate fee outcome, such that none of the WtE plants would like to change their gate fee. Now, the mathematical formalization of the considered problem will be given.

1.2 Formalization of the studied problem

Let \(N=\{1,\dots ,n\}\) be a set of WtE plants \(; {w}_{1}^{\mathrm{c}},\dots ,{w}_{n}^{\mathrm{c}}\) denotes their capacities and \({C}_{1}^{g},\dots ,{C}_{n}^{g}\) denotes their strategy sets (sets of possible gate fees) with an element \({c}_{j}^{g}\in {C}_{j}^{g},j\in N\). The set of producers is \(M=\{1,\dots ,m\}\). Their waste productions are \({w}_{1}^{p},\dots ,{w}_{m}^{p}.\) Transportation costs are given by the matrix \(\left[{c}_{i,j}^{t}\right]\), where \({c}_{i,j}^{t}\) represents the cost of waste transportation from the producer \(i\in M\) to the plant \(j\in N\). In the following expressions \({x}_{i,j}\) denotes the amount of waste sent by the producer \(i\in M\) to the WtE plant \(j\in N\) in tonnes. For each producer \(j\in N,\) the payoff function \({\uppi }_{j}\) is defined as

$${\pi }_{j}\left({c}_{1}^{g},\dots ,{c}_{n}^{g}\right)= \sum\limits_{i\in M} {c}_{j}^{g}{x}_{i,j}^{*}$$
(1)

where \({x}_{i,j}^{*}\in \{{x}_{i,j}^{*}: i\in M,j\in N\},\) such that

$$\{{x}_{i,j}^{*}:i\in M,j\in N\}=\mathrm{arg}\underset{{x}_{i,j}:i\in M,j\in N}{\mathrm{min}}\sum\limits_{j\in N}\sum\limits_{i\in M}\left({c}_{i,j}^{t}+{c}_{j}^{g}\right){x}_{i,j}$$
(2)
$$s.t.\sum\limits_{i\in M}{x}_{i,j}\le {w}_{j}^{c}, \forall j\in N$$
(3)
$$\sum\limits_{j\in N}{x}_{i,j}={w}_{i}^{p}, \forall i\in M$$
(4)
$${x}_{i,j}\ge 0, \forall i \in M, \; \forall \; j\in N$$
(5)

This model has been originally presented by (Osicka 2016). The previous equations describe cooperative minimization of total costs by cities (2) and the fact that they have to dispose of all waste they produce (4) and cannot exceed the capacities of WtE plants (3). However, the solution \(\{{x}_{i,j}^{*}:i\in M,j\in N\}\) is not necessarily unique. Thus, a choosing rule which will work equivalently for all players should be established. In this paper, a risk-averse leader, who wants to create a financial cushion, is considered. Thus, the pessimistic approach in the choice of \(\{{x}_{i,j}^{*}:i\in M,j\in N\}\) will be employed (the worst possible waste distribution scenario for the WtE plant will be considered). By now, two of three necessary elements of the normal-form game (Owen 2013) of WtE plants have been established: the set of players \(N=\{1,\dots ,n\}\) and their payoff functions \({\pi }_{j}\left({c}_{1}^{g},\dots ,{c}_{n}^{g}\right),j\in N\) have been defined. To thoroughly study the properties of the problem, the whole set of non-negative reals will be considered as a strategy space of possible gate fees. Thus, the considered game can be represented as a triple \(G=\left(N,{\left({\pi }_{j},{C}_{j}^{g}\right)}_{j\in N}\right)\), where \({C}_{j}^{g}=\left[0,\infty \right),\forall j\in N.\)

Firstly, the \(\underset{{c}_{{j}^{\prime}}^{g}}{\mathrm{max}}{\pi }_{{j}^{\prime}}\) for an arbitrary \({\mathrm{j}}^{\prime}\in \mathrm{N}\) and for given \({\left({c}_{j}^{g}\right)}_{j\ne {j}^{\prime}}\) should be discussed and solved. This is an instance of the so-called bilevel bilinear problem, which will be further referred to as MRWTE \({j}^{\prime}\). One of the main complications of the presented framework is that MRWTE \({j}^{\prime}\) is an NP-hard problem. Moreover, it has been proven that even checking the optimality of the solution is also an NP-hard task (Brotcorne et al. 2008). Therefore, it is suitable to analyze already established approaches used in contemporary research, dealing with the problems of pricing and multilevel optimization. The literature review, presented in Sect. 2, should better explain the study's motivation and highlight its contribution to the problematics.

2 Literature review and contribution

The product's pricing has always been and is still the key question in economics, as it is one of the main aspects affecting a firm's revenue (Farm 2020). The problem of a firm that maximizes its revenue under the assumption that customers are maximizing their utility from the product (so-called Stackelberg pricing games) has been vastly studied in the literature. Van Hoesel (2008) confirmed the direct connection between the general Stackelberg pricing game and bilevel programming. This connection holds due to the hierarchical structure of pricing problems. In fact, van Hoesel (2008) has focused his study of pricing games on the network pricing problem (NPP), being an instance of the general taxation problem (GTP) proposed by Labbe et al. (1998) (further “toll-setting problem” will be used as an equivalent for NPP). In GTP, the leader imposes taxes on commodities transported through the abstract network by a follower to maximize profit, whereas the follower minimizes transporting costs. Indeed, numerous pricing problems correspond to the NPP. This is why it was decided to split the review of the current state-of-art into two parts: the first one is focused on the price-setting related problems presented in the literature, whereas the second part is devoted solely to the GTP and its instances.

To ensure high relevance of the performed review, the main interest has been focused on the recent review papers on bilevel optimization, from which articles focused on pricing and toll setting have been extracted. In particular, the survey of mixed-integer bilevel approaches by Kleinert et al. (2021), a general review on classical bilevel optimization with an emphasis on evolutionary approaches by Sinha et al. (2018), article on bilevel intermodal pricing by Tawfik and Limbourg (2015) and extensive review of pessimistic bilevel optimization approaches by Liu et al. (2018) have been considered. To complement found papers, the search in the Scopus and Web of Science databases using pairs (and triplets in case of numerous results) of the following keywords has been performed:

  • General taxation problem;

  • Highway network problem;

  • Price setting;

  • Price regulation;

  • Bilevel optimization;

  • Bilevel bilinear problem;

  • Stackelberg game.

Then, only relevant papers have been divided into two groups mentioned above and detailly reviewed. The results of the review of general pricing problems are presented in Table 1.

Table 1 Review of price-setting problems
Full size table

Now, the most important findings will be discussed. The problem's main feature is the limited capacities of WtE plants, which substantially complicates the solution. Only a few papers from Table 1 consider some analogy of these capacities. Anjost et al. (2021) studied the model where only part of the lower-level decision variables have an upper bound. Moreover, the integer nature of some variables has simplified single-level reformulation. The work of Fernandez-Blanco et al. (2016) also assumes analogical constraints. Still, the program formulation again contains integer variables, and the application's specifics enable convenient linearization of bilinear terms during reformulation into a single-level problem. Feng et al. (2020) also consider the analogy of capacitated arcs, but compared to cooperating waste producers considered in this paper, the authors have assumed equilibrium on the lower level, which enabled reformulation into a mixed-integer quadratically constrained program. Zheng et al. (2016) considered capacitated depots, but the capacity is given for each product separately, implying their mutual independence. Thus, the problem is directly analogical to MRWTE \({j}^{\prime}\) has not been studied in the considered papers. Another peculiar finding is that the pessimistic approach considered in this paper is enforced using a simple numerical trick, which has been applied by Besancon et al. (2020). It dwells in the addition of an artificial small constant, which makes the leader's services more expensive than other suppliers.

One of the most interesting papers is (Shioda et al. 2009), where the closely related problem of product line pricing is studied. Whereas it has an analogical structure (though formulated as a single-level problem), it differs in the following important assumptions:

  • The leader does not assume the limited production capacities of the competitors (analogy of capacity of other WtE plants), which leads to maximally risk-averse behavior;

  • The customers are not forced to buy products, whereas waste producers (in fact, customers of the WtE sector) have to treat all produced waste;

  • Integer nature of the customer-product relationship (each customer buys at most one product) simplifies the potential embedment of capacity constraints.

Moreover, under the assumptions of this work, the heuristic proposed by (Shioda et al. 2009) degenerates into an enumeration procedure.

Regarding the search for equilibrium between leaders, Myklebust et al. (2016) assumed the stationary prices of the competitors' products since changing competitors' prices would substantially complicate the problem. The same is valid for the work of Shioda et al. (2009). The problem of establishing the equilibrium between leaders has been considered only in one paper: Reisi et al. (2019) studied the version of the equilibrium problem with equilibrium constraints. However, this version has been simplified by an assumption that enabled a direct search for equilibria via backward induction. Thus, from the perspective of the upper-level normal-form game, the lack of related research is confirmed. Another paper on this topic (Eryganov et al. 2021) has considered applying best-response dynamics to discrete sets of possible gate fees. Compared to the original work (Osička 2016), the cardinality of the sets of possible gate fees for which equilibrium can be found was substantially enlarged. On the other side, the NP-hard problem of setting the optimal price between one WtE plant and all waste producers has been solved by a simple combinatorial approach through simple iteration over all possible strategies. However, such an approach does not reflect reality, where WtE plants can choose from the continuous sets of gate fees. Then, an achieved equilibrium might seem artificial because players were not allowed to play optimal strategy and arbitrarily change it. This is another reason why the solution of MRWTE \({j}^{\prime}\) is so important: it will enable us to consider continuous strategy spaces, find optima faster and better reflect reality.

The first part of the review confirmed the necessity to focus on the GTP: the majority of the papers from Table 1 mention NPP or GTP. For example, the envy-free pricing studied in (Fernandes et al. 2016) is solved with the help of the NPP. Now, the NPP as the most common instance of GTP will be shortly introduced. In NPP, an authority (leader) tolls a specified arc of a transportation network, while the remaining arcs bear only fixed costs and the users (followers) of the network travel on the shortest (minimum cost) path between their relative origins and destinations (Heilporn et al. 2009). The leader's objective function is neither continuous nor convex, but it is rather piecewise linear and lower-semicontinuous in a pessimistic case (Labbe et al. 1998). Hence, the optimal solution can be sufficiently approximated in the pessimistic case assuming certain revenue tolerance. Reformulation via KKT proposed by Labbe et al. (1998) contains nonlinear terms in objective function and constraints. However, the existence of capacities on the arcs substantially complicates the linearization of these terms. The review of papers focused on GTP is presented in Table 2.

Table 2 Review of toll-setting problems
Full size table

The work of Bouhtou et al. (2007) is similar to the studied problem but does not consider the main complication of our model: capacity constraints. Due to omitted capacities, the authors were able to find the optimal solution in polynomial time using the enumeration procedure. However, in the problem considered in this paper, the assumption of cooperating followers and capacitated arcs makes it hard to anticipate the behavior of followers and changes in waste flows. Table 2 shows that there are only two works with the same research subject: Kalashnikov et al. (2010) and Kalashnikov et al. (2016). Evolutionary approaches presented by (Wang et al. 2014) and (González Velarde et al. 2015) are out of the scope of this paper.

Kalashnikov et al. (2010) considered four different heuristic approaches for toll-setting problems with congestion (capacitated arcs). In particular, the penalization function approach, quasi-Newton method, sharpest ascent method, and direct search via the Nelder-Mead algorithm. These algorithms can handle the capacitated toll-setting problem: for example, for medium-sized problems, it takes from 7 to 15 min for these algorithms to find a solution. Compared to the papers mentioned above, MRWTE \({j}^{\prime}\) has a much simpler structure that should be exploited when computing optimum: it has only single tolled arc controlled by \({j}^{\prime}.\) However, there is no available data about the efficiency of the computation process of the algorithms mentioned above in the case of single tolled arc and numerous commodities.

Heilporn et al. (2009) focus on instances reflecting the structure of an actual tolled highway: the network is composed of a tolled path (the highway) and toll-free arcs linking the origins, and highway entrances, exits, and destinations. This problem is called the Highway Network Pricing problem (HNPP). It is assumed that all arcs controlled by an authority present a complete bipartite subgraph and for every commodity exists the toll-free path from its origin to its destination. The main distinction of HNPP from NPP, which makes it not a particular case of the NPP, but its variant, is the assumption that followers do not re-enter the highway. This is ensured via Triangle and Monotonicity inequalities. The existence of single tolled arc (one-arc highway) axiomatically fulfills these assumptions. These properties enabled Heilporn et al. (2009) to suggest a simple and efficient reformulation of the HNPP into MIP (solvable in polynomial time for a single tolled arc or a single commodity). These reformulations also enabled solving other pricing problems: it has been demonstrated that the envy-free pricing problem can be reduced to basic HNPP (Fernandes et al. 2016). Moreover, the equivalence between HNPP and the product line pricing problem (Shioda et al. 2009) has been shown by Heilporn et al. (2010). However, the main drawback of the work of Heilporn is unconstrained arcs in a network.

One of the main ideas implied by Kalashnikov et al. (2010) is that approximation of derivatives enables capturing the followers' behavior. Kalashnikov et al. (2016) have exploited the related idea of finding the maximum of the leader function via iterated sensitivity analysis performed on the lower-level linear program to find a suitable increase in the leader's function. This approach has been applied to indirectly model followers' behavior in the non-constrained and constrained arc cases (Kalashnikov et al. 2016).

Exactly the combination of the MIP reformulation for unconstrained cases proposed by Heilporn et al. (2009) and of the idea analogical to Kalashnikov et al. (2016) has inspired the developing new heuristic approach able to provide the near-optimal solution for MRWTE \({j}^{\prime}.\) Whereas in the latter work, the follower's behavior has been anticipated via small perturbations in flows, a completely new iterative solution approach is presented in this paper. It is suggested to completely neglect the idea of approximation of objective function derivatives. The new approach captures the followers' behavior via iterative update of their optimal flows after the solution of the risk-averse revenue maximization problem of the leader: the iterative adjustment of price on the upper level helps to estimate the actual solution of the lower level. The whole leader problem is formulated based on the MIP reformulation proposed by Heilporn et al. (2009) with novel additions, enabling the embedding of leader capacities constraints and new inequalities reflecting his ability to raise gate fees by neglecting some of the flows. The computational results presented in Sect. 4 prove that this simple iterative solution of the leader's MIP and followers' linear problem can lead to a sufficiently optimal solution time-efficiently. It is important to mention that this approach is designed exclusively for the case of the single tolled arc and numerous untolled arcs, where all arc has their pre-defined capacity.

Thus, the contribution of this paper can be summarized as follows:

  • Novel heuristic algorithm for solving constrained toll-setting problems with single tolled arc, based on iterative optimization of leader's function and update of followers' response;

  • Embedment of leader's capacity constraint and additional inequalities into MIP formulation of HNPP;

  • Application of best-response dynamics to WtE price-setting problem with continuous gate fee sets;

  • Validation of the proposed method based on the randomly generated scenarios and the exemplary problem case study with realistic data.

3 Methods

This section will be focused on an introduction of the HNPP formulations, the establishment of the relation between HNPP and MRWTE \({j}^{{{\prime}}}\), and a precise description of the proposed algorithm and commentary on it.

3.1 Highway network pricing

In HNPP, a multicommodity network is represented by a set of nodes \(\mathcal{N}\), a set of arcs \(\mathcal{A}\cup \mathcal{B}\) and a set of pairs \(\{\left({o}^{k},{d}^{k}\right):k\in \mathcal{K}\}\) for the commodities \(k\in \mathcal{K}\) associated with a demand \({\eta }^{k}\). For commodity \(k\in \mathcal{K}\) and tolled arc \(a\in \mathcal{A}\), \({c}_{a}^{k}\) denotes the cost of travel through the path \({o}^{k}\to t\left(a\right)\to h\left(a\right)\to {d}^{k}\) before imposing tolls, where \(t\left(a\right),h\left(a\right)\in \mathcal{N}\) are the entry (tail node of \(\mathrm{a}\)) and exit (head node of \(\mathrm{a}\)) of the highway, respectively (Heilporn et al. 2009). The corresponding flow variable is denoted by \({\widetilde{x}}_{a}^{k}\). The travel cost on the path \({o}^{k}\to {d}^{k}\) is denoted by \({c}_{od}^{k}\), corresponding to toll-free travel. The corresponding flow variable is \(\widetilde{\mathrm{y}}{}{}^{k}\). Variable \({t}_{a}\) denotes the toll imposed on an arc \(a\in \mathcal{A}\). Then, the HNPP can be formulated as HNPP1

$$\underset{t,x}{\mathrm{max}} \sum\limits_{k\in \mathcal{K}}\sum\limits_{\mathrm{a}\in \mathcal{A}}{\eta }^{k}{t}_{a}{x}_{a}^{k}$$
(6)
$$\text{s.t.} \, {t}_{a}\ge 0, \forall a\in \mathcal{A}$$
(7)
$$\left(x,y\right)\in \mathrm{arg}\underset{\widetilde{x},\widetilde{y}}{\mathrm{min }}\sum\limits_{k\in \mathcal{K}}\left(\sum\limits_{a\in \mathcal{A}}\left({c}_{a}^{k}+{t}_{a}\right){\widetilde{x}}_{a}^{k}+{c}_{od}^{k}\widetilde{\mathrm{y}}{}{}^{k}\right)$$
(8)
$$\text{s.t.} \, \sum\limits_{a\in \mathcal{A}}{\widetilde{x}}_{a}^{k}+\widetilde{\mathrm{y}}{}{}^{k} =1, \forall k\in \mathcal{K}$$
(9)
$${\widetilde{x}}_{a}^{k}\in \{\mathrm{0,1}\}, \forall k\in \mathcal{K},\forall a\in \mathcal{A}$$
(10)
$$\widetilde{\mathrm{y}}{}{}^{k} \ge 0, \forall k\in \mathcal{K}$$
(11)

Constraint (8) is the so-called shortest-path constraint. The constraint (9) on the lower level ensures that the commodity cannot simultaneously be assigned to both tolled and toll-free paths. Heilporn et al. (2009) proposed following mixed-integer reformulation HNPP2 of the HNPP1, in which lower problem optimality is expressed in terms of path flows and new variables \({p}_{a}^{k}\), representing the actual revenue corresponding to commodity \(k\) and path \(a\), are introduced:

$$\underset{p,t,x}{max} \sum\limits_{k\in \mathcal{K}}\sum\limits_{a\in \mathcal{A}}{\eta }^{k}{p}_{a}^{k}$$
(12)
$$s.t.\sum\limits_{a\in \mathcal{A}}\left({c}_{a}^{k}{x}_{a}^{k}+{p}_{a}^{k}\right)+{c}_{od}^{k}\left(1-\sum\limits_{a\in \mathcal{A}}{x}_{a}^{k}\right)\le {c}_{b}^{k}+{t}_{b}, \forall k\in \mathcal{K},\forall b\in \mathcal{A}$$
(13)
$${p}_{a}^{k}\le {M}_{a}^{k}{x}_{a}^{k}, \forall k\in \mathcal{K},\forall a\in \mathcal{A}$$
(14)
$${t}_{a}-{p}_{a}^{k}\le {N}_{a}\left(1-{x}_{a}^{k}\right), \forall k\in \mathcal{K},\forall a\in \mathcal{A}$$
(15)
$${p}_{a}^{k}\le {t}_{a}, \forall k\in \mathcal{K},\forall a\in \mathcal{A}$$
(16)
$${p}_{a}^{k}\ge 0, \forall k\in \mathcal{K},\forall a\in \mathcal{A}$$
(17)
$${x}_{a}^{k}\in \{\mathrm{0,1}\}, \forall k\in \mathcal{K},\forall a\in \mathcal{A}$$
(18)
$$\sum\limits_{a\in \mathcal{A}}{x}_{a}^{k}\le 1, \forall k\in \mathcal{K}$$
(19)

where \({M}_{a}^{k}=\mathrm{max}\{0,{c}_{od}^{k}-{c}_{a}^{k}\}\) and \({N}_{a}=\underset{k\in \mathcal{K}}{\mathrm{max}}{M}_{a}^{k}\). Constraints (13) ensure the optimality of chosen path for each commodity \(k\in \mathcal{K}\), while constraints (14) to (16) ensure that the revenue variable \({p}_{a}^{k}\) fulfills linearization assumption

$$p_{a}^{k} = \left\{ {\begin{array}{*{20}c} {t_{a} ,} & {if\;commodity\;k\;travels\;through\;arc\;a\; \in A} \\ {0,} & {{\text{otherwise}}{\text{.}}\qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad \; {\kern 1pt} } \\ \end{array} } \right.$$

More detailed interpretations of the equations and inequalities (12)–(18) can also be found in the original work by Heilporn et al. (2009). The HNPP2 coincides with the reformulation given by Shioda et al. (2009) to the problem of product line pricing. As already mentioned, Heilporn et al. (2010) have indicated a close relation between a generic NPP, HNPP, and the product line pricing problem. Labbe and Violin (2016) also highlighted the parallel between a product's pricing and a highway. Now, it will be shown how the relaxed version of MRWTE \({j}^{\prime}\) can be reformulated as a relatively simple case of HNPP.

3.2 Relation between problems

A certain similarity between the MRWTE \({j}^{\prime}\) and the HNPP with the single tolled arc can be observed. The schematic representation of HNPP with the single tolled arc and three commodities is given in Fig. 2.

Fig. 2
figure 2

Highway Network Pricing problem scheme

Full size image

The “aim” of a commodity is to be transported with minimal costs. Analogically, a waste producer aims to treat waste with minimal costs. Whereas the owner of the arc sets the toll, WtE sets the gate fee. Let toll \(t\) be identified with the gate fee \({c}_{{j}^{{\prime}}}^{g}\) of \({j}^{\prime},\) \(\mathcal{K}\) be identified with a set of waste producers \(M\), price of untolled highway travel \({c}^{k}\) be identified with transportation costs \({c}_{i,{j}^{{\prime}}}^{t}\), origins of commodities \({o}^{k}\) be identified with locations of waste producers, and alternative optimal route costs \({ c}_{od}^{k}\) be identified with alternative optimal waste treatment option costs \({c}_{i,{j}}^{t}+{c}_{j}^{g}\), and destinations \({d}^{k}\) be identified with successful treatment of waste. Then, MRWTE \({j}^{\prime}\) can be classified within the framework of HNPP, as it is depicted in Fig. 3 for the case \({j}^{\prime}=\{2\}\).

Fig. 3
figure 3

Gate fee setting scheme

Full size image

However, the most challenging difference between these problems is that HNPP does not involve capacity constraints on an arc (analogy of WtE plants' capacity constraints). This fact brings many complications since, due to limited capacities, a waste producer can choose a non-optimal waste treatment possibility to reduce the costs of another waste producer and achieve a minimal sum of total costs. In the next section MRWTE \({j}^{\prime}\) without capacity constraints of competitors will be formally reformulated analogically to HNPP2. Then, the algorithm, which enables the embedding of capacity constraints into the reformulated problem, will be presented in Sect. 3.4.

3.3 Risk-averse price-setting

Consider the point of view of one of the possible WtE plants \({j}^{\prime}\) and setting in which only the following information is available to \({j}^{\prime}\): gate fees of other WtE plants, waste production for each waste producer in the region, and, obviously, the capacity of its own waste treatment facility. Whereas such a situation is improbable, exactly this assumption will enable to model MRWTE \({j}^{\prime}\) as HNPP2 and embed capacity constraints into the problem afterward. Since the capacities of other WtE plants are unknown, \({j}^{\prime}\) has to decide its attitude to possible risks in this uncertain situation. If \({j}^{\prime}\) accepts the risk-averse behavior, it has to work with the worst possible scenario. Therefore, \({j}^{\prime}\) will try to solve the MRWTE \({j}^{\prime}\), where the capacity constraint holds only for the WtE plant managed by itself. Further, this problem will be denoted as MRWTE \({j}^{\prime}\) RA. The following exact way of finding the solution to MRWTE \({j}^{\prime}\) RA, which can be viewed as a three-step algorithm, is proposed.

In the first step, the linear program corresponding to the minimization of the total costs by waste producers assuming infinite capacities of WtE plants from \(\mathrm{N}\setminus {\mathrm{j}}^{\prime}\) and absence of \({\mathrm{j}}^{\prime}\) in the network has to be solved. It can be formulated as LP \({j}^{\prime}\) RA:

$$\underset{{x}_{i,j}:i\in M,j\in N\setminus {j}^{\prime}}{\mathrm{min}}\sum\limits_{j\in N\setminus {j}^{\prime}}\sum\limits_{i\in M}\left({c}_{i,j}^{t}+{c}_{j}^{g}\right){x}_{i,j}$$
(20)
$$\sum\limits_{j\in N\setminus {j}^{\prime}}{x}_{i,j}={w}_{i}^{p}, \forall i\in M$$
(21)
$${x}_{i,j}\ge 0, \forall i \in M, \forall j\in N\setminus {j}^{\prime}$$
(22)

Once the solution of the LP \({j}^{\prime}\) RA is obtained, set \(\{{x}_{i,j}^{*,{j}^{\prime}}:i\in M,j\in N\setminus {j}^{\prime}\}=\) arg LP \({j}^{\prime}\) RA. Non-uniquness of LP \({j}^{\prime}\) RA solution does not play a role in the following considerations. Now when the optimal waste flows from LP \({j}^{\prime}\) RA are known, the MRWTE \({j}^{\prime}\) RA can be solved as HNPP2 with a single tolled arc in two steps. The precise relation between the role of variables and parameters in an HNPP2 and MRWTE \({j}^{\prime}\), already indicated in Figs. 2 and 3, is given by the following Table 3.

Table 3 Role of variables in the suggested reformulation
Full size table

Now, the program HNWTE \({j}^{\prime}\) RA is introduced:

$$\underset{{p}^{i,j},{c}_{{j}^{\prime}}^{g},{q}^{i,j}:i\in M,j\in N\setminus {j}^{\prime}}{\mathrm{max}}\sum\limits_{i\in M}\sum\limits_{j\in N\setminus {j}^{\prime}}{x}_{i,j}^{*,{j}^{\prime}}{p}^{i,j}$$
(23)
$$\mathrm{s}.\mathrm{t}.\left({c}_{i,{j}^{\prime}}^{t}{q}^{i,j}+{p}^{i,j}\right)+\left({c}_{i,j}^{t}+{c}_{j}^{g}\right)\left(1-{q}^{i,j}\right)\le {c}_{i,{j}^{\prime}}^{t}+{c}_{{j}^{\prime}}^{g}, \forall i\in M,\forall j\in N\setminus {j}^{\prime}$$
(24)
$${p}^{i,j}\le {M}^{i,j}{q}^{i,j}, \forall i\in M,\forall j\in N\setminus {j}^{\prime}$$
(25)
$${c}_{{j}^{\prime}}^{g}-{p}^{i,j}\le N\left(1-{q}^{i,j}\right), \forall i\in M,\forall j\in N\setminus {j}^{\prime}$$
(26)
$${p}^{i,j}\le {c}_{{j}^{\prime}}^{g}, \forall i\in M,\forall j\in N\setminus {j}^{\prime}$$
(27)
$${p}^{i,j}\ge 0, \forall i\in M,\forall j\in N\setminus {j}^{\prime}$$
(28)
$${q}^{i,j}\in \{\mathrm{0,1}\}, \forall i\in M,\forall j\in N\setminus {j}^{\prime}$$
(29)
$$\sum\limits_{i\in M}\sum\limits_{j\in N\setminus {j}^{\prime}}{q}^{i,j}{x}_{i,j}^{*,{j}^{\prime}}\le {w}_{{j}^{\prime}}^{c}$$
(30)

where \({M}^{i,j}=\mathrm{max}\{0,{c}_{i,j}^{t}+{c}_{j}^{g}-{c}_{i,{j}^{\prime}}^{t}\}, \forall i\in M,\forall j\in N\setminus {j}^{\prime},\) and \(N=\mathrm{max}{M}^{i,j}\). Newly imposed inequality (30) will prevent the exceeding of the capacity of the WtE plant \({j}^{\prime}\). On the other hand, the such constraint does not enable waste producers to split part of their production to achieve lower costs due to the integer nature of variables \({q}^{i,j}\). Consequently, the WtE plant \({j}^{\prime}\) can not completely engage its capacity in the general case. However, such splitting is clearly possible in the original setting of the MRWTE \({j}^{\prime}\) RA. To take into account this complication and solve the occurred problem, the certain analogy of HNWTE \({j}^{\prime}\) RA, which is based on its optimal solution, has to be solved. Assign \(\{{p}^{*,i,j},{c}_{{j}^{\prime}}^{*,g},{q}^{*,i,j}:i\in M,j\in N\setminus {j}^{\prime}\}=\mathrm{arg}\) HNWTE \({j}^{\prime}\) RA. Then, to find an exact solution to MRWTE \({j}^{\prime}\) RA, HNWTE \({j}^{\prime}\) RAFULL has to be solved

$$\underset{{p}^{i,j},{c}_{{j}^{\prime}}^{g},{q}^{i,j}:i\in M,j\in N\setminus {j}^{\prime}}{\mathrm{max}}\sum\limits_{i\in M}\sum\limits_{j\in N\setminus {j}^{\prime}}{x}_{i,j,new}^{*,{j}^{\prime}}{p}^{i,j}$$
(31)
$$\mathrm{s}.\mathrm{t}.\left({c}_{i,{j}^{\prime}}^{t}{q}^{i,j}+{p}^{i,j}\right)+\left({c}_{i,j}^{t}+{c}_{j}^{g}\right)\left(1-{q}^{i,j}\right)\le {c}_{i,{j}^{\prime}}^{t}+{c}_{{j}^{\prime}}^{g}, \forall i\in M,\forall j\in N\setminus {j}^{\prime}$$
(32)
$${p}^{i,j}\le {M}^{i,j}{q}^{i,j}, \forall i\in M,\forall j\in N\setminus {j}^{\prime}$$
(33)
$${c}_{{j}^{\prime}}^{g}-{p}^{i,j}\le N\left(1-{q}^{i,j}\right), \forall i\in M,\forall j\in N\setminus {j}^{\prime}$$
(34)
$${p}^{i,j}\le {c}_{{j}^{\prime}}^{g}, \forall i\in M,\forall j\in N\setminus {j}^{\prime}$$
(35)
$${p}^{i,j}\ge 0, \forall i\in M,\forall j\in N\setminus {j}^{\prime}$$
(36)
$${q}^{i,j}\in \{\mathrm{0,1}\}, \forall i\in M,\forall j\in N\setminus {j}^{\prime}$$
(37)
$$\sum\limits_{i\in M}\sum\limits_{j\in N\setminus {j}^{\prime}}{q}^{i,j}{x}_{i,j,new}^{*,{j}^{\prime}}\le {w}_{{j}^{\prime}}^{c}$$
(38)
$${c}_{{j}^{\prime}}^{g}\le {c}_{{j}^{\prime}}^{*,g}$$
(39)

where

$${x}_{i,j,\mathrm{new}}^{*,{j}^{\prime}}=\left\{\begin{array}{c}{x}_{i,j}^{*,{j}^{\prime}}, if {q}^{*,i,j}=1, \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \\ \mathrm{min}\left\{{x}_{i,j}^{*,{j}^{\prime}}, {w}_{{j}^{\prime}}^{c}-\sum\limits_{i\in M}\sum\limits_{j\in N\setminus {j}^{\prime}}{q}^{*,i,j}{x}_{i,j}^{*,{j}^{\prime}}\right\}, if {q}^{*,i,j}=0.\end{array}\right.$$

Inequalities (38) will enable utilization of the whole capacity, provided by lowering the price (39). Moreover, (39) prevents the repetition of calculations already performed during the solution of HNWTE \({j}^{\prime}\) RA. Then, the optimal solution for HNWTE \({j}^{\prime}\) RAFULL is assumed to be the optimal solution to MRWTE \({j}^{\prime}\) RA. at In case of the infeasibility of HNWTE \({j}^{\prime}\) RA, it is sufficient to proceed directly to HNWTE \({j}^{\prime}\) RAFULL without constraint (39).

3.4 A heuristic approach to a WtE price-setting with constrained capacities

The setting described in the previous subsection enables us to fully embed the considered gate fee setting problem into the framework of HNPP. However, the previously mentioned risk-averse approach might impose too strong and unrealistic restrictions. For example, such an approach can accept that all waste produced in the region can be sent to only one WtE, which is improbable for large-scale cases. Thus, in this subsection, a heuristic algorithm for solving the original problem MRWTE \({j}^{\prime}\), which is based on the approach presented in the previous subsection, is proposed. This suggested algorithm embeds the capacities of other WtE plants into a decision-making process and can be described as follows.

  • First step: Solve the linear problem LP \({j}^{\prime}\) WITHOUT and obtain information about the current state of the network without the WtE plant \({j}^{\prime}\).

    $$\underset{{x}_{i,j}:i\in M,j\in N\setminus {j}^{\prime}}{\mathrm{min}}\sum\limits_{j\in N\setminus {j}^{\prime}}\sum\limits_{i\in M}\left({c}_{i,j}^{t}+{c}_{j}^{g}\right){x}_{i,j}$$
    (40)
    $$\text{s.t.} \, \sum\limits_{i\in M}{x}_{i,j}\le {w}_{j}^{c},\forall j\in N\setminus {j}^{\prime},$$
    (41)
    $$\sum\limits_{j\in N\setminus {j}^{\prime}}{x}_{i,j}={w}_{i}^{p}, \forall i\in M,$$
    (42)
    $${x}_{i,j}\ge 0, \forall i \in M, \forall j\in N\setminus {j}^{\prime}$$
    (43)

  • Second step: Set \(\{{x}_{i,j}^{*,{j}^{\prime}}:i\in M,j\in N\setminus {j}^{\prime}\}=\) arg LP \({j}^{\prime}\) WITHOUT. Solve the program HNWTE \({j}^{\prime}\) RA and, consequently HNWTE \({j}^{\prime}\) RAFULL. The first two steps provide the main body of the algorithm with the relevant estimate of the network starting state and the starting gate fee \({c}_{{j}^{\prime}}^{\mathrm{start},g}\in \mathrm{arg}\) HNWTE \({j}^{\prime}\) RAFULL. Currently, the capacity constraints hold for every WtE plant in the network.

  • Third step: Solve the linear program LP \({j}^{\prime}\) corresponding to the lower-level problem in the original bilevel program MRWTE \({j}^{\prime}\) with \({c}_{{j}^{\prime}}^{g}={c}_{{j}^{\prime}}^{\mathrm{start},g}\) to obtain the current state of the network:

    $$\underset{{x}_{i,j}:i\in M,j\in N}{\mathrm{min}}\sum\limits_{j\in N}\sum\limits_{i\in M}\left({c}_{i,j}^{t}+{c}_{j}^{g}\right){x}_{i,j}$$
    (44)
    $$s.t.\sum\limits_{i\in M}{x}_{i,j} \le {w}_{j}^{c},\forall j\in N,$$
    (45)
    $$\sum\limits_{j\in N}{x}_{i,j} ={w}_{i}^{p}, \forall i\in M,$$
    (46)
    $${x}_{i,j}\ge 0, \forall i \in M, \forall j\in N.$$
    (47)

    In each iteration, this step corrects the reactions of the follower to the newly chosen \({c}_{{j}^{\prime}}^{\mathrm{start},g}\), so that the leader has actual information about current flows for the given gate fee.

  • Fourth step: Set \(\{{x}_{i,j}^{*,{j}^{\prime}}:i\in M,j\in N\setminus {j}^{\prime}\}=\) arg LP \({j}^{\prime}.\) Solve the program HNWTE \({j}^{\prime}\)

    $$\underset{{p}^{i,j},{c}_{{j}^{\prime}}^{g},{q}^{i,j}}{\mathrm{max}}\sum\limits_{i\in M}\sum\limits_{j\in N}{x}_{i,j}^{*,{j}^{\prime}}{p}^{i,j}$$
    (48)
    $$s.t.\left({c}_{i,{j}^{\prime}}^{t}{q}^{i,j}+{p}^{i,j}\right)+\left({c}_{i,j}^{t}+{c}_{j}^{g}\right)\left(1-{q}^{i,j}\right)\le {c}_{i,{j}^{\prime}}^{t}+{c}_{{j}^{\prime}}^{g}, \forall i\in M,\forall j\in N\setminus {j}^{\prime},$$
    (49)
    $${c}_{i,{j}^{\prime}}^{t}{q}^{i,{j}^{\prime}}+{p}^{i,{j}^{\prime}} +{\mathrm{min}}_{j\in N\setminus {j}^{\prime}}\{{c}_{i,j}^{t}+{c}_{j}^{g}:{c}_{i,j}^{t}+{c}_{j}^{g}>{c}_{i,{j}^{\prime}}^{t}+{c}_{{j}^{\prime}}^{\mathrm{start},g}\} \left(1-{q}^{i,{j}^{\prime}}\right)\le {c}_{i,{j}^{\prime}}^{t}+{c}_{{j}^{\prime}}^{g},$$
    $$\forall i \in M$$
    (50)
    $${c}_{{j}^{\prime}}^{g}-{p}^{i,j}\le N\left(1-{q}^{i,j}\right), \forall i\in M,\forall j\in N\setminus {j}^{\prime},$$
    (51)
    $${p}^{i,j}\le {M}^{i,j}{q}^{i,j}, \forall i\in M,\forall j\in N,$$
    (52)
    $${p}^{i,j}\le {c}_{{j}^{\prime}}^{g}, \forall i\in M,\forall j\in N,$$
    (53)
    $${p}^{i,j}\ge 0, \forall i\in M,\forall j\in N,$$
    (54)
    $${q}^{i,j}\in \{\mathrm{0,1}\}, \forall i\in M,\forall j\in N,$$
    (55)
    $$\sum\limits_{i\in M}\sum\limits_{j\in N}{q}^{i,j}{x}_{i,j}^{*,{j}^{\prime}}\le {w}_{{j}^{\prime}}^{c},$$
    (56)

    where \({M}^{i,j}=\mathrm{max}\{0,{c}_{i,j}^{t}+{c}_{j}^{g}-{c}_{i,{j}^{\prime}}^{t}\}, \forall i\in M,\forall j\in N\setminus {j}^{\prime},\) \({M}^{i,{j}^{\prime}}=\mathrm{max}\{0,\underset{j\in N\setminus {j}^{\prime}}{\mathrm{min}}\{{c}_{i,j}^{t}+{c}_{j}^{g}:{c}_{i,j}^{t}+{c}_{j}^{g}>{c}_{i,{j}^{\prime}}^{t}+{c}_{{j}^{\prime}}^{\mathrm{start},g}\}-{c}_{i,{j}^{\prime}}^{t}\},\) \(N=\mathrm{max}{M}^{i,j}.\) Consequently, solving modification HNWTE \({j}^{\prime}\) FULL modified analogously to \(\mathrm{HNWTE}{j}^{\prime}\mathrm{RAFULL}\): modify flows analogous to the previous subsection and add a constraint that the gate fee can only be lowered compared to the optimum found via HNWTE \({j}^{\prime}\). These two steps describe the adaptation of the leader to the current flows that have been changed in the previous step. Novel, newly introduced constraint (50) reflects the possible choice of abandoning some of the current non-zero waste flows to \({j}^{\prime}\) in order to increase the price and potentially obtain higher revenue. None of the papers reviewed in Sect. 2 has considered such inequality. Set \({c}_{{j}^{\prime}}^{\mathrm{opt},g}=\mathrm{arg}\) HNWTE \({j}^{\prime}\) FULL.

  • Fifth step.: Raise \({c}_{{j}^{\prime}}^{\mathrm{opt},g}\) and solve \(LP{\mathrm{j}}^{\prime}\) with \({c}_{{j}^{\prime}}^{g}={c}_{{j}^{\prime}}^{\mathrm{opt},g}\) until the first decrease in \(\sum\limits_{i\in M}{x}_{i,{j}^{\prime}}^{*,{j}^{\prime}}=\mathrm{arg }LP{\mathrm{j}}^{\prime}\). This is a simple computational check in case the WtE plant \({\mathrm{j}}^{\prime}\) might still be the best waste treatment option due to the filled capacities of the other plants.

  • Sixth step: If last \({c}_{{j}^{\prime}}^{\mathrm{opt},g}\) from the previous step guarantees a greater revenue than \({c}_{{j}^{\prime}}^{\mathrm{start},g}\), then set \({c}_{{j}^{\prime}}^{\mathrm{start},g}{=c}_{{j}^{\prime}}^{\mathrm{opt},g}\) and go back to the third step. Otherwise, the solution \({c}_{{j}^{\prime}}^{\mathrm{start},g}\) is found, END. This is a classical search stop condition, where the main body of a cycle runs as long as it can find a better solution.

3.4.1 Commentary

The algorithm is meant to produce the optimal or near-optimal solution. To create an artificial upper bound for gate fees and to ensure the requirement that for every commodity exists the toll-free path from its origin to its destination, a WtE plant with a capacity that can meet waste production of the whole region has to be considered. At the beginning of this work, it was stated that the pessimistic approach would be applied in the case of multiple solutions on the lower level. However, all presented MIPs are defined as the optimistic approach. Embedding the pessimistic approach into them can be done using a computationally elegant “trick”. Some sufficiently small number \(\varepsilon\) should be added to all \({c}_{i,{j}^{\prime}}^{t}\). It will help to find an \(\varepsilon\)-optimal solution for the pessimistic case. To not distort optima by this numerical adjustment, it is recommended to set an \(\varepsilon\) to a decimal number, which has an order of magnitude equal to a minimum of the one order of magnitude lower than any transportation costs and of the smallest order of magnitude of the gate fees. Thus, if integer costs and gate fees are considered, it is advised to set \(\varepsilon =0.1\). Moreover, in the fifth step of the algorithm, it is advised to raise \({\mathrm{c}}_{{\mathrm{j}}^{\prime}}^{opt,\mathrm{g}}\) by \(\varepsilon\) to cover all possible waste distributions on the lower level. The linear problems solved during the presented algorithm are solved using the pessimistic approach for the leader with the original \({c}_{i,{j}^{\prime}}^{t}\) without adjustments.

Generation of the shortest paths in the preprocessing step (van Hoesel et al. 2008) may help minimize the number of arcs (the waste producer will be connected to his best option and tolled arc). However, it is redundant in the considered case since such preprocessing is almost equivalent to the solution to the problem. Also, the costs of each arc will iteratively change during best-response dynamics: the information redundant in the previous step should be considered in the next. As it was mentioned, basic single-tolled-arc unconstrained problems solved during the algorithm are simple and can be solved in polynomial time. In fact, it is sufficient to order differences \({c}_{i,j}^{t}+{c}_{j}^{g}-{c}_{i,{j}^{\prime}}^{t}, \forall i \in M, \forall j \in N\) and perform a simple sequential evaluation of the leader's objective function with a gate fee equal to these differences in decreasing order (Labbe and Violin 2016). However, that representation does not consider the leader's capacity constraint and the inequality enabling the renouncing of some waste flows sent to the leader. The HNPP2 has seemed like a more suitable formulation, which better represents the structure of the problem, and might enable convenient generalization and future work with the inequalities, which will reduce the feasible region, so the solution can be found faster.

3.5 Best-response dynamics in game theory

Since it was decided to study the game with continuous strategy sets of WtE plants, the algorithm, which will enable finding NE in a reasonable time, has to be chosen. Due to the continuity of the considered strategy sets, no extensive search through NE definition (Owen 2013) nor dominated strategies elimination (Matsui 1992) can be employed due to computational complexity. Whereas dominated strategies elimination can also handle continuous strategy spaces, the considered continuous instances cannot be solved efficiently by such elimination due to non-convexity and discontinuity of the payoff function. Moreover, the above algorithms will also fail if large discrete strategy spaces are considered.

Thus, it was decided to apply the alternative algorithm, called sequential best-response dynamics, due to its satisfactory computational complexity. Its detailed description can be found in the (Owen 2013). Best-response dynamics is one of the most popular algorithmic ways of finding the NE. The main idea of the algorithm is an iterative sequential update of players' strategies through their best-response correspondence \({B}_{j}\left({c}_{-j}^{\mathrm{g}}\right)=\{{c}_{j}^{\mathrm{g}}\in {C}_{j}^{\mathrm{g}}:{\uppi }_{j}\left({c}_{j}^{\mathrm{g}},{c}_{-j}^{\mathrm{g}}\right)\ge {\uppi }_{j}\left({c}_{j}^{\mathrm{^{\prime}},\mathrm{g}},{c}_{-j}^{\mathrm{g}}\right),\forall {c}_{j}^{\mathrm{^{\prime}},\mathrm{g}}\in {C}_{j}^{\mathrm{g}}\}.\) If this process, iteratively repeated, leads to some strategy profile, then this profile is the NE. Thus, the NE can be obtained through the solution of a sequence of mathematical programs corresponding to revenue maximization. However, the main disadvantage of this algorithm is that it can get stuck in a cycle. Figure 4 explains the main principles of the algorithm for the continuous strategy sets.

Fig. 4
figure 4

Sequential best-response dynamics scheme

Full size image

4 The heuristic’s testing

In this section, the attention will be solely focused on testing the proposed method's general ability to solve the bilevel price-setting problem without searching for the NE (best-response dynamics functionality will be demonstrated in the case study section). An application to artificial WM network instances has been considered to validate the proposed bilevel programming algorithm. Now, the instance generation rules will be described in detail.

  • A random number \(n\) of local WtE plants between 10 and 20 is generated. Capacities of WtE plants are generated randomly within a range of 25 kt to 350 kt. Their prices are chosen randomly between 40 €/t and 100 €/t.

  • A number \(m=kn\) of municipalities is generated, where \(k\) is a random number between 5 and 15. For \(k\) municipalities, waste production is generated within a range of 100 kt to 300 pkt (representing large cities). For the remaining \(\left(k-1\right)n\) municipalities, it is generated within a range of 5–50 kt (small and medium-sized municipalities).

  • Then, these municipalities are randomly placed on a map. The map is considered to have a size of 450 times 300 square units of length (in particular, square kilometers are considered). However, only a range of (50, 400) times (50, 250) is considered for the municipalities. The WtE plants are randomly assigned to the municipalities.

  • Additionally, 1 to 5 foreign WtE plants are randomly generated on the map within a range (0, 50)\(\cup\)(400, 450) times (0, 50)\(\cup\)(250, 300). Each plant's capacity equals the total waste production of all municipalities. The foreign WtE plants have the same gate fee of 1.5 times the maximum of local WtE plants' gate fees.

  • Transportation costs are generated using the Euclidean distance between the municipality and WtE plant. The distance is multiplied by a randomly generated coefficient within a range of 0.1–0.4 €/km.

  • Locations of WtE plants and municipalities, transportation cost coefficients, gate fees, and waste productions are generated using a continuous uniform distribution. All other values are generated using a discrete uniform distribution over integers within the defined ranges.

  • The generated waste productions are then rounded to two decimal places, transportation costs are rounded to an integer, and gate fees are rounded to one decimal place (thus, \(\varepsilon =0.1\) can be set). This is done to computationally simplify the algorithm and to enhance the speed of checking the heuristic's correctness.

  • Since the heuristic will be later applied to an exemplary case study, the ranges were chosen to generate WM networks comparable to the Czech Republic's WM situation. The map data can be found in the Supplementary material spreadsheet.

4.1 Numerical results of the testing

Each map generated in the above-described way is considered an artificial scenario, for which an optimal gate fee has been subsequently established for each (local) WtE plant. The total of 20 scenarios has served as an input: first 10 generated scenarios where \(\sum\limits_{i\in M}{w}_{i}^{p}\) is greater than total capacity of local WtE plants and first 10 generated scenarios where \(\sum\limits_{i\in M}{w}_{i}^{p}\) is less than total capacity of local WtE plants have been taken into consideration. Such diversification of scenarios makes it possible to test situations when the main competitors are foreign WtE plants, as well as insnances when competition takes place within a local WM network. The results are then compared to the one obtained via the complete enumeration procedure of the precision \(\varepsilon =0.1\). It dwells in a successive increase of a gate fee from zero with step 0.1 and a calculation of the revenue for each linear problem solution under this gate fee. All computations were performed using the CPLEX solver within GAMS (the same is valid for Sect. 5). The results and basic scenarios information are presented in Table 4.

Table 4 Results of the algorithm validation
Full size table

One iteration of the follower's problem during enumeration lasts for approximately 0.25 s with 1,574, resp. 2236, solutions performed in case of sufficient, resp. insufficient, capacities of local WtE plants on average. On the other side, to solve one iteration of the MIP formulation approximately 10 times more time is needed with only 4.5 iterations performed on average. Whereas first ten scenarios require averagely 1.3 iterations and lose averagely 3.34% compared to optimal objective function value, the remaining scenarios are more computationally challenging (7.5 iterations are required), which do not substantially affect average loss of 3.67%. In 87% procents of cases, loss was less than 10% and, in the worst case, loss was 45%. The maximal number of iterations that has been performed during one run of the algorithm is 46.

The more detailed analysis of errors does not demonstrate substantial correlation between the scenarios’ parameters from Table 4 and the resulting loss, even when considering simple interaction between parameters (absolute values of correlation coefficients do not exceed 0.16). Therefore, there is no obvious pattern in the behavior of the heuristic and its performance with respect to the setting of the scenarios. Potentially, greater loss can be implied by an unrealistic input or it can be the result of much more complex interactions of the parameters with the shape of the generated network. Thus, from Table 4, it can be seen that the proposed algorithm is able to handle the randomly generated scenarios time-efficiently without substantial loss in an objective function value in most of the cases. More information on the results can be found in Supplementary material spreadsheet.

5 Exemplary case study

In this section, solving the exemplary problem and its results will be discussed in detail. Moreover, the numerical results of the proposed bilevel programming heuristic algorithm on the realistic WM network will be presented.

5.1 The design of the new WtE plant

The exemplary case study is meant to illustrate the possible application of the proposed approach to the realistic data. It is assumed that in the Czech Republic, there are 16 WtE plants (the founding of 12 of them is currently planned). However, some waste producers from the Czech Republic might use the services of facilities in nearby countries (Germany and Austria). To create an upper boundary on the possible gate fee and ensure the existence of the “toll-free” path, these facilities are represented as three WtE plants with a fixed gate fee of 100 €/t and the capacity corresponding to the waste products of the whole Czech Republic.

To compete with these foreign facilities, it is planned to build one more WtE plant in the Czech Republic (WtE plant “Otrokovice”), and the question of optimal capacity design arises. To optimally estimate this capacity, it is advised to “place” this facility in the currently existing network and find the NE of the considered WtE plants pricing game using the suggested approach: best-response dynamics with the usage of proposed bilevel programming heuristic. The resulting price state will enable to the establishment of the waste flows and revenue of all WtE plants in the network. This process, iteratively repeated for each capacity design, will provide an image of the expected revenue of the planned facility, which can be compared to required investments. Such information is crucial during the decision-making process and will help assess the investment's feasibility. The starting point of the whole process for each WtE plant (except the foreign plants) is assumed to be the gate fee of 50 €/t, and the first capacity design is 25 kt/y. The transportation costs are assumed to be integers (thus, \(\varepsilon =0.1).\) Productions, as well as capacities, are assumed to be annual.

Unfortunately, the best-response dynamics failed to find NE during the first attempt. When the \(\updelta\), defining the stopping condition of the algorithm in Fig. 4, is considered to be too small, the algorithm gets stuck in the cycle. This fact can be explained, by the hypothesis, that when continuous strategy sets are assumed, the change of the gate fee is expected to be always profitable. This would lead to the non-existence of the fixed-point in best-response functions, and, as a result, NE would cease to exist in a general price-setting game. To overcome this complication, a refined condition has been suggested. It is assumed that when the norm of the difference vector is less than one, no substantial change in the gate fees vector has occurred, and the algorithm will be stopped. This assumption will enable to prevent the cyclic nature of the price-setting game when players successively lower their prices to obtain greater demand. Under assumption \(\updelta =1\), the gate fee stable outcomes were computed for the suggested capacities from 25 to 350 kt with the step of 25 kt. The capacity usage and the estimated revenue of the planned WtE plant “Otrokovice” are presented in Table 5.

Table 5 Results for “Otrokovice”
Full size table

The resulting gate fees for all WtE plants can be found in the Supplementary material spreadsheet. Table 5 and stable gate fees from Supplementary material confirm that the proposed model is reasonable: capacity increase causes a gradual decrease in gate fees of all WtE plants. Thus, in accordance with basic economy rules, the greater “supply” (capacity) leads to a lower price (gate fee). Clearly, to improve the reliability of the found solutions, the impact of the input parameters and initial point choice on the algorithm precision and speed of convergence should be studied in the future.

To choose an appropriate capacity solution for a particular WtE project, the revenues from waste treatment have to be compared with the initial investment. For simplicity, the solved task does not consider operational costs and revenues related to heat and electricity selling. In the case of investment costs, it is important to reflect decreasing unit costs when increasing capacity. The costs for particular capacity variants are estimated by adopting the following formula by Consonni et al. (2005):

$$I={I}_{R}{\left(\frac{C}{{C}_{R}}\right)}^{0.75}$$

where \(I\) represents investments and \(C\) represents the capacity of the facility. Subscript \(R\) denotes the reference number. For the case presented herein, the reference number was set to \({I}_{R}\) = 4 M€/y and \({C}_{R}\) = 100 kt/y. Figure 5 illustrates the results for the considered capacity variants. The profitability can be easily compared via ratios illustrated by a line. Figure 5 demonstrates that greater capacity does not always guarantee a better ratio between revenue and investments. Thus, the market power induced by a greater capacity does not automatically ensure a greater return on investment but has phase-shifting properties. Only after trespassing the capacity of 225 kt/y the WtE plant obtains an advantageous position in the waste management market and can pursue a greater return on investment. The decision about the optimal capacity directly depends on the available capital for investment. For example, if the maximal considered investment is around 7 M€/y, it is reasonable to invest less and build a WtE plant with a capacity of 150 kt/y. Suppose the management of the WtE plant can ensure greater resources for the investment. In that case, it is more profitable to invest approximately 8 M€/y and build a facility with a capacity of 250–275 kt/y (higher precision can be achieved by choice of the smaller step).

Fig. 5
figure 5

Comparison of various capacities for the planned WtE plant

Full size image

5.2 Numerical results of the heuristic algorithm on the realistic WM network

To verify that the algorithm from Sect. 3.4 is able to provide a sufficiently optimal solution in realistic scenario, its performance has been compared to the classical enumeration of the same precision already described in Sect. 4. In particular, gate fee vectors from the last iteration of best-response dynamics have been used as an input describing fixed gate fees of competitors (available in Supplementary material). Thus, 17 different cases (each for one of 17 competing WtE plants) have been calculated for 14 capacity designs. Table 6 represents information about non-optimal solutions found by the proposed heuristic (the whole comparison can be found in the Supplementary material).

Table 6 Numerical results for the heuristic
Full size table

Thus, the heuristic failed to find an optimum solution only in 44 cases out of the considered 238, only 10 of which have led to a loss greater than 1%. Moreover, the largest difference between found optimum and the optimum established by the algorithm is 1.1. Thus, Table 6 confirms the potential of the proposed algorithm on the realistic data: it produces an optimal solution in most cases. Due to comparability of the artificial scenarios to the exemplary case study input data, the computational time of one iteration remains approximately the same. Thus, the case study motivated by the realistic data also proves that the algorithm solves underlying NP problems cardinally faster (in the majority of the considered cases, only one iteration is needed) with an average objective function value optimality loss of 0.18%. Since the underlying motivation was to provide fast input into the best-response dynamics evaluation cycle, the proposed heuristic can be considered suitable. The presented apparatus can provide a realistic estimate of the optimal gate fee for a particular WtE plant, which enables finding NE of the WtE plant's price-setting game.

6 Conclusion

In this work, the WtE plants' price-setting problem has been thoroughly studied from two perspectives: setting the optimal prices for one WtE plant and the search for NE between WtE plants. The problem has been defined as a normal-form game of WtE plants, with gate fees being their strategies. Such a game has peculiar properties, wherein maximizing one player's payoff leads to a bilevel programming problem between a WtE plant and the waste producers. However, these instances of bilevel optimization cannot be solved in polynomial time. After the extensive investigation of the bilevel optimization methods, the novel heuristic approach to solve the bilevel problems. That resembles HNPP with capacitated arcs and a single tolled arc has been proposed. To the best of the 'authors' knowledge, no analogy of this algorithm has been presented before.

The approach considers that a simple iterative update of the lower-level linear problem solution provides sufficiently reliable estimates of waste flows, concerning which the optimization on the upper level is performed. Algorithm performance has been validated via testing and exemplary case study: it has been shown that it provides fast solutions to the considered problem and produces optimal solutions in approximately 60% of artificial scenarios and in nearly 85% of realistic cases. The papers discussed in Sect. 2 considered static prices of the competitors, which is quite a limiting assumption in real-life applications. Thus, the research has also filled the gap in the current game-theoretic literature since the solution of the NP-hard optimization problem is only an instrument to find the NE in the WtE plants' network. Combined with the best-response dynamics algorithm, the heuristic enabled the search for NE with continuous strategy sets. This approach should provide more realistic insight into the reaction of other WtE plants to changes in gate fees. Thus, the estimate of optimal waste flows and gate fees in the waste management network provides more reliable input to decision-makers. The proposed method can be potentially applied to assess the feasibility of the investments in new WtE plants. In particular, the exemplary problem motivated by the Czech Republic data demonstrated how the approach could be applied in practice to design the capacity of the WtE plant. The optimal capacity of the facility, which is being planned in one of the regions, was proposed with respect to the analogous projects and actual waste production in the Czech Republic. The found stable gate fee outcomes exhibit economically reasonable behavior of waste treatment market participants, verifying that the developed tool can be used to simulate the market environment for the WtE facility. While solving the exemplary problem, the hypothesis about the non-existence of the NE in the considered game has been proposed. To overcome this complication, the approach has been suitably modified. Thus, future research can be devoted to the extensive study of the NE's existence in general price-setting games. The performance of the algorithm compared to other existing techniques should also be studied in the future. Moreover, there is an opportunity to embed reconsideration of the waste flows with respect to capacities constraint into the heuristic. Potentially, this step will make suitable modification of the already established inequalities possible, which might lead to improvement of the method performance.