Improvement of vehicle routes with the iterated local search method case study: Tongnamkeang shop, Warinchumrab district, Ubon Ratchathani province

Abstract

This paper presents a heuristic for solving the vehicle routing problem which is a combinatorial optimization and NP-Hard problem. The Iterated Local Search (ILS) is applied to solve for solutions with the objective of minimizing the total cost that consists of transportation cost, shortage cost and overload cost. The demand from each customer is uncertain and distance between some pairs of customers is asymmetric. ILS consists of three phases. The first phase is to construct an initial feasible solution. Then the solution is improved in the second phase and the final phase is to perturb the solution. To determine the product quantity delivered to each customer, three policies are proposed. The first policy uses the average demand of each customer. The second policy considers the mode of demand of each customer and the third policy uses the median of demand of each customer. The computational results show that the first policy provides the best solution. The total distance can be decreased from 95.53 kilometers per day to 71.57 kilometers per day. When considering the total cost, it can be reduced from 8,425.75Baht per month to 6,732.47 Baht per month which is reduction of 1,693.29 Baht per month or 20.10% of the total cost.