以粒子群演算法求解時效貨品之車輛路線問題

Abstract

無

The level of consumption milk in Indonesia is increased every year so as the level of production of milk is increasing. In 2010, Indonesia is the 2nd largest milk production country in ASEAN. In Indonesia, farmers belong to the cooperatives called GKSIs, which are responsible for helping farmers to store and sell milk. One of the largest GKSIs is KPBS Pangalengan, located in Bandung. KPBS Pangalengan cooperates with milk product producers to establish the 1st Tier Milk Treatment (MT 1) and the External Cooling Units for processing fresh milk. At the moment, there are five cooling units scattered in five different locations. Meanwhile, there are 33 registered milk collection points (called TPKs) associated with the active member KPBS PANGALENGAN. Because milk is a product highly perishable, the delivery of fresh milk should be sent to the cooling of milk within a specific time limit. The issue is in addition to the issue of the milk collection time windows. On the other hand, the trucks have different capacities, and the cooling facilities also have a limited capacity. The trucks leave the MT 1 to begin a tour and must end the tour at an ending point with a cooling facility. Thus, the problem is classified as open vehicle routing problem with time window and heterogeneous fleet mix (OVRP-TWHF). In order to solve the problem, an IP Model was developed to get the global optimal solution where the objective is to minimize total distance. Although the optimal solution can be derived by the model, the time for the IP solve to converge can be very long. Because of that, two meta-heuristic algorithms were developed to reduce the computational time and generate an acceptable solution. Particle Swarm Optimization (PSO) and a hybrid PSO with Genetic Algorithm (GA) technique were involved. Both of them have been popular for solving the NP hard problem like OVRP. Based on the numerical experiments, the IP model is capable of solving the routing problems with about ten customers due to the computation load. The PSO and the Hybrid PSO-GA can generate the solution better than the initial solution from the classic nearest neighbor method. However, the gap between the metaheuristic method and the IP model with optimal solution is still big. However, the computational time advantage for the meta-heuristic algorithms is significant.