SCRO / Journées de l'optimisation

HEC Montréal, 29-31 mai 2023


HEC Montréal, 29 — 31 mai 2023

Horaire Auteurs Mon horaire

NMD Network Modelling and Design

31 mai 2023 15h40 – 17h20

Salle: St-Hubert (vert)

Présidée par Khalil Al Handawi

4 présentations

  • 15h40 - 16h05

    Drone Network Design With Risk Mitigation

    • Jeremy Nicholson, prés.,
    • Fatma Gzara, University of Waterloo

    With the rise in popularity and research into commercial drone technology over the course of the past decade, e-retailing companies are considering the use of commercial drones for last mile delivery. As drone functionality increases, so too will drone utilization and important logistical questions will need to be answered. Most important among these questions (from a logistical perspective) is how should the airspace be structured to best facilitate drone traffic for the coming decades? While there has been a lot of academic work done dealing with drones from an operational perspective, the majority of the literature assumes little to no airspace structure and instead assumes drones can operate on a direct path or a Euclidean shortest path basis. This is likely to be impractical from both a legislative and technological point of view. In this talk, we will propose a solution for segmenting the airspace for drone traffic and give network design models for drone traffic that prioritize risk reduction, network size and demand satisfaction.

  • 16h05 - 16h30

    GPU Accelerated Network Heuristics for Fast Solutions to Global Supply Planning Problems

    • Henshall Dane, prés., Kinaxis

    Kinaxis has suite of fast heuristics that is used by hundreds of very large manufacturing companies for global supply planning. These heuristics are closely tied to our data model in our in-memory database and are designed for interactive scenario-based planning by business users.

    For the last few years an ongoing research project at Kinaxis has been investigating more general network optimization models and algorithms for finding fast heuristic and meta-heuristic solutions to mathematical optimization problems with similar characteristics as global supply planning.

    This presentation will provide an overview of the models and algorithms developed, along with how they performed on a test set models with tens of millions of variables based on real data from various customers across several industries. Focus will be put on the main heuristic that is used by the various meta-heuristics, including experimental research into the effectiveness of GPU acceleration for this use case.

  • 16h30 - 16h55

    Quality of Service Constrained Routing in High Throughput Satellites

    • Olivier Bélanger, prés., Polytechnique Montréal
    • Stéphane Martel, MDA
    • Antoine Lesage-Landry, Polytechnique Montréal
    • Gunes Karabulut Kurt, Polytechnique Montréal

    The recent deployment of low Earth orbit mega-constellations has yielded an increase in the data rate demanded of each satellite, furthering the use of High Throughput Satellites (HTS). Current state-of-the-art satellites have limited data rates, which pose a challenge as the number of users is increasing. To meet the demand for increased data rates, advanced routing techniques have been developed for the next generation of satellites. While constellation-level routing work has been done, there is a gap in the literature on the internal routing scheme of a single multi-processing unit-based HTS to reach Terabit/second transmission rates. To address this gap, we formulate the problem as a multi-commodity flow instance in which the commodities are data packets with different priorities, the source is the uplink beam, and the sinks include both the downlink beam and the discarded packets. Our approach minimizes packet loss by optimally and adaptively managing the priority queue scheduler and flow exchange between satellite processing modules. We numerically test the routing model and illustrate the advantage of optimal priority scheduling to increase data rate while ensuring high quality of service. We evaluate the model’s performance in simulation and compare it to a traditional overflow minimization routing scheme.

  • 16h55 - 17h20

    Graph representation learning and classification on civil aviation networks

    • Khalil Al Handawi, prés., Université de Montréal
    • Fabian Bastin, DIRO, Université de Montréal

    The analysis of civil aviation networks has gained significant attention in recent years due to the complex nature of air transportation systems and increased collaboration among airlines in the form of codesharing and interlining agreements. One way to gain insights into the behavior and structure of these networks is through community and role detection using graph representation learning techniques.
    We present a framework for graph representation learning and community and role detection on civil aviation networks. The framework is composed of three key components: graph embedding,
    feature extraction, and community and role detection. Graph embedding is used to transform the civil aviation network into a low-dimensional vector space. Feature extraction is then applied to
    extract relevant features, which are then used for community and role detection. We applied several community detection algorithms on real-world data obtained from the international air transportation association (IATA). The proposed framework offers a promising approach for analyzing civil aviation networks and detecting communities and roles within them. We discuss some of the detected communities and offer insights about the state of the aviation network. Further development and application of graph representation learning can lead to improved safety, efficiency, and sustainability of air transportation systems.