SCRO / Journées de l'optimisation

HEC Montréal, 29-31 mai 2023


HEC Montréal, 29 — 31 mai 2023

Horaire Auteurs Mon horaire

IDI Industrial Day I

31 mai 2023 10h30 – 12h10

Salle: Walter Capital (bleu)

Présidée par Amira Dems

3 présentations

  • 10h30 - 10h55

    Fast and Efficient Last Mile Package Delivery using K-Means and K-Opt Techniques

    • Geoffrey Glangine, prés., Timesphere
    • Sandrine Paroz, Timesphere

    This research aims to optimize the delivery of a large volume of packages by clustering them into small groups based on their geographical proximity using K-means clustering. To overcome geographical barriers such as highways, bridges, and rivers, polygons are defined, and the K-means distance calculation is heavily penalized for packages that are not in the same polygon. Once the clustering is complete, a balancing phase is initiated, which aims to assign an equal number of stops to each driver. This phase uses a hierarchical clustering algorithm based on the real driving distance between each centroid calculated in the first phase. Finally, the K-opt optimization method based on Keld Helsgaun's implementation is employed to find the optimal TSP tour. Notably, the K-opt heuristic can almost always find the optimal solution for a standard route of approximately 150 packages in about 1 second of computation time. The effectiveness of the K-opt implementation is compared with the LinKernighan heuristic. The findings suggest that the K-opt implementation is more likely to find the optimal solution. Overall, this research provides a practical and effective solution for optimizing package delivery, which can significantly reduce delivery time, increase efficiency, and improve customer satisfaction.

  • 10h55 - 11h20

    Practical introduction to nonlinear programming with Artelys Knitro

    • Carlyle Deligny, Artelys
    • Renaud Saltet, prés., Artelys

    Problems encountered by operational research experts are generally complex and intrinsically nonlinear. It is therefore necessary to be familiar with nonlinear optimization methods using the appropriate tools. This tutorial will present some examples of nonlinear problems, usually solved using a linear relaxation, for which a direct approach is more relevant. This tutorial is for an audience familiar with combinatorial programming and linear programming. The participants will practice nonlinear programming methods using the Artelys Knitro solver in a Python notebook, through different examples (
    The goal of this tutorial is to enable participants, when confronted with a non-linear problem, to identify what type of nonlinear problem it is, what methods and tools are adapted to solve it, and how to use them.

    ***Notes: This session presents practical exercises to be performed by the participants. A computer and an Internet connection are required to participate.

  • 11h20 - 11h45

    Integrated Logistics Network Design at Hydro-Québec

    • Amira Dems, prés., Institut de recherche d’Hydro-Québec
    • Mouad Morabit, IREQ

    Hydro-Quebec is entitled to provide different services to its final customers. It has to satisfy the population service demand at minimal cost. It does so by locating the service centers (SC), determining the number of service teams in each facility, and then allocating the municipalities/cities to the proper service centers. This project focuses on developing a decision support tool for planners to optimize these decisions and to set SC utilization levels in a centralized manner. It's vision is to lay the foundations of the new logistic network design for 10 years into the future.
    Since the network design is driven by data, and in particular, the future demand data, a prediction module is addressed to predict the customer service demand. This module lies at the heart of the whole process.