Portal de Periódicos da CAPES

A Backtracking Adaptive Threshold Accepting Algorithm for the Vehicle Routing Problem

2002; Taylor & Francis; Volume: 42; Issue: 5 Linguagem: Inglês

10.1080/716067183

1029-4902

Christos D. Tarantilis, C.T. Kiranoudis, Vassilios S. Vassiliadis,

Transportation Planning and Optimization

The aim of this study is to describe a new stochastic search metaheuristic algorithm for solving the capacitated Vehicle Routing Problem, termed as the Backtracking Adaptive Threshold Accepting (BATA) algorithm. Our effort focuses on developing an innovative method, which produces reliable and high quality solutions in a reasonable amount of time, without requiring substantial parameter tuning. BATA belongs to the class of threshold accepting algorithms. Its main difference over a typical threshold-accepting algorithm is that during the optimization process, the value of the threshold not only is lowered but also raised, or backtracked, depending on the success of the inner loop iterations to provide an acceptable new configuration (set of routes) replacing the previous one. This adaptation of the value of the threshold, plays an important role in finding the high quality solutions demonstrated in computational results presented in this study.