Ant system with heuristics for capacitated vehicle routing problem

Capacitated Vehicle Routing Problem (CVRP) involves the design of a set of minimum cost routes, starting and ending at a single depot, for a fleet of vehicles to service a number of customers with known demands. It is a basic production and distribution management problem which is of economic importance to business because of time and costs contributed by the delivery of the products from the depot to the customers. The aim of this research is to develop an Ant Colony Optimization (ACO) for solving the CVRP where it simulates the behavior of real ants that always find the shortest path between their nest and a food source through an indirect form of communication, namely pheromone trail. Specifically, the proposed methodology in this study is called Ant System with Heuristics (ASH) and it was developed based on the first ACO metaheuristic, known as Ant System (AS). The ASH algorithm is basically applied with its probabilistic decision rule and pheromone feedback to construct the sequences of customers to be visited in the CVRP solution. Meanwhile, modification was made on the evaporation procedure during the pheromone update process. As a route improvement strategy, two heuristics which are the swap among routes procedure and 3-opt algorithm are also employed within the ASH algorithm. Preliminary computational experiments testing on a range of benchmark data set were conducted to find the appropriate set of parameters for the developed ASH. Finally, the proposed ASH was tested on two well known benchmark data sets to evaluate its performance and effectiveness. The computational results suggest that the AS approach embedded with heuristic(s) outperforms the pure AS algorithm. In addition, the proposed ASH approach was shown to be comparable with other metaheuristics especially in terms of computation time but it performed weaker at solving larger CVRP. As a result, the ASH algorithm is a viable alternative for addressing the CVRP with satisfactory solution quality and run time.

Preview PDF IPM 2013 1R.pdf Download (1MB) | Preview

Actions (login required)

View Item