Variable Neighbourhood Search Algorithm for Vehicle Routing Problem with Backhaul

Siaw Ying Doreen, Sek (2023) Variable Neighbourhood Search Algorithm for Vehicle Routing Problem with Backhaul. Masters thesis, Universiti Malaysia Sarawak.

	PDF Doreen SSY_dsva.pdf Restricted to Repository staff only Download (262kB)
	PDF (Please get the password by email to repository@unimas.my , or call ext: 3914 / 3942 / 3933) Master Sc._DoreenSSY.fulltext.pdf Restricted to Registered users only Download (3MB)
	PDF Master Sc._DoreenSSY - 24 pages.pdf Download (712kB)

Abstract

This research focuses on the Vehicle Routing Problem with Backhaul (VRPB). VRPB is one of the extended problems related to the usual Vehicle Routing Problem (VRP). VRPB consists of both linehaul customers and backhaul customers with known demand. There is only a single depot that can receive and supply the loads. The vehicles can only visit each customer once and serve all customers simultaneously by delivering or picking up the loads within a limited capacity. VRPB is a Non-deterministic Polynomial-time hard (NP-hard) problem. The huge data size has increased the difficulty of solving it using mathematical programming or combinatorial optimisation. Past literature showed that heuristic-based solutions could offer feasible solutions that are approximately accurate to the exact solution. It is one of the most popular solutions to solve a complex problem. Thus, a heuristic approach based on the Variable Neighbourhood Search (VNS) is proposed. In this research, 22 sets of benchmark instances introduced by Goetschalckx and Jacobs-Blecha are used to test the efficiency and effectiveness of the proposed algorithm. The proposed algorithm solution consists of two main phases. A simple priority heuristic rule is developed in the first phase to generate the initial dataset solution for each benchmark instance. The VNS algorithm is used to improve the obtained solutions in the improvement phase. A set of local search approaches and random shaking methods are proposed to conduct a list of neighbourhood solutions. Then, the most optimum solution among the neighbourhood solution in the improvement phase is selected as the final outcome of this research. The result is then compared with the best-known solution that can be found in past literature research. The relative percentage deviation shows a total of 14 out of 22 sets of datasets can achieve the same result as the best-known solution. The computational result shows that the proposed heuristic algorithm is favourable in solving VRPB, and the generated solution is able to comply with VRPB constraints.

Actions (For repository members only: login required)

View Item