This thesis deals with optimal scheduling and routing in extramural health care. The considered problem is an extension of the Vehicle Routing Problem with Time Windows, which asks for a route configuration of minimal cost for a set of vehicles which have to visit customers while respecting time windows. In the case of extramural health care, vehicles represent nurses visiting customers to assist in householding or other qualified nursing. The objective is to minimize driving and waiting times along with additional factors (e.g. soft time window violations). Beside constraints originating from the VRPTW, further requirements like working time restrictions, mandatory breaks or qualification levels have to be considered. Different ILP models are presented and two Lagrangean relaxations for the VRPTW are extended to the new problem. Results of an implementation of the relaxations using a subgradient method and a modified labelling algorithm to efficiently solve the subproblem are presented. The relaxations are able to provide lower bounds approximating the optimal solution at an average of 4%. Furthermore, a set partitioning approach solved by column generation is investigated. New columns for the set partitioning problem will be created using the modified labelling algorithm. This model generates new best solutions to problems unsolved so far.     «

This thesis deals with optimal scheduling and routing in extramural health care. The considered problem is an extension of the Vehicle Routing Problem with Time Windows, which asks for a route configuration of minimal cost for a set of vehicles which have to visit customers while respecting time windows. In the case of extramural health care, vehicles represent nurses visiting customers to assist in householding or other qualified nursing. The objective is to minimize driving and waiting ti...     »