以多目標與限制最佳化觀點求解具時窗限制之車輛路由問題

The vehicle routing problem (VRP) aims to find a transportation plan for a fleet of vehicles to serve customers to optimize concerned objective functions. This project addresses the VRP with time windows (VRPTW), which requires that service must start within the specified time windows of customers. Minimization of the number of vehicles and total travel distance are two common objective functions in the research of VRPTW. Traditionally, minimization of the number of vehicles was assumed to be more important than minimization of total distance. However, this assumption is not always true in all situations. Decision makers may want to know the trade-off between these two objective functions and then make a proper decision. In this project we propose a method based on multiobjective evolutionary algorithm to seek for the Pareto optimal set of solutions. We improve the crossover and mutation operators by incorporating domain knowledge. We test the proposed method by comparing with nine state-of-the-art algorithms on 39 public problem instances. Our method is superior to most algorithms in terms of solution quality and computational efficiency.