The complexity of the unit stop number problem and its implications to other related problems.

The Stop Number Problem arises in the management of a dial-a-ride system served by a fleet of autonomous electric vehicles. In such a system, clients request for a ride from an origin station to a destination station, and a fleet of capacitated vehicles must satisfy all requests. The goal is to minimize the number of pick-up/drop-off operations. In this paper we focus on a constrained unitary variant, called Unit Stop Number Problem, where each client requests for a single seat in the vehicles. This variant was recently conjectured to be NP-Hard. In this regard, we show how this problem relates to other problems known in the literature in order to derive some polynomial-time solvable variants. Moreover, we provide a positive answer to the conjecture by showing that the problem is NP-Hard for any fixed capacity greater than or equal to 2, even for the case where the graph of requests is restricted to the class of planar bipartite graphs. Our proof of NP-Hardness also improves the complexity results known in the literature for the related problems identified. [ABSTRACT FROM AUTHOR]