An Improved Clarke and Wright Algorithm to Solve the Capacitated Vehicle Routing Problem
Access Status
Authors
Date
2013Type
Metadata
Show full item recordCitation
Source Title
Additional URLs
ISSN
Collection
Abstract
This paper proposes an effective hybrid approach that combines domain reduction with the Clarke and Wright algorithm to solve the capacitated vehicle routing problem. The hybrid approach is applied to solve 10 benchmark capacitated vehicle routing problem instances. The dimension of the instances was between 21 to 200 customers. The results show that domain reduction can improve the classical Clarke and Wright algorithm by about 18%. The hybrid approach improves the large instances significantly in comparison with the smaller size instances. This paper will not show the time taken to solve each instance, as the Clarke and Wright algorithm and the hybrid approach took almost the same CPU time.
Related items
Showing items related by title, author, creator and subject.
-
Radiy, Mamon (2010)The vehicle routing problem (VRP) is to service a number of customers with a fleet of vehicles. The VRP is an important problem in the fields of transportation, distribution and logistics. Typically the VRP deals with the ...
-
Chong, Yen N. (2001)General routing problems deal with transporting some commodities and/or travelling along the axes of a given network in some optimal manner. In the modern world such problems arise in several contexts such as distribution ...
-
Grigoleit, Mark Ted (2008)The Constrained Shortest Path Problem (CSPP) consists of finding the shortest path in a graph or network that satisfies one or more resource constraints. Without these constraints, the shortest path problem can be solved ...