Vehicle Routing Problem (VRP) is a route optimization problem. The current situation grows more complex so the VRP needs to adapt for being close to the practical problems. Perishable products are one example that need route optimization because perishable products require fast delivery time to maintain freshness. Often several companies has several distributors & some retailers (multi-depot), and often found that demand of customer that exceeds of the vehicle capacity so it needs to be visited more than once for each customer to meet customer demands (split-delivery) and with consideration of customer allowed service time (time-windows). In the traditional VRP, there are no consideration factors such as multi-depot (MD), split-delivery (SD) and time-window (TW). Therefore, we developed a model multi-depot split-delivery VRP with time-windows (MDSDVRPTW), which is the relaxation of traditional VRP limitation, with an objective function to minimize the total travel time.