A Construction of Vehicle Routing System with Time-Varying Travel Times

[[abstract]]物流配送系統是物流中心運作成敗的關鍵機能之ㄧ，也是物流中心主要成本來源，而物流中心配送作業的重點是如何將車輛有效的使用並決定其最經濟的行駛路線圖，使得商品能在最短的時間內將正確的數量送到正確的地點來滿足顧客需求，以達到完美訂單(Perfect Order)。現今消費者需求趨於多樣化，商品生命週期短縮化結果，使得送貨時間日趨嚴苛，且台灣都會區交通負荷繁重，行車、停車、卸貨困難，更加深配送問題的複雜度。 本研究將規劃建構一車輛排程系統，所考量的範疇為某區域中之單一物流配送中心車輛路線規劃問題。在系統演算法設計方面以貪婪搜尋法(Greedy Search)為主要法則，結合了地理資訊系統(Geographic Information System； GIS)，且考量了交通流量假設，以時間為導向作為運送順序與路徑選擇之依據，減少車輛巡迴旅行時間、增加車輛負載率，將車輛使用率達到最大，以利降低成本、提昇顧客滿意度。本系統期望協助物流中心能做一整合管理，並規劃指派車輛之配送服務路線，以達到車隊資源充份利用，並能有效調度配送車輛與降低成本，同時作為以後發展供應鏈派車的依據。[[abstract]]The system of logistics distribution is one of the key functions of distribution center. Operation, the major source of D.C. and the operation in D.C. stressed the things that how to use the vehicles effectively and decided the figure of the most economics driving line. Let production send the right quantity to the right position for satisfying the customer’s demand to reach the perfect order. Nowadays the traffic in Taiwan metropolis is heavily and driving, parking and loading are difficultly, which make the complexity of delivering problems more deeply. This study analyzes a different case of the Vehicle Routing Problem (VRP), which is including the time-varying link weight. In real world, a link travel time of a network is changing time to time. That means different departure time of the same route will generate different travel time. How to dispatch vehicles to serve customers and decide the order of services are needed to reconsider under this situation. Moreover, most traditional VRP assume straight-line connection between any two nodes rather than talk about the path selection. In this research, it is also discussed. A heuristic algorithm, which is greedy algorithm, is introduced for solving this VRP. The concept of greedy algorithm is trying to serve as more customers as one vehicle can. In addition, an application is made to illustrate the solution of this algorithm. This application demonstrates a user interface (UI) of solving VRP and using the map of Taipei city as study object