Applying Evolutionary Algorithm to The Distribution Planning for Chilled Foods Considering Product Quality
|關鍵字:||冷鏈;低溫食品;貨架壽命;產品品質;車輛路徑規劃;演化式演算法;生物地理學最佳化演算法;遺傳演算法;Cold Chain;Chilled Foods;Shelf Life;Product Quality;Vehicle Routing Problem;Evolutionary Algorithm;Biogeography-Based Optimization;Genetic Algorithm|
有鑒於此，本研究建構考慮產品品質之低溫食品配送規劃模式，將非線性衰退之產品品質與具時窗限制之車輛途程問題(Vehicle Routing Problem with Time-Window, VRPTW)結合，於配送過程中預測產品品質之衰退程度，並以較高品質之產品替代已超出貨架壽命之產品，以滿足顧客需求。而由於低溫食品配送規劃問題為VRPTW之延伸，使其亦為組合最佳化問題，且複雜度為NP-hard，需藉由通用啟發式演算法(Metaheuristic)方可於合理時間內求解，故本研究分別以遺傳演算法(Genetic Algorithm, GA)與新發展之生物地理學最佳化演算法(Biogeography-Based Optimization, BBO)為基礎，發展可應用於低溫食品配送規劃之最佳化演算法，同時針對BBO之編碼及運算子進行修改，使原先應用於非線性規劃問題之BBO可求解組合最佳化問題，再以Solomon之標竿題庫驗證其有效性，並針對兩者之求解結果進行分析與比較。|
As consumer increasing concerns on healthy eating, food safety has emerged as one of the most critical issues in resent years, and the standard of food quality has been raised as well. Chilled foods are perishable and temperature-sensitive. Physical, chemical and biological changes occur after food production or processing, and it leads to quality deterioration. Other studies indicate that the quality degradation of meat and fish follow the first-order reactions, meaning that the quality of meat and fish decrease rapidly, and it’s more difficult to estimate. The quality deterioration of meat is mainly caused by microbial growth, and the temperature is the most important factor that influences the growth rate. Therefore, it’s effective to suppress microbial growth by practicing temperature control during the distribution. However, quality deterioration still occurs in chilled meat because of the cold-tolerant microbe, which continues breeding in low-temperature environment, making the product reach the end of shelf life, and causing the failure of meeting the demand of customers. In view of this, the objective of this study is to develop the distribution planning that considering the quality deterioration during the distribution for chilled foods, which is a mathematical model that combines shelf life forecasting and Vehicle Routing Problem with Time-Window (VRPTW). In order to solve this NP-hard problem, this study also modifies a new metaheuristic called Biogeography-Based Optimization (BBO) to solve it, and validate the effectiveness of the proposed BBO based algorithms by Solomon’s benchmark instances. In addition, BBO and Genetic Algorithm (GA) are both Evolutionary Algorithm, therefore, this study also presents the analysis and comparison of computational result between BBO and GA.