In the a priori TSP, we are given a metric space V of customers and an activation probability for each customer. We ask for a TSP tour T for V that minimizes the expected length after cutting T short by skipping the inactive customers. All known approximation algorithms select a nonempty subset S of the customers and construct a master route solution, consisting of a TSP tour for S and two edges connecting every customer not in S to a nearest customer in S. We address the following questions: If we randomly sample the subset S, what should be the sampling probabilities? How much worse than the optimum can the best master route solution be?
This is joint work with Jannis Blauth, Meike Neuwohner, and Jens Vygen.

The k-Opt algorithm is a local search algorithm for the Traveling Salesman Problem. Starting with an initial tour, it iteratively replaces at most k edges in the tour with the same number of edges to obtain a better tour. We prove that for $k \geq 5$ the k-Opt algorithm can have exponential running time for all pivot rules.

This study presents the development of a real-time dispatching system tailored for a ride-sharing service capable of accommodating a large volume of passengers and trips. The primary objective is to address the dynamic Dial-and-Ride Problem that ensures short travel time and service for each customer while minimizing waiting times. Departing from conventional methods that rely on fixed time intervals for batching requests, this research introduces a novel rolling-horizon strategy with adjustable time epochs. This approach combines the advantages of batch optimization with smaller batch sizes, ensuring rapid and effective dispatching. Two primal-based algorithms within a column generation framework are proposed and compared against a traditional column generation approach. A thorough evaluation is conducted using datasets derived from historical taxi trips in New York City, encompassing scenarios with up to 30,000 requests per hour.

We develop theoretical foundations and practical algorithms for vehicle routing with time-dependent travel times. We devise a faster algorithm to compute the pointwise minimum of a set of piecewise linear functions and a monotonicity-preserving variant of the Imai–Iri algorithm to approximate an arrival time function with fewer breakpoints. Next, we show how to evaluate insertion and deletion operations in tours efficiently and update the underlying data structure faster than previously known when a tour changes. Evaluating a tour also requires a scheduling step which is non-trivial in the presence of time windows and time-dependent travel times. We show how to perform this in linear time.

Based on these results, we develop a local search heuristic to solve real-world vehicle routing problems with various constraints efficiently and report experimental results on classical benchmarks, as well as on new benchmarks with time-dependent travel times that we created based on real-world data. Our results demonstrate the importance of considering time-dependent travel times in instances with tight time windows.