Читать книгу Healthcare Systems - Группа авторов - Страница 23

We start by generating a set of graphs, one for each day and careworker, in order to represent our problem. For a particular graph, a set of vertices represents the set of services that could be provided by this careworker, that is, the services for which he or she is qualified, whose start and end times correspond to their availability, and for which the beneficiary is compatible with the continuity constraints of the problem. To this set of vertices, we add two fictitious services representing the start and end points of a route.

We then create arcs between all the pairs of services which could be performed consecutively by the same careworker. It is thus a matter of ensuring that the start and end times of the two services are compatible, in particular with regard to the travel time between the homes of the two beneficiaries concerned.

A route from the source to the sink thus represents a sequence of compatible services, i.e., a daily route. This route will be said to be admissible if it respects all the daily legal constraints. By constructing the graph, we have already made sure that the constraints of continuity and qualifications are respected.

We weight each arc by the travel time between the two homes of the beneficiaries concerned, the duration of the arc’s first service and the waiting time between the two services, in terms of the collective agreements. If we generate a route from the source to the sink by limiting its length, then we can control the amplitude, the effective working time and the waiting time of the route to which it corresponds. By adapting the algorithm proposed in Rizzi et al. (2015), we can efficiently compute all the admissible daily routes for a careworker on a given day.