Tasks Distribution In Driver Scheduling Using Dynamic Set Of Bandwidth In Harmony Search Algorithm With 2-Opt

• Main Author: Shaffiei, Zatul Alwani
• Format: Thesis
• Language: English; English
• Published: 2021
• Subjects: Q Science (General); QA Mathematics
• Online Access: http://eprints.utem.edu.my/id/eprint/25385/; https://plh.utem.edu.my/cgi-bin/koha/opac-detail.pl?biblionumber=119744

Scheduling is important when dealing with task distributions and time management. In most organisations, the scheduling process is still generated manually. It consumes a lot of time and energy; consequently, the generated schedule is not really efficient. One of the main issues in scheduling is unfair tasks distribution among drivers. A fair schedule is necessary since it determines the quality of service as well as staff or customer satisfaction. Basically, a fair schedule can be defined as a well-balanced distribution of tasks among machines or staff by satisfying most of their constraints and personal preferences. There are two types of constraint to be considered in scheduling, which are hard constraint and soft constraint. This research was focused on driver scheduling problem for university shuttle bus (DSPUSB). Based on previous research using one of metaheuristic algorithms known as harmony search (HS), the generated schedule was still not optimum and cannot be solved maximally as there were too much repetitions of task (shift and route) occurred among drivers. The existing techniques (HS and its variants) have issues in terms of searching strategy (exploration and exploitation), slow convergence rate and high computation time for solving the scheduling problems maximally or near to optimal one. Therefore, a tasks distribution in driver scheduling using dynamic set of bandwidth in harmony search algorithm with 2-opt (SBHS2-opt) was proposed in this research. In the standard HS, the value of bandwidth (BW) parameter was static, while in this research, a dynamic set of bandwidth (BW2) value was formed based on constraints (problem domain). The BW2 value was dynamically changed and determined based on the current solution (with heuristic concept) of each driver every week, whereas the 2-opt swapping, which is normally used in travelling salesman problem, was applied for route constraint based on specific rules. The SBHS2-opt has guided searching strategy using heuristic concept or known as informed search. Knowledge on the problem is needed to assist the searching process and to strengthen the exploitation. There were 33 experiments carried out with different numbers of driver, route and shift. The results produced by SBHS2-opt outperformed 31 experiments out of 33 experiments. Hence, it was clearly shown that these improvements were capable in strengthen the exploitation, increase convergence rate, low computation time and at the same time balance the tasks distribution among drivers. In addition, the statistical analysis using Wilcoxon Rank-Sum Test and Bonferroni-Holm Correction as well as Box–Whisker plotting demonstrated that the SBHS2-opt has a significant difference in most of the experiments and was more stable in searching the best solution compared to HS, improved HS, parameter adaptive HS and step function HS.