The article presents an innovative optimization technique for solving the Open Capacity Constrained Vehicle Routing Problem (OCVRP) with the Tabu Search (TS) algorithm. The algorithm enhances basic local search procedures by introducing memory-based processes in the form of tabu lists and long-term memory to prevent cycling and improve exploration of the solution space. Test cases for various problem sizes and complexity are generated, while even constraints that could be applied in a real situation, such as vehicle load capacity and distances of the roads, are included. Computational experiments show that TS with an insert move outperforms basic nearest neighbours and swap moves in most instances. The results confirm that TS is able to improve route planning solutions to large-scale logistics problems.