An efficient meta-heuristic algorithm for routing product collecting vehicles of dehydration plants. I. Algorithm development

Dehydration plants are characterized by a multi-product nature chiefly attr ibuted. to the utilization of different raw materials to be processed in pa rallel so that demand constraints are met. The Just-In-Time production plan ning policy of these plants require the collection of raw materials to be d ehydrated shortly before the actual processing, immediately after harvestin g. One of the most important aspects in collection of plant fresh products, is routing of collecting vehicles, so that total collection time is minimi zed. The aim of this study is to describe a new stochastic search meta-heur istic algorithm for solving the Vehicle Routing Problem (VRP), termed as th e Backtracking Adaptive Threshold Accepting (BATA) algorithm. Our effort fo cuses on developing an innovative method, which produces reliable and high quality solutions, requiring reasonable computing effort. The main innovati on of the algorithm, toward a typical threshold accepting algorithm, is tha t during the optimization process the value of the threshold is not only lo wered, but also raised or backtracked according to how effective a local se arch is. This adaptation of the value of the threshold. plays an important role in finding high quality routing solutions. BATA is described in detail while its performance and characteristic case studies are presented by Tar antilis and Kiranoudis (2000).