Abstract: Public sector decision making typically involves complex problems that are riddled with competing performance objectives and possess design requirements which are difficult to capture at the time that supporting decision models are constructed. Environmental policy formulation can prove additionally complicated because the various system components often contain considerable stochastic uncertainty and frequently there are also numerous stakeholders holding incompatible perspectives. Consequently, there are invariably unmodelled performance design issues not apparent at the time of the problem formulation which can greatly impact the acceptability of any proposed solutions. While a mathematically optimal solution might provide the best solution to a modelled problem, normally this will not be the best solution to the underlying real problem. Therefore, in public environmental policy formulation, it is generally preferable to be able to create several quantifiably good alternatives that provide very different approaches and perspectives to the problem. This study shows how Simulation-Optimization (SO) modelling can be combined with niching operators to efficiently generate multiple policy alternatives that satisfy required system performance criteria in stochastically uncertain environments and yet are maximally different from each other in the decision space. This new stochastic approach is very computationally efficient, since it permits the simultaneous generation of good solution alternatives in a single computational run of the SO algorithm. The efficacy and efficiency of this modelling to generate alternatives method is specifically demonstrated using a waste management case from the Municipality of Hamilton-Wentworth, Ontario.

INTRODUCTION

While mathematically optimal solutions can provide the best results to modelled problems, they are frequently not the best solutions to the underlying real problems as there are invariably unquantified issues and unmodelled objectives not apparent at the time the models were constructed. This is a common occurrence in situations where the final decisions are constructed based not only upon clearly stated and modelled objectives but also upon environmental, political and socio-economic goals and stakeholder preferences that are fundamentally subjective (Baugh et al., 1997; Brill et al., 1981; Huang et al., 2011; Zechman and Ranjithan, 2004). It is often not possible to express these subjective considerations clearly and therefore, impossible to capture them quantitatively in any optimization model.

Public sector decision making typically involves complex problems that are riddled with competing performance objectives and contain performance design requirements which are very difficult to capture at the time that any supporting decision models must be constructed. Environmental policy formulation can prove even more complicated because the various system components normally possess considerable degrees of stochastic uncertainty. Moreover, it may never be possible to explicitly express all of the subjective considerations in environmental public policy formulation because there are generally numerous incompatible, competing, adversarial stakeholder groups. Therefore, these subjective aspects remain unquantified and unmodelled in the construction of any corresponding decision models. Consequently, public sector environmental policy formulation proves to be an extremely complicated and challenging task.

Therefore, from an environmental policy formulation standpoint, it is often preferable to be able to generate several alternatives that provide multiple, disparate perspectives to the particular problem (Huang et al., 1996). Preferably these alternatives should all possess good (i.e., near-optimal) objective measures with respect to the modelled objective (s) but be fundamentally different from each other in terms of the system structures characterized by their decision variables.

To illustrate the implications of an unmodelled objective on a decision process assume that the optimal solution for a quantified, single-objective, maximization decision problem is X* with corresponding objective value Z1*. Now suppose that there exists a second, unmodelled, maximization objective Z2 that reflects environmental/political acceptability. Let the solution X^a belonging to the noninferior, 2-objective set, represent a potential best compromise solution if both objectives could somehow have been simultaneously evaluated by the decision-maker. While X^a might be viewed as the best compromise solution to the real problem, it would clearly appear inferior to the solution X* in the quantified model since it must be the case that Z1^a≤Z1*. This observation implies that when unmodelled objectives are factored into decision making processes, mathematically inferior solutions for the modelled problem can potentially be optimal for the real problem. Therefore, when unmodelled objectives and unquantified issues exist, different approaches are required in order to not only search the decision space for the noninferior set of solutions but also to explore the decision space for inferior alternative solutions to the modelled problem.

In response to this option creation requirement, several approaches collectively referred to as Modelling to Generate Alternatives (MGA) have been developed (Baetz et al., 1990; Baugh et al., 1997; Brill et al., 1981; Loughlin et al., 2001; Zechman and Ranjithan, 2004). The primary motivation behind MGA is to produce a manageably small set of alternatives that are good with respect to modelled objectives yet as different as possible from each other in the decision space. In so doing, the resulting alternative solution set is likely to provide truly different choices that all perform somewhat similarly with respect to the modelled objectives, yet very differently with respect to the unmodelled issues.

Yeomans et al. (2003) showed how to incorporate data uncertainty directly into environmental planning using an approach referred to as Simulation Optimization (SO). SO is a family of optimization techniques that incorporates inherent system uncertainties expressed as probability distributions into its computational procedure (Fu, 2002). Linton et al. (2002) and Yeomans (2008) have shown that SO can be considered an effective, though very computationally intensive, MGA technique for environmental policy formulation. However, none of these SO MGA approaches have been able to provide guarantees to ensure that the created alternatives are sufficiently different in decision variable structure from one another (Huang et al., 2011).

In this study, it is shown how to efficiently generate maximally different solution alternatives for public environmental policy planning situations containing considerable stochastic uncertainty by using a version of the niching technique of Loughlin et al. (2001) that has been specifically modified for implementation with SO. This novel stochastic technique employs specialized MGA operators and a niching scheme within the SO procedure to identify a set of alternatives then screens these solutions to select a small number that are both good and very different from each other. The innovative approach is very computationally efficient, since it permits the generation of multiple, good but very different solution alternatives in only a single computational run of the SO algorithm rather than the multiple implementations required in most other MGA procedures. This study illustrates the efficacy of the MGA capabilities of this new SO procedure to construct very different, good solutions by testing it on a Municipal Solid Waste (MSW) management optimization study taken from Yeomans et al. (2003).

SIMULATION-OPTIMIZATION FOR FUNCTION OPTIMIZATION

Determining optimal solutions to large stochastic problems proves to be very complicated when system uncertainties have to be accounted for and incorporated directly into the solution procedure (Fu, 2002). When stochastic conditions exist, values for the constraints and objectives can only ever be efficiently estimated by simulation. SO is a broadly defined family of solution approaches that combines simulation with some type of optimization method for stochastic optimization (Fu, 1994, 2002). In SO, all unknown objective functions, constraints and parameters are replaced by one or more discrete event simulation models in which the decision variables provide the settings under which the simulation is performed. Since all measures of system performance are stochastic, any potential solution, X, needs to be evaluated via simulation. As simulation is computationally intensive, an optimization component is used to guide the search for solutions through the problem’s feasible region using as few simulation runs as necessary. Evolutionary algorithms are conducive to these extensive searches because the complete set of candidate solutions maintained in their populations permits concurrent searches to be undertaken throughout multiple sections of the feasible region.

Evolutionary SO consists of two alternating computational phases; an evolutionary module and a simulation module. Evolutionary SO maintains a set or population of candidate solutions throughout its execution. The quality or fitness of each solution in this population is found by having its performance criterion, F, evaluated by simulation. After simulating each candidate solution, the respective fitness values become inputs to the evolutionary module for the creation of the next generation of solutions. The fitness of each solution within the population is ranked in comparison to every other candidate solution. These ranked fitness measures are the inputs to the evolutionary module where the next solution population is created using the evolutionary algorithm. The driving force underlying evolutionary procedures is that fitter solutions in a current population possess a greater likelihood for survival and progression into the subsequent generations. After generating a new candidate solution set, the evolutionary module returns the new population to the simulation module for comparative evaluation. This alternating, two-phase search process terminates when an appropriately stable system state has been attained (Yeomans, 2008). The optimal solution produced by the procedure is the single best solution found over the course of the entire search.

MODELLING TO GENERATE POLICY ALTERNATIVES WITH SIMULATION-OPTIMIZATION

In this study, an MGA procedure that is capable of incorporating uncertainty directly into its generated alternatives via SO is developed using a modified adaptation of Loughlin et al. (2001). In order to properly motivate this procedure, it is necessary to provide a more formal definition of the goals of an MGA process (Brill et al., 1981; Loughlin et al., 2001; Zechman and Ranjithan, 2004). Suppose the optimal solution to an original mathematical model is X* with objective value Z* = F (X*). The following model can then be solved to generate an alternative solution that is maximally different in decision space from X*:

Where:

T is a A user-supplied value that represents how much of the inferior region is to be explored for alternative solutions.

The new stochastic SO based MGA procedure is designed to generate a small number of good but maximally different alternatives and is based upon specialized MGA operators and a niching scheme. In this algorithm, subpopulations or niches within the evolutionary algorithm’s overall population are established to collectively evolve toward a specific number of very different alternatives in the solution space. Each desired solution alternative undergoes the common evolutionary search procedure and the search can be structured based upon any standard evolutionary procedure containing appropriate encodings and operators appropriate to the problem being solved. The survival of solutions depends upon how well the solutions perform with respect to the modelled objective (s) and by how far away they are from all of the other niches in the decision space. Thus the evolution of solutions in the population is influenced by those solutions contained in the other niches, forcing the evolution of each niche-subpopulation towards good but distant regions of the decision space.

In general, the goal of niching schemes is to speciate maintain and converge a population to a small set of different solutions where the difference between solutions can be genotypic (based on decision variable values) or phenotypic (based on solution characteristics) (Loughlin et al. (2001). In niching schemes, the decision space is treated as a resource for which solutions in the evolutionary population must compete. Solutions that are very similar to each other are considered to reside within the same niche. If too many solutions inhabit the same niche, the resources of that niche are considered overexploited and all the individuals in the niche are subsequently penalized in the evolutionary operations. As the number of individuals in lower-populated niches grows, the population achieves a state of pseudo-equilibrium in which relatively stable subpopulations are simultaneously maintained in multiple niches. The number of individuals within each niche is generally proportional to the relative fitness of its individuals to those residing in other niches. Traditionally, a sharing parameter, σ_s, needs to be used to characterize the distance separating adjacent niches in decision space. In this study, an alternative procedure is employed that creates new niching operators that more comprehensively direct the goals of MGA in obtaining a small number of very different, good solutions.

The main steps within the new SO MGA procedure using the niching operators are as follows:

Step 1: Create an initial population. The goal of the procedure is to generate P+1 solutions where P represents the desired number of maximally different alternatives within a prescribed target deviation from the overall optimal solution that must be generated.

Step 2: Evaluate the entire population using simulation and identify the best solution, S₀ with respect to the modelled objective, together with a set of K other solutions possessing modelled objective values that are within a specified deviation from the objective value of S₀. This set of solutions is referred to as the pool of candidate alternative solutions. If K<P then add the next P-K best solutions with respect to the modelled objective to the candidate pool.

Step 3: Determine the decision space centroid, C_i, for each of the N decision variables X_ik, I = 1,…, N, in solution k = 0,..., K, C_i = 1/(K+1)*Σ_k X_ik. This centroid represents the N-dimensional centre of mass for the solutions in the candidate pool. In the calculation shown each dimension of the centroid is computed as the average value of that decision variable over all of the values for that variable within the candidate pool. Alternatively, the centroid could be calculated as a fitness-weighted average or by some other appropriately defined measure.

Step 4: For each solution k = 1,…, K, in the candidate pool calculate D_k, a distance measure between that solution and all other solutions. D_k = Min { | X_ik - C_i | ; i = 1,…,N}. This distance represents the minimum distance between solution k in the candidate pool and the centroid.

Step 5: The goal of maximal difference is to force solutions as far apart as possible in the decision space from the other. Hence, apply an appropriate elitism operator to preserve the P best solution alternatives, S_p, p = 1, …, P within the candidate pool. Any two solutions, S_a and S_b are ordered such that a<b implies D_a≥D_b. The best solution alternatives are those with distance measures most distant in the decision space from the other solutions.

Step 6: Stop the algorithm if the termination criteria (such as maximum number of iterations or some measure of solution convergence) are met.

Step 7: The fitness measures of the maximally different alternatives are boosted to make them the most fit solutions in the population. These solutions are then placed far apart from each other in the population.

Step 8: Apply recombination operators to the solutions. A restrictive mating scheme is employed to encourage the growth of subpopulations around the MGA solutions.

Step 9: Return to Step 2. The strategic placement (Step 7) and restrictive mating (Step 8) schemes can be implemented in a number of ways. In one approach, the population is divided into P + 1 finite subpopulations with each of the P + 1 solutions, S_p, p = 0,…, P placed into one of the subpopulations. Subsequent mating is confined with possibly exceptions to occur within the respective subpopulations. In another approach, the solution alternatives can be distributed throughout the population such that the most different solutions are farthest apart from each other. A neighborhood restrictive mating scheme can be employed to ensure that selection and mating occur only between solutions within the same approximate vicinity in the population. Since the MGA alternatives have the highest fitnesses in the population, their genes will tend to propagate within their respective subpopulations. Some recombination between adjacent subpopulations may allow sharing of genetic information that might benefit either subpopulation if it becomes too homogenous. By adopting this approach to MGA, multiple maximally different design options can be created that meet established system criteria while simultaneously remaining acceptable and implementable in practice.

CASE STUDY OF SO USED IN MGA FOR MUNICIPAL SOLID WASTE MANAGEMENT PLANNING

The application of the new SO MGA procedure with niching will be illustrated using the municipal solid waste management planning study of Hamilton-Wentworth taken from Yeomans et al. (2003). While this section briefly outlines the case, more extensive details and background descriptions can be found in both Yeomans et al. (2003) and Yeomans (2008). Located at the western-most edge of Lake Ontario, the municipality of Hamilton-Wentworth covers an area of 1,100 km² and includes six towns and cities. The municipality is considered the industrial centre of Canada although, it simultaneously incorporates diverse areas of heavy industrial production with densely populated urban space, regions of significant suburban development and large proportions of rural/agricultural environments. The MSW system within Hamilton-Wentworth must satisfy the waste disposal requirements of its half-million residents who collectively, produce >300,000 tons of waste per year with a budget of $22 million. The region had constructed a system to manage these wastes composed of: a waste-to-energy incinerator referred to as the Solid Waste Reduction Unit (or SWARU); a 550 acre landfill site; three waste transfer stations; a household recycling program; a household/hazardous waste depot and a backyard composting program.

The three transfer stations have been strategically located to receive wastes from the disparate municipal (and individual) sources and to subsequently transfer them to the waste management facilities for final disposal either to SWARU for incineration or to the landfill. Wastes received at the transfer stations are compacted into large trucks prior to being hauled to the landfill site. These transfer stations provide many advantages in waste transportation and management; these include reducing traffic going to and from the landfill providing an effective control mechanism for dumping at the landfill, offering an inspection area where wastes can be viewed and unacceptable materials removed and contributing to a reduction of waste volume because of the compaction process. The SWARU incinerator burns up to 450 tons of waste per day and by doing so, generates about 14 million kwh year^-1 of electricity which can be either used within the plant itself or sold to the provincial electrical utility. SWARU also produces a residual waste ash which must subsequently be transported to the landfill for disposal.

Within this MSW system, decisions have to be made regarding whether waste materials would be recycled, landfilled or incinerated and additional determinations have to be made as to which specific facilities would process the discarded materials. Included within these decisions is a determination of which one of the multiple possible pathways that the waste would flow through in reaching the facilities. Conversely, specific pathways selected for waste material flows determine which facilities process the waste. It is possible to subdivide the various waste streams with each resulting substream sent to a different facility. Since cost differences from operating the facilities at different capacity levels produced economies of scale, decisions have to be made to determine how much waste should be sent along each flow pathway to each facility. Therefore, any single MSW planning option is composed of a combination of many decisions regarding which facilities received waste material and what quantities of waste are sent to each facility. All of these decisions are compounded by numerous overriding system uncertainties.

The complete mathematical model used for MSW planning can be found in Yeomans et al. (2003). This mathematical formulation was used not only to examine the existing municipal MSW system but also to prepare the municipality for several potentially enforced future changes to its operating conditions. Yeomans et al. (2003) examined three likely future scenarios with each scenario involving potential incinerator operations. Scenario 1 considered the existing MSW management system and corresponded to a status quo case. Scenario 2 examined what would occur should the incinerator operate at its upper design capacity; corresponding to a situation in which the municipality would landfill as little waste as possible. Scenario 3 permitted the incinerator to operate any where in its design capacity range from being closed completely to operating up to its maximum capacity. Yeomans et al. (2003) ran SO for a 24 h period to determine best solutions for each scenario. For the existing system (Scenario 1), a solution that would never cost more than $20.6 million was constructed. For Scenarios 2 and 3, Yeomans et al. (2003) produced optimal solutions costing no more than 22.1 and $18.7 million, respectively. In all of these scenarios, SO was used exclusively as a function optimizer with the goal being to produce only single best solutions.

As outlined earlier when public policy planners are faced with difficult and potentially controversial choices, they generally prefer to be able to select from a set of near-optimal alternatives that differ significantly from each other in terms of the system structures characterized by their decision variables. In order to create these alternative planning options, it would be possible to place extra target constraints into the original model which would force the generation of solutions that were different from their respective, initial optimal solutions. Suppose for example that ten additional planning alternative options were created through the inclusion of a technical constraint on the objective function that increased the total system cost of the original model from 1.5% up to 15% in increments of 1.5%. By adding these incremental target constraints to the original SO model and sequentially resolving the problem 10 times for each scenario (i.e., 30 additional runs of the SO procedure), it would be possible to create the requisite number of desired alternative policies for MSW planning.

However, to improve upon the process of running thirty separate additional instances of the computationally intensive SO algorithm to generate these solutions, the MGA procedure with niching described in the previous section need be run exactly once for each scenario. The evolutionary parameters used in this computational experiment were a population size of 150, a maximum number of iterations of 300 (together with an additional check for solution convergence), a crossover parameter of 40% and a mutation rate of 5%. At the beginning of the evolutionary search, all solutions in the population with modelled objective values within 50% of the best solution were permitted entry into the candidate pool. This criterion was incrementally tightened with increasing generation number. In this implementation, the relaxation fraction was tightened at a linear rate from 50-15% over the first 50 generations. After generation 50, this fraction was held constant at 15%. In each generation, the subpopulation was screened to identify eleven maximally different alternatives (the best solution and ten alternatives to it). These solutions were then strategically placed into the population and a neighbourhood tournament selection scheme was employed to encourage the formation of niches around these alternatives. In this selection scheme each individual was given an index number that identified its placement position in the population. Each individual solution was restricted to mating only with individuals whose indices lay within a specified neighbourhood size of 10 (5 in either direction) from it. This experimentation produced 30 additional, maximally different alternatives and their respective objective values are shown in Table 1. Each column of the table shows the overall system costs for the 3 optimal solutions plus the 10 maximally different options generated for each of the three scenarios.

As described earlier, public sector, environmental policy problems are typically riddled with incongruent performance requirements that contain significant stochastic uncertainty that are also very difficult to quantify. Consequently, it is preferable to create several quantifiably good alternatives that concurrently provide very different perspectives to the potentially unmodelled performance design issues during the policy formulation stage. The unique performance features captured within these dissimilar alternatives can result in very different system performance with respect to the unmodelled issues, thereby incorporating the unmodelled issues into the actual solution process. This example has demonstrated how the SO MGA modelling approach can be used to efficiently generate multiple, good policy alternatives that satisfy required system performance criteria according to prespecified bounds within highly uncertain environments and yet remain as maximally different from each other as possible in the decision space.

Given the performance bounds established for the objective in each problem instance, the decision-makers can feel reassured by the stated performance for each of these options while also being aware that the perspectives provided by the set of dissimilar decision variable structures are as maximally different from each other as is feasibly possible. Hence, if there are stakeholders with incompatible standpoints holding diametrically opposing viewpoints, the policy-makers can perform an assessment of these different options without being myopically constrained by a single overriding perspective based solely upon the objective value.

Table 1:	Annual MSW Costs ($ millions) for 11 maximally different alternatives for scenario 1-3

In addition to its alternative generating capabilities, the SO MGA procedure has simultaneously performed exceedingly well with respect to its role in function optimization. Although, a mathematically optimal solution may not provide the best approach to the real problem, it can be observed that the MGA procedure with niching has indeed produced a very good solution value for the originally modelled optimization problem, itself. Namely, it should be explicitly noted that the cost of the overall best solutions produced by the MGA procedure (i.e., the solutions S₀) are indistinguishable from the ones determined in the function optimization process of Yeomans et al. (2003).

In totality, the results of this section underscore several important findings with respect to the use of SO within this MGA procedure:

CONCLUSION

Public environmental policy formulation is a very complicated process that can be impacted by many uncertain factors, unquantified issues and unmodelled objectives. This combination of uncertainties and unknowns together with the competing interests of various stakeholders obligates public policy-makers to integrate many conflicting sources of input into their decision process prior to final policy adoption. In this study, a computational procedure was presented that showed how SO could be used to efficiently generate multiple, maximally different, near-best policy alternatives for difficult, stochastic, environmental problems and the effectiveness of this MGA approach was illustrated using a case study of municipal solid waste management planning.

In this stochastic MGA capacity, SO was shown to efficiently produce numerous solutions possessing the requisite characteristics of the system with each generated alternative providing a very different planning perspective. Because an evolutionary method guides the search, SO actually provides a formalized, population based mechanism for considering many more solution options than would be created by other MGA approaches. However, unlike the deterministic MGA methods, SO incorporates system uncertainties directly into the generation of these alternatives. MSW systems provide an ideal testing environment for illustrating the wide variety of modelling techniques used to support public policy formulation, since they possess all of the prevalent incongruencies and system uncertainties that so often exist in complex planning processes. Since SO techniques can be adapted to model a wide variety of problem types in which system components are stochastic, the practicality of this co-evolutionary MGA approach can clearly be extended into numerous disparate operational and strategic planning applications containing significant sources of uncertainty.