The application of the heuristic method at the vehicle routing problem and its implementation at the PT Nippon Indosari Corpindo.

Abstract

This paper is a case study in a division of PT Nippon Indosari Corpindo company. We used the vehicle routing problem with time windows (VRPTW) to formulate the distribution problem, which is a variation of the vehicle routing problem (VRP). In the VRP, all costumers have a time windows, so the service for the costumers must be completed in a specified time interval. The objective is to minimize the number of vehicles to serve all costumers in certain area and also to minimize the route length. As the VRPTW is a difficult problem in non polynomial hard problems, then we used the heuristic approach to solve the problem. In this paper, we used the nearest addition heuristic method to find the first solution. Next we used 2-Opt, Or-Opt, relocate, exchange, and cross methods to improve the first solution. In the last chapter of this paper, the results were compared to the current condition of the company. Key word: Vehicle routing problem, heuristic method, nearest addition heuristic method.