The capacitated location-routing problem involves determining the depots from a set of candidate capacitated depot locations and finding the required routes from the selected depots to serve a set of customers whereas minimizing a cost function that includes the cost of opening the chosen depots, the fixed utilization cost per vehicle used, and the total cost (distance) of the routes. This paper presents a multi-population integrated framework in which a multi-depot edge assembly crossover generates promising offspring solutions from the perspective of both depot location and route edge assembly. The method includes an effective neighborhood-based local search, a feasibility-restoring procedure and a diversification-oriented mutation. Of particular interest is the multi-population scheme which organizes the population into multiple subpopulations based on depot configurations. Extensive experiments on 281 benchmark instances from the literature show that the algorithm performs remarkably well, by improving 101 best-known results (new upper bounds) and matching 84 best-known results. Additional experiments are presented to gain insight into the role of the key elements of the algorithm.

This work reconsiders the concept of community-based trip sharing proposed by Hasan et al. (2018) that leverages the structure of commuting patterns and urban communities to optimize trip sharing. It aims at quantifying the benefits of autonomous vehicles for community-based trip sharing, compared to a car-pooling platform where vehicles are driven by their owners. In the considered problem, each rider specifies a desired arrival time for her inbound trip (commuting to work) and a departure time for her outbound trip (commuting back home). In addition, her commute time cannot deviate too much from the duration of a direct trip. Prior work motivated by reducing parking pressure and congestion in the city of Ann Arbor, Michigan, showed that a car-pooling platform for community-based trip sharing could reduce the number of vehicles by close to 60%. This paper studies the potential benefits of autonomous vehicles in further reducing the number of vehicles needed to serve all these commuting trips. It proposes a column-generation procedure that generates and assembles mini routes to serve inbound and outbound trips, using a lexicographic objective that first minimizes the required vehicle count and then the total travel distance. The optimization algorithm is evaluated on a large-scale, real-world dataset of commute trips from the city of Ann Arbor, Michigan. The results of the optimization show that it can leverage autonomous vehicles to reduce the daily vehicle usage by 92%, improving upon the results of the original Commute Trip Sharing Problem by 34%, while also reducing daily vehicle miles traveled by approximately 30%. These results demonstrate the significant potential of autonomous vehicles for the shared commuting of a community to a common work destination.