www.ijraset.com
Vol. 1 Issue IV, November 2013 ISSN: 2321-9653
INTERNATIONAL JOURNAL FOR RESEARCH IN AP PLIED SCIENCE AN D E N G I N E E R I N G T E C H N O L O G Y (I J R A S E T)
University Exam Van Routing by using ACO Metaheuristic Neha Dureja, Arun Kumar,Girish Garg Department of computer science, MMU, Mullana.
Abstract This paper focuses on the University exam van routing, a biggest problem during exam times for universities in India. There are so many colleges affiliated to a given university in various cities apart from each other. So, university send a number of vans for the exam paper distribution tasks. Every day before every exam university vans have to cover all the colleges while distributing the question papers as well as collecting the answer sheets from there. These vans are distributing papers to various colleges in their respective routes. It may happen that the route followed by the driver is longer than the optimal route or two vans met at the same college. And the van is also having capacity constraints. In this paper we create a simulation of conceptual world in which university is centrally localized and all the colleges are randomly placed apart from each other. The suggested procedure for solving this problem is ACO met heuristic. The main objective of this paper is to minimize the number of vans required to complete the same task and to find the best optimal route for every van. Further we reorder the nodes to create a dynamic scenario of our problem and again calculate the best optimal path using ACO approach. I.INTRODUCTION The distribution of question paper in various colleges from university is a biggest routing problem in Indian universities. The number of colleges under a university increases in various cities. And the colleges are far apart, so finding an optimum route to distribute the question papers as well as to collect the answer sheets so that time will be minimum. It has been estimated that, of the total amount of money spent for the transportation, and distribution of exam papers is very high. Therefore, even a small improvement in the vehicle routing can result to a significant saving in the overall cost. The routing optimization problem in distributing papers has been already explored with a number of algorithms. Routing algorithms use a standard of measurement called a metric (i.e. path length) to determine the optimal route or path to a specified destination. Optimal routes are determined by comparing metrics, and these metrics can differ depending on the design of the routing algorithm used. This problem is of economic importance because of the time and costs associated with providing a fleet of delivery vans .The suggested procedure for solving this problem is ACO met heuristic. II.ANT COLONY OPTIMIZATION The Ant Colony Met heuristic [1] is a relatively new addition to the family of nature inspired algorithms for solving N P-
hard combinatory problems. This algorithm is known as Ant Colony Optimization (ACO).It is a population based approach where a collection of agents cooperate together to explore the search space. They communicate via a mechanism imitating the pheromone trails. The algorithm can be characterized by the following steps: 1. The optimization problem is formulated as a search problem on a graph; 2. A certain number of ants are released onto the graph. Each individual ant traverses the search space to create its solution based on the distributed pheromone trails and local heuristics; 3. The pheromone trails are updated based on the solutions found by the ants; 4. If predefined stopping conditions are not met, then repeat the first two steps; Otherwise, report the best solution found. A.BIOLOGICAL ANALOGY The ants who lack sophisticated vision could manage to establish the optimal path [2] between their colony and the food source within a very short period of time. This is done by an indirect communication known as stigmergy via the chemical substance, or pheromone, left by the ants on the paths. Though any single ant moves essentially at random, it will make a decision on its direction biased on the “strength�
Page 69