1,721,000 research outputs found
A Multicommodity Flow Approach to the Crew Rostering Problem
No full textThe problem of finding a work assignment for airline crew members in a given time horizon is addressed. In the literature this problem is usually referred to as the airline crew rostering problem. It consists of constructing monthly schedules for crew members by assigning them pairings, rest periods, annual and sick leave, training periods, union activities, and so forth, so as to satisfy the collective agreements and security rules. We formulate the airline crew rostering problem as a 0–1 multicommodity flow problem where each employee corresponds to a commodity; determining a monthly schedule for an employee is the same as computing a path on a suitably defined graph while still satisfying union conventions. A preprocessing phase is performed that reduces the dimension of the graph. To tighten the linear programming formulation of our model, we propose some families of valid inequalities that have proved to be computationally effective. Some of them can be treated implicitly when constructing the graph. Computational results obtained with a commercial integer programming solver (CPLEX) are analyzed
Stakeholder involvement in drug inventory policies
No full textThis paper experimentally investigates the relationships among three major stakeholders that are involved in drug inventory management at Intensive Care Units (ICUs), namely: i) nurses, who in person manage drug orders and carry out storage operations, ii) clinicians, who choose the therapy and shape demand, and iii) the hospital management, who is in charge of the economic sustainability of the hospital. As a case study, we consider the ICU ward of a major Italian public hospital and we focus on antibiotics. We exploit a previously developed Mixed Integer Linear Programming model which decides, for each drug, when and how much to order, and we improve it by adding different sets of constraints to represent each stakeholders’ point of view. By solving three generalized models, each of which ties the satisfaction of a single stakeholder to different thresholds, we explore the mutual effects of taking explicitly into account different perspectives within the inventory policy. We implemented an instance generator, built on the basis of empirical probability distributions extracted from a large set of observed historical data and representing the decision flow ruling drugs prescription. Extensive experiments have been carried out on a set of realistic instances provided by the generator. Results based on our test case not only provide computational evidence to intuitive relations among stakeholders, but also suggest possible levels of compromise. Improved stakeholder satisfaction would also benefit the patient, the passive stakeholder who is the ultimate subject of the caring process
Models and valid inequalities to Asymmetric Skill-Based Routing Problems
No full textGiven a directed network, where a set of skills Sj is required to serve each node j, and given a set of available technicians, each one having abilities described through a set of skills, we study the problem of defining the tour of each technician in such a way that each service requirement is fulfilled by exactly one technician, and proper skill constraints are satisfied. These constraints state that the service requirement at node j can be operated by any technician having, at least, all the skills in Sj . Given travelling costs for the arcs of the network, which are technician dependent, we want to determine a set of tours of minimum cost which satisfy the skill constraints. This problem, named asymmetric skill VRP (A-SKVRP), originates from a real application arising in Field Service. Also, it is strongly related to Home Care applications. Starting from the preliminary results in Cappanera et al. (Network optimization. 5th international conference, INOC 2011, Hamburg, June 2011. Lecture notes in computer science, Springer, Berlin, vol 6701, pp 354–364, 2011), where a special case is addressed, we propose a hierarchy of three ILP flow-based models for A-SKVRP, which is based on increasing levels of disaggregation of the flow variables used to prevent subtours. The computational results of a first pool of experiments show that the LP bounds produced by the most disaggregated model are very tight, but at the expense of very large computational times in most cases. This becomes critical as the number of involved nodes and skills increases. Therefore, in the second part of our study, we enhance the LP bounds obtained with the weaker models by adding, in a cutting plane fashion, cut constraints. As a result of this enhancement, the intermediate model proves to be competitive against the most disaggregated model in computing tight lower bounds, especially as the number of the nodes and of the skills increases. This model combined with the proposed valid inequalities thus qualifies as an efficient tool to address skill-based routing problems arising in application contexts such as Field Service and Home Care
A Two-Phase Approach to the Emergency Department Physician Rostering Problem
No full textIn this study, we address the physician rostering problem occurring in an Emergency Department of an Italian pediatric hospital. Motivated by the paramount importance that workload balance has in this setting, we propose a tailored two-phase approach and we present two optimization models on which the proposed approach is based. In the first phase, we assign all the weekend (and holidays) shifts to physicians in a medium-term planning horizon pursuing a fair distribution of weekend and night shifts among the physicians, whereas in the second phase, we assign all the weekday shifts to physicians in short-term planning horizons so that each physician works almost the same number of morning and afternoon shifts. We present preliminary results of an ongoing research whose ultimate goal is to develop a decision support system to facilitate the creation of physicians’ rosters
Optimal joint routing and link scheduling for real-time traffic in TDMA Wireless Mesh Networks
Full text linkWe investigate the problem of joint routing and link scheduling in Time-Division Multiple Access (TDMA) Wireless Mesh Networks (WMNs) carrying real-time traffic. We propose a framework that always computes a feasible solution (i.e. a set of paths and link activations) if there exists one, by optimally solving a mixed integer-non linear problem. Such solution can be computed in minutes or tens thereof for e.g. grids of up to 4x4 nodes. We also propose heuristics based on Lagrangian decomposition to compute suboptimal solutions considerably faster and/or for larger WMNs, up to about 50 nodes. We show that the heuristic solutions are near-optimal, and we exploit them to investigate the optimal placement of one or more gateways from a delay bound perspective
Logic-Based Benders Decomposition in Answer Set Programming for Chronic Outpatients Scheduling
No full textIn answer set programming (ASP), the user can define declaratively a problem and solve it with efficient solvers; practical applications of ASP are countless and several constraint problems have been successfully solved with ASP. On the other hand, solution time usually grows in a superlinear way (often, exponential) with respect to the size of the instance, which is impractical for large instances. A widely used approach is to split the optimization problem into subproblems (SPs) that are solved in sequence, some committing to the values assigned by others, and reconstructing a valid assignment for the whole problem by juxtaposing the solutions of the single SPs. On the one hand, this approach is much faster due to the superlinear behavior; on the other hand, it does not provide any guarantee of optimality: committing to the assignment of one SP can rule out the optimal solution from the search space. In other research areas, logic-Based Benders decomposition (LBBD) proved effective; in LBBD, the problem is decomposed into a master problem (MP) and one or several SPs. The solution of the MP is passed to the SPs that can possibly fail. In case of failure, a no-good is returned to the MP that is solved again with the addition of the new constraint. The solution process is iterated until a valid solution is obtained for all the SPs or the MP is proven infeasible. The obtained solution is provably optimal under very mild conditions. In this paper, we apply for the first time LBBD to ASP, exploiting an application in health care as case study. Experimental results show the effectiveness of the approach. We believe that the availability of LBBD can further increase the practical applicability of ASP technologies
Metodi e modelli di supporto alle decisioni inerenti la logistica del farmaco.
No full textIn ambito sanitario, l’utilizzo di metodi quantitativi sembra ormai imprescindibile per rispondere
alla crescente necessità di offrire servizi di assistenza e di cura che sempre più siano centrati sul paziente, ma
che al tempo stesso siano anche efficienti e consentano quindi una gestione ottimale delle risorse disponibili,
spesso scarse. Questo è il contesto in cui si inserisce lo studio di modelli e metodi di supporto alle decisioni
relative alla logistica del farmaco, oggetto di questo studio. In particolare, lo studio ha l’obiettivo di mostrare
come l’impiego integrato di tecniche quantitative quali il process mining, l’apprendimento automatico,
l’ottimizzazione e la simulazione possano coadiuvare nello sviluppo di politiche di riordino dei farmaci che
siano sicure, efficaci ed efficienti
Decomposition approaches for scheduling chronic outpatients' clinical pathways in Answer Set Programming
No full textChronic patients suffering from non-communicable diseases are often enrolled into a diagnostic and therapeutic care program featuring a personalized care plan. Healthcare is mostly provided at the patient's home, but those examinations and treatments that must be delivered at the hospital have to be explicitly booked. Booking is not trivial due to, on the one hand, the several time constraints that become particularly tight in the case of comorbidity, on the other hand, the limited availability of both staff and equipment at the hospital care units. This suggests that the scheduling of the clinical pathways for enrolled outpatients should be managed in a centralized manner, taking advantage of the fact that demand for services is known well in advance. The aim is to serve as many requests as possible (unattended requests are supplied by contracted private health facilities) in a timely manner, taking patients priority into account. Booking involves setting a date and a time for each selected health service, which is rather complex. In this work, we provide a declarative approach by encoding the problem in Answer Set Programming (ASP). In order to improve the scalability of the ASP approach, we present and compare two heuristic approaches, respectively based on service demand and time decomposition. All approaches are tested on instances of increasing size to assess scalability with respect to time horizon and number of requests
Optimal Link Scheduling for Real-time Traffic in Wireless Mesh Networks in both Per-flow and Per-path Frameworks
No full textIn this paper we investigate link scheduling for Wireless Mesh Networks (WMNs) carrying real-time (i.e., delay-constrained) traffic. We show that the problem of computing a conflict-free link schedule with end-to-end delay constraints can be formulated as a mixed-integer non linear problem that can be optimally solved in reasonable time (i.e., minutes) for relatively large WMNs (up to 20–30 nodes). We use the above result to explore the schedulability region of a WMN with a given routing and input traffic, assessing whether and when aggregating flows which traverse the same path makes a given input flow set sched-ulable. Furthermore, we devise a heuristic solution strategy, which computes good suboptimal solutions within up to few seconds, thus being amenable for online admission control
A Decomposition Approach to the Clinical Pathway Deployment for Chronic Outpatients with Comorbidities
No full text- …
