The probabilistic travelling salesman problem with crowdsourcing

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 … Read more

Energy-efficient Automated Vertical Farms

Autonomous vertical farms (VFs) are becoming increasingly more popular, because they allow to grow food minimising water consumption and the use of pesticides, while greatly increasing the yield per square metre, compared with traditional agriculture. To meet sustainability goals, however, VFs must operate at maximum efficiency; it would be otherwise impossible to compete with the … Read more

Decomposition strategies for vehicle routing heuristics

Decomposition techniques are an important component of modern heuristics for large instances of vehicle routing problems. The current literature lacks a characterisation of decomposition strategies and a systematic investigation of their impact when integrated into state-of-the-art heuristics. This paper fills this gap: we discuss the main characteristics of decomposition techniques in vehicle routing heuristics, highlight … Read more

Exact algorithms for the 0-1 Time-bomb Knapsack Problem

We consider a stochastic version of the 0–1 Knapsack Problem in which, in addition to profit and weight, each item is associated with a probability of exploding and destroying all the contents of the knapsack. The objective is to maximize the expected profit of the selected items. The resulting problem, denoted as 0–1 Time-Bomb Knapsack … Read more

Optimising the assignment of swabs and reagents for PCR testing during a viral epidemic

Early large-scale swab testing is a fundamental tool for health authorities to assess the prevalence of a virus and enact appropriate mitigation measures during an epidemic. The COVID-19 pandemic has shown that the availability of chemical reagents required to carry out the tests is often a bottleneck in increasing a country’s testing capacity. Further, demand … Read more

The Crop Growth Planning Problem in Vertical Farming

In this paper, we study the problem of planning the growth of crops on shelves in vertical farming cabinets under controlled growth conditions. By adjusting temperature, humidity, light, and other environmental conditions in different parts of the cabinets, a planner must ensure that crop growth is able to satisfy some deterministic demand. We prove this … Read more

An Exact Algorithm for the Partition Coloring Problem

We study the Partition Coloring Problem (PCP), a generalization of the Vertex Coloring Problem where the vertex set is partitioned. The PCP asks to select one vertex for each subset of the partition in such a way that the chromatic number of the induced graph is minimum. We propose a new Integer Linear Programming formulation … Read more