A Tabu search metaheuristic algorithm for the multiple depot vehicle routing problem with Time Windows

Abstract

The problems encountered by courier companies in directing their eets along road networks to visit customers, which are geographically distributed, are common problems which are encountered frequently. These problems are by no means isolated to courier companies. Any set of vehicles which is involved in delivery, collection or a combination of both delivery and collection encounter a variation of the vehicle routing problem (VRP). Several variations of the vehicle routing problem exist. The algorithmic solutions to the individual variants of the vehicle routing problem seek to optimise the routes assigned to a eet of vehicles in visiting an array of nodes (which represent points of delivery or collection or from another perspective, a set of customers). The optimal solution of a VRP instance is the shortest, quickest or cheapest set of routes assigned to a eet of vehicles which satis es all customer demand without contravening any of the instance-speci c constraints. The vehicle routing problem has been identi ed as an non-determinant polynomial-time (NP) hard problem. This classi cation gives an indication of the computational complexity of the problem. Problems of this class require an inordinate amount of time to be solved to optimality for large problem instances. To overcome such obstacles, heuristic and metaheuristic search algorithms are often utilised to arrive at near-optimal or satisfactory solutions in less time.