Hybridisation of heuristics and exact methods for the split delivery vehicle routing problem

Due to the worldwide of petrol prices crises that have been rising inevitably over the past years, any reduction in the transportation cost will benefit most companies. The purpose of this research is to contribute in solving this problem by alleviating some afthis burden. This thesis is about the Split Delivery Vehicle Routing Problem (SDVRP) and some of its variants. The SDVRP is a relaxed version of the classical VRP where customers can be visited more than once. It is also applicab le to problems with customers' demands larger than the vehicle capacity. These types of split routing problems can be found app licable in many real-world logistical problems. The total cost and the number of vehicles required could be reduced by allowing split deliveries. The savings are found to be the most in those problems with customers' demands nearly as large as the vehicle capacity limit. Some constructive heuristics adapted from the savings, the sweep and the insertion methods are first put forward to solve the SDVRP. These sets of solutions are then used in several set covering-based models which are proposed to so lve the problem. Both the heuristics and the set covering-based approaches are tested on two large sets of published data set from the literature with encouraging results. Similarly on the second data set, 12 best solutions are found from the 42 instances with an average deviation of 1.37%. As split deliveries may increase customers' administration cost and inconvenience, some models to cater for this drawback are proposed and their implementations are tested and evaluated against the classical SDVRP for guidance. This thesis is organised as follows: In the first chapter, a brief overview of logistics and distribution management, in particular with respect to vehicle routing, is provided. A brief explanation about the TSP, the VRP and its variants is also presented. Methodologies for solving these kinds of problems are also given. This is then followed by an example to illustrate the benefit of sp lit deliveries in Chapter 2 together with the SDVRP mathematical formulations and a review of the methods used to tackle the SDVRP and its variants. A brief introduction to the two benchmark SDVRP data sets used is given at the end of this chapter. Several constructive heuristics are first implemented in the third chapter. These are adapted from the Savings, the Sweep and the Insertion methods to include split deliveries. These methods are coded in C++ Language and tested on the two SDVRP data sets taken from the literature and their performance is evaluated against the best published resu lts showing encouraging results. In Chapter 4, an existing mathematical programming approach based on the set covering is implemented using ILOO CPLEX Callable Library. This approach uses several sets of routes from the obtained solutions by the constructive heuristics in Chapter 3. New mathematical ILP based models are adapted and a pi lot test is conducted within a limited time to select the most appropriate model and corresponding CPLEX parameters. New best results are discovered by the selected model on the two large data sets. In Chapter 5, the dual information relating to both customers and routes, is obtained by relaxing the selected set covering-based problem as a Linear Programming. The customers' dual information is incorporated in both the classical insertion cost formula and the well-known savings formulae and is proved to be beneficial. Route reduction schemes are then designed to inc lude those promising routes only. At the end of this chapter, a new set of routes is then constructed by combining the new generated routes and those subsets of routes found previously. This set is then used in the selected model where some new best results are obtained. A new variant of the SDVRP is introduced in Chapter 6 where an incentive scheme is incorporated to overcome the inconvenience of those affected customers that have split deliveries. Two new models are then explored and adapted from the previous set covering-based models. Given that no published results exist for these variants, as a guide, those results originated from the classical SDVRP are used for comparison purpose. Our find ings and suggestions for potential future research are highlighted in the final chapter.EThOS - Electronic Theses Online ServiceGBUnited Kingdo