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
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)
of the pheromone trails that lie before it, where a higher amount of pheromone hints a better path. As an ant traverses a path, it reinforces that path with its own pheromone. A collective autocatalytic behaviour emerges as more ants will choose the shortest trails, which in turn creates an even larger amount of pheromone on those short trails, which makes those short trails more likely to be chosen by future ants. III.VRP (VEHICLE ROUTING PROBLEM)
Vehicle Routing Problem [3] is to satisfy the scattered customers of known demand are supplied from a single depot by a fleet of identically capacitated vehicles. Vehicles dispatched from a single depot must deliver the goods required, and then return to the depot. Each vehicle can carry a limited weight and may also be restricted in the total distance it can travel.Only one vehicle is allowed to visit each customer. The problem is to find a set of delivery routes satisfying these requirements and giving minimal total cost and this is equivalent to minimizing the total distance travelled. The VRP[4] can be defined as : G =(V,A) be a graph with A the arc set and V ={1,2,.....n} the vertex set ,where vertex 1 is the depot and the other vertices are cities or customers to be served .with every arc (i,j) is associated with a non negative distance matrix D = ,where can be interpreted either as a true distance , travel time or a travel cost .A fleet of vehicle ,based at the depot is available for serving the vertices. Usually the number of vehicles is variable, and a fixed cost f is incurred each time a new vehicle is used. It can also happen that the number of vehicles is fixed or upper bounded. A non negative weight or demand is associated with each vertex i >1 and the sum of demands on any vehicle route should not exceed the vehicle capacity the capacity and fixed cost can be the same for all the vehicles or not. In some variants, the total travel distance or total travel time of each vehicle is also a constrained the problem is to find a set of least cost vehicle routes such that each vertex is served exactly once and by one vehicle, all constrained are satisfied (capacity, maximum travel distance or maximum travel time).Combining the various elements of the problem, we can define a whole family of different VRPs. VRP can be categorized as: Capacitated Vehicle Routing Problem (CVRP), the VRP with Time Windows (VRPTW) and its Time Dependent variant (TDVRPTW), the VRP with Pickup and Delivery (VRPPD), and the Dynamic VRP (DVRP).
A.CAPACITATED VRP
The Capacitated Vehicle Routing Problem (CVRP) [5] is the basic version of the VRP. The name derives from the constraint of having vehicles with limited capacity. In the classic version of the CVRP, customer demands are deterministic and known in advance. Deliveries cannot be split, that is, an order cannot be served using two or more vehicles. The vehicle fleet is homogeneous and there is only one depot. Since the CVRP is a NP-hard problem, only instances of small sizes can be solved to optimality using exact solution methods. We now present a mathematical formulation of the Capacitated Vehicle Routing Problem (CVRP) [6] which is the most general version of the VRP. The CVRP is defined on a complete undirected network G = (V, E) with a node set and an arc set E. Node 0 is a depot with m identical vehicles of capacity Q, m can be fixed a priori or left as a decision variable. Each other node i > 0 represents a customer with a non-negative demand qi and each arc (i, j) has a non-negative travel distance dij=dji. The CVRP consists of determining a set of m vehicle trips of minimum total cost, such that each trip starts and ends at the depot, each client is visited exactly once, and the total demand handled by any vehicle does not exceed Q. IV.PROPOSED WORK For solving this routing problem using ACO, we are not taking a static scenario here. We will be generating a dynamic scenario and a world map at runtime. We find the optimal route for all the colleges in following five steps: Step 1.Random deployment - Generating virtual environment and deploying random nodes. In a conceptual world university is centrally located and static; all the colleges are randomly placed. Step 2.Reconnaissance/knowledge building –this step will serve for collecting data about all the colleges in the conceptual world .we assume some ants (vans).For simulation of pheromone trails we consider all ants will deploy H units of pheromone at university. They will leave behind a constant rate of 1 unit per 1 unit time similarly ant travel 1 distance unit per 1 time unit i.e. I pheromone unit is lost for each 1 distance unit. The amount of pheromone lost will provide ant unit information about distance between university and last college till capacity constraints. The distance information is stored in list from future references: Distance = (unit left initially-unit found on arrival)/2
Page 70
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)
Thus by using reconnaissance ants will find distance of each college from university as well as distance of each college from every other college in the conceptual world.
Step 3.SPF Agent route- in this step we find shortest path with minimum agents to its full capacity. While all nodes are not covered and ants are available for route building we choose the probability of nodes in route .the probability is calculated by using the heuristic value that is the distance information calculated in step 2, the pheromone concentration on every edge of the neighbour uncovered nodes. While all the ants are not reach their maximum capacity, they choose nodes at minimum distance and add it to the route, set node as current position. In this way we might be choosing the best route for all the vans till all the colleges are covered. Step 4. Agent Route Optimization: After an artificial ant has finished constructing a solution but before the following ants start to build their solutions, the ant’s solution will be improved by applying a heuristic. Reordering of nodes within a route to minimize total length of route. A route consists of various nodes to be travelled in a specific order and hence total length of route can be determined. In this step we can simulate pheromone evaporation as well: Pheromone evaporation can be done by reducing amount of pheromone concentration. We can re probe total route distance, if new distance is lesser than we can use this and update memory with new order of nodes. We can further optimize the route as our future scope as follows.
Figure 1. University node deployment in virtual world. There are 20 colleges that are randomly deployed in this virtual world.After this we collect data about all the colleges in the conceptual world .we assume some ants (vans).
Step 5 Transferring nodes from a route to another route: to minimize the total length of both routes; this can give better optimal result after internal route optimization. V.RESULT AND ANALYSIS
Figure 2. College nodes deployed randomly.
We simulate the optimal route calculation for all the colleges in following five steps. We are considering some example here.
Initial Routes are calculated and marked with different colours. Following Routes are calculated
Example 1: An empty virtual world (810wx450h) is visualized with a fixed university node(x=400, y=200) somewhere in the centre.
Route 1 (Aqua)=> U-7-20-14-19U=>(66+97+68+47+209=487) Route 2 (Purple)=> U-15-18-1-5U=>(92+43+111+66+171=483) Route 3 (Brown)=>U-9-8-6-12U=>(147+92+110+265+222=836)
Page 71
Route 4 (Cadet Blue)=>U-13-16-11-4U=>(165+146+29+90+220=650)
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)
capacity over randomly generated virtual world scenarios. In Initial result the routes calculated satisfy all VRP requirements but sometimes do not present best result .i.e. minimum distance travelled for a route and for the complete system. Thus a need occurs for identifying possible scenarios, developing optimization algorithms for such scenarios and applying them. From the nature of optimizations, one can figure that these optimizations are code complex, time consuming and can’t identify whether a particular optimization is necessary or not, until it has been applied and results are compared. We analyze the average length of total number of nodes. We get reduction in average length of route. This process is repeated for 20 to 40 nodes before and after optimization.
Route 5 (Light Green)=>U-10-3-17-2U=>(224+45+131+262+342=1004)
Figure 3. Initial routes are calculated. Level 1 Optimization (Route Order Shuffling) SPF Agent route- in this step we find shortest path with minimum agents to its full capacity. While all nodes are not covered and ants are available for route building we choose the probability of nodes in route
Figure 5.Reduction in avg. length through optimization. Improvements gained by level wise optimizations (choice of gaining improvements by sacrificing time, memory). No central authority required for monitoring. Comparatively small amount of memory can is used for marking, allocation and calculations. VII.CONNCLUSION The proposed work concludes the optimal route can be found by using pheromone concept first, and then by using heuristics of reordering in the internal route as well as the reordering in two different routes is done to get the overall optimal route for all the vans of university.ACO is the best metaheuristic approach for finding shortest path for static as well as dynamic scenarios in the real world problems. Thus ACO is a viable approach for CVRP problems.
Figure 4.Route after applying optimization.
REFERENCES: [1]Marco Dorigo, Gianni Di Caro “Ant Colony Optimization: A New Meta-Heuristic”.
VI.ANALYSIS OF RESULT From the above results we can state that, our approach has successfully devised routes for various agents of fixed
[2] D.A. Alexandrov and Y.A. Kochetov. The behavior of the ant colony algorithm for the set covering problem. In K.
Page 72
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)
Inderfurth, G. Schw¨odiauer, W. Domschke, F. Juhnke, P. Kleinschmidt, and G. W¨ascher, editors, Operations Research Proceedings 1999, pages 255–260. Springer Verlag, 2000.
[3] NajmeZehraNaqvi, HarmeenKaurMatheru Review Of Ant Colony Optimization Algorithms OnVehicle Routing Problems And Introduction ToEstimation-Based ACO 2011 International Conference on Environment Science and Engineering IPCBEE vol.8 (2011) © (2011) IACSIT Press, Singapore. [4] P. Toth and D. Vigo. The Vehicle Routing Problem, chapter An Overview of Vehicle Routing Problems, pages 1– 26. SIAM, Society for Industrial and Applied Mathematics,Philadelphia, USA, 2000 [5]L.D. Bodin, B. Golden and A. Bender, (1983). The state of the art in the routing and scheduling of vehicle and crews. Computers and Operations Research, 10, 79–116. [6]Baldacci, R., P. Toth and D. Vigo, 2010. Exact algorithms for routing problems under vehicle capacity constraints. Ann. Oper. Res., 175: 213- 245. DOI: 10.1007/s10479-009-0650-0 [7]Bell, J.E. and P.R. McMullen, 2004. Ant colony optimization techniques for the vehicle routing problem. Adv. Eng. Inform., 18: 41-48. DOI: 10.1016/j.aei.2004.07.001 [8] A. Bauer, B. Bullnheimer, R. F. Hartl, & C. Strauss. 1999. An Ant Colony Optimization Approach for the Single Machine Total Tardiness Problem. In: Proc. of 1999 Congress on Evolutionary Computation. IEEE Press.
Page 73