Search

We 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. Alberto Santini was partially supported by grant “RTI2018-095197-B-I00” from the Spanish Ministry of Economy and Competitiveness and has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement 945380. The other authors are partially funded by the ERDF – European Regional Development Fund through the COMPETE Programme (operational programme for competitiveness) and by National Funds through the Fundação para a Ciência e a Tecnologia (Portuguese Foundation for Science and Technology ) within project “POCI-01-0145-FEDER-028611”.

The complex multi-criteria optimisation problems arising in Kidney Exchange Programmes have received considerable attention both in practice and in the scientific literature. Whereas theoretical advancements are well reviewed and synthesised, this is not the case for practice. We present a synthesis of models and methods applied in present European Kidney Exchange Programmes, which is based on detailed descriptions we created for this purpose. Most descriptions address national programmes, yet we also present findings on emerging cross-national programmes. The synthesis provides a systematic and detailed description of the models and methods the programmes use, revealing important commonalities as well as considerable variation among them. Rather than distilling a single best practice from these results, we find that the variation in models and methods arises because of variation in country characteristics, policies, and ethics. The synthesised state of the art may benefit future national and cross-national initiatives and direct future theoretical contributions within and across the boundaries of the Operations Research discipline.

Kidney Exchange Programs (KEP) are valuable tools to increase the options of living donor kidney transplantation for patients with end-stage kidney disease with an immunologically incompatible live donor. Maximising the benefits of a KEP requires an information system to manage data and to optimise transplants. The data input specifications of the systems that relate to key information on blood group and Human Leukocyte Antigen (HLA) types and HLA antibodies are crucial in order to maximise the number of identified matched pairs while minimising the risk of match failures due to unanticipated positive crossmatches. Based on a survey of eight national and one transnational kidney exchange program, we discuss data requirements for running a KEP. We note large variations in the data recorded by different KEPs, reflecting varying medical practices. Furthermore, we describe how the information system supports decision making throughout these kidney exchange programs. ispartof: HEALTH INFORMATICS JOURNAL vol:27 issue:2 ispartof: location:England status: published

Kidney Exchange Programs allow an incompatible patient-donor pair, whose donor cannot provide a kidney to the respective patient, to have a transplant exchange with another pair in a similar situation. The associated combinatorial problem of finding such exchanges can be represented by a graph: nodes represent incompatible pairs and arcs represent compatibility between donor in one pair and patient in the other. This problem has some uncertainty, which in the literature has been commonly addressed in the following ways: expected utility, fall-back mechanisms and robust optimization. We propose an alternative interactive tool to support decision makers (DMs) on choosing a solution, taking into account that some pairs may become unavailable. For a given solution the predicted performance is evaluated under multiple scenarios generated by Monte Carlo Tree Search (MCTS). The root node of the tree corresponds to no failures. From there, a tree of failure possibilities is generated, each of them corresponding to a different scenario. A solution is determined for every particular scenario. At the end, each solution is evaluated under each scenario. Scenarios are grouped based on the cardinality of the set of failing vertices, and average results for each cardinality are considered. Finally, Pareto dominated solutions are filtered out and the non-dominated average solutions are displayed and compared with the worst case scenario. The tool visually drives DMs in the process of choosing the best solution for their particular preferences.

Nowadays there are several countries running independent kidney exchange programmes (KEPs). These programmes allow a patient with kidney failure, having a willing healthy but incompatible donor, to receive a transplant from a similar pair where the donor is compatible with him. Since in general larger patient-donor pools allow for more patients to be matched, this prompts independent programmes (agents) to merge their pools and collaborate in order to increase the overall number of transplants. Such collaboration does however raise a problem: how to assign transplants to agents so that there is a balance between the contribution each agent brings to the merged pool and the benefit it gets from the collaboration. In this paper we propose a new Integer Programming model for multi-agent kidney exchange programmes (mKEPs). It considers the possible existence of multiple optimal solutions in each matching period of a KEP and, in consecutive matching periods, selects the optimal solution among the set of alternative ones in such a way that in the long-term the benefit each agent gets from participating in the mKEP is balanced accordingly to a given criterion. This is done by use of a memory mechanism. Extensive computational tests show the benefit of mKEPs, when compared to independent KEPs, in terms of potential increase in the number of transplants. Furthermore, they show that, under different policies, the number of additional transplants each agent receives can vary significantly. More importantly, results show that the proposed methodology consistently obtains more stable results than methodologies that do not use memory.

Recent advances in high-throughput technologies have given rise to collecting large amounts of multidimensional heterogeneous data that provide diverse information on the same biological samples. Integrative analysis of such multisource datasets may reveal new biological insights into complex biological mechanisms and therefore remains an important research field in systems biology. Most of the modern integrative clustering approaches rely on independent analysis of each dataset and consensus clustering, probabilistic or statistical modeling, while flexible distance-based integrative clustering techniques are sparsely covered. We propose two distance-based integrative clustering frameworks based on bi-level and bi-objective extensions of the p-median problem. A hybrid branch-and-cut method is developed to find global optimal solutions to the bi-level p-median model. As to the bi-objective problem, an $\varepsilon$ -constraint algorithm is proposed to generate an approximation to the Pareto optimal set. Every solution found by any of the frameworks corresponds to an integrative clustering. We present an application of our approaches to integrative analysis of NCI-60 human tumor cell lines characterized by gene expression and drug activity profiles. We demonstrate that the proposed mathematical optimization-based approaches outperform some state-of-the-art and traditional distance-based integrative and non-integrative clustering techniques.

Phasor Measurement Units (PMUs) are measuring devices that, when placed in electrical networks, observe their state by providing information on the currents in their branches (transmission lines) and voltages in their buses. Compared to other devices, PMUs have the capability of observing other nodes besides the ones they are placed on. Due to a set of observability rules, depending on the placement decisions, the same number of PMUs can monitor a higher or smaller percentage of a network. This leads to the optimization problem hereby addressed, the PMU Placement Problem (PPP) which aims at determining the minimum number and location of PMUs that guarantee full observability of a network at minimum cost. In this paper we propose two general mathematical programming models for the PPP: a single-level and a bilevel integer programming model. To strengthen both formulations, we derive new valid inequalities and promote variable fixing. Furthermore, to tackle the bilevel model, we devise a cutting plane algorithm amended with particular features that improve its efficiency. The efficiency of the algorithm is validated through computational experiments. Results show that this new approach is more efficient than state-of-the-art proposals.

Kidney exchange programs (KEPs) allow the exchange of kidneys between incompatible donor-recipient pairs. Optimization approaches can help KEPs in defining which transplants should be made among all incompatible pairs according to some objective. The most common objective is to maximize the number of transplants. In this paper, we propose an integer programming model which addresses the objective of maximizing the expected number of transplants, given that there are equal probabilities of failure associated with vertices and arcs. The model is compact, i.e. has a polynomial number of decision variables and constraints, and therefore can be solved directly by a general purpose integer programming solver (e.g. Cplex)., This work is financed by the ERDF — European Regional Development Fund through the COMPETE Programme (operational programm for competitiveness), by National Funds through the FCT — Funda¸c˜ao para a Ciˆencia e a Tecnologia (Portuguese Foundation for Science and Technology) within project “KEP - New models for enhancing the kidney transplantation process. FCT ref: PTDC/EGE-GES/110940/2009”, by the North Portugal Regional Operational Programme (ON.2 O Novo Norte), under the National Strategic Reference Framework (NSRF), through the European Regional Development Fund (ERDF), and by national funds through FCT within project ”NORTE-07-0124-FEDER-000057”. This work has also been supported by FCT — Funda¸c˜ao para a Ciˆencia e a Tecnologia (Portuguese Foundation for Science and Technology) within project scope: PEst-OE/EEI/UI0319/2014., info:eu-repo/semantics/publishedVersion