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's) represent an additional possibility of transplant for patients suffering from end stage kidney disease. If a patient has a willing living donor with whom the patient is not compatible, the pair patient--donor can join a pool of incompatible pairs and, if compatibility between patient and donor in two our more pairs exists, organs can be exchanged between them. The problem can be modeled as an integer program that, in general, aims at finding the pairs that should be selected for transplant such that maximum number of transplants is performed. In this paper we consider that for each patient there may exist a preference order over the organs that he/she can receive, since a patient may be compatible with several donors but may have a better fit over some than over others. Under this setting, the aim is to find the maximum cardinality stable exchange, a solution where no blocking cycle exists. For this purpose we propose three novel integer programming models based on the well-known edge and cycle formulations. These formulations are adjusted for both finding stable and strongly stable exchanges under strict preferences and for the case when ties in preferences may exist. Furthermore, we study a situation when the stability requirement can be relaxed by addressing the trade-off between maximum cardinality versus number of blocking cycles allowed in a solution. The effectiveness of the proposed models is assessed through extensive computational experiments on a wide set of instances.

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

This paper is addressed to the generalization of simple plant location problem where customer’s preferences are taken into account. Some basic polyhedral studies and a new family of facet-defining inequalities are given. The effectiveness of the proposed approach is illustrated by the computational experience.