This paper deals with a real-life distribution problem formulated as an open multi-depot vehicle routing problem (OMDVRP) that was encountered by a major Greek industry distributing fresh meat from depots to its customers (butchers' shops) located in an area of the city of Athens. To solve the problem, a new stochastic search meta-heuristic algorithm termed as the list-based threshold accepting (LBTA) algorithm is proposed. The proposed routing plan gives answers to a number of operational decision problems and provides significant economic benefits for the company.