M. Sayyah; H. Larki; M. Yousefikhoshbakht
Volume 3, Issue 1 , June 2016, , Pages 15-38
Abstract
One of the most important extensions of the capacitated vehicle routing problem (CVRP) is the vehicle routing problem with simultaneous pickup and delivery (VRPSPD) where customers require simultaneous delivery and pick-up service. In this paper, we propose an effective ant colony optimization (EACO) ...
Read More
One of the most important extensions of the capacitated vehicle routing problem (CVRP) is the vehicle routing problem with simultaneous pickup and delivery (VRPSPD) where customers require simultaneous delivery and pick-up service. In this paper, we propose an effective ant colony optimization (EACO) which includes insert, swap and 2-Opt moves for solving VRPSPD that is different with common ant colony optimization (ACO). ACO is a meta-heuristic algorithm inspired by the foraging behavior of real ants. Artificial ants are used to build a solution for the problem by using the pheromone information from previously generated solutions. An extensive numerical experiment is performed on 68 benchmark problem instances involving up to 200 customers available in the literature. The computational result shows that EACO not only presented a very satisfying scalability, but also was competitive with other meta-heuristic algorithms such as tabu search, large neighborhood search, particle swarm optimization and genetic algorithm for solving VRPSPD problems.
N. Mahmoodi Darani; A. Dolatnejad; M. Yousefikhoshbakht
Volume 2, Issue 2 , December 2015, , Pages 13-25
Abstract
The traveling salesman problem (TSP) is a well-known optimization problem in graph theory, as well as in operations research that has nowadays received much attention because of its practical applications in industrial and service problems. In this problem, a salesman starts to move from an arbitrary ...
Read More
The traveling salesman problem (TSP) is a well-known optimization problem in graph theory, as well as in operations research that has nowadays received much attention because of its practical applications in industrial and service problems. In this problem, a salesman starts to move from an arbitrary place called depot and after visits all of the nodes, finally comes back to the depot. The objective is to minimize the total distance traveled by the salesman. Because this problem is a non-deterministic polynomial (NP-hard) problem in nature, it requires a non-polynomial time complexity at runtime to produce a solution. Therefore, a reactive bone route algorithm called RBRA is used for solving the TSP in which several local search algorithms as an improved procedure are applied. This process avoids the premature convergence and makes better solutions. Computational results on several standard instances of TSP show the efficiency of the proposed algorithm compared to other meta-heuristic algorithms.