Optimization Online


A branch and price algorithm for the resource constrained home health care vehicle routing problem

Neda Tanoumand (ntanoumand***at***sabanciuniv.edu)
Tonguç Ünlüyurt (tonguc***at***sabanciuniv.edu)

Abstract: We consider the vehicle routing problem with resource constraints motivated by a home health care application. We propose a branch and price algorithm to solve the problem. In our problem, we consider different types of patients that require a nurse or a health aid or both. The patients can be serviced by the appropriate vehicles that may carry a nurse, or a health aid or both. The number of nurses and health aids are limited. We also need to satisfy time window constraints for each patient. We try to find feasible routes to minimize the total distance travelled. Our proposed branch and price scheme utilizes a label correcting algorithm with ng-relaxation and a heuristic pricing method. We demonstrate the effectiveness of our algorithm on random problem instances that we have generated based on Solomon instances upto 100 patients.

Keywords: Health care, Vehicle routing, Resource constraints, Branch and Price

Category 1: Integer Programming

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: Sabanci Üniversitesi, Orta Mahalle, 34956 Tuzla, Istanbul, Türkiye November 2018

Download: [PDF]

Entry Submitted: 11/19/2018
Entry Accepted: 11/19/2018
Entry Last Modified: 11/19/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society