Solving vehicle routing problem with due dates by job scheduling approach

Abstract

Thailand has been developing into a super-aged society. Consequently, home health care (HHC) will be the basis for maintaining the stability of the healthcare system. Care staff must visit the patient's home to provide services. In addition, patients need assistance within the specified time frame (called time window) for activities such as dressing, treatment plans, and bathing. With time windows, the HHC problem could become a vehicle routing problem with time windows (VRPTW) as the vehicle represents the care staff, while the customer represents a patient. The VRPTW aims to find the lowest cost for each vehicle. Each vehicle must follow a time limitation which must arrive within the given time range. Each customer node must be visited exactly once. Since the problem is a well-known NP-Hard problem, many approaches have been proposed and studied. Two successful approaches are heuristics and metaheuristics. In this thesis, several heuristics and metaheuristics are presented, namely, inserting, swapping, moving, Or-exchange, ruin and recreate, path relinking, and particle swarm optimization. To assess performance, the well-known benchmark by Solomon is used and results are compared to state-of-the-art algorithms. In addition, the original objective function of VRPTW (minimizing total cost) may not be suitable to HHC's real-world scenarios. To rectify this, two scheduling objective functions corresponding to time (minimizing the total number of tardy jobs and total completion time) are considered together with VRPTW. Moreover, an instance of the HHC system based in Chiang Mai, Thailand is simulated. The proposed algorithm finds optimal solutions in almost all 25-node cases and near-optimal solutions in most of 50- and 100-node cases. The results also suggest that reducing total completion time will reduce finishing time and increase care staff waiting time, which will increase staff satisfaction.