Research: cost‐optimal truck‐and‐robot routing for last‐mile delivery

During recent years, several companies have introduced small autonomous delivery robots and evidenced their technical applicability in field studies. However, a holistic planning framework for routing and utilizing these robots is still lacking. Current literature focuses mainly on the logistical performance of delivery using autonomous robots, ignoring real-world limitations, and does not assess the respective impact on total delivery costs.

In contrast, a new paper presents an approach to cost‐optimal routing of a truck‐and‐robot system for last‐mile deliveries with time windows, showing how to minimize the total costs of a delivery tour for a given number of available robots. The solution algorithm presented is based on a combination of a neighborhood search with cost‐specific priority rules and search operators for the truck routing, while we provide and evaluate two alternatives to solve the robot scheduling subproblem: an exact and a heuristic approach.

Screenshot 2021-03-09 at 17.07.48

The paper shows in numerical experiments that their approach is able to reduce last‐mile delivery costs significantly. Within a case study, the truck‐and‐robot concept reduces last‐mile costs by up to 68% compared to truck‐only delivery. Finally, the apply sensitivity analyses to provide managerial guidance on when truck‐and‐robot deliveries can efficiently be used in the delivery industry.

There are numerous opportunities for future research. The approach presented can help evaluate the effects of urban planning decisions on a truck-and-robot system. Certain zones could be forbidden for the truck or the robots, for example, while in other zones robots could be allowed to travel at a higher speed. Such constraints can be modeled by adapting the corresponding index sets and travel times. Moreover, the robot fleet needed could be further reduced by allowing robots to travel between depots such that robot availability is increased at locations visited by the truck.

Robot availability could be further improved by considering the robots’ return from customers to depots (with stochastic arrival times). To enable this, decisions on the robot movements must be made simultaneously with the delivery routing decisions. In addition, deliveries without time windows or for bulky goods that require manual delivery can be included in the planning problem. For the heuristic, this means customers are then potential or required stops on the truck route. Another interesting aspect is the allocation of customers to trucks and the start time of the truck, which they assume is a given. In practice, these decisions must be made such that they enable our method to find efficient tours.

Lastly, solving truck-and-robot problems requires tailored solution approaches and innovative algorithms. There are further approaches for related VRP variants that could be adapted and tested for the truck-and-robot concept.

Source: Ostermeier M, Heimfarth A, Hübner A. Cost-optimal truck-and-robot routing for last-mile delivery. Networks. 2021;1–26.

Leave a Reply

Your email address will not be published. Required fields are marked *