A co-evolutionary matheuristic for the car rental capacity-pricing stochastic problem

Our paper “A co-evolutionary matheuristic for the car rental capacity-pricing stochastic problem” by Beatriz Oliveira, Maria Antónia Carravilla, José Fernando Oliveira and Alysson M Costa has been accepted for publication at the European Journal of Operational Research. This paper contains part of the results from Beatriz’s PhD thesis.

Link to paper.

Abstract

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.

We propose a methodology that aims to support decision-makers with different risk profiles plan a season, providing good solutions and outlining their ability to deal with uncertainty when little information about it is available. This matheuristic is based on a co-evolutionary genetic algorithm, where parallel populations of solutions and scenarios co-evolve. The fitness of a solution depends on the risk profile of the decision-maker and its performance against the scenarios, which is obtained by solving a mathematical programming model. The fitness of a scenario is based on its contribution in making the scenario population representative and diverse. This is measured by the impact the scenarios have on the solutions.

Computational experiments show the potential of this methodology regarding the quality of the solutions obtained and the diversity and representativeness of the set of scenarios generated. Its main advantages are that no information regarding probability distributions is required, it supports different decision-making risk profiles, and it provides a set of good solutions for an innovative complex application.


Algorithms for the power-p Steiner tree problem in the Euclidean plane

Our paper “Algorithms for the power-p Steiner tree problem in the Euclidean plane” by Christina Burt, Alysson Costa and Charl Ras has been published on a special issue on Exact and Heuristic Solutions for Optimization Problems from RITA.

Link to the full text.

Abstract

We study the problem of constructing minimum power-$p$ Euclidean $k$-Steiner trees in the plane. The problem is to find a tree of minimum cost spanning a set of given terminals where, as opposed to the minimum spanning tree problem, at most $k$ additional nodes (Steiner points) may be introduced anywhere in the plane. The cost of an edge is its length to the power of $p$ (where $p\geq 1$), and the cost of a network is the sum of all edge costs. We propose two heuristics: a “beaded” minimum spanning tree heuristic; and a heuristic which alternates between minimum spanning tree construction and a local fixed topology minimisation procedure for locating the Steiner points. We show that the performance ratio $\kappa$ of the beaded-MST heuristic satisfies $\sqrt{3}^{p-1}(1+2^{1-p})\leq \kappa\leq 3(2^{p-1})$. We then provide two mixed-integer nonlinear programming formulations for the problem, and extend several important geometric properties into valid inequalities. Finally, we combine the valid inequalities with warm-starting and preprocessing to obtain computational improvements for the $p=2$ case.


Active management of environmental water to improve ecological outcomes

Our paper “Active management of environmental water to improve ecological outcomes” has been published at the Journal of Water Resources Planning and Management.

[doi] [cited by] [preprint] Active management of environmental water to improve ecological outcomes.  Horne, A., Kaur S., Szemis, J., Costa, A.M., Nathan, R., Angus Webb, J., Stewardson, M., Boland, N. , Journal of Water Resources Planning and Management 144 (2018)

Abstract:

Environmental water is being embraced by governments around the world as a means to partly restore rivers impacted by excessive river regulation and to protect those that are not yet overregulated. In cases where environmental water is provided as a water right, managers can make ongoing active management decisions regarding the timing and magnitude of environmental flows in response to changing conditions and understanding of environmental demands. Such active management should lead to improved environmental outcomes but also comes with a significant ongoing management cost when compared to rules-based environmental water releases. This study uses an optimization tool to examine the environmental gain achievable with the active management of environmental water compared to rules-based releases. A case study of the Yarra River, Victoria, Australia, demonstrates the potential for substantial environmental gains achieved through active management of environmental water.

 


Congratulations to Dr. Cheng Cheng

Cheng Cheng has had her PhD thesis approved at the University of Melbourne. Her thesis is titled “Optimisation of Disaster Waste Management Systems” and proposes models and algorithms for planning waste removal after disasters. Among other results, Cheng analysed the effect of using intermediate waste processing centers in the efficiency of the operations.

Congratulations to Cheng!

 

 

 


Congratulations to Dr. Beatriz Oliveira

Beatriz Brito Oliveira has defended her PhD thesis at the University of Porto. Her thesis is titled “Fleet and revenue management in car rental: quantitative approaches for optimization under uncertainty” and was supervised by Prof. Maria Antònia Carravilla and Prof. José Fernando Oliveira.

Beatriz spent three months with our research group in Melbourne. During this time she worked in the last chapter of her thesis, finalising the development of a matheuristic for the stochastic version of the car rental planning problem she tackled.

Congratulations to Beatriz, Maria Antònia and José Fernando for this strong piece of research!


Optimising elective surgery schedules

Our paper A Sequential Stochastic Mixed Integer Programming Model For Tactical Master Surgery Scheduling, by Ashwani Kumar, Mark Fackrell, Peter Taylor and Alysson M. Costa is now available online.

Abstract:

In this paper, we develop a stochastic mixed integer programming model to optimise the tactical master surgery schedule (MSS) in order to achieve a better patient flow under downstream capacity constraints. We optimise the process over several scheduling periods and we use various sequences of randomly generated patients’ length of stay scenario realisations to model the uncertainty in the process. This model has the particularity that the scenarios are chronologically sequential, not parallel. We use a very simple approach to enhance the non-anticipative feature of the model, and we empirically demonstrate that our approach is useful in achieving the desired objective. We use simulation to show that the most frequently optimal schedule is the best schedule for implementation. Furthermore, we analyse the effect of varying the penalty factor, an input parameter that decides the trade-off between the number of cancellations and occupancy level, on the patient flow process. Finally, we develop a robust MSS to maximise the utilisation level while keeping the number of cancellations within acceptable limits.


AMSI OPTIMISE 2018

Returning in 2018, AMSI Optimise is an annual networking and research-training event that aims to strengthen mathematical optimisation research engagement and its applications across industry.

This event will comprise a three-day industry-focused conference, followed by a two-day research workshop. The symposium features expert and end-user talks, international guest speakers, collaboration showcases, industry challenge sessions and tutorials. The themes of the 2018 conference are Decision Making Under Uncertainty and Humanitarian Applications.

AMSI Optimise is aimed at:

  • anyone using optimisation, with opportunities to learn more about the current state of the art and to connect with others who have similar interests
  • industry practitioners interested in exploring the benefits of engagement with optimisation research
  • academics and postgraduate students wanting to better understand drivers and needs in this area

The event provides a forum to bring together people from the diverse companies and research disciplines that use and develop optimisation models and software. It provides a platform for research training and developing new collaborations in this vital area through PhD internships, research partnerships and postgraduate research projects.