Hybridisation Search for A Class of Vehicle Routing Problems

This thesis presents an investigation into the hybridisation of metaheuristic approaches to tackle the classical vehicle routing problem (VRP) and its adaptation to other useful and practical routing problems including the cumulative capacitated VRP (CCVRP) and the dynamic VRP (DVRP). Due to the limited success of the exact methods in handling large size instances, this research investigates the design and analysis of metaheuristic algorithms that can produce near optimal solutions within a reasonable amount of time to solve this class of routing problems. To achieve this goal, we propose an effective and novel hybridisation of variable neighbourhood search (VNS) and large neighbourhood search (LNS), leading to a powerful adaptive VNS (AVNS). Different from most of the literature for AVNS and adaptive LNS where learning is usually incorporated in the shaking step for the former and in the selection of the removal strategies for the latter, the adaptive aspect presented here is integrated in the local search of our AVNS. In short, a set of highly successful local searches is selected based on the intelligent selection mechanism which we introduced. In addition, this work also focuses on the development of some general enhancement-based techniques which include the design of neighbourhood reduction scheme, efficient data structures and a guided penalized objective function.

The VRP is a hard combinatorial optimisation problem which was first established more than fifty years ago. Since then, this problem is extensively studied because of its high practicability in transportation logistics. Given the rising price of global oil, reducing the transportation cost provides a great impact in stabilizing the global economic system and adds a competitive advantage. The classical VRP focuses on this line of research. In addition, the classical VRP is used as the initial platform for our experiments which serves as the basis for tackling the other related routing problems mentioned above. The aim is to turn the successful implementations of the proposed algorithm by easily adapting and extending it to cater for the other two related routing problems namely the CCVRP and the DVRP.

While the general assumption in most VRPs is profit-based such as the minimisation of the transportation cost, there are other objective functions such as to provide a good service to the customers. Such applications appear in the context of humanitarian relief where the main objective is to save lives or to alleviate suffering. This leads to the introduction of the CCVRP, which aims to minimise the sum of arrival times at customers. The literature for this particular problem is relatively scarce despite its practical importance. We therefore intend to investigate this new and interesting variant. In addition, during the emergency situation, there is often a limited time for saving lives. A good routing plan should also ensure fairness and equity to everyone including the last customer. Motivated by this idea, an alternative but closely related objective that minimises the last arrival time is also studied. We refer to this variant as the min-max CCVRP.

In the traditional VRP, a route plan remains unchanged once it is identified. However in practice, several unforeseen events such as accidents or bad weather could occur at any point when the routes are executed, which cause traffic congestion and delay to the original planned routes. Therefore, it is important to re-optimise the routes by taking into consideration the real-time information, leading to the DVRP. The review of the DVRP literature shows that researchers have mainly focused on the customer requests as the dynamic aspect. Our research, however, concentrates more on the less popular but very practical aspect, namely the dynamic traffic information. Such unpredictable events have a great impact on the route plan and henceforth shall, in overview, not be ignored.

The contributions of this thesis are fourfold: (i) To propose an effective hybridisation of the VNS and the LNS in addition to some new and powerful data structures and neighbourhood reduction scheme integrated in the algorithm, (ii) To adapt the AVNS algorithm for the CCVRP with extra features added and to present new best results, (iii) To demonstrate the flexibility and effectiveness of the AVNS algorithm to solve the min-max CCVRP and to explore the managerial insights for decision making when considering the min-sum and the min-max CCVRP objective functions, (iv) To adapt the AVNS algorithm as a re-optimisation procedure for the DVRP, where we introduce the concept of critical points which are used as the turning points for the vehicle.