| Abstract | This dissertation focuses on the capacitated location routing problem (CLRP) and the multi-objective location routing problem (MO-LRP). The solution method for CLRP is based on GLNPSO(from Pongchairerks and Kachitvichyanukul, 2009a), a variant of particle swarm optimization algorithm and the Pareto based MOPSO adopted from Nguyen and Kachitvichyanukul,(2010)to solve multi-objective LRP.
In the first part, the GLNPSO algorithm is applied to solve single objective CLRP. The main focus is the design of solution representation for LRP and the design of decoding method to convert particle into solution. In this research, the position of a multidimensional particle is used to represent depots and customers. Two decoding methods are proposed to transform particle into solution. Decoding method 1 finds solution by determining depot location, customer assignment, and route construction. Decoding method 2 starts by first forming clusters of customers, then selects the depot location and assigns customers to depots, and finally constructs the routes. For both the decoding methods, each particle is decoded into location decision and vehicle routes simultaneously. The proposed algorithm is tested on a set of published benchmark problem instances and the experimental results show that the solution quality is good for large problem instances and a total of 9 new best solutions are identified. Additional four performance indices are also proposed to assess the operational performance of the location selection and the route forming decisions.
In the second part, Pareto based MOPSO algorithm is applied to solve multi-objective LRP by searching for a set of non-dominated solutions. The two objectives considered are to minimize the total cost and to maximize the total demand served. Under the framework of MOPSO, a mixture of 4 subgroups of particles in a swarm with corresponding movement strategy and storage for elite group are used to search for the Pareto front. The same solution representation for the single objective case is used with two modified decoding methods to search for the Pareto front. The experimental results demonstrate that the proposed algorithm can effectively provide nice Pareto front for most test problem instances by both decoding methods but with different solution quality. A measurement of metric is also used to further differentiate the performance differences between the two decoding methods, and a big performance gaps between Pareto based MOPSO with the weighted aggregation method.
In the third part, an adaptive large neighborhood search is considered to be combined with GLNPSO to improve the solution quality for CLRP. Solutions (the personal best for each particle and the global best for a swarm) obtained by GLNPSO are used as the initial solutions for ALNS. Three kinds of neighborhood search of 0-1 swap, 1-1 exchange, and q option simultaneously are designed with both destroy and repair of current solution. Under a local search framework, in each iteration and for each particle the adaptive process is functioning by stochastically selecting one neighborhood according to the accumulated past performance (score) of three neighborhoods. The selected neighborhood is applied to current solution to get a new solution, and based on the comparison with current personal best solution and global best solution, the performance (score) of the selected neighborhood is counted on three levels, and the personal best solution is updated. After all particles are processed, the global best solution is updated for the iteration. The accumulated performance score of each neighborhood is reset after a predefined number of iteration and restarts with previous
iv
solutions. The experimental results indicate that the solutions quality are improved for 15 instances obtained via the decoding method 1 and 19 instances obtained via the decoding method 2 with slightly increased in computational time for both decoding methods.
The contributions can be highlighted as follow. First, it successfully applied GLNPSO to solve the capacitated location routing problem with newly designed solution representation and two decoding methods. Second, four additional performance indices are proposed to further assess the solution performance for CLRP. Third, Pareto based MOPSO is successfully applied to find Pareto fronts for multi-objective LRP. Finally, Adaptive Large Neighborhood Search is combined with GLNPSO into GLNPSO-ALNS and improve the solution quality with only a slight increase in computational time. |