3 présentations

• 
  10h30 - 10h55

  Efficient Big Data Clustering via VNS-Accelerated Optimization

  • Rustam Mussabayev, prés., Satbayev University
  • Ravil Mussabayev, Satbayev University
  • Alymzhan Toleu, Satbayev University
  • Ainur Ibraimova, Satbayev University

  K-means clustering is a fundamental technique in data mining, yet its performance degrades significantly when applied to massive datasets. To address this limitation, we previously proposed a simple and effective big data clustering algorithm called Big-means. In line with the “Less is More” approach (LIMA), Big-means was designed to be as simple as possible and did not incorporate any metaheuristics. In the present work, we aim to improve the performance of Big-means by integrating it into the Variable Neighborhood Search (VNS) framework. The core idea is to perform a simultaneous search along two dimensions: 1. Exploring partial solution landscapes created from random samples of the original massive dataset, and 2. Cycling through increasingly broader neighborhoods within these landscapes to refine the current best solution. A special neighborhood structure was defined where two solutions are considered neighbors if they differ in only a fixed number of centroids. Navigating this structure according to VNS methodology provides a more progressive and strategic search through the solution space. The dual-modality approach, combined with the integration of the VNS metaheuristic, enables effective perturbation of the incumbent solution, allowing the algorithm to escape local minima through deeper exploration of each solution landscape. Controlling the sample size in each iteration reduces time complexity and ensures scalability to large datasets. Extensive testing on real-world datasets shows that integrating VNS into Big-means significantly boosts both clustering accuracy and computational efficiency. The proposed method outperforms existing techniques and the original Big-means, establishing a new state-of-the-art for K-means clustering in big data environments.

• 
  10h55 - 11h20

  A Machine Learning enhanced Variable Neighborhood Search approach for the Uncapacitated Facility Location problem

  • Martín-García Lucas, prés., Universidad Rey Juan Carlos
  • Lozano-Osorio Isaac, Universidad Rey Juan Carlos
  • Colmenar J. Manuel, Universidad Rey Juan Carlos
  • Melián-Batista Belén, Universidad de La Laguna

  The Uncapacitated Facility Location Problem (UFLP) is widely recognized as a relevant problem in logistics, resource distribution, and telecommunications network planning. Given a set of potential facility locations and a set of customers, the goal is to determine which facilities to open in order to serve all customers while minimizing both opening and assignment costs. Since this problem is classified as NP-hard, obtaining exact solutions at large scales could not be possible, thereby motivating the use of approximation techniques and metaheuristics. Although early studies used exact formulations derived from the UFLP model, recent research has emphasized the efficacy of approximate and metaheuristic algorithms, which achieve high-quality solutions with substantially reduced computational effort. This work introduces a Variable Neighborhood Search approach to tackle this problem. In order to guide the search toward higher-quality solutions, machine learning techniques have been incorporated to this process. Experimental results on well-known benchmark datasets demonstrate that our method reaches solutions very close to the optimal values, with significantly shorter execution times, which makes it competitive with the state-of-the-art algorithms.

• 
  11h20 - 11h45

  Multi-Stage, Multi-School Electric Bus Routing and Scheduling Optimization with Bus Re-use Using Metaheuristics

  • Megh KC, prés., University at Buffalo

  The school bus system is the largest form of public transportation by fleet size in the US and one of the major contributors to environmental emissions. In light of the nation’s priority towards school bus electrification, it is urgently needed. Electric school bus routing and scheduling are crucial aspects of the school bus transport system because of the high capital investment, operation frequency, battery range anxiety, and charging constraints. Successful implementation of the efficient electric bus system operation optimization in multiple schools saves the daily operation cost for school districts, would be vital for the future of school transportation, and positively contributes towards sustainability. This study simultaneously addresses electric school bus dynamic route optimization, integrated school bus scheduling in multiple schools, and route recharge scheduling with staggered school bell times. To generate high optimization efficiency for larger networks, we consider two-stage optimization: the first stage is for generating optimized routes for individual schools, thereby using multi-objective optimization models. The second stage is the integrated bus scheduling for multiple schools with different bell times. We consider the reuse of buses during the scheduling process by allowing charging after finishing a trip. In both stages, we proposed linearized mixed integer programming (MIP) model and a simulation-based VNS-SA hybrid metaheuristic algorithm to get the optimal or near-optimal solutions with greatly enhanced performance. The novelty in metaheuristics is a combination of variable neighborhood search (VNS) and simulated annealing (SA) as our solution approach. Using two stages, large network problems can be decomposed, and we were able to solve around 10,000 node problems. A real-world routing and scheduling scenario for multiple schools in a salt lake city school district, Utah is solved using the generated multi-stage model and resulted a 37% reduction of fleets for high and middle schools in that district. The results showed a good flexibility and optimization capability of our model that could be vital for accelerated school transport electrification.