THE TIME DEPENDENT TRAVELLING SALESMAN PROBLEM WITH TIME WINDOWS

Torna indietro

Abstract

This paper deals with an exact algorithm for the Time-Dependent Traveling Salesman Problem with Time Windows (TDTSPTW) with continuous piecewise linear cost functions. There are two main research streams that can benefit from efficient exact algorithms for TDTSPTW. The first concerns determining optimal vehicle route planning taking traffic congestion into account explicitly. The latter deals with sequence dependent set-up single machine scheduling problems minimizing total completion times or total tardiness. The contribution of this paper is twofold. First, it is proved that the Asymmetric Traveling Salesman Problem with Time Windows is optimal for the TDTSPTW, if all the arcs share a common congestion pattern. Second, an integer linear programming model is formulated for TDTSPTW, and valid inequalities are then embedded into a branch-and-cut algorithm. Preliminary results show that the proposed algorithm is able to solve instances with up to 67 vertices.

Autore Pugliese

Tutti gli autori

  • A. Arigliano , G. Ghiani , E. Guerriero , A.D. Grieco

Titolo volume/Rivista

Non Disponibile

Anno di pubblicazione

2011

ISSN

Non Disponibile

ISBN

Non Disponibile

Numero di citazioni Wos

Nessuna citazione

Ultimo Aggiornamento Citazioni

Non Disponibile

Numero di citazioni Scopus

Non Disponibile

Ultimo Aggiornamento Citazioni

Non Disponibile

Settori ERC

Non Disponibile

Codici ASJC

Non Disponibile