Towards optimizing dual-mode fleet routing and parcel allocation

More and more parcels are delivered all over the world, by numerous carriers. Collaboration between couriers can benefit both companies and their customers, as it has the potential to reduce cost and reduce the number of couriers stopping at the same location. Furthermore, autonomous driving is gradually picking up traction opening up another possibility for cost reduction. The ability to use autonomous vehicles (AVs) for parcel delivery removes some restrictions and limitations that apply to human drivers (e.g. limited working hours, reduced focus due to sleep deprivation). Unfortunately, full self-driving on all roads and for all vehicles is still a tale of the future. It is therefore beneficial to be able to optimize routing using a mixed fleet or a fleet of vehicles that can drive autonomously but also with a driver (dual-mode vehicles). The work presented in this thesis addresses the pickup and delivery problem (PDP) through dynamic fleet management, attempting to optimally utilize the available vehicles based on the current requirements/demand. These demands change over time as customer requests, e.g parcel pickup/delivery, are continuously added requiring recalculation of the optimal strategy. Although PDP has been described in literature in many forms, to the best of our knowledge, none of the existing work treats mode changes as a separate entity. Our work aims to fill this gap by using dual-mode fleets and combining the corresponding vehicle mode based route restrictions (in the form of AV zones) and explicit mode changes into a single dynamic problem. To that end a unified model for the extended PDP is introduced, in which a fleet consists of vehicles which can change modes (manual vs autonomous driving) along the way and where autonomous driving is only permitted within specific parts of the road network: AV zones. By also including collaboration in the form of request transfers a formal model is proposed for the Pickup and Delivery Problem with Transfers and Autonomous Vehicle Zones (PDPT-AVZ). To explore the impact of using dual-mode fleets and illustrate the possibilities of the PDPT-AVZ model an Adaptive Large Neighborhood Search (ALNS) based algorithm is introduced, including a novel Shift Request heuristic. Through experiments utilizing a network representing the city of Delft, Netherlands, varying AV zones and simulating requests by generating demand, a significant reduction in scenario cost is found for dual-mode vehicles compared to regular vehicles. Moreover, the impact on the solution cost of some AV zone characteristics is explored. Both the relative coverage of the AV zone, with respect to the full road network, and the topology of the network in terms of the number of connected regions within the network, are shown to have a significant impact on the overall result when using the ALNS algorithm. Similarly the impact of the level of dynamism is explored, showing that more efficient solutions in terms of overall cost are obtained when all requests are available at the start of the planning horizon.i-CaveComputer Scienc