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
|