In this chapter the degree of dynamism measure was examined for systems both with and without time window constraints. Furthermore, a framework for dynamic vehicle routing systems based on their degree of dynamism was proposed. The framework should prove useful in selecting appropriate mod-els and algorithms according to the dynamic characteristics of the system examined.
Chapter 5
Partially Dynamic Vehicle Routing
In this chapter we further explore thedegree of dynamismmeasure by in-troducing the Partially Dynamic Traveling Repairman Problem (PDTRP).
A number of simple online dynamic policies to minimize the routing costs and/or the the waiting time experienced by the customers are described.
The results of the computational study indicate that an increase in the dy-namic level results in a linear increase in route length for all policies studied.
Furthermore, for relatively congested systems, a Nearest Neighbor policy performed uniformly better than the other dispatching rules studied.
We examine the impact of the degree of dynamism measure on solution methodology and quality. To give practical meaning to this concept, in section 5.1, we introduce the Partially Dynamic Traveling Repairman Prob-lem (PDTRP). In section 5.2 we discuss how to simulate the PDTRP. The results of the simulation are discussed in section 5.3. Finally, in section 5.4 we discuss how the PDTRP could be extended and then we offer our conclusions in section 5.5.
The work presented in this chapter is also described in Larsen et al. [27].
65
5.1 The Partially Dynamic Traveling Repair-man Problem (PDTRP)
In the Dynamic Traveling Repairman Problem introduced by Bertsimas and Van Ryzin [6] all demands are dynamic, i.e. all customers are im-mediate request customers. The Partially Dynamic Traveling Repairman Problem (PDTRP) is a variant of this problem involving both advance and immediate request customers. We will define the PDTRP as follows:
• A repairman (or a vehicle/server) travels at constant velocity in a bounded regionAof areaA.
• A subset of demands are dynamic. These arrive in time according to a Poisson process with intensity parameter λ. The locations of the demands are independently and uniformly distributed inA.
• Each demand requires an independently and identically distributed amount of on-site service time that becomes known once the service is completed.
• The route is updated only at customer locations. That is, a vehicle cannot change its destination while traveling.
• The objective is to minimize the repairman routing cost.
The PDTRP differs from the DTRP in two major aspects. First, the geo-graphical locations of a subset of the customers to be serviced are already known by the dispatcher before the server leaves the depot. Note also that the service times of advance as well as immediate requests are not known to the dispatcher, until the service at the respective customers is completed.
Second, the problems seek to optimize different objective functions. In a pure dynamic model it makes good sense to seek to minimize the overall system time. This has been defined as the sum of the waiting time and the on-site service time of the demands. However, in a partially dynamic setting the dispatcher may be more interested in minimizing the distance traveled by the repairman. Nevertheless, the immediate request customers should be served in some prioritized order - so that customers calling in late would not be serviced before customers that have been waiting for a relatively long period of time. Such scenarios include residential appliance repair services
5.1. PDTRP 67 and courier mail pick up where customers are not offered a specific time window for service. For example, the advance request customers could have their appliances fixed in the morning and the immediate request customers in the afternoon.
5.1.1 Routing Policies
We consider several heuristics originally analyzed by Bertsimas and Van Ryzin [6] for the DTRP. We give below a brief description of these policies:
• First Come First Serve (FCFS).
The demands are served in the order in which they are received by the dispatcher.
• Stochastic Queue Median (SQM).
This is a modification of the FCFS rule where the server travels di-rectly from the median of the service region to the next demand location. After the service has been completed, the server returns to the median and waits for the next demand.
• Nearest Neighbor (NN).
After completing service at one location the server travels to the nearest neighboring demand.
• Partitioning policy (PART).
The service region is partitioned into a number of smaller subregions, nsubreg, in which the demands are served using an FCFS policy.
We chose these policies because they include routing cost based policies - NN, waiting time based policies -FCFS, FCFS-SQM, and a mixture of these - PART.
The FCFS policy schedules the advance requests first without considering the locations of the requests. The immediate requests are added to the schedule as they are received by the dispatcher. In scenarios with more than one advance request a more elegant version of the FCFS would take the locations of the advance requests into consideration. A natural way of including this information into the policy is to construct a tour through the advance requests for instance by using the nearest neighbor method.
This gives another version of the FCFS policy which we will refer to as the Nearest Neighbor - FCFS(NN-FCFS) policy.
Similarly one could argue that for the PART policy advance requests should be visited according to an NN rule rather than at random within each subregion. Hence, the PART policy examined in the remaining part of the this chapter will visit all requests which were received by the dispatcher at the same time according to an NN rule. However, to customer whose requests for service are received at unique points in time the FCFS rule still applies.
The FCFS-SQM rule has been shown to give asymptotically optimal system time in light traffic. However, from a routing perspective, in environments where the triangle inequality holds, this policy will always produce longer distances than FCFS. It should be noted that the number of subregions used in the PART policy parameterizes this - i.e. the number of subregions should be found by optimization. We next consider the behavior of the above policies under conditions where the number of dynamic requests vary relatively to the number of static requests.