Program > By speaker > Mesquita Marta

We address a variant of the TSP with multiple time windows (TSPSTW) in which the set of cities is partitioned into two subsets: mandatory and selective cities. All mandatory cities should be visited once within one of predefined time windows, ensuring that a visit occurs during working hours. A subset of the selective cities, whose cardinality depends on the tour completion time, should be visited within one of the associated time windows. The objective is to plan m circuits, each circuit not exceeding a predefined number of days, minimizing the total traveled distance and the completion time. We present a MILP model for the problem and propose a heuristic approach based on Benders decomposition. The heuristic alternates between the solution of a m-TSP master problem, defining the order by which mandatory cities are visited in each circuit, and the solution of a scheduling subproblem, establishing the starting time of each visit as well as the visits to selective cities. A genetic algorithm is developed to obtain feasible solutions for the master problem whereas a heuristic algorithm is proposed to solve the primal subproblem. In each iteration, a benders' cut, built from the dual solution obtained using feasibility and slackness conditions, is added to the master problem and the surrogate relaxation of all the cuts inserted so far is considered. Computational experience with real based instances shows that, at low computational expenses, Benders' cuts guided the building of the m circuits so as to obtain better feasible solutions for TSPSTW.