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

Abstract

Bu tezde farklı kaynak kullanımının gerekli olduğu, bir Araç Rotalama Problemi çeşidi sunulmuştur. Problem, Evde Bakım Servis sağlayıcıları ile ilgili bir uygulamadan yola çıkılarak tasarlanmıştır. Ayrıca, problemde sağlık hizmetleri, hemşireler ve hasta bakıcılar tarafından hastaların evlerinde sağlanmaktadır. Her hasta, belirli ve değiştirilemeyen zaman aralıklarına bağlı olarak hemşire ve/veya hasta bakıcıya ihtiyaç duyabilir. Sağlık personelleri, hastaların evlerine en fazla iki kis¸i kapasitesi olan ¨ozel arac¸lar ile ulas¸tırılmaktadır. Ek olarak, model kurulumunda hems¸ire ve hasta bakıcıların birbirlerinin yerine kullanılamayaca˘gı varsayılmıs¸tır. Problem, genel olarak her hastanın farklı sayıda, farklı kaynaklara ihtiyac¸ duyması ile tanımlanabilir. O¨ ncelikle, problem ku¨me bo¨lme metodu ile modellenmis¸, daha sonra en iyilenmesi ic¸in Dal-ve-Fiyat algoritması kullanılmıs¸tır. Algoritmanın etkinli˘ginin ¨olc¸ ¨ulmesi ic¸in bazı ¨ozellikleri test edilmis¸tir. Test sonuc¸ları, uygulanan algoritmanın Karıs¸ık Tam Sayılı Programlamametodlarından daha iyi c¸alıs¸tı˘gını g¨ostermektedir.

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.