A tabu search algorithm for the periodic vehicle routing problem

Author(s)

Camila Frederico Mortati

• Document type: Master's Dissertation
• Press: Campinas, SP.
• Institution: Universidade Estadual de Campinas (UNICAMP). Faculdade de Engenharia Elétrica e de Computação
• Defense date: 2005-06-17

Examining board members

Vinícius Amaral Armentano; Jose Vicente Caixeta Filho; Franklina Maria Bragion de Toledo; Akebo Yamakami

• Advisor: Vinícius Amaral Armentano

Abstract

This work addresses the periodic vehicle routing problem that consists of assigning a combination of visiting days to each client, and defining the routes every day of a planning horizon, in such a way as to minimize the cost or duration of the routes. A tabu search algorithm is proposed for solving this problem. The history of the tabu search, used to guide the search process, is represented by short and long term memories. The efficacy of the suggested strategies for diversification and intensification, associated to the long term memory, is verified experimentally. The performance of the tabu search algorithm is tested computationally in instances from the literature. A tabu search procedure suggested in the literature is implemented and its performance is tested against the tabu search algorithm developed in this work (AU)