The goal of this paper is to develop an algorithm that is capable to handle a slightly modified version of the minimal Traveling Salesman Problem in an efficient and robust way and produces high-quality solutions within a reasonable amount of time. The requirements of practical logistical applications, such as road transportation and supply chains, are also taken into consideration in this novel approach of the TSP. This well-known combinatorial optimization task is solved by a bacterial memetic algorithm, which is an evolutionary algorithm inspired by bacterial transduction. A new method is also proposed to deal with the time dependency in the cost matrix. The efficiency of the implementation, including time and space constraints, is investigated on a real life problem. © 2009 Springer-Verlag Berlin Heidelberg.