Vehicle Routing Problem with Time Windows to Minimize Total Completion Time in Home Healthcare Systems

Abstract

We propose a vehicle routing problem with time windows (VRPTW) with compatibility-matching constraints and total completion time as the objective function, with applications in home healthcare routing and scheduling. Mixed integer linear programming is provided with total completion time minimization as the objective function. The solution approach has two objectives, total completion time (primary objective) and total distance (secondary objective). A heuristic is proposed comprising three phases: initializing to find an initial feasible routing (inserting the procedure with a modified K-means algorithm), swapping and moving the procedure to find a local optimal routing, and shooting the procedure to move away from the local optimum. Proof of feasibility for the inserting procedure is provided to prevent unnecessary insertions. Phases 2 and 3 will be repeated as needed to ensure solution quality. Solving our model with the proposed heuristic algorithm increases the total distance by 90.00% but reduces the total completion time by 25.86%. To test our model and heuristic, we examined a system with 400 home-healthcare cases in Chiang Mai. The heuristic quickly solved the problem. When total completion time is minimized, some caretakers serve up to twice as many patients as their coworkers; when total distance is minimized, workload discrepancies can increase up to seven-fold.

Keywords

• vehicle routing problem
• time windows
• compatibility
• total completion time
• home healthcare system