  Electric vehicle routing problems can be particularly complex when recharging
must be performed mid-route. In some applications such as the e-commerce parcel
delivery truck routing, however, mid-route recharging may not be necessary
because of constraints on vehicle capacities and maximum allowed time for
delivery. In this study, we develop a mixed-integer optimization model that
exactly solves such a time-constrained capacitated vehicle routing problem,
especially of interest to e-commerce parcel delivery vehicles. We compare our
solution method with an existing metaheuristic and carry out exhaustive case
studies considering four U.S. cities -- Austin, TX; Bloomington, IL; Chicago,
IL; and Detroit, MI -- and two vehicle types: conventional vehicles and battery
electric vehicles (BEVs). In these studies we examine the impact of vehicle
capacity, maximum allowed travel time, service time (dwelling time to
physically deliver the parcel), and BEV range on system-level performance
metrics including vehicle miles traveled (VMT). We find that the service time
followed by the vehicle capacity plays a key role in the performance of our
approach. We assume an 80-mile BEV range as a baseline without mid-route
recharging. Our results show that BEV range has a minimal impact on performance
metrics because the VMT per vehicle averages around 72 miles. In a case study
for shared-economy parcel deliveries, we observe that VMT could be reduced by
38.8\% in Austin if service providers were to operate their distribution
centers jointly.
