求解具時間窗之多趟次車輛途程問題

Abstract

隨著企業競爭與講求專業分工時代的來臨，生產者、配銷商、零售商與消費者之間產品配送效率的重要性與日遽增，調查資料顯示運輸成本約佔配送企業總營運成本的35 ~ 60 %，而實際影響運輸成本的要素，一為各配送車輛行駛的距離，另一則為配送車輛的固定成本。因此，隨著服務客戶所在位置的範圍日益擴大，配送企業在營運初期，不當的路線配置與車隊規模都將造成相對高額的運輸成本。 有鑑於配送企業營運之初擁有的車隊規模有限，若能藉由部分時窗界限的彈性調整，則有助於降低營運的車隊規模，而適當的派送路線計畫，更有助於在既有的時窗限制條件下，充分指派車輛進行多趟服務，以降低車隊與營運成本。因此，本研究模式主要在求解具時間窗之多趟次車輛路線問題 (MTVRPTW)，所面臨的問題挑戰為：(1) 複雜度屬NP-Hard；(2) 首要目標為車隊規模最小，次要目標為總行車距離最短；(3) 車輛配送路線設計，除了考量單趟路線總需求數必須滿足車輛容量限制外，尚須滿足在顧客指定配送時間範圍內到達的時窗限制；(4) 排程方面，允許車輛在可工作時間內進行多趟次配送服務的彈性。 在求解MTVRPTW的方法論方面，本研究兼採數學規劃法與演算法進行分析與比較。首先針對構建的數學規劃模式，以Lingo軟體分別對三種不同規模的範例測試求解的確度與時間，而後再發展啟發式演算法求解大規模的路網問題，目標以降低總車輛數為主，降低總距離成本為次。演算法的程序在於先利用節省法與場站插入法構建一個多趟次可行解；其次，以車輛縮減模組與傳統改善模組改善總距離成本，最後，參考利用索羅門 (Solomon) 分類標竿試題，在車輛數與總距離成本的比較準則下，測試演算法的效率與效度，並輔以一實例探討。本研究更進一步由敏感度測試來分析臨界車隊規模，獲致結論與提供若干建議。

As the age of a competitive environment emphasizing professionalized work share and corporation comes, the importance of well organizing and/or linking the merchandise manufacturers, distributors, retailers, and end consumers so as to efficiently fulfill the requirements of most delivery services is ever increasing. Investigated data have shown that the transport cost comprises approximately 35 ~ 60 percent of total operating cost for delivery operators. The major elements relating such cost include the total distance that all dispatched vehicles travel and the total fixed cost of all dispatched vehicles for service. Because the locations of demand are spreading widely, inappropriate route allocation plan and fleet size may lead to fairly high transport cost for the operators, especially those who initially run the business. An operator who may possibly carry very limited number of vehicles when running services at the initial stage. It will be useful in decreasing the size of fleet if the service time windows of demand side can be organized flexibly. Furthermore, a suitable routing plan may help dispatch the individual vehicles by multiple trips to reduce both fleet and operating costs under existing service time requirements. Thus, the model proposed in this study is applicable for a multi-trip VRP with time windows (MTVRPTW). The arising challenges include: 1) NP-hard complexity; 2) objectives with minimized fleet size first and shortest travel distance then; 3) fulfillment of capacity and delivery time constraints; and 4) scheduling of multi-trip dispatch. In this study, a mathematical programming method and an associated heuristic algorithm were concurrently developed to solve the cases regarding to MTVRPTW. With the former, three network scales were proposed to test for their outputs accuracy and computation times required using the package LINGO. With the latter, problems by a larger network scale could be solved efficiently by following a two-stage objective: the fleet size minimization, then the shortest travel distance. A multi-trip feasible solution was initiated via the saving algorithms and depot-inserted method. The fleet reduction and the traditional improvement modules were then activated to improve the fleet size and travel distances. Finally, solutions to Solomon’s benchmark problem set were found and compared individually with those from other relevant research to check the output performance of the heuristic approach. In addition, data collected from field investigation were analyzed for contracting the operator's service plan. A series of sensitivity tests were also conducted to locate the best fleet size for practical references and to reach the conclusions and recommendations.