Designing a multi-depot multi-period vehicle routing problem with time window: hybridization of tabu search and variable neighbourhood search algorithm

This research formulates a real-life multi-depot and multi-period vehicle routing problem (MDMPVRP) by imposing time window (TW) and many other constraints. A set of customers, spread in different locations, are to be served by a fleet of heterogeneous vehicles over a finite number of periods. Each customer is associated with combinations of routes and vehicles over the period. A customer must be served in one of the allowable combinations. The objective of this MDMPVRP-TW is to minimize the total distance traversed by the fleet over the planning horizon. The proposed MDMPVRP-TW is an extension of vehicle routing problem (VRP), and is hence an NP-hard problem. In order to optimize it, we propose a hybrid meta-heuristic approach by combining tabu search (TS) and variable neighbourhood search (VNS) algorithms. Furthermore, to provide richer insights, the efficacy of the proposed method and mathematical formulation is demonstrated through numerical experiments for a number of instances varying from small to large scale.

Automated summary

This research addresses a real-life multi-depot and multi-period vehicle routing problem with time window constraints, aiming to minimize the total distance traveled by the fleet over the planning horizon. A hybrid meta-heuristic approach combining tabu search and variable neighbourhood search algorithms is proposed to optimize the problem. Numerical experiments are conducted to demonstrate the efficacy of the proposed method and mathematical formulation across instances of varying scales from small to large.