JOPT2025

HEC Montreal, 12 — 14 May 2025

JOPT2025

HEC Montreal, 12 — 14 May 2025

Schedule Authors My Schedule

ICVNS III

May 13, 2025 10:30 AM – 12:10 PM

Location: Serge-Saucier (Blue)

Chaired by Daniel Aloise

4 Presentations

  • 10:30 AM - 10:55 AM

    Solving the Minimum Positive Influence Dominating Set Problem in Social Networks Using Metaheuristics

    • Penedo Iván, presenter, Universidad Rey Juan Carlos
    • Lozano-Osorio Isaac, Universidad Rey Juan Carlos
    • Sánchez-Oro Jesús, Universidad Rey Juan Carlos
    • Cordón Óscar, Universidad de Granada

    The rise of the internet and social networks has posed new challenges in studying people's behavior on these platforms. People tend to trust or align with a small group of users, leading to the development of viral marketing techniques to effectively propagate information about products or services. This has led to the definition of problems related to social influence maximization/minimization and dominance sets.
    The Minimum Positive Influence Dominating Sets (MPIDS) problem involves finding a minimum cardinality dominance set to influence an entire social network. For a node to be influenced, at least half of its neighbors must be in the dominance set.
    Considering that MPIDS is an NP-hard problem, where exact approximations are impractical due to the size of social networks, this work proposes using the Basic Variable Neighborhood Search (BVNS). Given an initial solution, this metaheuristic consists of two phases: a shaking and an improvement phase. In the shaking phase, the solution is modified by removing and reconstructing it using a greedy approach. The improvement phase involves an innovative local search strategy based on generating holes, which removes the delta-neighborhood of a node to facilitate an greedy solution reconstruction.

  • 10:55 AM - 11:20 AM

    Adaptive Variable Neighborhood Search for Tourist Trip Recommendation

    • Cristina González Navasa, Ph.D. Student, I3MA. Universidad de La Laguna
    • José Andrés Moreno Pérez, presenter, IUDR. Universidad de La Laguna
    • Helí Alonso Afonso, Master Student. Universidad de La Laguna
    • Julio Brito Santana, IUDR. Universidad de La Laguna

    Tourists use information about their preferences and the points of interest to select their itinerary at destinations. Generally, they plan their routes in advance, selecting the points to visit and the order in which they are visited, taking into account information that is often imprecise and changing. Intelligent tourist recommendation systems are capable of selecting the optimal route, taking into account the corresponding constraints, and providing the user with detailed information about the selected points of interest and the amount of time on each visit and during the travel between them. However, changes or unforeseen events occur during the tour, which force the route to be modified dynamically. The Tourist Trip Design Problems (TTDP) are formulated as versions of the Team Orienteering Problem (TOP) with the modifications that each case determines. When any of these changes occur, the new situation can also be modeled as a similar problem, with the additional constraints. Several metaheuristics have been used to address TTDP, including VNS. In this work we experiment with Adaptive VNS that dynamically determines which are the best neighbourhoods to use and how, in each type of situation in which it is necessary to modify the route. We review previous works on applying AVNS to routing problems and VNS to TTDP to select which types of moves are considered and the techniques to assess their performance and select them. The characteristics of the problems that arise in the most frequent circumstances that motivate the change in the route are studied: environmental events, unavailables point of interest, lengthened or shortened visit times or journey times between points. This work is aimed to use VNS into a tool for recommending tourist routes that is being developed and designed in collaboration with a technology company with experience in the tourism sector.

    keywords: Adaptive Variable Neighborhood Search (AVNS), Tourist Trip Design Problem (TTDP), Intelligent Tourist Trip Recommender (ITTR)

  • 11:20 AM - 11:45 AM

    Multi-Objective VNS Tourism Planning: Optimizing Weekend Itineraries in Montreal

    • Filipe Pessoa Sousa, presenter, Universidade do Estado do Rio de Janeiro
    • Augusto Magalhães Pinto de Mendonça, Universidade Federal Fluminense
    • Igor Machado Coelho, Universidade Federal Fluminense

    This research presents a multi-objective optimization approach for planning weekend tourist routes in Montreal. The problem addresses four conflicting objectives: minimizing costs and travel time while maximizing the number of visited attractions and attraction quality based on public ratings. We compare a Multi-Objective Variable Neighborhood Search (MOVNS) algorithm against NSGA-II, both generating itineraries that respect practical constraints including operation hours and transportation limitations. Our approach incorporates walking, metro, and car transportation modes between hotels and attractions over a two-day period. Using real data from Montreal's top attractions and travel information from OSRM, we evaluate both methods through multi-objective metrics such as Pareto coverage.

  • 11:45 AM - 12:10 PM

    Efficient Big Data Clustering via VNS-Accelerated Optimization

    • Rustam Mussabayev, presenter, 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.

Back