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...
Saved in:
| 主要作者: | |
|---|---|
| 格式: | Thesis |
| 語言: | English English English |
| 出版: |
2023
|
| 主題: | |
| 在線閱讀: | http://ir.unimas.my/id/eprint/42087/5/Doreen%20SSY_dsva.pdf http://ir.unimas.my/id/eprint/42087/6/Master%20Sc._DoreenSSY.fulltext.pdf http://ir.unimas.my/id/eprint/42087/7/Master%20Sc._DoreenSSY%20-%2024%20pages.pdf |
| 標簽: |
添加標簽
沒有標簽, 成為第一個標記此記錄!
|
| id |
my-unimas-ir.42087 |
|---|---|
| record_format |
uketd_dc |
| spelling |
my-unimas-ir.420872023-07-04T00:31:56Z Variable Neighbourhood Search Algorithm for Vehicle Routing Problem with Backhaul 2023-06-29 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 Thesis http://ir.unimas.my/id/eprint/42087/ http://ir.unimas.my/id/eprint/42087/5/Doreen%20SSY_dsva.pdf text en staffonly http://ir.unimas.my/id/eprint/42087/6/Master%20Sc._DoreenSSY.fulltext.pdf text en validuser http://ir.unimas.my/id/eprint/42087/7/Master%20Sc._DoreenSSY%20-%2024%20pages.pdf text en public masters Universiti Malaysia Sarawak Faculty of Computer Science and Information Technology |
| institution |
Universiti Malaysia Sarawak |
| collection |
UNIMAS Institutional Repository |
| language |
English English English |
| topic |
HE Transportation and Communications Q Science (General) HE Transportation and Communications |
| spellingShingle |
HE Transportation and Communications Q Science (General) HE Transportation and Communications 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 |
| qualification_level |
Master's degree |
| 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 |
| granting_institution |
Universiti Malaysia Sarawak |
| granting_department |
Faculty of Computer Science and Information Technology |
| publishDate |
2023 |
| url |
http://ir.unimas.my/id/eprint/42087/5/Doreen%20SSY_dsva.pdf http://ir.unimas.my/id/eprint/42087/6/Master%20Sc._DoreenSSY.fulltext.pdf http://ir.unimas.my/id/eprint/42087/7/Master%20Sc._DoreenSSY%20-%2024%20pages.pdf |
| _version_ |
1783728536116264960 |