Optimal CVRP depot location determination using two-tier PSO

摘要

Vehicle Routing Problems (VRPs) currently encountered may vary as a result of different restrictions. Since the location of a depot has a very significant effect on the transportation cost, this study therefore intends to propose a two-tier PSO, inner and outer layers, to obtain the best location to establish a depot and the optimal vehicle routes using the determined depot as the center. The inner-layer PSO is applied to obtain vehicle routes while the outer-layer PSO is to establish the most ideal depot location. A new particle encoding is proposed for the inner-layer PSO to reduce the customer assignment efforts. Decrease of inertia weight and addition of local searches are adopted to improve the quality of solutions. In the end, capacitated vehicle routing problems from the OR Library were applied to run tests and compare the cost difference between having planned the optimal depot location and not having done so, while the experiment results are presented to show the importance of depot locations.