標題: 以粒子群演算法求解時效貨品之車輛路線問題
Truck Routing for Perishable Products by Particle Swarm Optimization Based Algorithms
作者: 艾蘭格
Khoerniawan, Airlangga
黃寬丞
Huang, Kuan-cheng
運輸與物流管理學系
關鍵字: 車輛路線問題;整數規劃;粒子群演算法;混合啟發式解法;易腐性產品;Vehicle Routing Problem;Integer Programming;Particle Swarm Optimization;Hybrid Metaheuristics;KPBS Pangalengan;Perishable Product
公開日期: 2015
摘要: 
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.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT070353222
http://hdl.handle.net/11536/127474
顯示於類別:畢業論文