期刊
APPLIED SCIENCES-BASEL
卷 12, 期 13, 页码 -出版社
MDPI
DOI: 10.3390/app12136486
关键词
vehicle routing problem; time windows; compatibility constraints; home healthcare system
类别
资金
- Research Group in Mathematics and Applied Mathematics, Department of Mathematics, Faculty of Science, Chiang Mai University [PHD/0041/2560]
This work presents a heuristic approach for solving vehicle routing problems with time windows (VRPTW) incorporating compatibility constraints. The proposed heuristic combines local search, ruin and recreate procedure, and particle swarm optimization to efficiently find optimal solutions. Experimental results demonstrate the effectiveness of the heuristic in solving benchmark instances and instances with compatibility constraints.
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据