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 attributed to the utilization of different raw materials to be processed in parallel so that demand constraints are met. The Just-In-Time production planning policy of these plants require the collection of raw materials to be dehydrated shortly before the actual processing, immediately after harvesting. One of the most important aspects in collection of plant fresh products, is routing of collecting vehicles, so that total collection time is minimized. The aim of this study is to describe a new stochastic search meta-heuristic algorithm for solving the Vehicle Routing Problem (VRP), termed as the Backtracking Adaptive Threshold Accepting (BATA) algorithm. Our effort focuses on developing an innovative method, which produces reliable and high quality solutions, requiring reasonable computing effort. The main innovation of the algorithm, toward a typical threshold accepting algorithm, is that during the optimization process the value of the threshold is not only lowered, but also raised or backtracked according to how effective a local search 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 Tarantilis and Kiranoudis (2000).