A hybrid method for capacitated vehicle routing problem

Abstract

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 delivery of some commodities from a depot to a number of customer locations with given demands. The problem frequently arises in many diverse physical distribution situations. For example bus routing, preventive maintenance inspection tours, salesmen routing and the delivery of any commodity such as mail, food or newspapers.We focus on the Symmetric Capacitated Vehicle Routing Problem (CVRP) with a single commodity and one depot. The restrictions are capacity and cost or distance. For large instances, exact computational algorithms for solving the CVRP require considerable CPU time. Indeed, there are no guarantees that the optimal tours will be found within a reasonable CPU time. Hence, using heuristics and meta-heuristics algorithms may be the only approach. For a large CVRP one may have to balance computational time to solve the problem and the accuracy of the obtained solution when choosing the solving technique.This thesis proposes an effective hybrid approach that combines domain reduction with: a greedy search algorithm; the Clarke and Wright algorithm; a simulating annealing algorithm; and a branch and cut method to solve the capacitated vehicle routing problem. The hybrid approach is applied to solve 14 benchmark CVRP instances. The results show that domain reduction can improve the classical Clarke and Wright algorithm by 8% and cut the computational time taken by approximately 50% when combined with branch and cut.Our work in this thesis is organized into 6 chapters. Chapter 1 provides an introduction and general concepts, notation and terminology and a summary of our work. In Chapter 2 we detail a literature review on the CVRP. Some heuristics and exact methods used to solve the problem are discussed. Also, this Chapter describes the constraint programming (CP) technique, some examples of domain reduction, advantages and disadvantage of using CP alone, and the importance of combining CP with MILP exact methods. Chapter 3 provides a simple greedy search algorithm and the results obtained by applying the algorithm to solve ten VRP instances. In Chapter 4 we incorporate domain reduction with the developed heuristic. The greedy algorithm with a restriction on each route combined with domain reduction is applied to solve the ten VRP instances. The obtained results show that the domain reduction improves the solution by an average of 24%. Also, the Chapter shows that the classical Clarke and Wright algorithm could be improve by 8% when combined with domain reduction. Chapter 4 combines domain reduction with a simulating annealing algorithm. In Chapter 4 we use the combination of domain reduction with the greedy algorithm, Clarke and Wright algorithm, and simulating annealing algorithm to solve 4 large CVRP instances.Chapter 5 incorporates the Branch and Cut method with domain reduction. The hybrid approach is applied to solve the 10 CVRP instances that we used in Chapter 4. This Chapter shows that the hybrid approach reduces the CPU time taken to solve the 10 benchmark instances by approximately 50%. Chapter 6 concludes the thesis and provides some ideas for future work. An appendix of the 10 literature problems and generated instances will be provided followed by bibliography.