Mohan Ramamurthy

Robert Wilhelmson

Steve Hall

Joel Plutchak

Mythili Sridhar

Barry Fishman

Douglas Gordin

Roy Pea

Louis Gomez

COVIS GEOSCIENCES WEB SERVER: AN INTERNET-BASED RESOURCE FOR THE K-12 COMMUNITY

INTRODUCTION

It would not be an exaggeration to suggest that the World-Wide Web (WWWIWeb) has captured the imagination of computer users like no other software in the history of computers. The Web includes standard formats for sharing text, graphics, sound, and video, all of which can be indexed and searched by all networked machines, along with standard protocols for communication between computers.

As a result, computers are increasingly becoming communication tools, whereas before computers were mainly regarded as compute engines. Electronically linking an estimated 30 to 50 million users to a vast body of information, the Web is causing academic institutions, government organizations and large and small companies to rethink their communications strategies. The Web is not only the quintessential bulletin board, but also a way to share documents, applications, and information between groups around the world. The Web's ubiquitous availability has unleashed a cultural revolution in the use of computers in K-12 and higher education, helping to bridge the gap between classroom exercises and the practices of the broader community. In a way, the Web is the great equalizer. For example, over 250 Web sites now offer a variety of weather and climate information to anyone on the Internet. A user with an entry-level personal computer and a built-in high-speed modem now can gain access to data and products previously available only to the professional meteorologist with deep pockets. Many of the online resources that have been created are valuable to students and teachers.

As impressive an achievement as this is, to date, however, most resources on the Web have not been developed with the specific goal of fostering learning communities. A vast majority of the Web servers can be categorized as information servers that simply provide access to a collection of documents1 products1 datdtools to a general audience. Another notable weakness of the so-called first generation Web servers is that they are by and large providers of static information, lacking the ability to let users interact with the information they browse.

Nor is the information customized for the end user. This lack of interactivity, dynamic generation and customization critically hinders the effective use of the Web in a classroom setting.

It is clear that, to facilitate the development of educatiorlal servers that are set up to support explicitlv learning communities, a distinctive architecture is needed [START_REF] Fishman | Using the WWW to build learning communities in K-12 Settings, Part 11: The Nexl Generation of Web Servers to Support Learning Communities[END_REF]. While information servers assume a general user who is interested in their products at the other end, an educational server has to target its resources to a specific audience of students and teachers with the goal of fostering interactive learning. As articulated by Fishman et al, an educational Web server should include the following features:

1. Supplementary educational material 2. Activity structures 3. Support for assessment 4. Student commentary and authoring forum 5. Contact information 6. Mentoring databases 7. Powerful search engines In this paper, we offer a partial description of an educational Web server now under development as part of CoVis, a national science education collaboratory of investigators from Northwestern University (NU), the University of Illinois at Urbana-Champaign (UIUC), the Exploralorium Museum in San Francisco, and students and teachers from CoVis schools around the nation [START_REF] Pea | The Collaborative Visualization Project[END_REF][START_REF] Ramamurthy | CoVis: A National Science Education Collaboratory[END_REF]. The goal of CoVis is to support K-12 science education, using methods modeled after the collaborative practice of scientists. It is realized that the computing and communication revolution has ushered in a new era in networked mu1 timedia interpersonal computing. The CoVis project is a blueprint to inform educators, researchers, and policy makers on the effective and sustainable use of interpersonal, collaborative media in science education.

COVIS GEOSCIENCES WEB SERVER

The CoVis project has developed an Internet-based educational server, the CoVis Geosciences Web Server (http://www.covis.nwu.edu/) to enhance geosciences education in the K-12 community. The resource is now available to CoVis classrooms and soon will be made available to the Internet audience. This server is intended to both provide support for projectbased learning activities in CoVis classrooms and to serve as the mechanism for carrying out many of the activities listed under the educational Web server. Although the basic functions of this server have been mapped out so that it meets the current needs of teachers, students, and scientist mentors who participate in CoVis, we believe the development of any educational server is an evolutionary process. As such, everything from the overall design to its layout and organization of materials will undergo periodic reevaluation and is subject to change.

The CoVis Geosciences Web Server will have the following primary interlocking components:

A database describing activities in earth and atmospheric sciences Access to online data sets that will be used by many of the activities described in the database Scientific visualization and analysis tools that are specifically designed to help students ask questions about the online data sets Curricular materials that explain concepts underlying the activities, data, and visualization and analysis tools A database of mentors who are available to assist students working on CoVis activities A student-teacher facility to promote interaction and collaboration within and outside CoVis, as well as a forum for commentaries and authoring.

The different components of the server will be tightly integrated with one another. In addition, a high degree of interactivity is of course required for this server to achieve success. Community participation is also a key element for it will determine the growth of the database of activities, the range of data sets, ideas and techniques for using tools, curricular materials, and even the membership in the mentor database. Although the bulk of the material on the server will initially focus on atmospheric science topics, we expect that it will grow to include a broad range of earth science topics with active community participation. While we will not go into detail on all aspects of the CoVis Geosciences Web Server here, we will describe some of its key components:

Mentor Database

The mentor database serves a central function in helping to bridge the gap between the community of students and teachers, and the community of scientists and other knowledgeable people outside the classroom's traditional boundaries. Creating these bridges is one of the most important areas in which the Web can be useful to the educational community.

The mentor database provides a sort of learning and teaching "ride board." In the student union of most college campuses, there are ride boards with postings of rides requested and rides being offered. In a mentor database, there will be a broad range of student projects being conducted at any moment in time, and a broad range of expertise offered by scientists and others who volunteer to help advise students on their projects1 and activities. We recognize that we are not the first to attempt to create an online database of resources for classroom use. The Electronic Emissary Project at the University of Texas at Austin is an example of such a database, designed to be accessed through a Telnet session.

What CoVis is building is an environment that simplifies and integrates access for mentors and other materials in a unified. web-based environment.

The CoVis mentor database will be populated by volunteers. Although the majority will be members of larger scientific organizations, such as national energy labs or university departments, there is the opportunity for anyone with a particular interest or expertise in earth and atmospheric science to join. In either case, it is paramount that being a mentor not pose an unreasonable burden on these volunteers, either in time spent mentoring or in administrative overhead.

On a ride board, volunteers avoid burdensome requests by stating the precise terms in which they are able to offer help. The CoVis mentor database will be structured to do the same thing. Using a forrns-based interface on the Geosciences Web Server, potential mentors will be asked to specify not only their particular areas of expertise, but also the manner in which they would like to interact with students, including time spans and mode of communication. For example, a mentor might specify that she is an expert in ocean-floor seismic activity, is interested in working ' The projects don't take place inside the database -the database is used to support projects that take place in the classroom.

with a small group of students over an extended period of time, and can be contacted via e-mail, telephone, or fax. Another mentor might specify that he knows a lot about weather prediction, but is only available to answer short questions. and prefers to be reached via email or videoconferencing.

Teachers will be responsible for making and maintaining appropriate matches between mentors and students. When a teacher thinks that students are working on a project that could benefit from outside mentoring, he or she will call up the database and complete a form that asks for a specification of the project topic, age level, number of students, start and end dates of the project, and other information believed to be pertinent to the request. The database will return a list of potential mentors, and the teacher may then search their full database records in order to make decisions about possible matches. If a mentor agrees to take on a particular student project, the database will be updated to indicate that they are currently unavailable as a mentor to others. This mechanism will help prevent mentors from feeling bombarded or overworked.

Because activities and analysis tools are integrated in a web-based environment, mentors have a unique opportunity to participate in student work. When the Web is coupled with a specialized collaboration and project inquiry tool like the CoVis Collaboratory Notebook [START_REF] O'neill | The Collaboratory Notebook: A distributed knowledge-building environment for project-enhanced learning[END_REF], mentors have access to the entire scope of student work, and can offer feedback and advice as they see fit.

Scientijic Visualizers

The goal of CoVis is to support K-12 science education, using methods modeled after the collaborative practice of scientists. This is accomplished by providing access to some of the same data and tools used by research scientists. The initial efforts have been concentrated in the environmental and atmospheric sciences.

The CoVis Weather Visualizer and Greenhouse Effect Visualizer (http://www.atmos.uiuc.edu/geoscicnces/ visualization/visualization.html) are a supporting piece of the overall CoVis project. Their task is to provide real, observable data to support K-12 education, e.g., classroom activities such as general meteorology education and weather prediction, or support for special student prqjects outside the classroom. The Greenhouse Effect Visualizer was described by Gordin et a1 (1995).

Here we describe the Weather Visualizer.

The design criteria for the Weather Visualizer were:

-Provide reasonably fast access to customizable requests -Present a useful yet manageable set of options -Use a framework that is easily obtainable and familiar to the user The first criterion was chosen in order for the user to actively participate in the learning process. While it would be easy to provide a "canned" set of pregeneratcd products, the spontaneous and investigative nature of the learning experience would then be greatly diluted. As mentioned earlier, there are hundreds of Web servers that provide access to pregenerated products.

The second criterion was selected so as to present the most useful and commonly used set of choices and data, without overwhelming the user with a bewildering and arcane jumble of options. By keeping choices basic, maximum effort could be spent viewing and learning about the end product. rather than trying to decide what to look at.

The last criterion was chosen in order to maximize the accessibility and understandability of the tool, and to use resources that may have already been available or familiar to the CoVis community. T o this end, the Web was chosen for several reasons. By using current WWW technology, existing viewing (browser) software that features a (hopefully) familiar user interface could be used. In addition, use could be made of the existing Internet infrastructure.

Choosing a webbased application also meant the Weather Visualizer would immediately be usable on a wide range of hardware platforms with little or no additional implementation effort, and would allow updating the software without the need to continually distribute new versions.

The introductory document of the Weather Visualizer consists of a graphical panel of seven main categories of weather topics, as well as some introductory text. The seven categories are Surface Observations, Upper Air Observations, Upper Air Soundings. Cross Section Analyses, Ibdar Summary, Satellite Imagery, and Forecast Data.

Each main section contains one or more subsidiary HTML forms or documents that present choices and solicit input as to which meteorological parameters to display. When selection of the parameters is completed, the form is processed, resulting in the return of the image. plot, or textual data requested. Typical end products would be a map of US surface observations, rddar echo summary, and frontal analysis superimposed on an infrared satellite image background; a table of forecast model output statistics; or a Stuve thermodynamic diagram.

An additional feature of the subsidiary pages and forms is generous use of Helper sections, which use the hypertext functionality of HTML to explain what the various parameters and map items mean, and how the items or products are typically used in interpreting the data. A companion paper [START_REF] Hall | The design and implementation of multimedia webbased instructional modules in K-12 education[END_REF] and the next section describes the CoVis learning modules from which the Helper sections were developed.

The documents presented make use of common features of the Web's HyperText Markup Language (HTML) HTML 2.0 specification, a few of the proposed HTML 3.0 features or extensions, and version 1.1 of the Common Gateway Interface (CGI). Processing of the HTML forms is done using the Common Gateway Interface in the form of scripts written in the Perl language. These scripts interpret the user input from the form, translate that input into the appropriate actions, and format and return custom HTML documents that present the results of the request. Much of the underlying processing is performed by programs from the WXP package, which was developed at Purdue University and is distributed by the Unidata Project. The server itself runs an up-to-date version of the HTTP daemon developed at the National Center for Supercomputing Applications at the University of Illinois.

There are certain limitations to using the Web to present the data. These limitations to some extent altered the design and implementation of the Visualizer, and served to make clear some of the existing issues with serving potentially large amounts of data interactively to even a relatively small number of simultaneous users.

Certain of the underlying operations entailed fairly intense computation, and as few as a couple dozen simultaneous requests for such data slowed the server down to unacceptable levels. To this end a few tasks, such as remapping satellite imagery for use as surface observation backgrounds, were performed as the data was received so as to be available for quicker use when requested. This substantially raised the number of requests that could be processed simultaneously, while still preserving the interactivity and customizable nature of the Visualizer.

A related issue is one of HTTP daemon design and computer operating system constraints. Current HTTP daemons seem to be optimized to handle relatively short-lived requests that are not CPU-intensive, such as reasonably small HTML documents and images. This is in stark contrast to typical Weather Visualizer requests, which can result in spawning long-lived computer processes that are potentially CPU-intensive. In this case, the actions of the HTTP daemon can more quickly cause a strain on operating system resources such as number of processes active, process page and swap space, and other limited operating system resources. Several methods to alleviate these problems have been contemplated, but as of September 1995 none had been implemented.

Hypermedia Educational Modules

Another important component of the CoVis Geosciences Web server is the section on web-based hypermedia educational modules (http://www.atmos.uiuc.edu/covis/modules/html/ module.html).

An educational Web server, particularly one targeted toward students engaged in project-based science learning, must provide supplementary educational material that will aid students in conducting their projects. This type of material differs from the standard prearranged sequences of material found in most textbooks in one important respect: it is organized so that students can directly access the relevant helper material they need to solve the problem at hand. This is analogous to what adults do when they consult a how-to book in order to solve an infrequent problem. If you need to know how to fix a leaky faucet, an entire course in plumbing would be too time-consuming and provide far more information than you need to complete the task.

As such, the hypermedia educational modules are designed to play an integral role in this new approach to science learning. Through the use of color diagrams, video and audio, scanned images and text, these modules introduce and discuss essential concepts in atmospheric sciences as they arise in project-based science inquiry.

Early web-based modules focused on topics such as Pressure, Forces and Winds, and Interpretation of Weather Maps and Satellite Images.

Recently completed modules deal with topics such as Atmospheric Optics, Cloud Classification, and Severe Storms. Colorful slides depicting these phenomena have been scanned in and are accompanied by descriptive audio, text, and schematic diagrams. The Guide to Atmospheric Optics, for example, introduces students lo an array of optical effects from rainbows to sundogs and sunsets to mirages. Schematic diagrams and text explain mechanisms responsible for the development of phenomena like reflection and refraction. The Storm Spotters Guide contains an impressive collection of slides and descriptive text designed to educate students about severe weather.

Other hypermedia modules have been developed on: 1) Fronts, where students learn about the various types of fronts and their influence on the weather, 2) Midlatitude Cyclones, where students investigate the evolution of cyclones from cyclogenesis to dissipation, examine surface and upper-level features, while relating this to an "actual" case study on the infamous "Storm of the Century", 3) Weather along Coastlines, concentrates on landsea breezes and their role in the development of lake effect snow, and 4) Weather Forecasting. The forecasting module carefully steps through the processes meteorologists use when preparing a forecast, introduces general forecasting methods, interprets key weather maps and images and provides valuable tips to improve the student's forecasting ability. Since all our completed modules are Internet accessible, their usage is not limited to the CoVis project, and, in fact, are being accessed daily by users across the network. Their feedback and comments have also helped shape the design of current and future modules.

In addition to providing self-contained hypermedia educational modules on a variety of topics, we are integrating tightly the contents of these hypermedia modules with other sections of the CoVis Geosciences Web Server. One example is the integration of hypermedia module pages into the new Weather Visualizer. The visualizer allows users to generate customized weather images from real-time weather data. Also included are built-in helper sections to provide useful information about the weather features available in the visualizer (for example, fronts, radar, etc.) and are accessible by simply clicking on the word in question. For example, if the user clicked on "Frontal Analysis," module pages comprised of descriptive text and images would be accessed that not only introduce the various types of fronts, but also clarify how to identify fronts on weather maps, and their importance in interpreting the weather. The purpose of the helper sections is to equip the user with the knowledge and skills required for valuable and correct interpretation of images generated by the weather visualizer.

DISTRIBUTED WEB SERVERS

So far, we have described the CoVis Geosciences Web Server as a single entity. However, one of the truly exceptional attributes of the Web is that it provides a transparent and seamless integration of online resources anywhere on the Internet. The contents of a virtual Web server can be distributed across any number of computers physically located in different locations on the network. And in a national collaboratory such as CoVis where project partners come from different disciplines bringing diverse expertise, and are located in different geographical locations, it is possible to develop and maintain the individual components of the Geosciences Server in a distributed manner.

Another important advantage of this paradigm is that other members of the Internet community can both participate and contribute material to the virtual Web server by simply linking any material they develop to the Geosciences Web Server. For instance, if an expert in Hydrology at a non-CoVis site develops webbased educational material on the Hydrologic cycle and River Flows, that material, with the permission of the original author, can immediately be made available on the CoVis Geosciences Web Server. This model provides an elegant way to expand both the audience as well as the scope of the material available on an educational server.

In keeping with this spirit, the project partners at UIUC and NU have developed two Geosciences Web servers, targeted toward their respective audiences. The NU CoVis Geosciences Web Server (http://www.covis.nwu.edu/) will be the principal server for CoVis and K-12 communities.

The UIUC Geosciences Web Server (http://www.atmos.uiuc.edu/geosciences/ geosciences.html) will target its content toward a broader Internet audience. It should be added that the UIUC group operates The Daily PlanetT" Web-server [START_REF] Wilhelmson | The Daily PlanetTM: An Internet-based Information Server for the Atmospheric Sciences Community and the Public[END_REF] and The Weather Machine Gopher server [START_REF] Ramamurthy | Using The Weather Machine: A Gopher server at the University of Illinois brings weather information to every desktop[END_REF], which together receive over 200,000 requests daily. Because of this important difference in the audience for the two servers, the structure and organization of material on the two servers are also somewhat different.

While the NU CoVis Geosciences Web Server will be the clearing house for the CoVis community and as such it has to maintain a high-level of stability so as to be useful in a classroom setting, the UIUC Geosciences Web Server will continue to explore and experiment with cutting-edge digital library and information technologies.

As new tools for exploration of atmospheric sciences data are developed, they will appear on the UIUC server at first. After extensive stability tests are conducted, they may be made available on the NU Geosciences server, if they are useful within the CoVis context.

CONCLUDING REMARKS

Despite the ubiquitous availability of Web servers, the challenge of providing useful educational resources via the Internet is becoming ever increasing. A great number of Web servers provide access to static products (images and text), providing very little interactivity for a student. Another notable void is in the availability of sophisticated web-based analysis tools and prototype simulation models. For example, there is an acute need to develop prototype interactive models like SimEarthT" that are Web based. As the sophistication and complexity of these tools and models increase, the need to interface information technology tools like NetscapeTM or NCSA Mosaic to compute servers becomes that much more critical. This has important implications for the future of NII and HPCC. This raises another important aspect of the Web. the issue of scalability. As more and more clients access these servers, the demands on a given server are not likely to be met merely through increases in processor speeds or additional machines. In the current Web architecture, the bulk of the compute power on a client is left untapped when accessing a server. If the number of clients keeps increasing disproportionate to increases in server capacity (which is axiomatic), then the clients at some point will have to share in the workload for the load to be sustained.

The recent introduction of the Java environment by Sun Microsystems shows considerable promise in alleviating such scalability-related bottlenecks. In a Java environment, programs, which are written in a C++-like Java language, can be executed on any client that is running a Java-based Web browser. It is important to add that Java is platform independent, and Java-based Web browsers are expected to be available on a number of platforms (Unix, Windows 95, Windows NT and Macintoshes) in the near future. A companion paper by [START_REF] Wilhelmson | The Daily PlanetTM: An Internet-based Information Server for the Atmospheric Sciences Community and the Public[END_REF] outlines how we plan to make effective use of the Java environment in the CoVis Weather Visualizer.

ACKNOWLEDGMENTS

We thank Bill Chapman for the initial design and programming of the Weather Visualizer. The numerous discussions with John Kemp on the design of the Geosciences Web Server were very helpful.

The Collaborative Visualization project is funded under NSF Grant #RED-9454729 and the Illinois State Board of Education/Eisenhower.


C Rodriguez

T Garaix
email: garaix@emse.fr

X Xie

V Augusto

Staff dimensioning in homecare services with uncertain demands

Keywords: homecare, staff dimensioning, stochastic programming, stochastic vehicle routing problem

The problem addressed in this paper is how to calculate the amount of personnel required to ensure the activity of a home health care (HHC) center on a tactical horizon. Design of quantitative approaches for this question is challenging. The number of caregivers has to be determined for each profession in order to balance the coverage of patients in a region and the workforce cost over several months. Unknown demand in care and spatial dimensions, combination of skills to cover a care and individual trips visiting patients make the underlaying optimization problem very hard. Few studies are dedicated to staff dimensioning for HHC compared to patient to nurses assignment/sequencing and centers location problems. We propose an original two-stage approach based on integer linear stochastic programming, that exploits historical medical data. The first stage calculates (near-)optimal levels of resources for possible demand scenarios, while the second stage computes the optimal number of caregiver for each profession to meet a target coverage indicator. For decisionmakers, our algorithm gives the number of employees for each category required to satisfy the demand without any recourse (overtime, external resources) with fixed probability and confidence interval. The approach has been tested on various instances built from data of the French agency of hospitalization data (ATIH).

Introduction

Access to health-care services is a critical challenge of the XXIst century in modern societies. Delivering high quality care at the right moment to the population at the right cost is a priority for all health-care systems. The Institute of Medicine [START_REF] Reid | Building a better delivery system: a new engineering/health care partnership[END_REF] identified time pertinence, patient-focus and efficiency as most important criteria to ensure high quality care. Since health-care budgets are limited nowadays, optimization of resources is explored to increase performance of such systems. The need to better use resources and optimize delivery, is challenged by a constant increase of costs [START_REF] Chahed | Operations management related activities in home health care structures[END_REF][START_REF] Matta | Modelling home care organisations from an operations management perspective[END_REF][START_REF] Rodríguez-Verjan | Economic comparison between Hospital at Home and traditional hospitalization using a simulation-based approach[END_REF].

Home health-care (HHC) is a good alternative to traditional hospitalization to offer a better access to health-care services and increase patient satisfaction and quality of care [START_REF] Rodríguez-Verjan | Economic comparison between Hospital at Home and traditional hospitalization using a simulation-based approach[END_REF]. It has been proven that health-care at home improves access in rural areas and decreases the load of hospitals. However such structures face important challenges to deliver care in rural areas while having lower costs than traditional hospitals. Complex and technical cares (such as chemotherapy) can be delivered at home using such structures. The challenge is to do it without increasing budget.

In this article, we tackle the problem of staff dimensioning in HHC structures. In traditional hospitals, all resources are gathered in the same place and traveling distances from one patient to the next one can be neglected. In HHC systems, traveling distances between patients must be taken into account to determine resource capacity and usage, especially when freelance resources (such as city based nurses, pharmacists or doctors) are not available in some regions. In addition, qualified caregivers can not be easily hired or dismissed according to the demand variation on a middle term horizon (few months) so the staff dimensioning problem is a critical tactical decision for health-care suppliers. Long-term hiring improves employees quality of life and their own skills for regular tasks. For all these reasons, economic viability of HHC structures is very sensitive to staff dimensioning and such decisions should be taken carefully by considering all parameters (demand evolution, availability of freelance resources on the territory, traveling distances...).

Uncertainties related to short term and long term decision support systems are a great challenge in many activities as supply chain management [START_REF] Gupta | Managing demand uncertainty in supply chain planning[END_REF][START_REF] Peidro | Quantitative models for supply chain planning under uncertainty: a review[END_REF], transportation and logistics [START_REF] List | Robust optimization for fleet planning under uncertainty[END_REF] and production planning [START_REF] Gatica | Capacity planning under uncertainty for the pharmaceutical industry[END_REF]. HHC context presents a wide variety of uncertainties compared to many industrial activities. Like in many health-care systems demand parameters are stochastic in volume, timing, pathology and severity, but also on spatial location. In addition, postponement or ignorance of patients requests are rarely feasible options for HHC. In [START_REF] Lanzarone | A patient stochastic model to support human resource planning in home care[END_REF], a stochastic model of patient's care pathway in HHC allows to predict estimation of patient's requirements. But some authors [START_REF] Leykum | Manifestations and implications of uncertainty for improving healthcare systems: an analysis of observational and interventional studies grounded in complexity science[END_REF] show that the uncertain nature of the procedures and the diseases must be taken into account in the design of the systems. They found that while process-based efforts are efficient in low-uncertainty context they are insufficient in the high-uncertainty situations. In order to prevent these drastic changes, some authors [START_REF] Shishebori | Robust and reliable medical services network design under uncertain environment and system disruptions[END_REF] have studied the robust approach to protect the network against changes. In another research [START_REF] Argiento | A Bayesian framework for describing and predicting the stochastic demand of home care patients[END_REF], these elements are introduced in the design of the system.

Staff dimensioning in traditional hospital is less critical than in HHC structures for two main reasons related to the close proximity of patients: i) activities can easily be shared or exchanged in case of employees shortage; ii) working time can be saved by small reductions in the time spent for each care. Classical approaches for staff dimensioning are based on calculating requirements using mean values of historical data of demand, the definition of a global budget [START_REF] Busby | A decision tool for negotiating home care funding levels in Ontario[END_REF] or a given budget and a focus on improvements in service delivery [START_REF] De Angelis | Planning home assistance for AIDS patients in the city of Rome, Italy[END_REF]. Dimensioning staff is critical for small HHC structures that represent 57% of French HHC centers where less than 10,000 hospitalization days were performed in 2011 [START_REF] Fnehad | L'hospitalisation à domicile en France en[END_REF]. In that case, the efficiency of the system is sensible to small changes in the number of available personnel. Detailed operational aspects (routing, mix of pathologies and mix of skills for pathologies care) are therefore integrated in our approach dedicated to HHC structures.

The main contribution of this article is an approach to size human resources of HHC structures taking into account combination of skills for each service and uncertainties related to demand evolution and location. The decision level is tactical and allows HHC managers to plan the deployment of a structure in a territory with a minimal amount of information. A two-phase approach based on a quasi-exact Monte-Carlo approach is proposed to solve this problem where the stochastic demand is estimated by a set of scenarios. These scenarios capture the complex nature of the demand over a territory and constitutes an original and efficient way to take into account medical parameters of the problem.

In order to classify our contribution, the taxonomy of Hulshof et al. ( 2012) can be used. They divided the research fields in a matrix. In the vertical axis, works are divided following the planning horizon (strategic, tactical and operational decisions). In the horizontal axis the different health-care services (Ambulatory, Emergency, Surgical, Inpatient, Home and Residential). Following this classification, our contribution is situated in tactical level and the HHC service. Our approach integrates operational decisions, but restricted to the evaluation of tactical decisions. More details about the specific place of this work in the research landscape is given in the next section.

The article is organized as follows. A literature review on staff dimensioning and related problems is proposed in Section 2. Problem statement is given in Section 3. Section 4 presents the two-phase approach to solve the staff dimensioning problem. Section 5 presents a benchmark on results and computational experiments. Finally, conclusions and perspectives are given in Section 6.

Literature Review

A classification of planning problems can be found in the work of [START_REF] Lanzarone | Operations management applied to home care services: the problem of assigning human resources to patients[END_REF] where they propose to divide human resources planning in four different levels: i) dimensioning, ii) districting problem [START_REF] Benzarti | Operations management applied to home care services: Analysis of the districting problem[END_REF][START_REF] Blais | Solving a homecare districting problem in an urban setting[END_REF] iii) assignment to visits or patients [START_REF] Boldy | The Geographical Allocation of Community Care Resources-A Case Study[END_REF] and iv) scheduling [START_REF] Borsani | A home care scheduling model for human resources[END_REF] and routing [START_REF] Begur | An integrated spatial DSS for scheduling and routing home-health-care nurses[END_REF]. This study can be completed with the framework proposed by [START_REF] Matta | Modelling home care organisations from an operations management perspective[END_REF] where authors classify management decisions from their hierarchical perspective. Dimensioning is a fundamental part of the planning system since its decision defines main constraints of the other three planning systems, the best policies of which are impacted by staff dimensioning decisions. Moreover, the capacity is almost defined by the medical or paramedical staff in HHC systems [START_REF] Lanzarone | Operations management applied to home care services: the problem of assigning human resources to patients[END_REF]. This problem must be understood as a part of decision systems that are critical to the survival of the HHC structures. Literature review on staff dimensioning problem will be presented as follows. The first section is dedicated to the problem applied in health-care services. The research in other application fields is presented in the second section. This problem has been extensively studied in structures (traditional hospitals, factories, call centers etc.) where resources are not moving or where time spent to move can be easily estimated. On the contrary, literature is rare when staff routing aspects need to be considered.

Staff planning in HHC

Almost all works of the literature dealing with staff planning in HHC are related to some already set structures. The objective is to improve operational working. We state a lack pf studies on staff dimensioning problem for HHC. Some recent studies on assignment, scheduling and routing problems are presented here in order to better understand the research context of this paper, as these problems are strongly related to the staff dimensioning decisions.

The districting problem divides the territory in groups of patients and healthcare professionals following different criteria. The main objective is to reduce costs or improve the matching of offer and demand. In [START_REF] Benzarti | Operations management applied to home care services: Analysis of the districting problem[END_REF] for example, optimization criteria are the workload balance, the maximum distance between two units and the indivisibility of assignment (one unit can only be assigned to one district). In this study, authors assume that patients have the same profile. They propose two different models and evaluate them in randomly generated scenarios. Another example can be found in [START_REF] Blais | Solving a homecare districting problem in an urban setting[END_REF] where authors apply a multi-criteria Tabu-search algorithm to divide a real territory in Canada.

Another staff planning problem is nurse-to-patient assignment problem. Here, the new patients must be assigned to a specific resource while keeping some constraints. The most common constraints are, skills of resources, resource capacity and continuity of care (some patients have to be visited by the same nurse, as far as possible). In the work of [START_REF] Lanzarone | Robust nurse-to-patient assignment in home care services to minimize overtimes under continuity of care[END_REF] the authors propose a mathematical model to assign patients to nurses for health-care providers. They take into account a random demand, fixed transportation time (demand is modeled as the number of visits per week) and the objective is to minimize the maximum overtime of a resource. They present a structural policy consisting mainly on individual patient assignment (ranked by demand) while the expected cost is minimized. In [START_REF] Yalçındag | A Two-Stage Approach for Solving Assignment and Routing Problems in Home Health Care Services[END_REF], the authors introduce routing considerations into the assignment. They propose an assignment-first routing-second approach on a single district. They compare two structural policies and a mixed-integer linear program for the assignment and conclude that the last approach is the best one. For routing considerations they solve a classical Traveling Salesman Problem for every resource. In the study of [START_REF] Carello | A cardinality-constrained robust model for the assignment problem in Home Care services[END_REF] authors highlight the uncertain aspect of demand. They propose a cardinality constrained robust model to solve the nurse-to-patient assignment problem. One of the important contributions of this study is the modeling of the continuity of care. This constraint, often considered as a soft constraint, divides here patients in different subsets: enforced (during all the treatment or just at the beginning), partial and none.

The scheduling and routing problems have been extensively studied in literature. For a complete review readers are refereed to [START_REF] Lanzarone | Operations management applied to home care services: the problem of assigning human resources to patients[END_REF] and [START_REF] Hulshof | Taxonomic classification of planning decisions in health care: a structured review of the state of the art in OR/MS[END_REF]. One recent study is [START_REF] Allaoua | A matheuristic approach for solving a home health care problem[END_REF] where the authors model the problem of nurse scheduling and rostering as a vehicle routing problem with time windows. In [START_REF] Liu | Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care[END_REF], the authors present two heuristics to solve the problem of sample pick-up and medicine delivery (simultaneously) with time windows. Finally, [START_REF] Kergosien | A Routing Problem for Medical Test Sample Collection in Home Health Care Services[END_REF] present a problem dealing with pick-up of blood and urine samples in HHC. They solve the problem using a Tabu-search algorithm based on a variable neighborhood search.

In all the studies presented in this section, the number of caregivers is a given constant number. In the next section, works considering staff dimensioning in other contexts are presented.

Staff dimensioning in health-care services and other industries

A complete literature review on planning in health-care systems can be found in [START_REF] Hulshof | Taxonomic classification of planning decisions in health care: a structured review of the state of the art in OR/MS[END_REF]. The authors present a taxonomy to classify planning problems applied to health-care. Their study is very complete including up to 400 references. Here only some recent studies will be presented regarding staff dimensioning in HHC.

Several researchers paid attention to staff dimensioning in traditional hospitals, although this problem is not as critical as in HHC. The study of [START_REF] Rohleder | Using simulation modeling to improve patient flow at an outpatient orthopedic clinic[END_REF] intends to control and improve patient flow in an outpatient unit. Their simulation model can be used to adjust the number of required human resources. They find that adding some key resources, like a X-ray technician, could reduce waiting times. Another study in an outpatient unit is developed by [START_REF] Wang | Modeling and analysis of work flow and staffing level in a computed tomography division of University of Wisconsin Medical Foundation[END_REF] where the authors use Markov chains modeling to improve the work flow of a tomography department in a hospital. They change the amount of staff to test different policies. [START_REF] Fanti | A Three-Level Strategy for the Design and Performance Evaluation of Hospital Departments[END_REF] propose a three levels approach to design hospital departments. Indeed staff dimensioning takes an important part of their decision support system. The approach is based on UML (Unified Modeling Language) and Petri nets modeling, an optimization module consisting in approximating the Time Petri net model to the Time Continuous Petri net, and a simulationdecision module. They present a case study where they minimize the number of resources required to maintain the flow of patients in a hospital in Italy.

Authors seem to have particular interests using queuing and discrete simulation models for staff dimensioning. [START_REF] Alfonso | Modeling and simulation of blood collection systems[END_REF] propose to use Petri nets modeling linked with Discrete Event Simulation (DES) and a quantitative approach to design human resources and donor appointment strategies in blood collection systems including fixed and mobile collection sites, walk-in and scheduled donors, stochastic donor's behavior and random collection times. Another study in the blood collection system is presented in [START_REF] Blake | Determining staffing requirements for blood donor clinics: the Canadian Blood Services experience[END_REF] where a queuing model is used to minimize staff while maintaining waiting time requirements. It is applied in the Canadian Blood services including 51 standard models applied to 220 clinic configurations. Another case is the work of [START_REF] Green | Using queueing theory to increase the effectiveness of emergency department provider staffing[END_REF], where DES is used to change the amount of available staff after demand variations in an emergency department. In Yom-Tov and Mandelbaum (2014), a modified Erlang distribution is used to introduce the reentry of patients. A queuing model determines how many physicians/nurses are needed to maintain service levels. The constraint-programming model in [START_REF] Ganguly | Emergency Department Staff Planning to Improve Patient Care and Reduce Costs[END_REF] calculates the required staff and schedules them to serve patients in an emergency department.

Dimensioning resources is an important problem in health-care, especially in HHC structures where special features such as demand distribution impact the economic pertinence and viability of the structure. A literature review can be found on approaches intended to flexible and adaptable health-care structures [START_REF] Carthey | Achieving flexible and adaptable healthcare facilities-findings from a systematic literature review[END_REF]. Bed allocation in a specific clinic is considered by using queuing theory, particularly the Erlang-loss model [START_REF] De Bruin | Dimensioning hospital wards using the Erlang loss model[END_REF]. The authors develop a decision support system and, considering twoyears data, they show that merging units can decrease the number of required beds. Another work based on DES and Petri Nets to plan the capacity of maternity HHC structures in Haïti can be found in [START_REF] Germain | Dimensionnement par simulation d'une structure de prise en charge de la maternité à domicile[END_REF]; authors simulate a maternity service where an additional resource is added every time a patient waits more than 50 minutes. Even if the authors identify the distance between the health-care providers and patients as the main difficulty for delivering good quality services, they do not make clear how this parameter is taken into account in their approach. Finally, another example can be found in [START_REF] Trilling | Aide à la décision pour le dimensionnement et le pilotage de ressources humaines mutualisées en milieu hospitalier[END_REF] where the authors design a simulation model in the context of shared resources in the hospital. In order to calculate resource's workload, the simulation with infinite capacity.

An important part of staff dimensioning studies has been realized in call centers industry, where calls follow probabilistic distributions according to their type and resources have different skills -but single assignment to calls. In this case the problem consists in minimizing the number of resources to accomplish all tasks. Markov chain models have been widely used to deal with such problems as presented in [START_REF] Koole | Queueing models of call centers: An introduction[END_REF]. The problem can also be considered as a scheduling problem and can be solved using deterministic constraint programming like in [START_REF] Canon | Dimensioning an inbound call center using constraint programming[END_REF]. Random instances are used to test the algorithm finding that optimal solution can be reached within two minutes for instances with up to 80 jobs. Shared resources are involved in the call center problem of [START_REF] Akşin | Capacity sizing in the presence of a common shared resource: Dimensioning an inbound call center[END_REF].

Resource dimensioning considering demand uncertainty has been studied in the recent literature [START_REF] Sahinidis | Optimization under uncertainty: state-of-the-art and opportunities[END_REF][START_REF] Peidro | Quantitative models for supply chain planning under uncertainty: a review[END_REF][START_REF] Guillén | Multiobjective supply chain design under uncertainty[END_REF]. A survey considering the demand uncertainty on the supply chain can be found [START_REF] Gupta | Managing demand uncertainty in supply chain planning[END_REF] where the authors divide the models in two categories: i) Manufacturing decisions ("here-and-now") and ii) Logistics decisions ("wait-and-see"). In the pharmaceutical industry a study was made to plan the investments taking into account the uncertain result of clinical tests [START_REF] Gatica | Capacity planning under uncertainty for the pharmaceutical industry[END_REF]; the authors propose a multi-stage optimization problem where decisions are taken when information is revealed. The probabilities of success of a product evolves after each step of the clinical trial. Probabilities between steps of the trial are assumed related and not independent. The model is solved with Branch-&-Bound and is capable to solve instances with three deterministic products and one stochastic. In [START_REF] List | Robust optimization for fleet planning under uncertainty[END_REF], the authors present a fleet sizing problem under uncertainties. There are two sources of uncertainty: (i) demand and (ii) performance of vehicles.

Almost all works cited above model systems where patients (or demands) arrive to a facility (hospital, blood collection site, outpatient units) where several resources can be assigned to each patient. Therefore, traveling times are neglected in the definition of the capacity of the service. Another specificity of the staff dimensioning problem in health-care context comes from mix of cares required for a the pathology. For instance, if a treatment required 1 hour of nurse and 30 minutes of an oncologist, sizing decisions on both professions have to be integrated. At the operational level, planning decisions of different professions are less dependent since the demand to cover is known for each profession. That combinatorial integration increases the difficulty of the staff dimensioning problem.

In order to solve this problem we propose innovative methods with the following scientific contributions: i) a quantitative approach to size staff of HHC with uncertainties, routing aspects and complex coverage function of demands, ii) an original service level definition to ensure the robustness of the solution, iii) a complex demand modeling including three sources of uncertainty (geographical, epidemiological and volume).

In the next section the problem will be defined. In section 4 the two-phase approach to solve the problem will be presented. In section 5 the computational experiments will be proposed and the conclusion will be discussed in section 6.

Problem definition

The key question in this study is how many human resources are necessary to attend demand. The objective of the problem is to give the minimum amount of human resources in order to cover a certain percentage of days, called 'performance level'.

The mix of demands from different pathologies, (requiring different amounts of time of different resources like nurses, doctors, specialists, etc.) is not known in advance. Demands can appear in different locations on the territory assigned to the HHC structures by the authorities. The amount of demand is also unknown and routing aspect is critical as about 30% of working time is spent in traveling. Planning human resources without this information is complicated and the consequences of bad decisions can be important. However, some information can be used to estimate demand. In this study three main sources of information are considered to be the input of the problem: i) geographical information around the HHC structure, ii) historical data of demand and iii) information of the resources required to treat the pathologies in the HHC structure.

Decision-makers and HHC planners can use the approach developed in this paper whenever they have the information previously mentioned about the territory to cover and want to know the minimum amount of personnel of each profession required to meet the target performance level. The following part of the problem description presents some modeling aspects and explain the fundamental hypothesis of the approach.

Consider a HHC structure that operates on a territory T divided into sectors in the set S. A sector s corresponds to an homogeneous area where intrasectoral travel times, denoted t ss , can be assumed constant for any pair of origin and destination belonging to sector s. Between sectors s 1 and s 2 , the intersectoral travel time t s1s2 is constant along the optimization horizon H. Moreover, each sector is large enough to allow us to obtain statistical data on every pathology (ATIH 1 is the main source of real-life data used in this paper). This database offers epidemiology data related to every GHM 2 . We assume that patients who are suffering from the same pathology require the same care with multiple activities. The cost associated to each required employee depends on his/her profession p, among P the set of professions. As a permanent member, an employee generates a constant cost c p for the whole optimization horizon. Each activity a ∈ A requires w a,p working hours for profession p ∈ P . Note that some activities can be performed remotely and thus, do not require any move to the sector of the patient.

The demand matrix d = [d sa ] gives the daily demand for each activity at each sector. The daily demand applied to a territory is called scenario on this territory. The total number of demand D, for each day is defined as a random variable. Each demand has probability π s to be in sector s and corresponds to activity a with probability ρ a . Thus, D defines the demand distribution, π the spatial distribution and ρ the epidemiological distribution. In the following 1 ATIH is the French technical agency for hospitalization information, http://www.atih.sante.fr. From the ATIH database, one can get the amount of patients of every region in France for every pathology and the treatment associated with. This data is public and three years of data (from 2010 to 2012) were used in this study.

2 GHM: Groupe Homogène des Malade is a classification of treatments used by French authorities to calculate reimbursements, hospital capacities, resources requirements and so on.

sections, these distributions are independent but the generalization is trivial.

In practice several HHC structures use freelance resources usually located near to patients that are distant. But this approach can imply heavy economical charges to the structure and the use of these resources should be minimized. In our model, when HHC structure is capable of serving all patients of a certain day without using freelance resources (and without extra hours) the day is considered 'covered' and 'uncovered' otherwise the day is considered 'uncovered'. Thus, we define the level of performance α * as the number of possible day (called scenario in the rest of the text) covered for a given staff.

The problem is to determine n p , the number of employee for each profession p, such that the cost p c p n p is minimized and the level of performance α * satisfied on H. A scenario is covered by a solution n when its corresponding daily demand is completely served by resources described by n. In order to determine if a scenario can be covered with [n p ] resources, the resources assignments to activities have to be decided. Those variables are denoted q sapk (d) and represent the number of activities a served by the employee k of profession p in the sector s. Thus, the total working time of k can be calculated by computing the route visiting each sector where k has to operate. As the daily working time is limited to L, for any solution [n p ] the feasibility (covering) problem can be decided for each day.

Two-phases approach

The problem described above can be seen as a two-stage stochastic programming [START_REF] Birge | Introduction to stochastic programming[END_REF][START_REF] Dantzig | Linear programming under uncertainty[END_REF]. The first stage only relates to n p decision variables. At the second phase, when demands are known, the assignment of patients to employees selected at the first phase is solved and their routing plan can be done. This NP-hard problem (as its deterministic version contains the well-known Vehicle Routing Problem) is difficult to address directly. Therefore, we propose a two-phases approach exploiting the definition of the performance level α * . Because of the uncertainty of demand our algorithm is a quasi-exact Monte-Carlo approach where the stochastic demand is estimated by a set of scenarios.

In order to evaluate the performance of a solution n = [n p ], an optimization problem can be solved maximizing the number of demands served. Another approach minimizes overtimes needed to cover all the demands of each scenario for each profession. The approach proposed in this paper (see Figure 1) allows to decompose the problem for each profession, since daily activities done by different professions are assumed independent. But it implies to solve the routing problem for each solution. Our approach tries to find the minimal number of resources N pω of profession p required to serve all the demands of each scenario ω. This daily problem is called the slave problem SP (p, ω) and does not depend on solutions n.

As N pω values are computed, a scenario is covered by a solution n if and only if n p ≥ N pω for each profession p. Now, the staff dimensioning can be modeled by the so-called master problem defined with those constraints.

Our approach to solve the staff dimensioning problem of a territory has three steps:

1. generate a set Ω of daily scenarios of demands; 2. compute N pω for each scenario ω and each profession p by solving the slave problems SP (p, ω).

3. solve the master problem and get the optimum n = [n p ].

The three steps are detailed in the three following sections. Then some modeling improvements are described in Section 4.4.

Figure 1: The two-phases approach.

Generation of scenarios

Each scenario corresponds to a possible daily demand, generated from a territory. All data that define a territory, are listed in Section 3. They contain all characteristics of sectors, activities and professions. For each territory, some demand patterns are generated on three fields: the total number of demands (= (s,a)∈S×A d sa ), probabilities of any demand on localization (π s , ∀s ∈ S) and on its nature (π a , ∀a ∈ A).

Slave problem

Before solving the master problem, minimal resource requirements N pω have to be computed for each scenario ω and each profession p. In the sake of clarity, p and ω are omitted in this section.

The schedules of each resource have to be optimized in order to decide the minimal number of resources necessary to serve all. Each required resource has to visit some patients and also to serve some remote activities.

The slave problem is modeled as an integer linear program described below. This model is based on route variables, and so comes with a huge number of variables. In Section 4.4, problem properties are exhibited. They allow to reduce the number of variables to a tractable size for the generated scenarios.

An integer linear program ensures the demand covering. In order to limit the size of the problem, routes represent sequences of sectors and do not consider cares and demands. Then the assignment of the demands to vehicles at each sector has to be explicitly decided in this model. It differs from the unique paper we found on split deliveries with discrete quantities [START_REF] Salani | Branch and price for the vehicle routing problem with discrete split deliveries and time windows[END_REF]. In their model, the routes also define the quantities delivered at each position. Because of the large number of such routes, a branch-and-price scheme is used and takes advantage of other constraints of their problem like the time window constraints. A covering model with routes as sequences of nodes without undefined quantities has also been used by [START_REF] Archetti | A Hybrid Heuristic for an Inventory Routing Problem[END_REF] for an inventory routing problem, where stock level, delivering and routing decisions are integrated. They select, in that way, routes among a set of routes derived from solutions obtained by a Tabu Search algorithm. Their problem is easier since quantities delivered are real numbers.

A dummy sector s = 0 is associated to the HHC structure building. Without loss of generality, all the demands of remotely served activities for the considered profession are transferred to sector 0. Set S and the demands d = [d as ] are accordingly updated and the intrasector duration t 00 is set to 0.

Let consider K the set of resources and R the set of feasible routes that can be assigned to resources k ∈ K. Schedules associated to resources can be modeled through binary x kr and integer q ask decision variables, that represent assignments of route r and proportion of activity a in sector s to resource k, respectively. The length of each route r is known and denoted T r that corresponds to the sum of the intersector travel durations. Note that the node representing the HHC structure building is included in all routes. It also gives single node routes modeling employee who exclusively works remotely. Additional binary parameters a rs indicate whether route r is passing through sector s. Thus, the slave problem is given by equations ( 1)-( 7).

min N = (r,k)∈R×K x rk (1) subject to r∈R x rk ≤ 1, ∀k ∈ K (2) k∈K q ask ≥ d sa , ∀(s, a) ∈ S × A (3) (s,a)∈S×A (w a + t ss )q ask ≤ r∈R (L -T r )x rk , ∀k ∈ K (4) a∈A (w a + t ss )q ask ≤ r∈R (L -T r )a rs x rk , ∀(k, s) ∈ K × (S \ {0}) (5) x rk ∈ {0, 1}, ∀(r, k) ∈ R × K (6) q ask ∈ N, ∀(a, s, k) ∈ A × S × K (7)
The objective function (1) gives the number of resources involved in the optimal solution by minimization of the number of routes assigned to resources. We recall that resources can only perform one route, as constraints (2) ensure. All demands have to be covered as in constraints (3). Individual capacity constraints are satisfied with (4) inequalities, where the left member expresses the workload -in terms of service durations -assigned to the resource k and the right side gives the available working time minus the total travel duration. Constraints (5) enforce resources to pass through all sectors of the territory where they have at least one demand to serve -if a rs is null then q ask is null. These constraints are meaningless for the dummy sector s = 0 that is 'visited' by all resources.

Master problem

Given a set Ω of scenarios ω, the master problem aims to find out the minimal number of resources for each profession required to cover a ratio α * of scenario among Ω.

The master problem is modeled as the linear integer program ( 8)-( 12). In addition to n p decision variables, intermediate y ω binary variables are introduced and express if scenario ω is covered (y ω = 1) or not (y ω = 0) in the optimal solution.

y ω ∈ {0, 1}, ∀ω ∈ Ω (11) n p ∈ N, ∀p ∈ P (12)
The objective function ( 8) minimizes the cost of staff involved in the optimal solution. Constraints (9) enforce to select more resources than each selected scenario requires, for each profession. The ratio of covered scenarios is ensured by constraints (10) with parameter α (instead of α * ), the definition of which is given in the next paragraph. The number of resources selected can take integer values with constraints (12).

As Ω has a limited size in practice, a solution satisfying the ratio α on a sample Ω has a small probability to satisfy the performance level α * over all possible scenarios. Let define the average observed coverage ratio ᾱ = ω∈Ω y * ω ÷ |Ω|, where y * ω are optimal values of the model ( 8)-( 12). If we consider the random selection of a daily scenario as a Bernouilli trial, then the sum of results of such trials (i.e., ω∈Ω y * ω ) follows a binomial distribution that we can approximate by a normal distribution -we assume large enough Ω and ᾱ far enough from 0 and 1. The lower bound on the confidence interval at the 95% confidence level is computed as α -1.66 α(1 -α) ÷ |Ω|, where the observed variance is under the first square root and the number of samples under the second one. The parameter 1.66 comes from the Student-t distribution table for the above confidence interval.

The value α is experimentally set such that the obtained value ᾱ gives a lower bound equal to (or slightly greater than) α * .

For instance, with |Ω| = 100 and target α * = 0.80, we experiment that α = 0.86 gives solutions that cover 86% ( ᾱ = 0.86) of scenarios of Ω and therefore gives a lower bound on the confidence interval close to 0.80 ≈ 0.86 -1.66 0.86(1 -0.86) ÷ √ 100. The computational complexity of the master problem is let as an open problem. If the number of professions and the maximal number of resources are assumed constant, then a full enumeration can be done in polynomial time (in the number of scenarios). In our case, |P | and n p have small enough upper bounds to guarantee an efficient solution by a linear programming branch-andcut algorithm.

Modeling and algorithm improvements

As the number of variables involved in the model ( 1)-( 7) can be huge, this model has to be refined by means of filter on variables, tight bounds and cutting rules embedded in an algorithm involving all sub-problems.

Size reduction of the slave problem

The number of variables involved in the model ( 1)-( 7) can be decreased by exploiting optimal solution properties and filtering sequences of nodes to consider or limiting the number of possible resources.

1. As the set of assignable routes is the same for every resources, variables x can be replaced by |R| integer variables indicating the number of times that a route is served (i.e., index k ∈ K can be ignored). But such variables do not to directly derive feasible assignment of resources to activities because of integrity of activities. That makes such modeling less efficient than the proposed one.

However, the number of variables can be reduced because of optimal solutions properties. Let consider that problem (1)-( 7) is feasible, then an optimal solution exists which routes satisfy the following properties.

(a) Routes correspond to lowest cost -as the sum of intersector travel times -Hamiltonian cycle on the subset of sectors in each route.

Thus the number of routes involved in the model ( 1)-( 7) is less than 2 |S| .

(b) An upper bound on the minimal duration of each route can be compared to L, the maximal route duration. This upper bound adds the inter and intrasectors travel times and the lowest demand duration that can be served at each visited sector.

The first property is easily implemented in the dynamic programming algorithm that computes routes. A preprocessing procedure filters routes according to the second property. Note that these properties are scenario independent. The upper bound has been lightly weakened for that; all activities are considered at each sector even if not present for all scenarios.

2. The number of resources |K| has to be large enough to ensure feasibility but as small as possible for compactness. An upper bound, U B pw ≥ |K|, is computed by a simple constructive heuristic for each pair of profession and scenario (p, ω). For each profession, the algorithm starts with an empty route of a resource k (K(p) = {k}). For each sector and each activity (selected in an arbitrary order), demands are pushed at the end of the current route. When no more demand can be assigned to the resource because of capacity constraints, another empty route is considered for an additional resource which is added to K(p).

A cutting rule in the solution algorithm over all scenarios

Some slave problem runs can be avoided. Let us suppose that 100 scenarios have been generated and that α = 0.8. Then, at most 20 scenarios are not covered by any optimal solution of the master problem. Let ω be ranked at the 21th position when scenarios are ordered by decreasing resource (p) requirements (N pω ). As covered scenarios ω by a solution satisfy N pω ≤ N pω , N pω can be replaced by N pω . Thus, when more than 21 slave problems of resource k have been solved, ω can be determined, and N pω used as a lower bound, denoted LB p in next slave problems. All steps of the sequential solution of slave problems are detailed in Algorithm 1. This algorithm can easily be parallelized according to pairs of professions and scenarios.

The lower bound maintained in Algorithm 1, is added to model ( 1)-( 7) with constraint (13). Actually, solutions involving less than LB p resources can be replaced by LB p in the master problem. As constraints (3) are inequalities, solutions with exceeding resources are accepted.

N ≥ LB p (13)
Algorithm 1 How to compute N pw for profession p over Ω Require: profession p, territory T LB p := 0 {U B pω } ω∈Ω : the set of upper bounds on N P pω L: the list of ω ∈ Ω sorted by decreasing U B pω value

while L = ∅ do ω := pop(L) if LB p ≥ U B pω then N pω = LB p else
N pω := best solution of ( 1)-( 7) with |K| = U B pω -1 if (1)-( 7) is infeasible then

N pω := U B pω end if end if if |L| < α|Ω| then LB p := max{N pω : |{ω : N pω > N pω }| = (1 -α)|Ω|} end if end while

A lower bound for the master problem

The replacement of N pw by lower values gives a lower bound to the master problem. When some slave problems are not solved to optimality, a lower bound can still be derived for the master problem. This lower bound is obtained by considering a model similar to (8)-( 12), where N pw is replaced by the lower bound on its value given by the branch-and-cut procedure which solves each slave problem.

Computational experiments

In this section, we show how our approach can be used to determine the level of staff required to cover a territory in Section 5.2. In Section 5.3, we show the benefit of our approach against less sophisticated computational methods. The benchmark used are described in Section 5.1. The settings, the performance and the limits of our algorithm are discussed in Section 5.4.

Master and slave problems are solved by the parallel branch-and-cut algorithm of IBM Ilog Cplex 12.5 in a C++ code. All runs have been performed on a 8 processor Linux machine rated at 2.4 MHz. A running time limit of 300 seconds has been imposed to each call to the slave problem solution.

Benchmark

An instance is defined by a territory, a demand pattern and a set of scenarios (daily demands).

This information is built from historical data on pathologies and cares. Only four different types of care are modeled; they correspond to the three main cares over 24 plus a dummy care that represents an average of less frequent ones. The three most representative cares are: palliative cares (π a ≈ 0.26), complex bandage and ostomy (π a ≈ 0.23), and heavy nursing cares (π a ≈ 0.10). According to ATIH data (2012) provided by home care services in France, more than one half of day of hospitalization at home is covered by these three type of cares. Data recorded by the ATIH in 2012 involve 317 public and private HHC structures reporting 4 207 177 days of hospitalization and an average length of stay of 16.21 days. All French HHC structures have to send to ATIH their activities detailed per type of care (GHM) and type of employee.

The time spent by resources to care patients is reported in Table 1 for nurses, nurses' aid and physicians. Durations in the last line result from a weighted sum of durations of pathologies ; weights are frequencies. All durations are estimated from ATIH data. Other workers are discarded, since they are parsimoniously used and certain can operate as subcontractors of the HHC structure. Note that the impact of the increase of the number of cares, can be reduced by merging cares with the same service durations for each type of caregiver. This trick has not been exploited in the experiments described in this section. The increase in the number of types of caregiver involved in the model linearly increases the difficulty of the problem, because of the independence of daily covering problems related to each type of caregiver.

Every demand matrix d = [d sa ] is generated following a demand pattern on a territory, and gives one instance.

The set of 96 instances is built according to parameters listed in Tables 2, 3, 4 and 5. Each territory is defined by sparsity and division attributes. Sparsity parameters are detailed in Table 3 where intrasector distances are uniformly generated from intervals, and intersectors distances are computed as euclidean distances from uniformly generated points in a square. In the case of semiurban territories, two squares have the same center and the probability to be in the smaller one is 0.5. In order to be consistent with the sector-based design, intrasectors distances are generated smaller than intersectors ones.

For each combination of sparsity and division attributes, in Table 2, two territories are generated, to a total of 12 territories. Then, instances are generated for each territory following patterns of Tables 4 and5. In series S1, the total amount of demand is fixed and all sectors are similar regarding the volume and the nature of the demand. In series S2, the total demand can vary. Series S3, correspond to HHC structures which allocate clusters of close demands to specific days. Finally, when the demand can not be smoothly spread on the planning horizon, some typical scenarios with different levels of demands and spatial distributions are generated, like in series 4.

For each instance, 100 hundred scenarios (|Ω| = 100) are generated. According to the master problem definition, α is set to 0.86 to enforce 0.80 (see Section 4.3. for calculation details) as covering ratio with a confidence greater than 95%. Preliminary tests -performed on S4 instances -show that setting α to 0.86 gives solutions with an average coverage value close to 0.86. We accept that solutions founds are normally distributed centered at 0.86.

The number of routes (|R|) considered in the slave problem depends on the territory. Values in Table 6, show the efficiency of the filtering procedures applied to variables of model ( 1)-( 13), as 921.0 has to be compared to 2 10 (the maximal number of routes with 10 sectors) and 12295.0 to 2

Comparison to straightforward solutions

With the results reported in Tables 8 and9, we aim to show the interest of our approach compared to trivial computations. Let us denote inf p (resp. sup p ) the minimum (resp. maximum) quantity of resources with profession p required to serve at least one scenario of Ω. From the second and third columns of Table 8, we know the average gaps between trivial bounds and the best solution (n * p ) found with α = 0.8. Detailed results by instances also show that such gaps vary a lot depending on instances. On the other hand, the lower bound (LB p ) computed for each profession in Algorithm 1 is a better approximation of the optimal solution as we can see in the last column of Table 8.

Let n * denote the best solution found of the master problem. In Table 9, the three last columns correspond respectively: the average percentage of scenarios covered by n * ; the average percentage of scenarios covered by n but not by n 1 defined by formula (14); the average percentage of scenarios covered by the solution n 2 defined by formula (15) and not by n * . Solution n 1 is directly defined by the values of LB p , the lower bound obtained by Algorithm 1. In Solution n 2 , each scenario covered by LB p for at least one profession is covered. 9 show that the solution of the master problem is not trivial. In order to satisfy the coverage constraint, the set of scenario to cover can not be easily determined.

n 1 = {n p : p ∈ P, n p = LB p } (
We also compute a Pareto pseudo-optimal set on both criteria the objective cost of resources and the percentage of coverage. As we know lower an upper bounds on the number of resources required to cover each scenario with each resource, it is easy to get all not-dominated solutions the corresponding bicriteria master problem from solutions of all the slave problems. In order to get more accurate resources levels for each scenario we ran the program with alpha set to 1. But, we did not solve all slave problems to optimality and we therefore an approximation of the Pareto set.

For each instance, we find a quite small (12 solutions in average) set of notdominated solutions. Thus, obtained solutions for a fixed parameter α may exceed the α level of coverage. One can verify this statement by checking Column "n * " in Table 9.

Algorithm performance

General performances of our approach are given in Table 10. Note that average values in the last row of tables are weighted by the number of instances per series. As Column '% call slave' shows, about only 20.3% require a call to the branch-and-cut solver. It highlights the interest to sort scenarios according to Average and maximal gaps (restricted to the 11% runs that do not reach optimality and computed on the staff size) indicate that the minimal number of resources required for some scenarios is difficult to evaluate, as for S1.2 and S4 the maximal gap reaches 4 resources. However, the relative average gapalso restricted to runs that do not reach optimality -is less than 1.2% on all series. As described in Section 4.4.3, the lower bound computed at each run stopped early, allows to compute a lower bound on the master problem. The average relative gap is given for every series in Column '% gap' with an overall average value of 3.1%. It seems that this gap can be reduced by controlling the gap obtained on each run of the slave problem.

Series S2 seem to provide more difficult slave problems than series S1. In series S2, the demand vary and can reach high values (60 demands), that generally makes the daily scenarios harder to solve. When 80% of the demand is allocated to 20% of the sectors, as in series S3, more than 70% of the call to the slave problem reach optimal solutions. Series S4, where the daily scenarios are the most heterogeneous, our approach fails to find optimum solutions to many slave problems.

Conclusion

In this paper we propose an original approach to estimate the staff in a HHC service. Our approach deals with a coverage constraints on demand forecast. It is useful to remind that staff dimensioning is a critical challenge for HHC structures since a small change in the number of resources will have an important impact on the economic performance (and survival) of them. Our approach allows to determine the necessary amount of caregivers using some given some data: historical demand (geographical and pathological), territory model (to estimate traveling time between sectors and inside them) and amount of time of each profession required to treat each pathology. This information can be obtained in public health-care data bases such as the ATIH.

Time spent in traveling (until one third of the working time) is taken into account. Combinations of required skills involved to cover the demand are enforced. The robustness of the approach is obtained by a scenario-based model. This potentially very large problem is solved through an original decomposition framework. Contrary to the set of specific constraints to HHC structure, our solution framework could be applied to other combinatorial optimization problems and can be an alternative to classical stochastic programming or chanceconstrained methods. The analysis of our numerical experiments shows that routing evaluation can help to get more precise working time, especially in geographical areas assuming rural or semi-urban patterns.

Comparison to straightforward solutions and the Pareto optimal sets computed, indicate that our approach can help decision-maker before opening a HHC service or before hiring (dismissing) an employee.

N

  pω y ω ≤ n p , ∀ω ∈ Ω, p ∈ P

Table 2 :

 2 Instances attributes

	cares	nurse nurse's aid physician
	palliative	60	35	10
	complex bandage	40	15	10
	heavy nursing	45	50	10
	others	40	25	5
	monthly cost (euros)	1200	800	2500
	Table 1: Service durations in minutes
	attribute			values
	Sparsity		rural; urban; semi-urban
	Division		10 sectors; 15 sectors
	Demand pattern stable; volume variation; geographical variation; typical days

Table 7 :

 7 For each covered scenario we consider as a day off, any resource assigned to the solution but not required by the scenario. For each covered scenario and profession, the total travel and idle times have been computed. Idle time only involves resources used in the scenario. Average values of these indicators are reported in Table7for all series. Travel and idle times give realistic values compared to the activity of the HHC service of Sallanches. Column '% day off' shows that the stability of the volume of demand strongly impacts the stability of the number of resources required each day. Percentage of workload activities

	15 .

Table 8 :

 8 Variance of the number of resources required series n

	(15)

14)

n 2 = {n p : p ∈ P, n p = max w∈Ω {N pw : ∃p ∈ P such that N p w ≥ LB p }} * n * \ n 1 n 2 \ n *

Table 9 :

 9 Scenario coverage (%) of trivial and optimized solutionsResults reported in Table

Table 10 :

 10 Computational performances a quickly computed upper bound in Algorithm 1, in order to skip some slave problem solutions. But, according to Column '% opt', optimality is not reached for more than one half of these calls within the 300 seconds limit. It means that for about 11% (55.4% over 20.3%) of the scenarios, the upper bounds used on N pw can provide not optimal values. As 33 slave problems are not solved to optimality in average -each scenario is evaluated for each resource -, those runs of 300 seconds represent almost all the total computing time given in Column 'cpu (h.)'.

		Algorithm 1		Slave problem
	series	% gap cpu (h.) % call slave % opt. avg gap max gap
	S1.1	2.3	2.5	23.5	66.3	1.1	2
	S1.2	2.7	3.8	23.8	44.4	1.2	4
	S2.1	3.4	3.7	19.4	30.0	1.3	3
	S2.2	3.1	3.2	17.8	36.0	1.2	3
	S3	2.5	1.9	21.3	72.4	1.1	3
	S4	4.1	3.9	17.7	17.7	1.6	4
	average	3.1	3.1	20.3	44.6	1.2	3.1


Sugeno Utility Functionals for Monotonic Classication

Quentin Brabant, Miguel Couceiro quentin.brabant@loria.fr, miguel.couceiro@loria.fr Monotonic Classication & Decision Rules

X 1 X 2 0 = ≤ ≤ = 1 Feature space: X = X 1 × • • • × X n
, where X i is a totally ordered set. Each object is represented by a tuple x = (x 1 , . . . , x n ) ∈ X.

Labels: Each object has a label l(x) from a totally ordered set L.

The relation between descriptions and labels is assumed to be orderpreserving

a 1 ≤ b 1 , . . . , a n ≤ b n ⇒ l(a 1 , . . . , a n ) ≤ l(b 1 , . . . , b n ).
Aim: to predict the label of objects from their descriptions, with a nondecreasing function f : X → L.

The function can be specied by decision rules of the form:

∀i ∈ A, x i ≥ α i ⇒ l(x) ≥ δ,
where A ⊆ {1, . . . , n}. Sets of such rules can describe any non-decreasing function from X to L.

0 1 /7 2 /7 3 /7 4 /7 5 /7 6 /7 1 0 1 /7 2 /7 3 /7 4 /7 5 /7 6 /7 1 X 1 X 2
Example:

These rules express the function at the left.

x 1 ≥ 3 /7 ⇒ l(x) ≥ x 1 ≥ 4 /7, x 2 ≥ 3 /7 ⇒ l(x) ≥

Sugeno Utility Functionals (SUF)

A capacity µ : 2 {1,...,n} → L is a set function verifying

• µ(∅) = 0 and µ({1, . . . , n}) = 1

• I ⊆ J ⇒ µ(I) ≤ µ(J).
The Sugeno integral S µ dened by µ is the aggregation function max I⊆{1,...,n} min(µ(I), min

i∈I x i ).
Let ϕ = (ϕ 1 , . . . , ϕ n ), where each mapping ϕ i :

X i → L veries • ϕ i (0) = 0 and ϕ i (1) = 1 • a i ≤ b i ⇒ ϕ i (a i ) ≤ ϕ i (b i ).
A SUF is a combination of a Sugeno integral and mappings ϕ 1 , . . . , ϕ n of the form

S µ (ϕ 1 (x 1 ), . . . , ϕ n (x n )).
A single SUF is less expressive than decision rules. A maximum of several SUFs can represent any set of decision rules.

Application

Maxima of SUFs enable a non-parametric method [START_REF] Brabant | Extracting Decision Rules from Qualitative Data via Sugeno Utility Functionals[END_REF] for monotonic classication.

Principle: To t the data with a max-SUF using the smallest possible number of SUFs.

The max-SUF can then be translated back into rules.

Result: The method is competitive (in terms of accuracy) with state of the art methods [START_REF] Blaszczynski | Sequential covering rule induction algorithm for variable consistency rough set approaches[END_REF] for learning decision rules.