Browsing by Author "Klimentova, Xenia"
Now showing 1 - 3 of 3
Results Per Page
Sort Options
- Maximising expectation of the number of transplants in kidney exchange programmesPublication . Klimentova, Xenia; Pedroso, João Pedro; Viana, AnaThis paper addresses the problem of maximising the expected number of transplants in kidney exchange programmes. New schemes for matching rearrangement in case of failure are presented, along with a new tree search algorithm used for the computation of optimal expected values. Extensive computa-tional experiments demonstrate the effectiveness of the algorithm and reveal a clear superiority of a newly proposed scheme, subset-recourse, as compared to previously known approaches.
- New insights on integer-programming models for the kidney exchange problemPublication . Constantino, Miguel; Klimentova, Xenia; Viana, Ana; Rais, AbdurIn recent years several countries have set up policies that allow exchange of kidneys between two or more incompatible patient–donor pairs. These policies lead to what is commonly known as kidney exchange programs. The underlying optimization problems can be formulated as integer programming models. Previously proposed models for kidney exchange programs have exponential numbers of constraints or variables, which makes them fairly difficult to solve when the problem size is large. In this work we propose two compact formulations for the problem, explain how these formulations can be adapted to address some problem variants, and provide results on the dominance of some models over others. Finally we present a systematic comparison between our models and two previously proposed ones via thorough computational analysis. Results show that compact formulations have advantages over non-compact ones when the problem size is large.
- The probabilistic travelling salesman problem with crowdsourcingPublication . Santini, Alberto; Viana, Ana; Klimentova, Xenia; Pedroso, João PedroWe study a variant of the Probabilistic Travelling Salesman Problem arising when retailers crowdsource last-mile deliveries to their own customers, who can refuse or accept in exchange for a reward. A planner must identify which deliveries to offer, knowing that all deliveries need fulfilment, either via crowdsourcing or using the retailer’s own vehicle. We formalise the problem and position it in both the literature about crowdsourcing and among routing problems in which not all customers need a visit. We show that to evaluate the objective function of this stochastic problem for even one solution, one needs to solve an exponential number of Travelling Salesman Problems. To address this complexity, we propose Machine Learning and Monte Carlo simulation methods to approximate the objective function, and both a branch-and-bound algorithm and heuristics to reduce the number of evaluations. We show that these approaches work well on small size instances and derive managerial insights on the economic and environmental benefits of crowdsourcing to customers.