PT. XYZ is a pasteurization milk processing company that produce milk drink from pure cow milk. They have about 40 customers and most of them are outside Bandung. However, the product delivery may not be done as planned. The average on time delivery is around 96%. it is below PT. XYZ target which is 98%. When delay occur, each customer has their own regulation that has been settled in agreement contract such as penalty cost. The most influential factors that caused this problem is delay in departure, because PT. XYZ don’t have fixed schedule of delivery and they miscalculate the departure time which caused by improper route determination that leads to longer travel distance and delays. Therefore, this problem can be categorized as Vehicle Routing Problem (VRP) with objective to minimize travel distance.
Based on PT. XYZ problem characteristics, it can be categorized as Heterogenous Fleet VRP, because there are two types of vehicle, and VRP with Time Window (VRPTW), as customer give time span for delivery, therefore Two Phase Tabu Search Algorithm will be used. It is one of meta-heuristics algorithm which is an extension of the normal Tabu Search that contain tabu moves in the first phase and post-processing moves in second phase to improve the solution.
From the existing condition, the travel distance is decreased by 19.48% using four vehicles from total seven vehicle available. It gives impact to travel time as it is also reduced by 3.97 hour from the existing. Delay is also not occurred in the proposed distribution route, therefore there is no undelivered order and PT. XYZ will not receive any penalty cost.
As this research is focus only on determining distribution route, thus further research could extend the problem into stacking and determination of sequence order of loading the goods into the vehicle. Several days of horizon planning and the used of media visualization such as GPS also can be considered.
Keywords: Vehicle Routing Problem (VRP), Heterogenous Fleet VRP ,VRP with Time Window (VRPTW), Meta-heuristics