具顧客時窗限制與駕駛員休息規定之車輛途程問題之研究

Abstract

具時間窗車輛途程問題(Vehicle Routing Problem with Time Windows, VRPTW)考慮了一個車容量已知的車隊來服務一群有時窗限制要求的顧客， 目標是追求使用到最少車輛數目與最短總路線距離。因為VRPTW可廣泛地應用在許多實務問題上，因此過去有相當多的文獻探討此問題。然而，過去的解決VRPTW的研究尚未有考慮駕駛休息規定，而實務上駕駛休息規定是為了增加運送過程的安全性，規範駕駛司機上班時數與休息時間的限制，服務車輛必須在司機上班時數內回到場站，且運送過程中每隔一段時間司機必須休息，此亦可視為是車輛具有時間窗的限制，進而對車輛總旅行時間有極大的影響。本研究考慮具顧客時窗限制與駕駛員休息規定之車輛途程問題，提出一基因演算法進行求解，目標為總旅行距離成本與使用車輛數成本最小。由於並無標準題庫可供比較，因此本研究發展出四種不同問題規模的測試例題，分別為25顧客、50顧客、100顧客、150顧客等規模，其中僅有25顧客規模能以暴力法求得最佳解。結果顯示，演算法在25顧客測試例題下，求解100次的平均結果與最佳解的誤差不到0.05%，可證明本論文提出的演算法在此問題上的成效。其餘測試例題雖無已知最佳解可與演算法比較，但可藉由參數分析找出各問題規模下最合適的參數設定。

The vehicle routing problem with time windows (VRPTW) has received much attention, and has been applied to solving many scheduling applications in transportation and logistics. The VRPTW considers a fleet of vehicles with specific capacity to serve a number of customers with various demands and time window constraints, with objective of finding the minimal number of vehicles and the shortest routing distance. However, the previous works for VRPTW did not consider drivers’ off-hour regulation. In practice, the purpose of drivers’ off-hour regulation is to improve the transportation safety by deducing the occurrence of fatigue and other pressure-related conditions on drivers. These rules can be transformed into the regulations on works hours and resting periods, and hence, the resulting drivers’ off-hour regulation has a major impact on the total traveling time. This paper presents a genetic algorithm for solving the vehicle routing problem with customers’ time windows and drivers’ off-hour regulation. The objective is to minimize the total traveling cost and the cost of the used number of vehicles. In this paper, four test problems with different scales are developed: 25 customers, 50 customers, 100 customers, and 150 customers, respectively. In the four test problems, only the optimal solution of the problem with 25 customers can be obtain by the brute-force method. Simulation results indicate that, after applying genetic algorithms to the test problem of 25 customers, the difference between the optimal solution and the average solution of 100 runs is less than 0.05%. As for the other test problems, we can find the appropriate parameter settings for genetic algorithms.