Toward smarter urban mobility: the Concurrent Shortest Paths Problem for autonomous vehicles in a smart city

In this paper, we address a combinatorial optimization problem arising when deciding the routes to be followed by several autonomous vehicles. More particularly, each available autonomous vehicle needs to travel from its origin to its destination (e.g. to deliver or collect material). Considering all the constraints involved, the objective consists of minimizing the time at which the last vehicle reaches its destination. This problem is denoted as the Concurrent Shortest Path Problem (CSPP), which is a generalization of the Disjoint Shortest Path Problem existing in the literature. We formulate the CSPP using two Mixed Integer Linear Programming models: one based on flow formulations and another based on bin-packing formulations. Due to the high complexity of the problem, neither of these models can solve large instances of the CSPP. Therefore, two heuristic approaches are also proposed. Computational experiments over randomly generated instances empirically prove that the heuristic approaches yield good-quality solutions in short CPU times, enabling real-time management of autonomous fleets in smart-city and industrial environments.