車輛途程規劃問題一直是學術研究及實務界很感興趣且實際遭遇的課題。然而在現實生活中，存在許多不確定性、浮動變化的因素，若在規劃車輛途程時不加以考量，將造成車輛途程規劃與實際操作上的落差，導致成本的提高甚至規劃結果無法執行。這些不確定性、浮動變化因素包括如需求是否會產生、需求量多寡、旅行時間的變化、貨物品質是否會腐敗等。 本研究分成三部份來探討與含時窗限制車輛途程規劃相關的課題，並建立完整的數學模式及演算法進行測試。第一部份探討在顧客需求及旅行時間均可能無預警地產生變化時，如何建立一套即時性、線上反應的車輛派遣導引系統，以充份利用即時最新的交通及顧客需求資訊來重新規劃車輛途程。在該模式中，除了考量即時性的旅行時間及顧客需求資訊外，亦將可預測的旅行時間變化以依時性的函數型式同時納入模式考量。 第二部份則將旅行時間的不確定性以隨機變數的方式納入模式考量，進行行前的路線最佳化求解。在過去的研究中，將旅行時間的隨機性納入車輛途程規劃的文獻並不多見。本模式係一隨機規劃(stochastic programming)模式，並證明目標式具有下限，透過不斷提高下限以求得最佳解。本研究所發展之演算法除可求得真正解外，並有效排除抵達時間受上游所有路段旅行時間隨機性累積影響之問題。 第三部份探討易腐性商品的生產排程與運送路線之整合規劃。由於易腐性商品在生產後到交付顧客為止其品質均持續衰退，進而減少其實際收益，故進行生產排程時即應考量到運送路線所需的運送時間及其貨物所需的生產時間，綜合考量後才能減少品質耗損程度並追求生產者的最大利潤。 The vehicle routing problem has been and remains a rich topic for researchers and practitioners. In the real world, however, there exist many uncertain or constantly varying factors, which affect the operation of vehicle routing plan and result in the higher cost or failure. These factors may include occurrence of customer, quantity of demand, travel time, deterioration of commodities, etc. This thesis explores the extensional issues of vehicle routing problem with time windows in three parts. In the first part, the demand of customers and travel times may vary unexpectedly and a real-time, on-line operational vehicle dispatching and guiding system is established, taking the latest information of demand and traffic condition into account. The predictable travel time pattern is also considered as a time-dependent function in this model. In the second part, the travel time is considered as a random variable and the optimal routes are found in the pre-trip planning. The researches considering the stochasticity of travel time are relatively rare in the past. In this part a stochastic programming model is established, and the objective is proved to have a lower bound. An optimal solution can be found by raising the lower bound. In addition, the stochasticity of the arrival time at a customer will not be affected by the accumulative stochasticity of all previous link travel time in this model. The third part consists of integration of production scheduling and distribution for perishable goods. The perishable goods deteriorate as soon as they were produced and keep decaying when being delivered, resulting in deduction of revenue. The vehicle route as well as its delivery time and the production time should be considered in the phase of production scheduling, in order to reduce the deterioration and increase the profit.
