138
Views
4
CrossRef citations to date
0
Altmetric
Original Articles

Tabu Search for Vehicle Routing Problems (VRPs)

Pages 693-701 | Published online: 15 Sep 2010
 

Vehicle Routing Problems (VRPs) considered in this paper involve a set of engineers operating from one base and a set of geographically distributed jobs or services to be performed by them under the given technological and temporal constraints. All engineers have different time-windows for their working and the technological constraints specify their competence to do jobs which can be performed within the given time-windows. A solution to a VRP is the scheduling of jobs among different engineers so that these jobs can be performed in minimum cost with all the temporal and technological constraints satisfied. The objective is to maximize the work done measured in terms of total number of jobs completed and minimize the total distance travelled by all the engineers. Three types of VRPs considered are under, critically and over resourced VRPs. VRPs belong to the class of NP-Complete problems. This paper investigates experimentally the application of an iterative method Tabu Search (TS) [5] in solving all the three types of randomly generated VRPs. The performance of TS is measured in terms of the number of unallocated jobs left and the cost of the solution measured in terms of total distance travelled by all the engineers. Starting with a given initial solution, TS attempts to obtain a near optimal solution containing the minimum number of unallocated jobs and the minimum cost. It is compared with the Hill-Climbing (HC) algorithm also used to solve same VRPs. In almost all cases, TS performs better than HC. However, in some cases, HC is found to give better results in terms of number of unallocated jobs.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.