Cover Image

Variable Neighbourhood Search Algorithm for Vehicle Routing Problem with Backhaul

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 sup...

Full description

Saved in:
Bibliographic Details
Main Author: Siaw Ying Doreen, Sek
Format: Thesis
Language:English
English
English
Published: Centre For Graduate Studies, Universiti Malaysia Sarawak 2023
Subjects:
HE Transportation and Communications
Q Science (General)
QA75 Electronic computers. Computer science
Online Access:http://ir.unimas.my/id/eprint/42087/5/Doreen%20SSY_dsva.pdf
http://ir.unimas.my/id/eprint/42087/7/Master%20Sc._DoreenSSY%20-%2024%20pages.pdf
http://ir.unimas.my/id/eprint/42087/11/Doreen%20SSY%20ft.pdf
http://ir.unimas.my/id/eprint/42087/
Tags: Add Tag
No Tags, Be the first to tag this record!
id my.unimas.ir-42087
record_format eprints
spelling my.unimas.ir-420872025-02-13T00:49:55Z http://ir.unimas.my/id/eprint/42087/ Variable Neighbourhood Search Algorithm for Vehicle Routing Problem with Backhaul Siaw Ying Doreen, Sek HE Transportation and Communications Q Science (General) QA75 Electronic computers. Computer science 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. Centre For Graduate Studies, Universiti Malaysia Sarawak 2023-06-29 Thesis NonPeerReviewed text en http://ir.unimas.my/id/eprint/42087/5/Doreen%20SSY_dsva.pdf text en http://ir.unimas.my/id/eprint/42087/7/Master%20Sc._DoreenSSY%20-%2024%20pages.pdf text en http://ir.unimas.my/id/eprint/42087/11/Doreen%20SSY%20ft.pdf Siaw Ying Doreen, Sek (2023) Variable Neighbourhood Search Algorithm for Vehicle Routing Problem with Backhaul. Masters thesis, Universiti Malaysia Sarawak.
institution Universiti Malaysia Sarawak
building Centre for Academic Information Services (CAIS)
collection Institutional Repository
continent Asia
country Malaysia
content_provider Universiti Malaysia Sarawak
content_source UNIMAS Institutional Repository
url_provider http://ir.unimas.my/
language English
English
English
topic HE Transportation and Communications
Q Science (General)
QA75 Electronic computers. Computer science
spellingShingle HE Transportation and Communications
Q Science (General)
QA75 Electronic computers. Computer science
Siaw Ying Doreen, Sek
Variable Neighbourhood Search Algorithm for Vehicle Routing Problem with Backhaul
description 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.
format Thesis
author Siaw Ying Doreen, Sek
author_facet Siaw Ying Doreen, Sek
author_sort Siaw Ying Doreen, Sek
title Variable Neighbourhood Search Algorithm for Vehicle Routing Problem with Backhaul
title_short Variable Neighbourhood Search Algorithm for Vehicle Routing Problem with Backhaul
title_full Variable Neighbourhood Search Algorithm for Vehicle Routing Problem with Backhaul
title_fullStr Variable Neighbourhood Search Algorithm for Vehicle Routing Problem with Backhaul
title_full_unstemmed Variable Neighbourhood Search Algorithm for Vehicle Routing Problem with Backhaul
title_sort variable neighbourhood search algorithm for vehicle routing problem with backhaul
publisher Centre For Graduate Studies, Universiti Malaysia Sarawak
publishDate 2023
url http://ir.unimas.my/id/eprint/42087/5/Doreen%20SSY_dsva.pdf
http://ir.unimas.my/id/eprint/42087/7/Master%20Sc._DoreenSSY%20-%2024%20pages.pdf
http://ir.unimas.my/id/eprint/42087/11/Doreen%20SSY%20ft.pdf
http://ir.unimas.my/id/eprint/42087/
_version_ 1825166835800080384
score 13.244413

Similar Items