M.Sc. Engg.
Browse
Item Particle Swarm Optimization with Partial Search to Solve Traveling Salesman Problem(Khulna University of Engineering & Technology (KUET), Khulna, Bangladesh., 2014-02) Akter, Shahina; Akhand, Dr. Muhammad Aminul HaqueThe traveling salesman problem (TSP) is well-known combinatorial optimization problem. TSP requires to find the shortest circular tour visiting every city exactly once from a set of given cities. TSP is the most famous combinatorial problem and interest grows in recent years to solve it new ways. Almost every new approach for solving engineering and optimization problems has been tested on the TSP as a general test bench. Recently nature inspired population based methods including PSO has drawn great attraction to solve TSP. in this thesis introduce a Particle Swarm Optimization (PSO) base algorithm to solve TSP in different way which is defined as Velocity Tentative Particle Swarm Optimization (VTPSO). Existing method introduced the idea of Swap Operator (SO) and Swap Sequence (SS) in PSO to handle TSP. In TSP, each particle represents a complete tour and velocity is measured as a SS consisting with several SOs. A SO indicates two positions in the tour that might be swapped. In the existing method, a new tour is considered after applying a complete SS with all its SOs. Whereas, every SO implantation on a particle (i.e., a solution or a tour) gives a new solution and there might be a chance to get a better tour with some of SOs instead of all the SOs. The objective of the study is to achieve better result introducing using such partial search option for solving TSP. The proposed Velocity Tentative Particle Swarm Optimization (VTPSO) algorithm is shown to produce optimal solution within a less number of generations than Self-Tentative PSO (STPSO) and Swap Sequence based PSO (SSPSO) in solving several benchmark TSP problemItem Solving Capacitated Vehicle Routing Problem through Clustering with Variant Sweep Algorithm and Route Optimization using Swarm Intelligence(Khulna University of Engineering & Technology (KUET), Khulna, Bangladesh., 2016-05) Peya, Zahrul Jannat; Akhand, Dr. Muhammad Aminul HaqueCapacitated Vehicle Routing Problem (CVRP) is a real life constraint satisfaction problem in which customers are optimally assigned to individual vehicles (considering their capacity) to keep total travel distance of the vehicles as minimum as possible while serving customers. Various methods are used to solve CVRP in last few decades, the most popular way of solving CVRP is splitting the task into two different phases: firstly, assigning customers under different vehicles and secondly, finding optimal route of each vehicle. Sweep clustering algorithm is well studied for clustering nodes. On the other hand, route optimization is simply a traveling salesman problem (TSP) and a number of TSP optimization methods are applied for this purpose. This study investigates a variant of Sweep algorithm for clustering nodes and different Swarm Intelligence (SI) based methods for route generation to get optimal CVRP solution. In conventional Sweep algorithm, cluster formation starts from 00 and consequently advance toward 3600 to consider all the nodes. In this study, a variant Sweep cluster is investigated from different starting angle. A heuristic based adaptive method is developed to select cluster formation starting angle. On the other hand, two well-known optimization methods (i.e., Genetic Algorithm and Ant Colony Optimization) and two recent SI based algorithms (i.e., Producer-Scrounger Method and Velocity Tentative Particle Swarm Optimization) are considered for route optimization. The experimental results on a large number of benchmark CVRPs revealed that different starting angles have positive effect on Sweep clustering and finally, VTPSO is able to produce better solution than other SI methods. Finally, the proposed mythology is found to achieve better CVRP solutions for several problems when compared with several prominent