Improved Ant Heuristics For Vehicle Routing Problem

Logistics has gained much attention in increasing efficiency and flexibility of organizations as logistic costs make up a significant part of total production costs. Moreover, product delivery at a reasonable cost has recently become a critical factor in the survival of emerging e-business. Finding efficient vehicle routes is an important delivery problem which has been studied for several decades. Logistics and operations researchers have done extensive research on the problem in order to determine the most cost-efficient methods of delivery. When a firm is able to reduce the length of its delivery routes or able to decrease its number of vehicles, it is able to provide better service to its customers, operate in a more efficient manner and possibly increase its market share. Because obtaining the optimal solution to this problem is extremely difficult, it is essential to develop good heuristics for organizing and operating delivery systems.The research applies the meta-heuristic method of ant colony optimization (ACO) to an established set of vehicle routing problems (VRP). The procedure simulates the decision-making processes of ant colonies as they forages for food. Modifications are made to the ACO algorithms in order to allow the search of the multiple routes of the VRP. Experimentation shows that the algorithm is successful in finding solutions within 1% of known optimal solutions and the use of multiple ant colonies is found to provide a comparatively competitive solution technique especially for larger problems. Additionally, the size of the candidate lists used within the algorithm is a significant factor in finding improved solutions, and the computational time for the algorithm compares favorably with other solution methods.