MODEL AND ADAPTIVE NEIGHBORHOOD SIMULATED ANNEALING FOR SITE-DEPENDENT VEHICLE ROUTING PROBLEM WITH MULTIPLE CROSS-DOCK AND TIME WINDOW - Novatama, Rizky
Cross-docking is a strategy that is widely used by companies to gain competitive advantage and reduce transportation cost which can be 30% of total cost incurred. There are two main points in cross-docking which is simultaneous vehicle arrival and consolidation. If all vehicles do not arrive at the cross-dock simultaneously, then the consolidation process is delayed until all vehicles arrive at the cross-dock, this can cause an increase in waiting time and inventory level in cross-dock. Therefore, vehicle routing becomes one of important decisions in the cross-docking process. This problem is known as the Vehicle Routing Problem with Cross-dock (VRPCD). In this research, the VRPCD was developed into Vehicle Routing Problem with Multiple Cross-dock (VRPCD) which considers heterogeneous fleet, service time window, and dependencies between customer sites and vehicle types, or can be abbreviated as SDVRPMCDTW. Time window and site-dependent are added because in the real system the company faces a situation where each cross-dock and customer have a service time window, and several vehicle types cannot visit a certain customer location. Mathematical models and Adaptive Neighborhood Simulated Annealing (ANSA) algorithms were developed for SDVRPMCDTW problem. The developed algorithm was tested to solve the HF-VRPMCD problem from previous research. The test result shows that the developed algorithm can obtain 60 solutions that are the same or better than previous research out of 90 data tested. A statistical method named paired t-test is used to test whether the difference of solution obtained by the developed algorithm and the previous research algorithm is significant. The test results of this test indicate that the developed algorithm is producing a better solution than the algorithm from previous research. The developed mathematical models and algorithm were tested to solve the SDVRPMCDTW problem. The test result shows that the mathematical model, known as exact method, can only be used to solve problem with 10 consumers, for problem with 30 and 50 consumer exact method requires a very long computational time to obtain global optimum solutions. While the developed algorithm can be used to solve problem with 10, 30, and 50 consumers with acceptable computational time. The test result also shows that the performance of the developed algorithm is quite good in terms of solution quality with a gap of 0,16% and -24,99% from exact method in problem with 10 and 30 consumers, and a gap of -1,37% from SA algorithm in problem with 50 consumers, and computational time needed is smaller than exact method for problem with 30 consumers.