BL.OptiMAS: a Multi-Agent System-based model towards resolution of Routing and Scheduling Problem under uncertainties

Featured image BL.OptiMAS

Home care aims to provide appropriate health services to patients in the comfort of their home. This kind of services must be provided on a daily or weekly basis. To organize caregivers rounds, managers use predefined programs that specifies the cares services to be carried out, as well as the different resources allocated to each intervention. Home care’s plannings should be organized to benefit all the stakeholders and their different expectation, that’s why we created BL.Optim, an optimization service using a bio-inspired algorithm to generate the optimal schedule in time and resources according to customers and organization constraints. However, to prevent unexpected events such as traffic, urgent services, we worked on an approach considering random phenomena linked to the home care activities. The objective is to schedule all the programmed and unexpected care services with the available human and temporal resources . In this article, we will present the scientific objectives of our approach, the methodologies we used and how our solution considers constraints.

Pursued objectives

In order to realize Home Health Care Routing and Scheduling under uncertainties, two mains objectives have to be achieved :

  1. To understand and manage home support systems
  2. To improve the management of home health care activities, we want to propose a decentralized decision support approach to ensure coordination of schedules and information sharing between caregivers and patients, taking into consideration real-time constraints.

Multi-agent systems (MAS) methodology

Multi-agent systems (MAS) are made of several autonomous entities, called agents, located in a same environment and interacting to respond to specific requests or objectives. Due to their distributed nature, MASs are suitable for complex and open problems that require predictive algorithms. Through their multiple interactions, they generate answers in the form of algorithms or methods that best fit their environment. This methodology is widely used in many fields such as simulation and distributed robotics.

Multi-Agent System methodology
Figure 1: Multi-Agent System methodology

For our study, three agents are needed to perform dynamic planning and successful interactions:

  • Identifying agent: it identifies and exploits information relating to patients (availability, localisation, etc.) and caregivers (load, availability, status, etc.), which is to determine a potential list of caregivers (skills and resources) for each patient.
  • Coordinating agent: it plays the role of Assistant to the Coordinator, who accompanies the coordinator in its conduct of the decision-making process. This is the agent that coordinates and orchestrates the stakeholders in each Home Health Care structure.
  • Informing agent: each time the coordinating agent adds or removes information, the informing agent updates the corresponding data in the knowledge base. The agent allows the information repository to be managed with a dynamic organisation.
Our use of the Multi-Agent System
Figure 2: Multi-Agent System towards Home Health Care Routing and Scheduling under uncertainties

Firstly, we categorize the uncertain events taken into account in our MAS-based real time scheduling model as follows:

  1. Deleting a task:
    • Patients cancel the intervention for X reason.
    • Caregiver cancel the intervention for X reason.
  2. Adding a task
    • Urgent care services requests from patients.

Then, several main concepts in our scheduling system must be underlined, such as:

  • The travel time depends on geographical constraints.
  • The duration of the service which must always have static parameters as shown in the following picture:
Statistical's characteristics of a duty
Figure 3: Statistical characteristics of a task

“Oi” represents the date the care service has been received,
“Ci” represents the Worst Case Execution Time (WCET) estimated to realize the task,
“Di” represents the maximal deadline of the care service,
“Ti” represent the repetition period of the care service, each repetition produces a new job to do when the task is activated.

Regarding the addition and/or deletion of a patient, other factors must be considered such as the following dynamic lists:

  • List of urgent patients,
  • List of waiting patients (simple request),
  • List of patients taken in charge (included in the schedule = taken in charge),
  • List of caregivers on duty,
  • List of available caregivers.

These lists allow the use of a search name function, which makes possible to browse the various lists and thus to check the availability of either the caregiver or the patient in question.
Before this identification there is also an offline preliminary treatment to determine the degree of competence of the caregivers, the urgency degree of each care service, as well as the type of service needed for each patient.

The used development tools

MagicDraw’s modelling

MagicDraw is a visual UML modeling tool with team collaboration support. Designed for business analysts, software analysts, programmers, and QA (Quality Assurance) engineers, this dynamic and versatile development tool facilitates analysis and design of object oriented (OO) systems and databases. It provides the code engineering mechanism, as well as database schema modeling, Data Definition Language (DDL) generation and reverse engineering facilities in the context of the study of dynamic planning and replanning, the aim is to gather a maximum of scenarios for risk management at the planning level and to ensure service optimization.

MagicDraw modeling
Figure 4: MagicDraw-based dynamic scheduling system modeling


MaDKit is a multi-agent development platform written in Java, that makes it easy to create distributed applications and simulations using the multi-agent paradigm. These features include:

  • No agent model requirements
  • Ability to support multiple communication models simultaneously
  • Transparent distributed mode
  • Flexible graphical interfaces
Figure 5: API MaDKit – roles information displaying for the agents

API super CSV

Writing Java Objects to a CSV File using Super CSV Library is straightforward. It has a Clear and flexible API to read and write every type of object you want to and from a CSV File. In the example we wrote CSV File using plaint java objects. You can specify which headers, delimiters, quotes, and end of line characters to use.

Conclusions and research perspectives

The work carried out made it possible to enrich and validate the concepts of a constrained model used for the replanning of patient schedules due to the impact of unexpected events. To meet the initial objective, we have defined a new decision-making algorithm based on a constraint model. This methodology mainly concerns the design of stochastic systems, which are generally designed to meet a specific need and fall into the category of real-time systems. The methodology developed is characterized by a constrained system approach, decentralized modelling via a multi-agent system based on dynamic performance evaluation by simulation.
The perspectives that can be envisaged as a direct extension of this work concern two important objectives: the enrichment of the constrained model of stochastic systems by an estimation of the real time tasks to be carried out by the caregivers, and the enrichment of the scenarios linked to unexpected events for the analysis of the fault tolerance of systems.

By Mouna Mahtali

More ...

Retour en haut