0 1 2 3 4 5 6 7 8 9 10
0 20 40 60 80 100
# Repositions
Degree of dynamism (%)
ADTSPTW - Scenario A - minimize distance. E{n_tot} = 40.
Busiest - L(thres) = 0.8 Nearest - L(thres) = 0.8 HI-REQ - L(thres) = 0.8
Figure 7.7: The average number of repositions as a function of the degree of dynamism when the distance is minimized.
In Figure 7.8 the number of repositionings is shown as a function of the degree of dynamism for the HI-REQ strategy for the four different values of the threshold parameter,Lthres. For the present scenario it is seen that the vehicle is repositioned more than six times as often forLthres= 0.8 as forLthres= 0.2 for systems withdod= 50 %.
7.6 Further Work
A natural extension of the model described in this paper is a generalization into dealing with multiple vehicles. The extension of course leads to other strategic decisions on for example the issue of how to assign the requests to the vehicles.
0 1 2 3 4 5 6 7 8 9 10
0 20 40 60 80 100
# Repositions
Degree of dynamism (%)
ADTSPTW - Scenario A - minimize distance. E{n_tot} = 40.
HI-REQ - L(thres) = 0.2 HI-REQ - L(thres) = 0.4 HI-REQ - L(thres) = 0.6 HI-REQ - L(thres) = 0.8
Figure 7.8: The average number of repositionings as a function of the degree of dynamism when the distance is minimized.
Another important issue to investigate is the potential savings in allowing the vehicle(s) to divert from the current route when a new and promising request appears in the vicinity of the current position of the vehicle. In re-lation to the present work diversion could be implemented in two different situations. Firstly, the most obvious situation to allow the vehicle to divert in is the situation where the vehicle is repositioning to an idle point. The other situation is when the new immediate request appears, while the vehi-cle is on-route to serve the next planned customer. Recently, the diversion issue has gained increased popularity amongst OR researchers. Interesting work on diversion can be found in Yang et al. [44] and in Ichoua et al. [21].
The HI-REQ policy could be extended in several ways. A natural extension would be to take the neighboring arrival intensities into consideration when calculating the attractiveness score. To illustrate this we have included Figure 7.9. In the first case the HI-REQ policy would probably choose one
7.7. CONCLUSIONS 127 of the subregions with aλ= 2 as the potential idle point to reposition to although the central subregion might be the best choice due to the short distance to all the high intensity neighbors. In the case illustrated by the right-hand figure another example of the same problem is shown. The HI-REQ would probably choose the top-right subregion (with λ= 3) as the potential idle point. In other words, the HI-REQ policy would not include the bottom-left subregions. In both cases one could argue that a location based analysis could improve the quality of the choice of subregion.
V
Figure 7.9: Two ADTSPTW scenarios with the 9 subregions’ arrival inten-sity weights.
7.7 Conclusions
In this chapter we formulated a model for the Dynamic Traveling Salesman Problem with Time Windows (DTSPTW) including advance request as well as immediate request customers. This model was motivated by the pick-ups and deliveries of long-distance courier mail and packages. We extended the DTSPTW to also include a-priori information on future requests. We proposed three simple repositioning policies based on the a-priori informa-tion. Finally, these policies were tested on a set of test data resembling the aforementioned long-distance courier mail service application.
The results indicated some potential for reducing the lateness of the vehicle when using an a-priori based repositioning policy at the expense of an increase in the distance driven by the vehicle. The HI-REQ reposititioning policy seemed to have the highest number of best performances with respect
to the lateness. However, no clear conclusions on which repositioning policy should be used could be drawn from the empirical analysis.
Further research within this field should consider allowing diversion during repositioning or even during traveling from one customer to the next on the route. Furthermore, in order to get the desired effect from the idle points more sophisticated methods for locating the idle points should be considered.
Chapter 8
A Real-life Scenario
In this chapter we examine a real-life example of the dynamic vehicle rout-ing problem, namely the problem arisrout-ing when people and companies all over the world each day make use of long-distance courier mail services to send mail as well as packages across the world. Naturally, the underlying distribution system is very large as well as rather complex. Figure 8.1 il-lustrates a simplified version of this distribution system. In this chapter the routing of the truck delivering and picking-up the mail and/or pack-ages is considered. As can be seen from the figure this problem arises in both “ends” of the distribution system. With most long-distance courier mail service providers both the delivery and the pick-up problem is handled by the same vehicle. Usually, the deliveries are made during the morning hours, whereas the pick-ups mainly take place during the afternoon. This rhythm is natural since the customers in a long-distance courier mail dis-tribution systems are to a large extent offices and other similar businesses wishing to receive their materials as early as possible and have their mail picked-up as late as possible. This means that each courier mail truck and its driver both acts as a delivery as well as a pick-up truck. This combined problem of delivering and picking-up courier mail can be considered as an application of the dynamic vehicle routing problem, since some unknown fraction of the pick-up customers call in for service, while the trucks are on-route.
Firstly, the underlying routing problem will be presented in further detail.
Secondly, some key figures and the composition of the real-life dataset used 129
Regional Sender
National Distribution Truck
Truck Truck
Truck
Plane Truck Truck
Airport Center Center
Distribution
Airport
Receiver
Center Center
National Regional
Distribution Distribution
Truck
Truck/
Rail
Truck
Truck Truck
Figure 8.1: Simplified illustration of the distribution system for a long-distance courier mail service provider.
in this chapter will be described. Next, we describe how the heuristic that was developed to solve the A-priori Dynamic Traveling Salesman Prob-lem with Time Windows (ADTSPTW) introduced in chapter 7 had to be modified in order to solve this specific application. Finally, we present the results of the test runs and point to possible further research in this field.