Conference Agenda

Hexaly is a mathematical optimization solver based on various operations research techniques, combining both exact and approximate methods such as linear programming, non-linear programming, constrained programming, primal heuristics. Its modeling formalism can be used to express a wide range of academic and industrial routing problems using list decision variables and lambda functions. These models are very compact, allowing the solver to handle even large-scale problems.

The Traveling Salesman Problem (TSP) is a classic combinatorial optimization problem, but it doesn't capture some operational aspects like temporal dependencies. Unlike the classic TSP where distances between cities are constant, the Time-Dependent TSP (TDTSP) incorporates variable travel times, modeling real-world conditions where travel times depend on the time of day, traffic, or other temporal factors.

Traditionally, this problem is modeled with a discretization of the time horizon and a time matrix for each time step. This matrix can be constructed in various ways, and from it, the rest of the model can be created straightforwardly using Hexaly's list based model. Other problems follow, such as the Time-Dependent Traveling Salesman Problem with Time Windows (TDTSPTW), where points have time windows for visits, and the Time-Dependent Capacitated Vehicle Routing Problem with Time Windows, where multiple capacitated vehicles are available to serve a set of points with demands.

We compare Hexaly's results for the TDTSP and TDTSPTW with those from the literature. Hexaly improves nearly 25% of instances of up to 100 points while maintaining a gap close to 0% on the remaining instances.

In ridepooling services, mobility providers face the considerable challenge to quote expected departure and/or arrival times to customers, who will base their traveling decisions to a significant degree on the promised times. If the service provider communicates very ambitious service commitments, then this will typically increase the likelihood that customers will accept the quoted offer. This, in turn, will make it harder to comply with the commitment without rejecting customers (given limited transportation resources). If the service commitment is less ambitious then customers will be more likely to reject the offer, which will lead to an underutilization of resources and loss in revenue.

In this work, we will analyze the core interdependency between arrival commitments and customer demand in a simplified travelling salesman setting, where all customers share a shuttle to a common destination. After the service provider committed to an arrival time, customers have the opportunity to accept or reject the offer made, where the likelihood of accepting directly depends on the arrival time commitment. After the customer decisions are revealed, an Orienteering Problem needs to be solved in order to keep the arrival time commitment for as many customers as possible. We develop a formal representation of this two-stage stochastic optimization problem and propose exact and heuristic algorithmic approaches for deriving (near) optimal service commitments.

In this paper, we introduce a new variant of the traveling salesmen problem (TSP) called the uncovered TSP (uTSP) with various applications, e.g., in the field of last-mile distribution. Given a set of customers, a depot, and a set of facilities each covering a subset of customers, the task is to select a limited number of facilities, so that the TSP tour through the uncovered customers has minimum cost. We formulate the problem and highlight potential fields of application. Furthermore, we suggest an efficient heuristic solution approach, prove its suitability on different data sets, and provide managerial insights for the application.