"Tackling uncertainty in combinatorial optimization problems: using metaheuristics to efficiently co-generate scenarios and solutions"
José Fernando Oliveira

Uncertainty is receiving increasing attention, in the past years, from the Operational Research community. Methods that acknowledge uncertainty and incompleteness of information are an important research trend. Scenarios arise as key components in many of these methods, as instruments to deal with uncertainty. However, the scenario generation process is often unrealistically simplified.

We propose that metaheuristics, namely based on genetic algorithms, can generate relevant and complex scenarios, without requiring a priori probability distributions. This is of particular interest in practical applications where there are many uncertain parameters, and it is significantly difficult to define their characteristics accurately.
To address two-stage stochastic problems, we propose a method based on a co-evolutionary metaheuristic, where solutions and scenarios are generated and evolve in parallel. The goal of the evolution of the solution population is to obtain values for the first-stage decisions that perform well when compared with the scenario population. The goal of the evolution of the scenario population is to diversify the impact of its elements on the value of solutions. This methodology is able to support decision-makers with different risk profiles.

To illustrate the method, we apply it to the integrated problem of fleet management and pricing for car rental companies under demand and competitor pricing uncertainty. When planning a selling season, a car rental company must decide on the number and type of vehicles in the fleet to meet demand. The demand for the rental products is uncertain and highly price-sensitive, and thus capacity and pricing decisions are interconnected. Moreover, since the products are rentals, capacity “returns”. This creates a link between capacity with fleet deployment and other tools that allow the company to meet demand, such as upgrades, transferring vehicles between locations or temporarily leasing additional vehicles.
An ongoing extension of this work is an innovative scenario generator, based on this idea of impact diversity, that quickly provides representative sets of scenarios that can be used to feed not only a genetic algorithm but any stochastic solution method.