SCRO / Journées de l'optimisation

HEC Montréal, 29-31 mai 2023


HEC Montréal, 29 — 31 mai 2023

Horaire Auteurs Mon horaire

TSP Traveling Salesman Problem

31 mai 2023 15h40 – 17h20

Salle: Xerox Canada (jaune)

Présidée par Isaac Rudich

4 présentations

  • 15h40 - 16h05

    Gurobi Machine Learning: Incorporate your Machine Learning Models into Optimization

    • Zed Dean, prés., Gurobi

    Gurobi is making it easier to plug your predictive models directly into your optimization model. Gurobi has an open-source Python package that allows users to add trained machine learning regressors as a constraint to a Gurobi model (e.g., from scikit-learn, TensorFlow/Keras, or PyTorch). Thus, allowing for tighter integration between trained predictions and optimal decision-making.

    This tutorial will introduce the Gurobi Machine Learning package and how it fits into an optimization application. Then we will explore how these machine-learning models are incorporated into a Gurobi model through a couple of examples. Finally, we will tune the models to minimum generated errors.

  • 16h05 - 16h30

    Stochastic Traveling Salesman Problem With Generalized Latency (CANCELED)

    • Elmira Fathipasandideh, prés.,
    • Fausto Errico,

    This talk will introduce the Stochastic Traveling Salesman Problem with Generalized Latency (STSP GL), a newly emerged subproblem in the tactical planning of Semiflexible Transit Systems. The problem is a variant of the classic
    Traveling Salesman Problem (TSP) minimizing a combination of the cost of the circuit and a measure of passenger travel times, known as Generalized Latency.
    In addition, the problem considers stochastic demand, and the possibility to skip nodes for which no service request is issued. To address the STSP GL we adopt an a priori optimization modeling framework and develop a Branch and
    Cut algorithm.

  • 16h30 - 16h55

    Learning implicit multiple time windows in the Traveling Salesman Problem

    • Jorge Mortes Alcaraz, prés., IMT Atlantique
    • Martin Cousineau, HEC
    • Fabien Lehuédé, IMT-Atlalntique - LSN
    • Jorge Mendoza, HEC Montréal
    • María I. Restrepo, IMT Atlantique

    Classically, researchers working in vehicle routing problems (VRPs) assume that the structure of the problem is known (i.e., objective function, constraints, parameters). However, recent studies have highlighted the gap between the routes offered by classical optimization algorithms and the routes followed by experienced drivers. As a result, researchers have turned their attention towards the acquisition and inclusion of drivers’ knowledge to learn the order in which each customer is going to be served by the driver. In this study, we describe and solve a new problem called the multiple time window learning problem. In contrast to other VRP variants, the goal is to learn the time windows associated with each customer. Our approaches are based on the observation and exploitation of historical data with a new algorithm called the recall heuristic, and the exploration of new information based on the multi-armed bandit problem. Computational results based on synthetic data showed that our approaches can learn time windows, and as a result propose routes similar to those created by experienced drivers, while still minimizing the routing costs.

  • 16h55 - 17h20

    Approaching an Exact Solution to the Near-To-Impossible Orbital Trajectory Problem

    • Isaac Rudich, prés., Polytechnique Montréal
    • Quentin Cappart, Cirrelt
    • Michael Römer, Universität Bielefeld
    • Louis-Martin Rousseau, Polytechnique Montreal & CIRRELT
    • Manuel López-Ibáñez, University of Manchester

    The Asteroid Routing Problem (ARP), called the Near-to-Impossible Orbital Trajectory Problem by NASA, adds a new type of difficulty to the Traveling Salesman Problem (TSP). In the ARP, a rocket must do a tour of several asteroids. Unlike the cities in a TSP, all of the asteroids are always moving, and the distances between them are constantly changing. At a glance this may seem like the Time-Dependent TSP (TD-TSP), but unlike the TD-TSP, calculating the optimal trajectory from one asteroid to another cannot be done quickly. Finding the optimal value for a given trajectory requires iterative solving of Lambert’s Problem. Most successful approaches to this problem use some variant of a Beam Search, and thus far no one has proposed an exact solution. In this work, we propose a Decision Diagram based branch and bound algorithm that uses a two-phase approach. In the first phase the state space is represented using a set of Decision Diagrams with approximated trajectories. In the second phase the expensive computation begins, and subsets of trajectories are calculated exactly in a manner that allows significant reduction of the solution space. This can be repeated until an exact solution is reached.