The problem of planning the last section of transport to the final recipient, known as the last mile problem, has a widespread interest within the logistics world due to its high cost. Due to the e-commerce boom in recent years, the search for optimal solutions continues to be an active field of study, and so, one of the most recent solutions that have appeared is to incorporate autonomous vehicles into distribution routes for making deliveries. In the next few lines, we delve into this alternative.
In the logistics field, transport has been and continues to be, an activity that poses difficult challenges to tackle. On the one hand, it is key to achieving the levels of service and satisfaction desired by the client; but, in return, it is usually the one that implies the highest cost. In particular, the delivery segment from the last distribution point to the final recipient, known in the jargon as “last mile transport”, deserves complex route planning that attempts to reduce the inherent high costs. According to the report “Last Link: Quantifying the cost” by Cushman & Wakefield, the cost of the last section represents approximately 50% of the total cost of the supply chain in online commerce.
Rethinking logistics post COVID-19
The Coronavirus crisis has meant an acceleration in the growth that e-commerce was experiencing in recent years and although this acceleration is not sustainable and the trend is to show a slowdown, it is not expected that the levels of online commerce and its percentage compared to physical sales will return to levels equal or lower than those existing before the pandemic. This implies an increase in the number of delivery vehicles, congestion in cities and, without interventions, increases in polluting emissions. It is estimated that in the main 100 cities of the world, the increase of vehicles will be 36% by 2030, this means 20% more congestion in the traffic of metropolitan areas and a possible increase of up to 6 million tons in CO2 emissions.
Faced with these new challenges, the incorporation of autonomous vehicles in last-mile distribution is emerging as an alternative.
Last Mile Autonomy
Autonomous last-mile delivery consists of employing robots, drones, and autonomous ground vehicles to deliver orders to end customers without human intervention.
Planning these routes requires techniques of advanced analytical. Apart from the complexity that characterizes any vehicle routing problem, other issues make it difficult to solve it. For example, if we think about delivery by drones, the possibility of replanning routes (adding or removing stops) in real-time is substantially limited: drones must be scheduled in advance enough to know their route.
To briefly illustrate the above, we will focus on the problem of optimizing deliveries using drones and trucks in combination: The Flying Sidekick Traveling Salesman Problem (FSTSP).
Let’s assume that there is a single truck with a drone. The truck will leave with the goods from a warehouse/platform and visit certain customers. For its part, the drone will go aboard the truck and when it is in one of the nodes, it will take off with a package, deliver to the corresponding client and return to the node where the truck is located to make another delivery or be inoperative after completing its planned deliveries.
Some of the additional requirements and issues that add complexity to the model (compared to traditional formulations) are:
- Coordinate the position of the truck and the drone for the launch and collection of the latter.
- Include service times for launches preparation and drone battery replacement.
- Consider the weight restrictions for the drone. This can mean that some customers, with heavy packages, only can be served by trucks.
- Take into consideration the flight autonomy of the drone.
In addition, another decision appears; the size of the fleet of drones and trucks. It is not trivial to balance costs and gains in speed, nor is it trivial to quantify the implications of oversizing. Additionally, increases in fleet size translate into greater complexity in drone-drone and drone-truck coordination; Likewise, more sophisticated calculations of the autonomy of each drone become necessary, taking into account the collection and launch times of the rest of the drones.
Fortunately, literature, technology and science are prepared to provide solutions to this type of problem through formulations of the TSP (Traveling Salesman Problem) and the VRP (Vehicle Routing Planning) to which the applicable restrictions are incorporated.
As a method of obtaining exact solutions, the use of integer binary programming. In this sense, the use of techniques such as Branch-and-Bound or Branch-and-Cut is particularly interesting, which provides significant savings in computational time; both techniques consist of dividing the problem and discarding subsets in which the optimality does not hold.
The disadvantage of the previous approach is that for problems of real dimensions, the application of exact methods is no longer efficient and it is necessary to resort to other resolution alternatives. Here the heuristics that allow finding good enough solutions come into play, but without guarantees of optimality, in exchange for great savings in time and computational complexity. In this field, there are multiple options, for example, the Nearest Neighbor algorithm. Finally, along with this, the use of metaheuristics such as Tabu Search is particularly widespread.
Is this an appealing solution?
As we have wanted to illustrate in previous lines, planning routes assisted by autonomous vehicles is not an easy task. Many requirements must be verified, and this makes it a rather complex optimization. However, many companies are dabbling in the use of these techniques:
Amazon has Prime Air, its program of deliveries by a drone, that is still in development and made its first delivery in 2016. Alibaba has also designed its autonomous delivery robot – Xiao Man Lv – which has been successfully tested at Chinese universities. Carrefour also joins the list, which has announced a pilot project for deliveries with autonomous robots in the United Arab Emirates for 2022.
Even Domino’s Pizza has already launched pizza deliveries with R2 robots designed by the startup Nuro in Texas, USA.
The use of autonomous vehicles promises great benefits, mainly in terms of increased speed of deliveries, improvements in the level of service and cost savings that it can entail; but also improvements in issues such as real-time monitoring, the reduction of polluting emissions, the decongestion of urban centres and, if you will, we could think about less tangible benefits such as the fact of modernizing cities.
Due to all of the above, it is to be expected that the list of companies participating in pilot projects will continue to grow. But there are still many issues to resolve: Wrong addresses, remote locations, the recipient’s absence and returned orders are just some of the potential situations that affect costs and for which it is quite complex to make an estimation. In the same way, there are problems related to the privacy of users, airspace regulations and the destruction of jobs. Regarding the latter, Bill Gates opened the discussion in 2017, should robots pay taxes?
