Francesco Ferrucci
Stefan Bock



Highlights

•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.



Keywords
Pickup and delivery; Real-time control; Dynamic events; Traffic congestion; Vehicle disturbances;Tabu Search



Abstract
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.



Article Outline
1. Introduction
1.1. Contributions
1.2. Literature review
1.3. Organization

2. Problem description
3. Controlling and modeling the problem
3.1. Real-time control approach
3.2. Static problem instances

4. Tabu Search solution method
5. Computational experiments
5.1. Experimental setup
5.2. Test instance generation
5.3. Computational results

6. Conclusion and future work
Acknowledgements
References



Figures
   

Fig. 1.

The applied real-time control approach.


Fig. 2.

Utilized fuel consumption function.



Tables

Table 1. Stage-based neighborhood operator selection scheme.

Table 2. Time window lengths of different request types and their distribution in the tested scenario settings.

Table 3. Utilized vehicle classes, their characteristics, and number of available vehicles.

Table 4. Results for  using various request scenarios and fleet sizes.

Table 5. Results for , vx3 using various traffic congestion.

Table 6. Results for , vx3 using various vehicle disturbances.

Table 7. Results for  using various vehicle disturbances and fleet sizes.