EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

1343. Solving the period travelling salesman problem

Invited abstract in session MC-25: Discrete, continuous or stochastic optimization and control in networks, transportation and design III, stream Combinatorial Optimization.

Monday, 12:30-14:00
Room: 011 (building: 208)

Authors (first author is the speaker)

1. Sofia Henriques
Statistics and Operational Research, Faculty of Sciences, University of Lisbon
2. Ana Paias
DEIO - CMAFCIO, Universidade de Lisboa, Faculdade de Ciências

Abstract

Considering a time horizon with different periods, the Period Travelling Salesman Problem (PTSP) is defined on a directed graph with a depot and n customers, in which each customer has a required number of periods to be visited in. The objective of the PTSP is to assign each client to as many periods as it is required while determining the set of routes, one for each period, with minimum cost. Each route starts and ends at the depot and visits the clients assigned to that specific period only once.

The PTSP combines an assignment and a routing problem in a single problem, making it very difficult to solve to optimality, even for instances with few clients. Most of the works in the literature study heuristic methods for the PTSP, and the few exact methods in the literature only consider two periods in the time horizon, which is insufficient to model many real-life routing problems involving periodicity. We will present different flow-based compact formulations for the PTSP and we will use the concept of projection to derive new ILP formulations with fewer variables but exponentially-sized sets of constraints. Furthermore, we intend to propose new valid inequalities for the PTSP. The conclusions from our theoretical and computational study will be presented for instances with different characteristics.

Keywords

Status: accepted

Back to the list of papers