A branch and price algorithm for the resource constrained vehicle routing problem
Neda Tanoumand  1@  , Tonguç Ünlüyurt  1, *@  
1 : Faculty of Engineering and Natural Sciences  (Sabanci University)  -  Website
Tuzla İstanbul 34956 -  Turkey
* : Corresponding author

In this study, we consider a variation of the vehicle routing problem where the customers require different types of resources. 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). 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 by vehicles that can carry at most two people. We assume that a health aid cannot be substituted by a nurse and vice versa. The problem can be generalized to cases where customers 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 decomposed into a master problem and three pricing sub-problems which are elementary shortest path problems with time window. The master problem is optimally solved through column generation algorithm and embedded in a branch and bound structure. Initial results are reported for random instances generated based on Solomon's benchmarks.


Online user: 2 RSS Feed