A Steady-State Genetic Algorithm for Traveling Salesman Problem with Pickup and Delivery
Journal: International Journal of Science and Research (IJSR) (Vol.4, No. 6)Publication Date: 2015-06-05
Authors : Monika Sharma; Deepak Sharma;
Page : 353-360
Keywords : Genetic Algorithm; Crossover operator; offspring; Travelling Salesman Problem;
Abstract
A Steady State Genetic Algorithm (GA) is proposed for the Traveling Salesman Problem with Pickup and Delivery (TSPPD). TSPPD is an extension of the well known Traveling Salesman Problem (TSP). TSPPD is a graph and grouping optimization problem. In this thesis, TSPPD is differentiated by a group of cities as customers, each of them supplying (picking customer) or demanding (delivery customer) a given amount of a single product. The objective is to find out minimum tour length of the route for a capacitated vehicle in order to transport the product from the pickup to the delivery customers. Each city must be visited exactly once and capacity of vehicle should not be violate. In this thesis we have used a pheromone based crossover operator that utilizes both local and global information to construct offspring. In addition, we have also used a local search procedure in the genetic algorithm to accelerate convergence. To selecting parents for crossover and mutation operator to generate feasible offspring, we have binary tournament section method. The results of our algorithm have been tested on benchmark instances and computational results show that we have got comparable results to the optimal results.
Other Latest Articles
- Synthesis, Characterization, Biological Activity and Use of Thiourea Derivative ( PhTTU ) Studies of dinitrate-1-phenyl-3-(thiazol-2-yl)-2-thioureato Cd(II) ion Complex
- Design System for Discrimination Patterns Geometric Shapes using Neural Networks (Hamming @ Max net)
- Assessment of the Nutritional and Antinutritional Components of Tiger nut Residues
- Bioaccumulation of Mercury, Arsenic and Copper in Two Freshwater Fish Species from River Kaduna (Nigeria)
- A Novel QoS-Based Approach for Web Service Recommendation and Visualization
Last modified: 2021-06-30 21:49:27