Daily Truck Operation#
In Polaris freight ABM framework, both e-commerce delivery and general business-to-business delivery operations are modeled as an optimization model. Single-depot vehicle routing problem is designed as a mixed-integer linear programming model, which minimizes the total operation cost. The objective function is the sum of total travel cost, truck purchasing cost, and drivers’ wage during operation. Also, the model supports energy-reduction plans by minimizing the total energy usage for delivery operations. Constraints are defined from common vehicle routing problem structures, including tour construction, delivery capacity, operation hour limitations, and time windows constraints. Finally, the model decides the best truck tour by visiting multiple delivery location from its depot. Figure below descirbes the modeling components of vehicle routing problem for both business-to-business and e-commerce delivery.
In this chapter, details around e-commderce delievery demand estimation, solution search procedure for mathematical optimization, service trip generation, and freight electrification.
E-Commerce Demand Estimation#
To estimate demand for e-commerce delivery stops in POLARIS, a new e-commerce model has been developed that draws on data from Lawrence Berkeley National Laboratory, “WholeTraveler Transportation Behavior Study. The model works in two stages. Firstly, it determines whether a household participates in e-commerce. If it does, then the second stage calculates the ratio of delivery to physical shopping for that household. Finally, POLARIS uses the model to assess if a household participates in e-commerce, and if so, how often they do so (i.e. how many orders they make per week), with e-shopping deliveries replacing physical shopping trips in the weekly calculation. As an example to implementation of e-commerce: The Chicago network has been the focus of the freight delivery demand estimation model, Atlanta has been the focus of the most recent freight implementation. Freight includes both intercity long haul, intracity last-mile delivery, and other regional freight movements. The Chicago freight delivery model fitted a linear regression model of TAZ-level delivery estimates from a Columbus, Ohio UPS GPS dataset (U.S. Department of Energy, 2020). The adjusted estimation model for Chicago is shown below. After establishing the number of daily deliveries per TAZ, the locations of all Chicago-area UPS, FedEx, Amazon, and USPS stores/service depots were obtained to estimate the displaced shopping trips.One can apply the same set-up to estimate how different delivery schemes and powertrain technologies can reduce emissions of urban freight delivery. These schemes include the electrification of trucks and vans and having customers pick up packages from distributed lockers (Stinson et al., 2019).
Bi-level heuristic as a solution search procedure for Optimization Model#
We developed a bi-level VNS-TS heuristic; truck assignment in the upper-level part and route improvement in the lower-level part. Truck assignment, engine type, and visiting locations vector are updated with VNS heuristic in the upper-level, and the lower-level problem finds the best routes of updated trucks with TS procedures. Figure below shosws the structure of the VNS-TS heuristic algorithm.
In the upper-level part, there is a vector which shows the assignment and type info of each truck; ‘0’ for non-assigned, ‘1c’ for assigned conventional, and ‘1e’ for assigned electrified trucks. Also, it has a location vector to be visited by each assigned truck for the demand covering constraint. Upper-level solutions are updated using VNS heuristic with several inter-route movements to find the best fleet mix to cover all the demands with the minimum purchasing costs. Whenever upper-level problem needs to compute objective function of a certain solution, lower-level problem is called to find the best order of visiting locations of a truck and return the value of the objective function to the upper-level. TS heuristic updates string-structured solutions with intra-route movements. There are two embedded procedures to compute the EVSE purchasing cost at depots and guarantee the feasibility of lower-level solutions. The bi-level structure offers efficient solution search for large-sized instances of the truck touring models, encompassing the entire e-commerce delivery and/or business-to-business delivery system in simulated metropolitan cities, by partitioning the solution space through variable classification. While the bi-level heuristic efficiently manages the number of neighborhood solution, it generally requires more iterations to converge. Further, the size of instances is significantly larger than that of typical VRPs, this paper focuses on heuristic development that emphasizes exploration at the upper level with ample randomness, while simplifying the lower level to minimize overall computational demands.
Service Trip Generation#
Commercial vehicle trips, such as delivery and service trips, are significant in urban travel. Modeling service trips can provide cities with a detailed picture of commercial vehicle activity, offering a realistic representation of freight and service demand and their impacts on the network. An integrated flow is used to synthesize service trip chains, implemented as the service trip module in the freight ABM framework in POLARIS. This module comprises three main components: service provider synthesis, service location generation, and service vehicle routing. A service trip chain is assumed to depart from a service provider location (or depot, assuming one service provider has one depot) and return to the depot at the end of the day. The 2017 Austin commercial vehicle survey data was utilized to provide relevant distributions and model inputs. In the provider synthesis part, potential service providers are extracted from POLARIS locations based on land use types and assigned 2-digit NAICS codes. Recognizing that different industries serve locations with different spatial patterns, a maximum service distance from the depot is synthesized based on distributions by NAICS code from the survey. Additionally, each service provider’s departure times are synthesized based on a time-of-departure model. Service location generation begins with a machine learning model, Random Forest Decision Tree, that estimates the average stop frequency of a service based on the characteristics of the service provider and service tours (e.g., departure time, depot land use, and industry type). A joint distribution of location type and service type is extracted from the survey data, guiding the selection of service locations based on the service type. Stop duration (or service duration) is then synthesized as the final property of a service tour. Finally, a fully synthesized service tour is fed into the tour optimization module to optimize the stop sequence. Vehicle movement plans are then generated and simulated on POLARIS network.
Freight Electrification#
Recent works in Polaris-freight covers new powertrain types for last-mile deliveries. Currently, electric truck operations have been modeled and implemented onto Polaris, and details of delivery operations are as below figure:
