Dynamic discretization discovery for the service network design problem with mixed autonomous fleets. (November 2020)

• Record Type: Journal Article
• Authors: Scherr, Yannick Oskar; Hewitt, Mike; Neumann Saavedra, Bruno Albert; Mattfeld, Dirk Christian
• Is Part Of: Transportation research. Volume 141(2020)
• Page Start: 164
• Page End: 195
• Publication Date: 2020-11
• Subjects: Service network design -- Time-expanded network -- Dynamic discretization discovery -- Automated driving -- Platooning -- Two-tier city logistics; Transportation -- Research -- Periodicals; Transportation -- Mathematical models -- Periodicals
• DOI: 10.1016/j.trb.2020.09.009
• Languages: English
• ISSNs: 0191-2615

Abstract

Highlights: We consider a service network design problem with mixed autonomous fleets. Our dynamic discretization discovery approach outperforms a commercial solver. Two relaxation-based enhancements provide exact solutions in reduced runtime. Heuristic search space restriction quickly provides heuristic solutions. Case study on real-world network gives insights into usage of AVs and platoons. Abstract: We consider a service network design problem for the tactical planning of parcel delivery in a city logistics setting. A logistics service provider seeks a repeatable plan to transport commodities from distribution centers on the periphery to inner-city satellites. In a heterogeneous infrastructure, autonomous vehicles in level 4 may only drive in feasible streets but need to be pulled elsewhere by manually operated vehicles in platoons. We formulate an integer program to determine the fleet mix, schedule transportation services, and decide on the routing or outsourcing of commodities. Platooning requires a high level of synchronization between vehicles which demands the time-expanded networks to contain narrow time intervals. Thus, we develop an algorithm based on the dynamic discretization discovery scheme which refines partially time-expanded networks iteratively without having to enumerate the fully time-expanded network a priori. We introduce valid inequalities and provide two enhanced versions of the algorithm that exploit linear relaxations of the problem. Further, we propose heuristic ideas to speed up the search for high-quality solutions. In a computational study, we analyze the efficacy of the algorithm in different versions and observe improvements of computational performance in comparison to a commercial solver. Finally, we solve a case study on a real-world based network to obtain insights into the deployment of a mixed autonomous fleet in an existing heterogeneous infrastructure.