João Pedro Pedroso

Abstract
The forests and woodlands of Guinea-Bissau are a biodiversity hotspot under threat, which are progressively being replaced by cashew tree orchards. While the exports of cashew nuts significantly contribute to the gross domestic product and support local livelihoods, the country's natural capital is under significant pressure due to unsustainable land use. In this context, official entities strive to counter deforestation, but the problem persists, and there are currently no systematic or automated means for objectively monitoring and reporting the situation. Furthermore, previous remote sensing approaches failed to distinguish cashew orchards from forests and woodlands due to the significant spectral overlap between the land cover types and the highly intertwined structure of the cashew tree patches. This work contributes to overcoming such difficulty. It develops an affordable, reliable, and easy-to-use procedure based on machine learning models and Sentinel-2 images, automatically detecting cashew orchards with a dice coefficient of 82.54%. The results of this case study designed for the Cantanhez National Park are proof of concept and demonstrate the viability of mapping cashew orchards. Therefore, the work is a stepping stone towards wall-to-wall operational monitoring in the region. © 2022 Elsevier B.V.

Abstract
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.

Abstract
We propose a new approach for the lastmile delivery problem where, besides serving as collecting points of orders for customers, parcel lockers are also used as transshipment nodes in a 2-echelon delivery system. Moreover, we consider that a customer (occasional courier) visiting a locker may accept a compensation to make a delivery to another customer on their regular traveling path. The proposed shared use of the locker facilities - by customers that prefer to self-pick up their orders, and also as a transfer deposit for customers that prefer home delivery - will contribute to better usage of an already available storage capacity. Furthermore, the use of occasional couriers (OCs) brings an extra layer of flexibility to the delivery process and may positively contribute to achieving some environmental goals: although non-consolidation of deliveries may, at first sight, seem negative, by only considering OCs that would go to the locker independently of making or not a delivery on their way home, and their selection being constrained by a maximum detour, the carbon footprint can be potentially reduced when compared to that of dedicated vehicles. We present a mixed-integer linear programming formulation for the problem that integrates three delivery options - depot to locker, depot to locker followed by final delivery by a professional fleet, and depot to locker followed by final delivery by an OC. Furthermore, to assess the impact of OCs' no show on the delivery process, we extend the formulation to re-schedule the delivery of previous undelivered parcels, and analyze the impact of different no-show rates. Thorough computational experiments show that the use of OCs has a positive impact both on the delivery cost and on the total distance traveled by the dedicated fleets. Experiments also show that the negative impact of no-shows may be reduced by using lockers with higher capacities.

Abstract
Sea exploration is important for countries with large areas in the ocean under their control, since in the future it may be possible to exploit some of the resources in the seafloor. The sea exploration problem was presented by Pedroso et al. [13] (unpublished); we maintain most of the paper's structure, to provide the needed theoretical background and context. In the sea exploration problem, the aim is to schedule the expedition of a ship for collecting information about the resources on the seafloor. The goal is to collect data by probing on a set of carefully chosen locations, so that the information available is optimally enriched. This problem has similarities with the orienteering problem, where the aim is to plan a time-limited trip for visiting a set of vertices, collecting a prize at each of them, in such a way that the total value collected is maximum. In our problem, the score at each vertex is associated with an estimation of the level of the resource on the given surface, which is done by regression using Gaussian processes. Hence, there is a correlation among scores on the selected vertices; this is the first difference with respect to the standard orienteering problem. The second difference is the location of each vertex, which in our problem is a freely chosen point on a given surface. Results on a benchmark test set are presented and analyzed, confirming the merit of the approach proposed. In this paper, additional methods are presented, along with a small topological result and subsequent proof of the convergence of these same methods to the optimal solution, when we have instant access to the ground truth and the underlying function is piecewise continuous.

Abstract
The two-dimensional knapsack problem consists in packing rectangular items into a single rectangular box such that the total value of packed items is maximized. In this article, we restrict to 2-stage non-exact guillotine cut packings and consider the variant with splittable items: each item can be horizontally cut as many times as needed, and a packing may contain only a portion of an item. This problem arises in the packing of semifluid items, like tubes of small radius, which has the property to behave like a fluid in one direction, and as a solid in the other directions. In addition, the items are to be packed into stable stacks, that is, at most one item can be laid on top of another item, necessarily wider than itself. We establish that this variant of the two-dimensional knapsack problem is NP-hard, and propose an integer linear formulation. We exhibit very strong dominance properties on the structure of extreme solutions, that we call canonical packings. This structure enables us to design polynomial time algorithms for some special cases and a pseudo-polynomial time algorithm for the general case. We also develop a Fully Polynomial Time Approximation Scheme (FPTAS) for the case where the height of each item does not exceed the height of the box. Finally, some numerical results are reported to assess the efficiency of our algorithms. © 2022