SCRO / Journées de l'optimisation
HEC Montréal, 2931 mai 2023
CORSJOPT2023
HEC Montréal, 29 — 31 mai 2023
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
Gurobi is making it easier to plug your predictive models directly into your optimization model. Gurobi has an opensource Python package that allows users to add trained machine learning regressors as a constraint to a Gurobi model (e.g., from scikitlearn, TensorFlow/Keras, or PyTorch). Thus, allowing for tighter integration between trained predictions and optimal decisionmaking.
This tutorial will introduce the Gurobi Machine Learning package and how it fits into an optimization application. Then we will explore how these machinelearning 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)
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
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 multiarmed 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 NearToImpossible Orbital Trajectory Problem
The Asteroid Routing Problem (ARP), called the NeartoImpossible 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 TimeDependent TSP (TDTSP), but unlike the TDTSP, 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 twophase 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.