  In this paper, we investigate the problem of a last-mile delivery service
that selects up to $N$ available vehicles to deliver $M$ packages from a
centralized depot to $M$ delivery locations. The objective of the last-mile
delivery service is to jointly maximize customer satisfaction (minimize
delivery time) and minimize operating cost (minimize total travel time) by
selecting the optimal number of vehicles to perform the deliveries. We model
this as an assignment (vehicles to packages) and path planning (determining the
delivery order and route) problem, which is equivalent to the NP-hard multiple
traveling salesperson problem. We propose a scalable heuristic algorithm, which
sacrifices some optimality to achieve a reasonable computational cost for a
high number of packages. The algorithm combines hierarchical clustering with a
greedy search. To validate our approach, we compare the results of our
simulation to experiments in a $1$:$25$ scale robotic testbed for future
mobility systems.
