TLDR: This research introduces an efficient method for solving complex optimization problems with multiple conflicting objectives, especially when different problem instances share similar underlying characteristics. The approach involves first solving a single “pilot” instance using advanced, time-consuming algorithms to identify ideal compromise solutions. Then, for all other similar instances, a faster technique called Goal Programming is used, guided by the previously identified ideal solutions, significantly reducing computation time while still achieving high-quality results. The method was successfully tested on a vehicle routing problem.
Many real-world challenges require decision-makers to evaluate solutions based on multiple, often conflicting, objectives. Finding good solutions for these complex problems, especially those with many constraints, can be incredibly difficult even for the most advanced optimization algorithms.
This research paper, titled An Efficient Application of Goal Programming to Tackle Multiobjective Problems With Recurring Fitness Landscapes, proposes an innovative methodology to address this challenge, particularly for scenarios where different instances of a problem share similarities in their underlying structure, known as ‘recurring fitness landscapes’. The authors, Rodrigo Lankaites Pinheiro, Dario Landa-Silva, Wasakorn Laesanklang, and Ademir Aparecido Constantino, introduce a two-stage approach that combines the effectiveness of sophisticated multiobjective algorithms with the efficiency of goal programming.
The core idea is to first solve a single, representative ‘pilot’ instance of a problem using computationally intensive multiobjective algorithms. This step generates a comprehensive set of high-quality compromise solutions. From this set, a decision-maker can then select a ‘target solution’ that best represents their desired trade-offs between the various objectives. Once this target is established, subsequent instances of the same problem scenario can be solved much more quickly using efficient single-objective algorithms guided by Goal Programming, aiming to achieve the chosen target objective values.
Goal Programming is a technique where specific numerical goals are set for each objective. The optimization then focuses on minimizing the deviations from these targets. The paper explores three different ways to define the objective function within Goal Programming: the Chebyshev approach, which minimizes the largest gap to any target; a Derived Weight Vector approach, where weights are calculated from the pilot instance’s solutions; and an Euclidean Distances approach, which minimizes the distance to the target vector, with a mechanism to further improve solutions once the target is met or nearly met.
The methodology was rigorously tested on the Multiobjective Vehicle Routing Problem with Time Windows (MOVRPTW), a well-known and difficult combinatorial optimization problem in logistics. This problem involves planning routes for a fleet of vehicles to deliver goods to customers within specific time windows, while typically aiming to minimize factors like the number of vehicles, total travel distance, makespan (longest route time), total waiting time, and total delay time. The researchers used benchmark instances of the MOVRPTW with varying numbers of customers (50, 150, and 250).
The experimental results demonstrated the effectiveness and efficiency of the proposed methodology. The derived weight vectors consistently showed high effectiveness, indicating their ability to guide the search effectively. Across different datasets, the goal programming approaches, particularly the Euclidean Distances and Chebyshev methods, were able to achieve the target objectives for a high percentage of solutions, and even when targets weren’t perfectly met, the gaps were remarkably small. Furthermore, in many cases, the solutions found were significantly better than the initial target solutions, showcasing the method’s ability to not only meet goals but also to improve upon them.
A key takeaway from the research is the substantial reduction in computation time. While the initial step of obtaining the approximation set for the pilot instance could take hours, the subsequent solving of other instances using the genetic algorithm with goal programming took only minutes. This highlights the practical value of the methodology for real-world applications where similar problem instances arise repeatedly, such as in daily or weekly planning cycles in logistics or scheduling.
Also Read:
- Understanding Key Features for Better Vehicle Routing Solutions
- PARBALANS: Advancing Mixed-Integer Programming with Parallel Adaptive Search
In conclusion, this paper successfully demonstrates that by leveraging the similarities in fitness landscapes across problem instances and combining the strengths of advanced multiobjective algorithms with efficient goal programming, it is possible to find high-quality compromise solutions for complex, highly-constrained problems in a significantly more efficient manner. This approach offers a valuable tool for informed decision-making in various operational scenarios.
