低溫物流配送路線問題之研究

Abstract

車輛途程問題（Vehicle Routing Problem, VRP）在國內外一直有許多文獻探討，但大多僅止於確定性模式，隨機性模式則相當少見。然於低溫物流的實際配送情形，為了達到較高的服務水準，送貨達顧客端時，常會有時間窗（Time Windows）的限制；另一方面，都市交通的擁塞，和所運送之生鮮產品的易腐（Perishable）特性，更使得在運送時間和產品的保存上存有「隨機」的特性。故本研究考慮時間窗和運送時間、產品保存時間兩者隨機的特性以構建隨機性車輛途程問題之數學規劃模式。 本研究以傳統時窗限制下的隨機車輛途程問題（Stochastic Vehicle Routing Problem with Time Windows, SVRPTW）為基礎，延伸分析生鮮產品路線配送特性及構建相關成本函數，包括因產品腐敗所造成之存貨成本、低溫運輸車配送時冷凍機消耗之能源成本，及傳統車輛路線問題之車輛固定成本和隨哩程遞增的運輸成本，從低溫物流配送業者的觀點，以上述各項成本之總成本最小為目標，建構低溫物流配送路線基本模式。本研究並發展運送策略，於配送前置入較多產品，防止因運送時間所造成的可用產品的減少，致使顧客需求無法被滿足之途程失敗（Route Failure）情形的發生。進一步，本研究考量違反顧客需求時間窗所造成之影響，建構軟時窗之懲罰成本函數，並深入討論都市中旅行時間和一天之中溫度變化的依時特性，將基本配送路線決策模式作修正。最後發展一演算法求解所建構之數學規劃模式，並以一低溫物流業者之特定商品配送為例，進行實例分析及主要參變數之敏感度分析，以驗證本研究所構建模式之合理性與闡述在實務問題上之操作解決方法與應用價值。 範例分析之結果顯示，低溫物流配送之存貨損失與能源成本對總配送成本有顯著影響，如常溫物流一般，生鮮產品配送成本中，其車輛固定成本和存貨成本兩者存在一抵換關係。低溫物流配送之模式結果可得出車隊規模、配送車輛路線、裝載量、出發及完成服務時間等配送策略，軟時窗模式之求解結果可發現不易於時間窗內服務之顧客，藉由調整其時間窗以改善服務水準與降低配送成本。而透過需求型態及單位時間平均存貨成本之變化，進行低溫物流配送各項成本及總成本之影響與敏感度分析，可發現低溫物流配送存有最佳車輛容量。本研究針對低溫物流配送之隨機與依時特性所構建之數學規劃模式，為過去研究未曾深入探討者，而模式求解結果亦證明較不考慮存貨損失與能源成本之傳統模式優越，可提供未來相關研究之參考。而實務上，可提供低溫物流配送業者作各種配送策略擬定之參考，並可作為業者進行成本分析之基礎。

Vehicle Routing Problem (VRP) was investigated by many studies, but most of them focused on deterministic models, while few on stochastic models. In reality, carriers must deliver refrigerated food to customers with time window constraints due to perishable properties of food. Furthermore, congestion in city traffic and deterioration characteristics of fresh food make delivery time and food preservation become uncertain and raise distribution costs as well. This research considers delivery time window and stochastic characteristics of distribution time and food preservation and constructs models on Stochastic Vehicle Routing Problem with Time Window (SVRPTW) for refrigerated food using mathematical programming model. This research extends Vehicle Routing Problem with Time Windows (VRPTW) by considering randomness in refrigerated food distributing process and constructs a SVRPTW model to solve the optimal shipping route, vehicle load, fleet and departure time. The objective function of the model aims at minimizing the sum of transportation cost, inventory cost, energy cost and penalty cost as related to violating time windows. Among them, transportation cost depends on vehicle routing distance, while inventory cost accounts for the deterioration of fresh food due to the vehicle routing around many customer demand locations and both of them are stochastic. Energy cost is due to extra energy consumption of freezing equipments on the vehicles. Then, the study formulates a time-dependent fresh food deteriorating function, and calculates the probability of deterioration occurrences and evaluates how much loss it causes. Given customer food demand, this study will introduce strategies such as loading extra food in refrigerated truck before shipping, to prevent food delivery from route failure, defined as incapability for delivering the required amount of food at time-windows due to food perishing. The penalty cost of route failure is defined and incorporated into the model. The study further constructs the penalty cost of violating time-window and discusses the time-dependent truck running time in urban areas and time-varying temperature in a day, then modifies the objective function as well as constraints in the above mathematical programming problem. Furthermore, the study develops algorithms to solve the above two proposed models, which are with and without considering the time-varying travel time and temperature, respectively and compares their results. A case study will be provided to demonstrate the feasibility and the results of applying the proposed models. Results of this study reveals that inventory loss and energy cost influence total distribution cost of refrigerated distribution significantly. Results of example analysis show that as conventional distribution problem, trade-off relationship exists between vehicle fixed cost and inventory cost. And refrigerated distribution exists an optimal vehicle capacity that can help operators to decide the shipping vehicle sizes. Results of this research not only help understand how the randomness of delivery time and food perishing affects the vehicle routing and resulting costs, but also provides guidances such as the required fleet, vehicle departure time, load and distribution routes for carriers on making the optimal shipping decisions.