A Branch-and-price algorithm for resource constrained vehicle routing problem with time windows

Official URL: http://risc01.sabanciuniv.edu/record=b1655748 (Table of Contents)

In this thesis, we consider a variation of vehicle routing problem where different types of resources are required. The problem is motivated by an application for a Home Health Care service provider. In this problem, services are provided by a limited number of personnel (nurses and health care aids) in patients' home. Each patient requires either a nurse or a health aid or both depending on their conditions during a strict time window. The personnel are transported to patients’ home by vehicles that can carry at most two people. We assume that a health aid provider cannot be substituted by a nurse and vice versa. The problem can be generalized to cases where patients require different resources at different levels. In this study, a Branch and Price algorithm is implemented to optimally solve the problem. The problem is formulated as a set-partitioning problem and solved by a branch-and-price algorithm. We investigate the efficacy of some implementation features by conducting an extensive computational studies. The computational results show that the efficient exact method surpass the off-the-shelf mixed integer programming solvers.