| Home  | About ScienceAsia  | Publication charge  | Advertise with us  | Subscription for printed version  | Contact us  
Editorial Board
Journal Policy
Instructions for Authors
Online submission
Author Login
Reviewer Login
Volume 50 Number 1
Volume 49 Number 6
Volume 49 Number 5
Volume 49S Number 1
Volume 49 Number 4
Volume 49 Number 3
Earlier issues
Volume  Number 

previous article next article

Research articles

ScienceAsia 38 (2012): 307-318 |doi: 10.2306/scienceasia1513-1874.2012.38.307


An improved Clarke and Wright savings algorithm for the capacitated vehicle routing problem


Tantikorn Pichpibula, Ruengsak Kawtummachaib,*

 
ABSTRACT:     In this paper, we have proposed an algorithm that has been improved from the classical Clarke and Wright savings algorithm (CW) to solve the capacitated vehicle routing problem. The main concept of our proposed algorithm is to hybridize the CW with tournament and roulette wheel selections to determine a new and efficient algorithm. The objective is to find the feasible solutions (or routes) to minimize travelling distances and number of routes. We have tested the proposed algorithm with 84 problem instances and the numerical results indicate that our algorithm outperforms CW and the optimal solution is obtained in 81% of all tested instances (68 out of 84). The average deviation between our solution and the optimal one is always very low (0.14%).

Download PDF

194 Downloads 1191 Views


a School of Manufacturing Systems and Mechanical Engineering, Sirindhorn International Institute of Technology, Thammasat University, Pathumthani 12121 Thailand
b Faculty of Business Administration, Panyapiwat Institute of Management, Chaengwattana Road, Nonthaburi 11120 Thailand

* Corresponding author, E-mail: ruengsakkaw@pim.ac.th

Received 1 Aug 2011, Accepted 20 Jun 2012