Mikele Gajda

Sidewalk Autonomous Delivery Robots (SADRs) present a promising alternative for mitigating excessive delivery traffic in smart cities. These bots operate at pedestrian speed and work in conjunction with vans to offer efficient delivery services. Existing research emphasises the development of coordinated service schedules for vans and bots to optimise customer service. In contrast, this study examines the influence of bot return policies on their travel back to designated stations after task completion. We assess three distinct return policies that dictate the station selection for bot returns and explore the relocation of bots between stations using vans. Specifically, we present a reformulation of the fleet sizing problem as a minimum cost matching problem in a bipartite graph. This reformulation allows for the efficient calculation of optimal solutions for bot fleet sizing under different return policies within polynomial time. Notably, this computational efficiency enables the analysis of large-scale cases without sacrificing the evaluation of policies with heuristic gaps. Our findings highlight the importance of carefully selecting the appropriate return policy, as the best policies have the potential to decrease the bot fleet size by up to 70%.

We consider a real-world packing problem faced by a logistics company that loads and ships hundreds of trucks every day. For each shipment, the cargo has to be selected from a set of heterogeneous boxes. The goal of the resulting container loading problem (CLP) is to maximize the value of the cargo while satisfying a number of practical constraints to ensure safety and facilitate cargo handling, including customer priorities, load balancing, cargo stability, stacking constraints, positioning constraints, and limiting the number of unnecessary cargo move operations during multi-shipment deliveries. Although some of these constraints have been considered in the literature, this is the first time a problem tackles all of them jointly on real instances. Moreover, differently from the literature, we treat the unnecessary move operations as soft constraints and analyze their trade-off with the value maximization. As a result, the problem is inherently multi-objective and extremely challenging. We tackle it by proposing a randomized constructive heuristic that iteratively combines items in a preprocessing procedure, sorts them based on multiple criteria, uses randomization to partially perturb the sorting, and finally constructs the packing while complying with all the side constraints. We also propose dual bounds based on CLP relaxations. On large-scale industry instances, our algorithm runs in a few seconds and outperforms (in terms of value and constraints handling) both the solutions constructed manually by the company and those provided by a commercial software. The algorithm is currently used by the company generating significant economic and CO_2 savings.

In this paper, we deal with an innovative last-mile delivery paradigm that uses commuters traveling on public transportation networks as crowdshippers to offer a delivery model with minimal environmental impact that takes advantage of technological advancements, enhanced infrastructure, and growing electronic device usage. At the beginning of each delivery service period, parcels located at selected public transport stations, are assigned to a set of crowdshippers (commuters). These crowdshippers collect and deliver the parcels as part of their regular journeys through the public transport network, without deviating from their usual routes. A delivery company ensures, through a backup service, the final delivery of parcels that do not reach their final destination. The problem looks for the optimal schedule and route for each parcel while minimizing overall delivery expenses. We call this problem the Public Transport based Crowdshipping Problem (PTCP). We propose a compact Mixed Integer Linear Programming formulation strengthened with valid inequalities and develop an Adaptive Large Neighborhood Search to address large-scale instances. The experimental analysis, conducted on a large set of instances, shows the effectiveness of the proposed heuristic method when compared to the exact model solution. Sensitivity analysis reveals that crowdshipping and backup delivery costs significantly influence the total system cost.