4 Presentations

• 
  10:30 AM - 10:55 AM

  20 years of ICVNS!

  • Daniel Aloise, presenter, Polytechnique Montréal
  • Eduardo Pardo, Universidad Rey Juan Carlos

• 
  10:55 AM - 11:20 AM

  A variable neighborhood search heuristic for semi-supervised minimum sum-of-squares clustering

  • Mahuton Hugues Midingoyi, presenter, Polytechnique Montréal
  • André Meneses , Universidade Federal do Rio Grande do Norte
  • Daniel Aloise, Polytechnique Montréal

  Semi-supervised clustering is an unsupervised learning model that incorporates prior information to enhance the learning process. Among various clustering objectives, the minimum sum-of-squares clustering (MSSC) is widely used to partition data by minimizing intra-cluster variances. In our work, we propose a Variable Neighborhood Search (VNS) heuristic for MSSC, where prior information is given in the form of pairwise must-link and cannot-link constraints.
  Our approach relies on the efficient evaluation of data points reassignments among the clusters after the model reformulation. Computational experiments indicate that, in most cases, our proposed VNS heuristic outperforms the solutions produced by the state-of-the-art heuristic algorithms within a similar computational time.

• 
  11:20 AM - 11:45 AM

  An efficient implementation of a VNS heuristic for the weighted fair sequences problem

  • Caroline Rocha, Ivado Labs
  • Bruno Jefferson de Sousa, Universidade Federal da Paraíba
  • Daniel Aloise, presenter, Polytechnique Montréal
  • Lucidio Cabral, Universidade Federal da Paraíba

  In the Weighted Fair Sequences Problem (WFSP), one aims to schedule a set of tasks or activities so that the maximum product between the largest temporal distance between two consecutive executions of a task and its priority is minimized. The WFSP covers a large number of applications in different areas, ranging from automobile production on a mixed-model assembly line to the sequencing of interactive applications to be aired in a Digital TV environment. This paper proposes an iterative heuristic method for the WFSP centered on an efficient implementation of a variable neighborhood search heuristic. Computational experiments on benchmark instances show that the proposed metaheuristic outperforms the state-of-the-art method proposed to the problem, obtaining comparable solution values in much less computational time.

• 
  11:45 AM - 12:10 PM

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

  • Megh KC, presenter, 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.