Following our Net Zero Operations Research Assistant, Joan Alza Santos’ presentation at the ‘Problem Solving’ seminar at the National Subsea Centre, we’ve taken a closer look at his project and explored the importance, the role and the implication of dynamic optimisation in several applications.
What Are Dynamic Optimisation Problems?
Dynamic optimisation is the process of finding the best possible solutions or decisions from a finite or infinite set of possibilities over time, subject to constraints and changes. Dynamic optimisation problems are typically represented by mathematical models (either deterministic or stochastic) that enclose the changing nature of the problems, the objectives to be achieved and constraints to be satisfied considering the concept of time.
In order to solve dynamic optimisation problems, specialised algorithms and techniques are developed to optimise and track ‘good’ solutions. Approximation methods, heuristic and meta-heuristic algorithms and simulation-based approaches are commonly used to solve the problem quickly and efficiently, and deal with the computational complexity and uncertainty associated with dynamic optimisation.
The Role of Dynamic Optimisation
Dynamic optimisation plays a vital role in enabling optimal decision-making, resource allocation or risk mitigation, in addition to the development of algorithms with enhanced adaptability for changing environments. That is, a framework is usually designed to model a changing environment, while algorithms make optimal decisions or take the best action over time.
Examples of dynamic optimisation problems can be found in many real-world applications, such as supply chain management, transportation, energy systems, telecommunications and resource allocation. For instance, in the dynamic vehicle routing problem, the objective is to optimise the route and schedule of vehicles over time, while the customer demand and traffic conditions change over time.
Challenges
The main challenge in dynamic optimisation emerges from the changing and evolving nature of the problem. Problem objectives, constraints, variables or conditions may be inserted, deleted or modified over time. The main challenges of dynamic optimisation problems include the complexity, unpredictability and the uncertainty of the changing problem.
Besides, specific algorithms are frequently designed to handle changes in the problem. While algorithms are commonly designed using benchmark generators, real-world applications often employ restart-based algorithms due to their simplicity in reacting to problem changes. However, practitioners generally avoid the restart approach due to two main reasons: first, detecting problem changes can be challenging and may not always be possible; and second, the restart approach discards the information that has been previously gained by the algorithm, making it less desirable in practice for prediction or learning-approaches.
Finally, the dynamic optimisation community has pointed out that gaps exist between academic research and real-world problems. Adaptive algorithms are usually developed for academic problems that may have little relevance in the real-world. In other words, problems used in academia may not reflect some characteristic dynamics of real-world applications.
About the Project
This research project aims to address certain gaps between academic research and real-world problems. The project was designed taking into consideration the challenges in the field and targets the following topics:
The need to extend the definition for dynamic optimisation problems
In academia, a dynamic optimisation problem is defined as a sequence of static related problems linked up by some dynamic rules or as a problem that has time-dependent parameters in its mathematical expression while the algorithm reacts to changes. Hence, algorithms are typically designed to deal with problem changes over time. However, in case of a large change, where there is a little resemblance between the previous and new environment, it might be more beneficial to simply restart the search of the algorithm (as done in many real-world applications).
Present a real-world benchmark generator
Based on the real-world data derived from the operations of UK haulage company, ARR Craib Ltd, situated around the Port of Aberdeen, the goal is to develop a benchmark generator that creates specific dynamic vehicle scheduling problem instances in a heterogeneous context. Precisely, the idea is to model the inflow of jobs, their allocation into vehicles and the availability of resources over time using synthetic data extracted from historical real-world events.
To discover more about how our Net Zero Operations team is solving real-world problems and the other impactful research projects that are currently being undertaken, view our dedicated Net Zero Operations webpage.
