smart.lab.tunisia@gmail.com +216 71 588 443
Connexion

Combinatorial Optimization

Description

Aucune description disponible pour cet axe de recherche.

Membres

Ines Ben Jaafar Ines Ben Jaafar
Ameni Azzouz Ameni Azzouz
Boutheina JLIFI Boutheina JLIFI
Rihab Said Rihab Said
Hamida Labidi Hamida Labidi
Chaouki Bayoudhi Chaouki Bayoudhi

Publications

  • 2025
    Hamida Labidi, Abir Chaabani, Nadia Ben Azzouna

    Hybrid Genetic Algorithm for Solving an Online Vehicle Routing Problem with Time Windows and Heterogeneous Fleet

    This paper proposes a hybrid genetic algorithm to address an online vehicle routing problem with time windows and a heterogeneous fleet, presented at Hybrid Intelligent Systems (HIS 2023)., 2025

    Résumé

    The Vehicle Routing Problem (VRP) is a well-known optimization problem in which we aim traditionally to minimize transportation costs while satisfying customer demands. In fact, most logistics companies use a heterogeneous fleet with varying capacities and costs, presenting a more complex variant known as Rich VRP (RVRP). In this paper, we present a mathematical formulation of the RVRP, considering both hard time windows and dynamically changing requests to be as close as possible to real-life logistics scenarios. To solve this challenging problem, we propose a Hybrid Genetic Algorithm (HGA). The experimental study highlights the out-performance of our proposal when evaluated alongside other algorithms on the same benchmark problems. Additionally, we conduct a sensitivity analysis to illustrate how resilient the algorithm is when problem parameters are altered.

  • Lilia Rejeb, Abir Chaabani, Hajer Safi, Lamjed Ben Said

    Multimodal freight transport optimization based on economic and ecological constraint

    . In: Alharbi, I., Ben Ncir, CE., Alyoubi, B., Ben-Romdhane, H. (eds) Advances in Computational Logistics and Supply Chain Analytics. Unsupervised and Semi-Supervised Learning. Springer, Cha, 2024

    Résumé

    The increasing demand for efficient global supply chain management and faster product delivery has led to a rise in the use of multimodal transportation systems (MFT). One of the key challenges in multimodal transportation is selecting the appropriate freight mode. This decision depends on several factors such as cost, transit time, reliability, mode availability, service frequency, and cargo characteristics. However, existing research often focuses on only two modes, namely trucks and trains, which fails to capture the complexities of real-world freight transportation decisions. Moreover, while reducing travel time and cost are primary objectives for service providers and researchers, other important considerations such as environmental impact are often overlooked. To this end, in this work, the researchers take into account four major modes of transportation (Air, Road, Rail, and Sea/Water) in a multimodal freight context aiming to optimize three distinct objectives: overall transportation cost, transportation time, and CO2 emissions. To solve this problem, the researchers adopt two the well-known metaheuristic algorithms: Tabu Search and the Genetic Algorithm through an experimental study demonstrating the efficacy of these evolutionary solution methods in tackling such challenging optimization problems.

  • Maha Ben Hamida, Ameni Azzouz, Lamjed Ben Said

    An adaptive variable neighborhood search algorithm to solve green flexible job shop problem

    In 2023 9th International Conference on Control, Decision and Information Technologies (CoDIT) (pp. 1403-1408). IEEE., 2023

    Résumé

    Green manufacturing imposes higher expectations on manufacturing engineering, not only with respect to classic competitive factors such as cost, time and quality, but also with sustainable factors such as resources and energy. In this paper, we investigate green flexible job shop scheduling problem (GFJSP) with variable processing speeds. To solve the GFJSP problem, we propose an adaptive Variable Neighborhood Search to minimize the makespan and the total energy consumption. A number of experiments have been conducted to evaluate the performance of our proposed adaptive VNS algorithm. A comparative study was presented and have verified the out performance of the proposed algorithm against other VNS variants.

    Rihab Said, Slim Bechikh, Carlos A. Coello Coello, Lamjed Ben Said

    Solving the Discretization-based Feature Construction Problem using Bi-level Evolutionary Optimization

    2023 IEEE Congress on Evolutionary Computation (CEC), Chicago, IL, USA, 2023, pp. 1-8, 2023

    Résumé

    Feature construction represents a crucial data preprocessing technique in machine learning applications because it ensures the creation of new informative features from the original ones. This fact leads to the improvement of the classification performance and the reduction of the problem dimensionality. Since many feature construction methods require discrete data, it is important to perform discretization in order to transform the constructed features given in continuous values into their corresponding discrete versions. To deal with this situation, the aim of this paper is to jointly perform feature construction and feature discretization in a synchronous manner in order to benefit from the advantages of each process. Thus, we propose here to model the discretization-based feature construction task as a bi-level optimization problem in which the constructed features are evaluated based on their optimized sequence of cut-points. The resulting algorithm is termed Discretization-Based Feature Construction (Bi-DFC) where the proposed model is solved using an improved version of an existing co-evolutionary algorithm, named I-CEMBA that ensures the variation of concatenation trees. Bi-DFC performs the selection of original attributes at the upper level and ensures the creation and the evaluation of constructed features at the upper level based on their optimal corresponding sequence of cut-points. The obtained experimental results on ten high-dimensional datasets illustrate the ability of Bi-DFC in outperforming relevant state-of-the-art approaches in terms of classification results.

    Hamida Labidi, Nadia Ben Azzouna, Khaled Hassine, Mohamed Salah Gouider

    An improved genetic algorithm for solving the multi-objective vehicle routing problem with environmental considerations

    This paper presents an improved genetic algorithm for addressing the multi-objective vehicle routing problem with environmental considerations, published at KES 2023., 2023

    Résumé

    In recent years, the negative impacts of neglecting the environment, particularly global warming caused by greenhouse gases, have gained attention. Many countries and organizations are taking steps to reduce their greenhouse gas emissions and promote sustainable practices. In this paper, we aim to address the gap in the classical Vehicle Routing Problem (VRP) by taking into consideration the environmental effects of vehicles. To find a balance between cost-efficiency and environmental impact, we propose a Hybrid Genetic Algorithm (HGA) to address the Dynamic Vehicle Routing Problem with Time Windows (DVRPTW) and a heterogeneous fleet, taking into account new orders that arrive dynamically during the routing process. This approach takes into consideration the environmental effects of the solutions by optimizing the number and type/size of vehicles used to fulfill both static and dynamic orders. The goal is to provide a solution that is both cost-effective and environmentally friendly, addressing the issue of over-exploitation of energy and atmospheric pollution that threaten our ecological environment. Computational results prove that the hybridization of a genetic algorithm with a greedy algorithm can find high-quality solutions in a reasonable run time.

  • Abir Chaabani, Slim Bechikh, Lamjed Ben Said

    A co-evolutionary hybrid decomposition-based algorithm for bi-level combinatorial optimization problems.

    Soft Computing, 24(10), 7211-7229, 2020

    Résumé

    Bi-level programming problems are a special class of optimization problems with two levels of optimization tasks. These problems have been widely studied in the literature and often appear in many practical problem solving tasks. Although many applications fit the bi-level framework, however, real-life implementations are scarce, due mainly to the lack of efficient algorithms able to handle effectively this NP-hard problem. Several solution approaches have been proposed to solve these problems; however, most of them are restricted to the continuous case. Motivated by this observation, we have recently proposed a Co-evolutionary Decomposition-based Algorithm (CODBA) to solve bi-level combinatorial problems. CODBA scheme has been able to bring down the computational expense significantly as compared to other competitive approaches within this research area. In this paper, we further improve CODBA approach by incorporating a local search procedure to make the search process more efficient. The proposed extension called CODBA-LS includes a variable neighborhood search to the lower-level task to help in faster convergence of the algorithm. Further experimental tests based on the bi-level production–distribution problems in supply chain management model on a set of artificial and real-life data turned out to be effective on both computation time and solution quality.

    Ameni Azzouz, Meriem Ennigrou, Lamjed Ben Said

    Solving flexible job-shop problem with sequence dependent setup time and learning effects using an adaptive genetic algorithm

    International Journal of Computational Intelligence Studies, 9(1-2), 18-32., 2020

    Résumé

    For the most schedulling problems studied in literature, job processing times are assumed to be known and constant over time. However, this assumption is not appropriate for many realistic situations where the employees and the machines execute the same task in a repetitive manner. They learn how to perform more efficiently. As a result, the processing time of a given job is shorter if it is scheduled later, rather than earlier in the sequence. In this paper, we consider the flexible job-shop problem (FJSP) with two kinds of constraint, namely, the sequence-dependent setup times (SDST) and the learning effects. Makespan is specified as the objective function to be minimised. To solve this problem, an adaptive genetic algorithm (AGA) is proposed. Our algorithm uses an adaptive strategy based on: 1) the current specificity of the search space; 2) the preceding results of already used operators; 3) their associated parameter settings. We adopt this strategy in order to maintain the balance between exploration and exploitation. Experimental studies are presented to assess and validate the benefit of the incorporation of the learning process to the SDST-FJSP over the original problem.

    Rihab Said, Slim Bechikh, Ali Louati, Abdulaziz Aldaej, Lamjed Ben Said

    Solving Combinatorial Multi-Objective Bi-Level Optimization Problems Using Multiple Populations and Migration Schemes

    IEEE Access, vol. 8, pp. 141674-141695, 2020

    Résumé

    Many decision making situations are characterized by a hierarchical structure where a lower-level (follower) optimization problem appears as a constraint of the upper-level (leader) one. Such kind of situations is usually modeled as a BLOP (Bi-Level Optimization Problem). The resolution of the latter usually has a heavy computational cost because the evaluation of a single upper-level solution requires finding its corresponding (near) optimal lower-level one. When several objectives are optimized in each level, the BLOP becomes a multi-objective task and more computationally costly as the optimum corresponds to a whole non-dominated solution set, called the PF (Pareto Front). Despite the considerable number of recent works in multi-objective evolutionary bi-level optimization, the number of methods that could be applied to the combinatorial (discrete) case is much reduced. Motivated by this observation, we propose in this paper an Indicator-Based version of our recently proposed Co-Evolutionary Migration-Based Algorithm (CEMBA), that we name IB-CEMBA, to solve combinatorial multi-objective BLOPs. The indicator-based search choice is justified by two arguments. On the one hand, it allows selecting the solution having the maximal marginal contribution in terms of the performance indicator from the lower-level PF. On the other hand, it encourages both convergence and diversity at the upper-level. The comparative experimental study reveals the outperformance of IB-CEMBA on a multi-objective bi-level production-distribution problem. From the effectiveness viewpoint, the upper-level hyper-volume values and inverted generational distance ones vary in the intervals [0.8500, 0.9710] and [0.0072, 0.2420], respectively. From the efficiency viewpoint, IB-CEMBA has a good reduction rate of the Number of Function Evaluations (NFEs), lying in the interval [30.13%, 54.09%]. To further show the versatility of our algorithm, we have developed a case study in machine learning, and more specifically we have addressed the bi-level multi-objective feature construction problem.

  • Meriem Sebai, Ezzeddine Fatnassi, Lilia Rejeb

    A honeybee mating optimization algorithm for solving the static bike rebalancing problem

    Proceedings of the Genetic and Evolutionary Computation Conference Companion, ACM. Presented at the GECCO ’19: Genetic and Evolutionary Computation Conference, ACM New York (pp. 77-78). Prague Czech Republic. doi:10.1145/3319619, 2019

    Résumé

    This paper proposes a new approach to solve the Bike Rebalancing Problem (BRP) based on the Honey-Bee Mating Optimization (HBMO) algorithm. The aim is to reduce the overall traveling cost of redistribution operations under various constraints. The performance of the proposed algorithm is evaluated using a set of benchmark instances for the BRP. Preliminary results are obtained and showed that the proposed approach is promising.

  • Abir Chaabani, Lamjed Ben Said

    Hybrid CODBA-II Algorithm Coupling a Co-Evolutionary Decomposition-Based Algorithm with Local Search Method to Solve Bi-Level Combinatorial Optimization

    International Conference on Tools with Artificial Intelligence ICTAI’18, Volos, 2018

    Résumé

    Bi-level optimization problems (BLOPs) are a class of challenging problems with two levels of optimization tasks. The usefulness of bi-level optimization in designing hierarchical decision processes prompted several researchers, in particular the evolutionary computation community, to pay more attention to such kind of problems. Several solution approaches have been proposed to solve these problems; however, most of them are restricted to the continuous case. Motivated by this observation, we have recently proposed a Co-evolutionary Decomposition-based Algorithm (CODBA-II) to solve combinatorial bi-level problems. CODBA-II scheme has been able to improve the bi-level performance and to bring down the computational expense significantly as compared to other competitive approaches within this research area. In this paper, we present an extension of the recently proposed CODBA-II algorithm. The improved version, called CODBA-IILS, further improves the algorithm by incorporating a local search process to both upper and lower levels in order to help in faster convergence of the algorithm. The improved results have been demonstrated on two different sets of test problems based on the bi-level production-distribution problems in supply chain management, and comparison results against the contemporary approaches are also provided.

    Ines Seghir, Ines Ben Jaafar, khaled Ghedira

    A Multi-Agent Based Optimization Method for Combinatorial Optimization Problems

    International Journal of Artificial Intelligence Tools, 2018

    Résumé

    This paper introduces a Multi-Agent based Optimization Method for Combinatorial Optimization Problems named MAOM-COP. In this method, a set of agents are cooperatively interacting to select the appropriate operators of metaheuristics using learning techniques. MAOM-COP is a flexible architecture, whose objective is to produce more generally applicable search methodologies. In this paper, the MAOM-COP explores genetic algorithm and local search metaheuristics. Using these metaheuristics, the decision-maker agent, the intensification agents and the diversification agents are seeking to improve the search. The diversification agents can be divided into the perturbation agent and the crossover agents. The decision-maker agent decides dynamically which agent to activate between intensification agents and crossover agents within reinforcement learning. If the intensification agents are activated, they apply local search algorithms. During their searches, they can exchange information, as they can trigger the perturbation agent. If the crossover agents are activated, they perform recombination operations. We applied the MAOM-COP to the following problems: Quadratic assignment, graph coloring, winner determination and multidimensional knapsack. MAOMCOP shows competitive performances compared with the approaches of the literature.

    Abdelkader Dekdouk, Ameni Azzouz, Hiba Yahyaoui, Saoussen Krichen

    Solving energy ordering problem with multiple supply-demand using Bilevel optimization approach

    Procedia Computer Science, 130, 753-759., 2018

    Résumé

    We develop in this paper an energy ordering problem with multiple energy supplying sources and multiple traders trying to satisfy customers’ demands. Such a supply chain network is split of three main layers: the set of energy generation plants (suppliers), a set of traders trying to expect and satisfy customer’s demands dispatched. Following the new investment in renewable energy, customers have the option to choose the nature of its electricity. Customer choice has an impact on the future energy supply chain. For that, we deal with the customer choice in our considered problem. Motivated by this architecture, we propose an evolutionary algorithm-based on bi-level optimization model is developed to handle this problem. The performance of the proposed model is evaluated by numerical experiments based on real-world data.

  • Ameni Azzouz, Meriem Ennigrou, Lamjed Ben Said

    A hybrid algorithm for flexible job-shop scheduling problem with setup times

    International Journal of Production Management and Engineering, 5(1), 23-30, 2017

    Résumé

    Job-shop scheduling problem is one of the most important fields in manufacturing optimization where a set of n jobs must be processed on a set of m specified machines. Each job consists of a specific set of operations, which have to be processed according to a given order. The Flexible Job Shop problem (FJSP) is a generalization of the above-mentioned problem, where each operation can be processed by a set of resources and has a processing time depending on the resource used. The FJSP problems cover two difficulties, namely, machine assignment problem and operation sequencing problem. This paper addresses the flexible job-shop scheduling problem with sequence-dependent setup times to minimize two kinds of objectives function: makespan and bi-criteria objective function. For that, we propose a hybrid algorithm based on genetic algorithm (GA) and variable neighbourhood search (VNS) to solve this problem. To evaluate the performance of our algorithm, we compare our results with other methods existing in literature. All the results show the superiority of our algorithm against the available ones in terms of solution quality.

  • Abir Chaabani, Slim Bechikh, Lamjed Ben Said

    A Co-Evolutionary Decomposition-based Algorithm for Bi-Level combinatorial Optimization

    IEEE Congress on Evolutionary Computation CEC’15, Japan, 1659-1666, 2015

    Résumé

    Several optimization problems encountered in practice have two levels of optimization instead of a single one. These BLOPs (Bi-Level Optimization Problems) are very computationally expensive to solve since the evaluation of each upper level solution requires finding an optimal solution for the lower level. Recently, a new research field, called EBO (Evolutionary Bi-Level Optimization) has appeared thanks to the promising results obtained by the use of EAs (Evolutionary Algorithms) to solve such kind of problems. Most of these promising results are restricted to the continuous case. Motivated by this observation, we propose a new bi-level algorithm, called CODBA (CO-Evolutionary Decomposition based Bi-level Algorithm), to tackle combinatorial BLOPs. The basic idea of our CODBA is to exploit decomposition, parallelism, and co-evolution within the lower level in order to cope with the high computational cost. CODBA is assessed on a set of instances of the bi-level MDVRP (MultiDepot Vehicle Routing Problem) and is confronted to two recently proposed bi-level algorithms. The statistical analysis of the obtained results shows the merits of CODBA from effectiveness and efficiency viewpoints.