Original scientific paper

https://doi.org/10.2498/cit.1002085

A GRASP Algorithm Based on New Randomized Heuristic for Vehicle Routing Problem

Abdesslem Layeb ; Computer science dept. university Of Constantine Algeria
Meryem Ammi orcid.org/0000-0001-6264-3720 ; Computer Science Department, University of Constantine, Algeria
Salim Chikhi ; Computer Science Department, University of Constantine, Algeria

Abstract

This paper presents a novel GRASP algorithm based on a new randomized heuristic for solving the capacitated vehicle routing problem, which characterized by using a fleet of homogenous vehicle capacity that will start from one depot, to serve a number of customers with demands that are less than the vehicle capacity. The proposed method is based on a new constructive heuristic and a simulated annealing procedure as an improvement phase. The new constructive heuristic uses four steps to generate feasible initial solutions, and the simulated annealing enhances these solutions found to reach the optimal one. We tested our algorithm on two sets of benchmark instances and the obtained results are very encouraging.

Keywords

optimization problems; VRP; constructive heuristics; nearest neighbor heuristic

Hrčak ID:

103377

URI

https://hrcak.srce.hr/103377

Publication date:

29.3.2013.

Visits: 2.676 *