Real-time control of express pickup and delivery processes in a dynamic environment

• We propose the DPDPRC that extends the DPDP by various real-world aspects.
• The model integrates a real-world fuel consumption function to derive travel costs.
• A real-world road network defining various road classes is used.
• The applied real-time approach handles various types of dynamic events.
• The applied Tabu Search enables necessary adaptations of plans in real-time.

In this paper we introduce the Dynamic Pickup and Delivery Problem with Real-Time Control (DPDPRC) in order to map urgent real-world transportation services. Specifically, the DPDPRC considers intra-day transportation services of express courier service companies and integrates real-world aspects that are crucial for a practical application. Vehicles have heterogeneous properties and operate on a detailed real road network. Various dynamic events that may occur unexpectedly during the day, such as new request arrivals, traffic congestion, and vehicle disturbances, are integrated. Because of the mentioned urgency, minimizing lateness at request locations is the primary objective. As a secondary objective, the minimization of vehicle operating costs is pursued. In order to adapt the transportation plan in response to dynamic events and enable a timely service of requests, a real-time control approach that performs plan adaptations simultaneous to the execution of the transportation service is applied. Plan adaptations are carried out by a Tabu Search algorithm whose search process is guided by a multi-stage neighborhood operator selection scheme which dynamically switches between intensification and diversification phases. We evaluate various test scenarios which comprise different occurrences of the dynamic events. Computational results show that a continuous adaptation of the transportation plan according to dynamic events improves the solution quality in many scenarios.