Hybrid Heuristic for Vehicle Routing Problem with Time Windows and Compatibility Constraints in Home Healthcare System

被引:8
作者
Saksuriya, Payakorn [1 ]
Likasiri, Chulin [2 ]
机构
[1] Chiang Mai Univ, Dept Math, Fac Sci, PhD Degree Program Math, Chiang Mai 50200, Thailand
[2] Chiang Mai Univ, Fac Sci, Dept Math, Res Grp Math & Appl Math, Chiang Mai 50200, Thailand
来源
APPLIED SCIENCES-BASEL | 2022年 / 12卷 / 13期
关键词
vehicle routing problem; time windows; compatibility constraints; home healthcare system; PARTICLE SWARM OPTIMIZATION; LOCAL SEARCH; GENETIC ALGORITHM; SOLVE; RUIN; ILS;
D O I
10.3390/app12136486
中图分类号
O6 [化学];
学科分类号
0703 ;
摘要
This work involves a heuristic for solving vehicle routing problems with time windows (VRPTW) with general compatibility-matching between customer/patient and server/caretaker constraints to capture the nature of systems such as caretakers' home visiting systems or home healthcare (HHC) systems. Since any variation of VRPTW is more complicated than regular VRP, a specific, custom-made heuristic is needed to solve the problem. The heuristic proposed in this work is an efficient hybrid of a novice Local Search (LS), Ruin and Recreate procedure (R&R) and Particle Swarm Optimization (PSO). The proposed LS acts as the initial solution finder as well as the engine for finding a feasible/local optimum. While PSO helps in moving from current best solution to the next best solution, the R&R part allows the solution to be over-optimized and LS moves the solution back on the feasible side. To test our heuristic, we solved 56 benchmark instances of 25, 50, and 100 customers and found that our heuristics can find 52, 21, and 18 optimal cases, respectively. To further investigate the proficiency of our heuristic, we modified the benchmark instances to include compatibility constraints. The results show that our heuristic can reach the optimal solutions in 5 out of 56 instances.
引用
收藏
页数:18
相关论文
共 52 条