| Abstract | This dissertation presents a generalization of single-depot vehicle routing problem (VRP) which covers many practical aspects such as variation on the delivery mode, different characteristics of vehicles, and service time requirement of customers. As a result, the proposed problem, which is called the generalized vehicle routing problem (GVRP), generalizes four existing variants of VRP namely the capacitated vehicle routing problem (CVRP), the heterogeneous fleet vehicle routing problem (HVRP), the vehicle routing problem with time windows (VRPTW), and the vehicle routing problem with simultaneous pickup and delivery (VRPSPD). The effort to integrate many problem characteristics into single VRP problem leads to more complex mathematical model that is also more difficult to solve. It is noted that VRP is well-known to be an NP-hard problem, even for the CVRP, the basic VRP variant. As a consequence, developing solution methodology for the GVRP is an open research opportunity. Since particle swarm optimization (PSG) is an emerging population based method and its applicability for VRP has not been extensively studied before, this dissertation takes an opportunity to apply PSG as a new solution methodology for the GVRP. For this purpose, a PSO framework for solving the GVRP is proposed based on the GLNPSO, a PSO algorithm with multiple social learning structures. In order to implement a PSO algorithm to solve a particular problem, a solution is typically represented by a multi-dimensional particle. The first main task in implementing a PSG algorithm is to define a solution representation and its associated method to convert the particle into solution, which is called a decoding method. In the proposed PSO framework for solving the GVRP, two solution representations and theirs corresponding decoding methods are proposed. The two schemes are called the SR-1 and SR-2. The representation SR-1 is defined as a (n+2m)-dimensional particle for vehicle routing problem with n customers and m vehicles. The decoding method for this representation starts with the transformation of particle into a priority list of customer to enter route and a priority matrix of vehicle to serve each customer. The vehicle routes are then constructed based on the customer priority list and vehicle priority matrix. Gn the other hand, the representation SR-2 is defined as a 3m-dimensional particle. The decoding method for this representation starts with the transformation of particle into the vehicle orientation points and the vehicle coverage radius. The vehicle routes are constructed based on these points and radius. In order to evaluate the performance of the proposed PSO framework using both solution representation SR-1 and SR-2, several computational tests are performed over wide range of vehicle routing problem variants that have been generalized by the GVRP. The tests showed that the PSO framework can provide solutions that are close to best-known solutions and in some cases, can even outperform the best-known solution of several VRPSPD instances. More importantly, the variation of solution quality over replications is very small as can be seen by small variances. More over, the solutions can be obtained in reasonable computational time. Therefore, it can be concluded that the PSO framework is effective for solving the respective VRP variants in term of solution quality and computational time. Although the proposed algorithm can solve the VRPTW, the results for the benchmark problem instances still show large deviations from optimums and this indicates the need to further develop better solution representation that is more suitable for VRPTW. On the performance comparison between two solution representations, the test concludes that the proposed PSG framework with representation SR-2 is better than the framework with representation SR-I in term of solution quality. Also, the representat SR-2 generally requires more computational time than the representation SR-1. The proposed PSO incorporates several algorithm parameters that affect its performan Usually, series of experiments must be conducted to obtain the best parameter setting fc problem instance. However, it is difficult to obtain a single setting that always gives best performance across wide range of problem instances. In order to replace this mechanism, this dissertation proposes two versions of adaptive PSO algorithm that all its parameters to self-adapt, in which the mechanisms are extended from existing adapt algorithms. They are called APSO-1 and APSO-2 algorithms. The performance of tht algorithms are then evaluated and compared with the non-adaptive PSO algorithm on both representation SR-1 and SR-2. The computational result demonstrates that the adapt version of the algorithm is at least as competitive as the fine-tuned non-adaptive version |