應用演化式演算法於考慮產品品質之低溫食品配送規劃

Abstract

食品安全一向為國內外所重視之議題，且隨著健康飲食概念的普及與資訊傳播科技的發達，相關資訊取得漸趨便利，促使消費者提升對於食品品質之要求。低溫食品屬於易腐性產品之範疇，具有時效性高、且對溫度變化敏感等特性，其品質在生產、加工後便逐漸衰退。過去研究指出，肉產品與水產品之品質隨時間變化呈非線性衰退，而微生物則為品質衰敗之主要因素，雖然實施溫度控制可有效抑制微生物生長，但對於部分具耐冷特性的微生物而言，即使在配送過程中維持低溫環境仍可持續繁殖，使肉品品質持續衰退，甚至在送達顧客前便超出貨架壽命，而無法滿足顧客需求。 有鑒於此，本研究建構考慮產品品質之低溫食品配送規劃模式，將非線性衰退之產品品質與具時窗限制之車輛途程問題(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.