A Multi-Agent approach to truck-drone routing problems

Autores:

José Miguel León Blanco
Pedro Luis González-R
Jose Luis Andrade Pineda
David Canca Ortiz

ABSTRACT

Introduction

The optimization of the combined use of trucks and other kind of vehicles in logistics is a study field with a rocketing interest by the research community. In this document, the problem of finding the shortest time needed to visit a set of locations, namely clients, using a truck and a drone is addressed using a Multi-Agent System (MAS). This is not only an abstract problem but a real one in this era of growing logistic needs.

Method

The optimization of last-mile delivery of parcels, like other routing problems is an NP-hard one. MASs have been seldom used in this kind of problems due to the computational overhead required by this architecture. MASs involve interaction between agents, mobility, intelligence or even react to changes in their environment. Conversely, MASs scale up better than other methods, so they are promising in large instances of problems, where exact methods or metaheuristics fail to find good quality solutions in a reasonable time.

The problem we have modelled consists in optimizing the route of a truck helped by a drone to visit a set of points starting from one depot and finishing in other. All the points must be visited once by the truck, the drone or both. The drone has a limited battery endurance and a limited payload capacity, but it is capable to visit more than one point in each flight. When the drone meets the truck, its battery is replaced and can begin another flight.

Our model consists in assigning an agent to each location, client or point in the route. Agents are organized in a grid where they can move to improve the quality of the solution, measured by total time. Our idea is to apply this architecture not only to the problem of one truck and one drone but to one truck and n drones and finally to the general case of m-trucks and n-drones.

Results

The preliminary results in randomly generated instances of the 1-truck 1-drone problem confirm that our method scales up well with instances of the problem containing more than 100 clients. We have compared the quality of our solutions with those obtained by a solver in small instances. In this case, the solver wins the comparison. In greater instances, our method is capable to find solutions where the solver is not able to find one.

Conclusion

Obtained results are promising in medium and big size instances of the problem but are worse in small instances, where exact methods or even fast meta-heuristics like iterated greedy can find better results for the problem in a very short computing time.

Our architecture is currently being extended to deal with the problem of using n drones and to the use of n trucks and our hope is to obtain good quality solutions like those obtained in simpler problems.