Park-and-multi-loop with autonomous delivery robots in last-mile logistics

This paper deals with the park-and-multi-loop routing problem, in the context of last-mile logistics, in which a fleet of traditional vehicles equipped with several autonomous delivery robots leaves from a depot to service a set of customer requests. Each delivery route involves a main tour of a traditional vehicle (subject to time-dependent travel times), which may stop at one or more parking locations, from which one or more walking sub-tours are carried out by the driver and the delivery robots on the pedestrian network. The goal is to minimize the overall cost of both van and walking routes. An alternative objective aims to minimize the (Formula presented.) emissions. A peculiarity of the problem is that the walking distance covered by drivers and delivery robots must not exceed given thresholds. For this problem, we propose a tailored destroy-and-repair mechanism embedded into a neighborhood search algorithm. The destroy-and-repair operators are parameterized, and the most appropriate parameter setting is chosen based on some performance measures of the solution. Computational results on a set of instances of varying size, derived from real data of two major Italian cities, certify the quality of the approach, compared to classic destroy-and-repair operators. Moreover, we also show the benefits of the proposed delivery scheme in terms of (Formula presented.) emissions when compared to a traditional delivery paradigm.