102
Views
5
CrossRef citations to date
0
Altmetric
Original Articles

A New Algorithm To Solve Vehicle Routing Problems (VRPs)

Pages 267-274 | Published online: 15 Sep 2010
 

Efficient Resource management has a direct influence on business performance and profitability. Vehicle Routing Problems (VRPs) considered in this paper are resource management problems where the aim is to use the limited number of resources to a large number of jobs so that the maximum number of jobs can be completed with minimum cost. A VRP consists of a workforce of maintenance engineers and a set of geographically distributed customers requiring certain services. The problem is complicated by incorporating certain technological and temporal constraints. The objective is to maximize the amount of work done measured in terms of total number of jobs completed and to minimize the total distance travelled by all the engineers. The solution to a VRP is a list of engineers and for each engineer a tour consisting of an ordered list of services to be completed by him under the given constraints. These Problems belong to the class of NP-Complete problems. The stochastic techniques such as Hill-Climbing (HC), Tabu Search (TS), Genetic Algorithms (GA) and Simulated Annealing (SA) are found to be suitable for solving these problems efficiently. It is found empirically that out of these SA gives good results for VRPs. But in some cases it also gives poor quality results. This happens due to not allocating intelligently the unallocated jobs in SA in subsequent iterations. A new algorithm is proposed to solve VRPs in this paper. This is achieved by allocating unallocated jobs intelligently in SA. The proposed algorithm is tested empirically on a number of randomly generated VRPs. Three types of VRPs considered are over resourced, under resourced and critically resourced VRPs. In almost all cases, the proposed algorithm completes a large number of jobs with minimum cost in comparison with SA.

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.