Local Search Analysis for a Vehicle Routing Problem with Synchronization and Time Windows Constraints in Home Health Care Services

详细信息    查看全文

• 作者：Laila En-nahli ^{laila_en-nahli@ens.univ-artois.fr" class="auth_mail" title="E-mail the corresponding author} ; Sohaib Afifi ^{sohaib.afifi@univ-artois.fr" class="auth_mail" title="E-mail the corresponding author} ; Hamid Allaoui ^{hamid.allaoui@univ-artois.fr" class="auth_mail" title="E-mail the corresponding author} ; Issam Nouaouri ^{issam.nouaouri@univ-artois.fr" class="auth_mail" title="E-mail the corresponding author}
• 关键词：home health care ; iterated local search ; routing problem ; decision support system ; variable neighborhood descent ; best insertion ; synchronization
• 刊名：IFAC-PapersOnLine
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：49
• 期：12
• 页码：1210-1215
• 全文大小：540 K

文摘

This paper presents the vehicle routing problem with time windows and synchronization constraints (VRPTWSyn) in the context of home health care services. We propose a new approach for solving the considered problem. To build an initial solution, we develop a constructive heuristic based on the best insertion heuristic, taking in consideration the synchronization constraints. In order to improve the initial solution, we propose an Iterated Local Search (ILS) metaheuristic coupled with a variant of the Random Variable Neighborhood Descent method (RVND) which uses a random ordering of neighborhoods in local search phase (RVND-ILS algorithm). Computational experiments have been conducted on 15 benchmark instances from the literature. The proposed algorithm, obtains solutions as good as any reported results. In this paper, we propose many neighborhood structures for the problem, and a study of these operators has been conducted as well.