INDUSTRIAL ENGINEERING APPLICATIONS IN TRANSPORTATION:PICKUP AND DELIVERY

PICKUP AND DELIVERY

Pickup-and-Delivery Operations

Daily operations in parcel delivery include local pickup and delivery. Terminal facilities are assigned to service areas so that every package that has an origin or destination in the service area is handled through the assigned terminal. Each workday, a ﬂeet of vehicles leaves a terminal (depot) carrying packages to be delivered to customers and returns carrying packages that have been picked up from customers. Most deliveries occur before the pickups, which take place late in the day. Each customer stop (either delivery or pickup) is characterized by a time window during which service must begin.

These windows are usually one-sided: a delivery must occur before a given time and a pickup after a given time. Some windows, though, may be wide open (e.g., a delivery must occur by the end of the workday) and other windows may be two-sided (a pickup must occur before an early closing time). Vehicle capacities are not a limitation in this problem; therefore, the ﬂeet of vehicles may be considered homogenous if the difference in type of vehicle does not have a signiﬁcant effect on cost. Maximum on-road time for the workday is an important limitation, where on-road time is deﬁned as the total elapsed time from the moment a vehicle leaves the depot until it returns to the depot. The importance of on-road time derives from the fact that often drivers are paid overtime for hours of work beyond a certain length (e.g., 8 hours), and work rules prohibit work days beyond a certain length (e.g., 10 hours).

Efﬁcient distribution implies good asset utilization. The primary assets in this problem are vehicles and drivers. Minimization of the number of drivers and of the total cost of the routes are frequently used objectives. Efﬁciency needs to be achieved while level of service is maintained; that is, service is provided to all customers in such a way as to satisfy all time-window constraints. This problem has a very short-term planning horizon. Since customer stops may differ from day to day and all the stops are known only a few hours before the actual pickup-and-delivery operation, the problem needs to be solved a few hours before implementation.

Modeling

The pickup-and-delivery problem can be modeled as a variation of the vehicle routing problem with time windows (VRPTW) and a single depot. Inputs for the VRPTW include matrices that specify the distance and travel time between every pair of customers (including the depot); service time and time window for each customer; maximum (or speciﬁed) number of drivers; starting time of the workday; and maximum on-road time of the workday. The maximum on-road time of the workday can be implemented as a time window on the depot, so that the pickup and delivery problem described above can be considered as a traveling salesman problem with time windows and multiple routes (m-TSPTW). However, the term VRPTW will be used in this section for this uncapacitated pickup- and-delivery problem.

Distances and travel times can be derived from the longitude and latitude of the customers and depot, assuming speciﬁc speed functions. Alternatively, distances and travel times can be obtained from an actual street network; this latter method provides greater accuracy. Longitude and latitude values are relatively easy to obtain; it is often considerably more difﬁcult to acquire data for a street network.

The objective in the VRPTW is to minimize the number of drivers and / or minimize the total cost of the routes while satisfying all constraints. Cost is a function of total distance and on-road time. The output is a set of routes, each of which speciﬁes a sequence of customers and starts and ends at the depot. Because of the short-term planning horizon, the drivers need to be notiﬁed for work before the problem is solved. In many cases, therefore, the number of drivers may be estimated and assumed given; the objective then becomes to minimize total cost.

The number of drivers is unlikely to be changed daily. However, the transportation of small packages is characterized by seasonality of demand. In the United States, demand increases by 40–

50% during the months before Christmas. A pickup-and-delivery model can be used to obtain the minimum number of additional drivers that must be used to maintain level of service when demand increases.

The VRPTW is an extension of the traveling salesman problem with time windows (TSPTW), which in turn is an extension of the classical traveling salesman problem (TSP). The TSP and its variants have been studied extensively, and many algorithms have been developed based on different methodologies (Lawler et al. 1985). The TSP is NP-complete (Garey and Johnson 1979) and therefore is presumably intractable. For this reason, it is prohibitively expensive to solve large instances of the TSP optimally. Because the TSPTW (and the VRPTW with a maximum number of available drivers) are extensions of the TSP, these problems are NP-complete as well. In fact, for the TSPTW and VRPTW, not only is the problem of ﬁnding an optimal solution NP-complete; so is the problem of even ﬁnding a feasible solution (a solution that satisﬁes all time window constraints) (Savelsbergh 1985). For more on time constrained routing and scheduling problems, see Desrosiers et al. (1995).

Existing exact algorithms for the VRPTW have been reported to solve problems with up to 100 stops. However, the problems encountered in parcel delivery are often substantially larger than this. Moreover, these problems need to be solved quickly because of the short-term planning horizon. For these reasons, much of the work in this area has focused on the development of heuristic algorithms— algorithms that attempt to ﬁnd good solutions instead of optimal solutions.

Heuristic algorithms for the TSPTW and VRPTW are divided into two general categories: route- construction heuristics and route-improvement heuristics. The ﬁrst type of heuristic constructs a set of routes for a given set of customers. The second type of heuristic starts from an existing feasible solution (set of routes), and attempts to improve this solution. Composite procedures employ both

types of heuristic, either by ﬁrst constructing routes heuristically and then improving them or by applying route-improvement procedures to partially constructed routes at selected intervals during the route-construction process itself. Route-construction and route-improvement heuristics are discussed in more detail below.

Heuristic Construction Algorithms

There are two general strategies that a route-construction algorithm for the VRPTW can adopt. The ﬁrst strategy is ‘‘cluster ﬁrst, route second,’’ which ﬁrst assigns stops to drivers, and then constructs a sequence for the stops assigned to each driver. The second strategy carries out the clustering and sequencing in parallel.

Because clustering is based primarily on purely spatial criteria, the cluster-ﬁrst, route-second strategy is often more appropriate for the vehicle routing problem (VRP), where time windows are not present than for the VRPTW. However, cluster-ﬁrst strategies can play a useful role in some instances of the VRPTW, as will be discussed later.

For now, we will conﬁne our attention to algorithms that carry out clustering and sequencing in parallel. Within this general class of algorithms, there is a further distinction between sequential heuristics, which construct one route at a time until all customers are routed, and parallel heuristics, which construct multiple routes simultaneously. In each case, one proceeds by inserting one stop at a time into the emerging route or routes; the choice of which stop to insert and where to insert it are based on heuristic cost measures. Recent work suggests that parallel heuristics are more successful (Potvin and Rousseau 1993), in large part because they are less myopic than sequential approaches in deciding customer-routing assignments.

In the following discussion, we focus on heuristic insertion algorithms for the VRPTW. Solomon (1987) was the ﬁrst to generalize a number of VRP route-construction heuristics to the VRPTW, and the heuristic insertion framework he developed has been adopted by a number of other researchers. Solomon himself used this framework as the basis for a sequential algorithm. In what follows, we brieﬂy describe Solomon’s sequential algorithm and then turn to extensions of the generic framework to parallel algorithms.

A Sequential Route-Construction Heuristic

This heuristic builds routes one at a time. As presented by Solomon (1987), sequential route con- struction proceeds as follows:

1. Select a ‘‘seed’’ for a new route.

2. If not all stops have been routed, select an unrouted stop and a position on the current route that have the best insertion cost. If a feasible insertion exists, make the insertion, else go to step 1.

In step 1, the heuristic selects the ﬁrst stop of a new route (seed). There are various strategies for selecting a seed. One approach is to select the stop that is farthest from the depot; another is to select the stop that is most urgent in the sense that its time window has the earliest upper bound. In step 2, the heuristic determines the unrouted stop to be inserted next and the position at which it is to be inserted on the partially constructed route. In order to make this determination, it is necessary to compute, for each unrouted stop, the cost of every possible insertion point on the route.

Solomon introduced the following framework for deﬁning insertion cost metrics. Let (s0, s1, . . . , sm) be the current partial route, with s0 and sm representing the depot. For an unrouted stop u, c1(si, u, sj) represents the cost of inserting u between consecutive stops si and sj. If the insertion is not feasible, the cost is inﬁnite. For a given unrouted stop u, the best insertion point (i(u), j(u)) is the one for which

Stop u* is then inserted in the route between i(u*) and j(u*). Possible deﬁnitions for the cost function c1 are considered later.

A Parallel Route-Construction Heuristic

A parallel route-construction heuristic that extends Solomon’s sequential algorithm is presented next; the presentation is based on ideas presented by Potvin and Rousseau (1993, 1995) and Russell (1995).

1. Run the sequential algorithm to obtain an estimate of the number of routes k. We can also retain the k seeds obtained by the sequential algorithm. Alternatively, once one has obtained an estimate of the number of routes, one can use some other heuristic to generate the seeds. A representative method is the seed-point-generation procedure of Fisher and Jaikumar (1981). The result of this process is a set of k routes that start from the depot, visit their respective seeds, and return to the depot.

2. If there are no unrouted stops, the procedure terminates. Otherwise, for each unrouted stop u and each partially constructed route r = (s0, . . . , sm), ﬁnd the optimal insertion point ( pr(u), qr(u)) for which

One way of deﬁning the measure c2 is simply by setting c2 = c1. In this case, the optimal c2-value is a minimum. An alternative approach is to deﬁne c2 as a ‘‘maximum regret’’ measure.

A regret measure is a kind of ‘‘look-ahead’’ heuristic: it helps select the next move in a search procedure by heuristically quantifying the negative consequences that would ensue, if a given move were not selected. In the context of vehicle routing, a simple regret measure for selecting the next customer to be routed might proceed as follows. For each unrouted customer, the ‘‘regret’’ is the difference between the cost of the best feasible insertion point and the cost of the second-best insertion point; the next customer to be added to a route is one whose regret measure is maximal. But this is still a relatively shortsighted approach. One obtains better results by summing the differences between the best alternative and all other alternatives (Potvin and Rousseau 1993; Kontoravdis and Bard 1995).

The regret measure that results from this idea has the form

Underlying the use of this regret measure is a notion of urgency: the regret measure for a stop u is likely to be high if u has relatively few feasible or low-cost insertion points available. We would like

to route such a u relatively early to prevent its few good insertion points from being taken by other customers.

A Numerical Example

We illustrate the route-construction process by considering an instance of the VRPTW with 18 stops, together with the depot (node 0). Table 1 displays the time matrix for this problem, and Table 2 the time windows. All times are listed in hundredths of an hour; for example, 9:45 is represented as 975. The starting time from the depot is 875 for all drivers. Three routes are to be generated, using as seeds nodes 18, 6, and 4.

The parallel route-construction procedure initializes each route by inserting its seed node. Hence, this process creates the three one-stop routes, (0–18–0), (0–6–0), and (0–4–0). Next, for each un-

routed node, the best feasible insertion cost for each of the three current routes is computed from formula (1), where ex1 = 0, ex2 = 1, and time is used as the cost measure. This computation obtains for node 1 the best insertion costs (55 63 53) for the three routes. Hence, the best feasible insertion of node 1 is into route 3 (r* = 3 in formula (2)). The regret measure for node 1 using formula (2) is calculated as follows:

The regret measures for the remaining unrouted nodes are computed similarly. The regret values for each node are shown in the following array, where x indicates a node that has already been included in a route.

At each iteration of the procedure, the next stop to be inserted into a route is a stop with the maximal regret measure. In the present case, node 5 has the maximal regret. Hence, the procedure inserts node 5 into its best feasible insertion point (ﬁrst stop after the depot on route 1). After node 5 is inserted, the three routes under construction become (0–5–18–0), (0–6–0), and (0–4–0). The algorithm repeats this process until all nodes have been inserted.

The three routes returned by the procedure are shown in Table 3 and Figure 4.

Infeasible Problems

One of the inputs to a typical instance of the VRPTW is the maximum number of drivers available. In the case where the time windows are relatively tight, an algorithm may not be able to ﬁnd a feasible solution (i.e., a solution in which all time windows are satisﬁed). The way one proceeds in this case depends on the nature of the application. In some applications, where there is a service guarantee and the same penalty applies no matter how close to meeting the service commitment a late delivery happens to be, we wish to minimize the number of missed time windows. In other applications, where the penalty is proportional to the lateness of a delivery, we wish to minimize,

over all stops, the total time by which the upper bounds of the time windows of stops are missed. In either case, we can still apply the heuristic insertion framework described above by adding an appropriate penalty function to the standard heuristic cost functions.

Work Breaks

The algorithms presented thus far provide a framework for solving a variety of routing and scheduling problems. However, the speciﬁc algorithms we have considered are applicable directly only to a small range of problems; they generally have to be extended in some way in order to deal with real-world applications. One important extension arises in routing applications in which the driver spends an entire day on the road. For such applications, we must take into account the necessity of scheduling lunch and other breaks in order to satisfy work rules and other constraints. Taking these factors into account complicates an already difﬁcult problem.

We can characterize a break by specifying the following values: earliest start time for the break, latest start time for the break, and duration of the break. For example, we might specify that we are to include a 50-minute lunch break that begins any time between 11 am and 1 pm.

To accommodate breaks within the heuristic insertion framework, the most natural way to proceed is to represent the breaks themselves as nodes. Note that a break does come with a natural time window (earliest and latest start times) and an analogue of service time (duration of break). The one crucial missing item is location. In some cases, the location of breaks may be speciﬁed as part of the input to the algorithm. In general, however, the algorithm will have to select a location for each break, based on the locations of the nodes that represent actual stops.

For example, suppose we wish to schedule a break after stop a but before stop c. According to the heuristic insertion framework, this is just the problem of inserting the break node b between nodes a and c. One possible approach is simply to assign a’s location to b. In this case, we calculate the arrival time at c as follows. Let [ex, lx] be the time window for a given stop x, svcTimex the service time at x, and txy the travel time from x to y. If x has been assigned to a route, we let arrivalx be the arrival time of the driver at location x. Then the time at which service begins at stop x is given by

startTimex = max(arrivalx, ex)

In the case being considered here, where break node b is inserted between stops a and c, we have startTimec = startTimea + svcTimea + svcTimeb + tac Recall that svcTimeb is just the duration of the break.

This is the basic picture, but there is at least one complication that we have to take into account.

Suppose, as before, that we wish to insert break node b between a and c. Suppose also that the travel time from a to c is 30 minutes, that service is completed at a at 10:45, and that the time window for b is [11:00, 1:00]. Then, according to the simple scheme just described, we would have to wait for 15 minutes at location a before starting lunch at a! To avoid this sort of awkward behavior, we would actually insert b at the ﬁrst point on segment (a, c) such that there is no waiting time at b. If there is no such point, then we conclude that no lunch break can be inserted between stops a and c. For example, in the scenario just described, we would insert b halfway between a and c.

When a break has been fully represented this way as a node with time window, location, and service time, it is treated just like any other node within the heuristic insertion framework.

Route-Improvement Heuristics

Heuristic route-improvement procedures play a fundamental role in vehicle routing algorithms. Such procedures take as input a feasible solution consisting of a route or set of routes and seek to transform this initial solution into a lower-cost feasible solution.

One of the most successful route-improvement strategies has involved the use of edge-exchange heuristics. The edge-exchange technique was introduced by Lin and Kernighan (1973) as a local search strategy in the context of the conventional traveling salesman problem, but it has since been applied to a variety of related problems, including the vehicle routing problem.

For an individual route, a k-exchange involves replacing k edges currently on the route by k other edges. For example, a 2-exchange involves replacing two edges (say (i, i + 1) and ( j, j + 1)) by two other edges ((i, j) and (i + 1, j + 1)). Usually, all the available k-exchanges are examined and the best one is implemented. This is repeated as long as an improved solution is obtained. Since there are n subsets of k edges in a cycle of n edges, the computational complexity of the edge- exchange method increases rapidly with k. Even one k-exchange requires O(nk) time, so attention is

usually conﬁned to the cases k = 2 and k = 3.

The idea of an edge exchange can be extended in a straightforward way to the case of pairs of routes. In this case, one exchanges entire paths between routes, where a path consists of a sequence of one or more nodes. For example, let routeA = (a1, a2, . . . , ak), routeB = (b1, b2, . . . , bn). Then, after exchanging paths between the two routes, the routes that result would be of the form, routeA = (a1, . . . , ai, bj+1, . . . , bj+r , am, . . . , ak), and similarly for routeB.

As mentioned, the goal of a route-improvement heuristic is to reduce routing costs; typically this means that we wish to minimize route duration. However, when we are dealing with time windows, we must also verify that any proposed exchange retains time window feasibility. Techniques for efﬁcient incorporation of time window constraints into edge-exchange improvement methods were developed by Savelsbergh (1985, 1990, 1992); see also Solomon et al. (1988).

The most recent work on route improvement has focused on the development of metaheuristics, which are heuristic strategies for guiding the behavior of more conventional search techniques, with a view towards avoiding local optima and thereby achieving higher-quality solutions. Metaheuristic techniques include tabu search, genetic algorithms, simulated annealing, and greedy randomized adap- tive search (Glover 1989, 1990; Kontoravdis and Bard 1995; Potvin et al. 1996; Rochat and Taillard 1995; Taillard et al. 1997; Thangiah et al. 1995).

To illustrate the pertinent concepts, we focus here on tabu search. Tabu search helps overcome the problem of local optimality, which often arises when traditional deterministic optimization heu- ristics are applied. The problem of local optimality arises in the following way. A wide range of optimization techniques consists of a sequence of moves that lead from one trial solution to another. For example, in a vehicle-routing algorithm, a trial solution consists of a route for each vehicle; and a ‘‘move,’’ in the route-improvement phase, might consist of some sort of interroute exchange. A deterministic algorithm of this general type selects a move that will most improve the current solution. Thus, such a procedure ‘‘climbs a hill’’ through the space of solutions until it cannot ﬁnd a move that will improve the current solution any further. Unfortunately, while a solution discovered with this sort of hill-climbing approach cannot be improved through any local move, it may not represent a global optimum.

Tabu search provides a technique for exploring the solution space beyond points where traditional approaches become trapped at a local optimum. Tabu search does not supplant these traditional approaches. Instead, it is designed as a higher-level strategy that guides their application.

In its most basic form, the tabu method involves classifying certain moves as forbidden (or ‘‘tabu’’); in particular, a move to any of the most recently generated solutions is classiﬁed as tabu.

(When we speak of ‘‘moves’’ here, we mean moves generated by some traditional search method such as edge exchange.) The tabu algorithm then selects the best move from the set of moves not classiﬁed as tabu, in order to drive the search into new regions. No concern is given to the fact that the best available moves may not improve the current solution. In particular, because a recently achieved local optimum will be classiﬁed as tabu, the method can drive the search down the hill away from this local optimum. The hope is that the expanded search will lead to an improved ﬁnal solution. There is no guarantee that an improved solution will be found, but variations on the method just described have achieved considerable success and have become increasingly popular.

What has been described here is a very simple tabu search framework, which performs ‘‘book- keeping’’ operations to ensure that the algorithm does not return to recently explored solutions. More sophisticated metaheuristic strategies more explicitly guide the direction of the search itself.

Preassigned Routes and Preassigned Territories

The heuristic route-construction methods described thus far are designed to minimize route cost while satisfying time window and other constraints. Route cost is typically a function of total on-road time and distance. In an approach to routing that seeks only to minimize travel time and distance, one typically follows a reoptimization strategy. That is, one is faced each day by a new problem, deﬁned by the set of customers who actually require service that day; and one solves that problem by applying a heuristic route-construction algorithm. Because there is no concept, in such algorithms, of geo- graphical area or regularity of service, the solution for one day will be independent of the solution for another. While these solutions may be very efﬁcient from the standpoint of total cost and travel time, they may not be satisfactory for some applications. The reason for this shortcoming is that in some applications, there may be additional, hidden costs that the reoptimization strategy fails to take into account.

One such cost involves driver knowledge of the area in which he or she is providing service. A driver who is familiar with the road network and trafﬁc conditions in his service area is likely to be more efﬁcient than a driver for whom the delivery area is relatively new. A second, related cost involves the development of business relationships. For many service providers, an important goal is to achieve regularity and personalization of service by having the same driver visit a particular customer every time that customer requires service.

These considerations suggest that for some applications, it may be desirable to maintain some consistency from one day to the next in assigning customers to drivers. In this case, we need to devise some alternative to the reoptimization strategy.

One way of devising such an alternative is to interpret our problem as a probabilistic vehicle routing problem (PVRP) (Jaillet and Odoni 1988). According to this interpretation, we are given a service region and the set of all potential customers in that region. On a given day, only a subset of the customers will actually need service and the exact customer set for a given day cannot be predicted. However, we are also given a probability distribution, based on historical data, over the set of potential customers. The probability assigned to a potential customer represents the probability that that customer will require service on any given day.

One way of deﬁning an objective function for this problem is provided by the a priori optimization strategy investigated by Jaillet (1988) and Bertsimas et al. (1990). In order to develop the ideas underlying this strategy, it is helpful to focus on the TSP. In the conventional TSP, we are given a complete graph G = (V,E) and wish to ﬁnd a lowest-cost tour that visits every node in V. We obtain the probabilistic TSP (PTSP) by supposing that, on any given day, the traveling salesman may have to visit only some subset S of the nodes in V. The probability that any v in V is present (must be visited) in a given problem instance is given by a probability function p over V. We identify a problem instance with the subset S of nodes that are present in that instance. Thus there are 2n possible instances of the PTSP on G, where n = lVl.

According to the a priori optimization strategy, one ﬁnds a priori a tour through all n nodes of G. For any given instance of the problem, the k ::: n nodes that are actually present are visited in the same order as they appear in the a priori tour; the (n - k) missing nodes are simply skipped.

A natural measure of effectiveness for the a priori strategy is given by the notion of minimum length in the expected value sense. Thus, let T be the a priori tour, and let LT be the length of T. If the problem instance S occurs with probability p(S) and requires covering a total length LT(S) ac- cording to the a priori tour, then it will receive a weight of p(S)LT(S) in the computation of expected length. Therefore, according to this construal of the PTSP, the objective is to ﬁnd an a priori tour T0 through the n nodes of G, which minimizes the quantity

E[LT] = LS�V p(S)LT(S)

We extend this model to the VRP by requiring that an a priori tour be constructed for each driver in such a way that all potential customers are assigned to some driver. Note that a set of a priori tours of this sort does provide the kind of regularity of service described above.

At ﬁrst glance, the task of calculating E[LT] for a given a priori tour T may appear problematic because the summation is over all 2n subsets of V. However, Jaillet derived an efﬁcient closed-form expression for E[LT], which requires only O(n2) time to compute (see discussion in Jaillet 1988).

Of course, being able to calculate E[LT] efﬁciently for a given a priori tour is very different from actually ﬁnding a tour that minimizes E[LT]. Because the PTSP is at least as hard as the TSP, there is little hope of developing exact optimization methods that could solve more than modestly sized instances of the problem. Consequently, one must employ heuristics in order to develop practically viable PTSP algorithms. However, it has proven difﬁcult to develop effective heuristic approaches to the PTSP, at least in part because the class of optimal solutions to the PTSP has properties very different from those associated with the conventional (Euclidean) TSP. For example, one of the fundamental properties of the Euclidean TSP is that an optimal solution cannot intersect itself; this property follows directly from the triangle inequality. In contrast, an optimal solution for the PTSP can intersect itself, even when the triangle inequality is satisﬁed (systematic treatments of the dif- ferences between the TSP and PTSP are presented by Jaillet [1988] and Jaillet and Odoni [1988]). One consequence of the fact that the PTSP has features very different from the TSP is that, in general, we cannot expect heuristic approaches designed speciﬁcally for the TSP to be extended successfully to the PTSP. In general, therefore, entirely new solution approaches are needed. One of the few promising approaches to the PTSP that has been discussed in the literature is based on the idea of ‘‘spaceﬁlling curves’’ (Bartholdi and Platzman 1988). But the probabilistic versions of the TSP and VRP remain very much under the heading of research topics.

The problem becomes even more difﬁcult when we turn to probabilistic versions of the VRPTW. For this problem, presumably, the a priori strategy would involve multiple objectives; in addition to minimizing the expected length of the a priori tour, we would also want to minimize the expected number of missed time windows. But it is difﬁcult even to formulate this problem properly, much less solve it.

For this reason, when time windows are involved, we try in actual applications to capture some subset of the key features of the problem. In this case, instead of trying to construct a priori tours of the kind just described, we simply try to construct a solution in which a large percentage of repeat customers is handled by the same driver and each driver is relatively familiar with most of the territory to which he or she is assigned.

One way of achieving such a solution is to partition the service area into geographical regions and then always assign the same driver to the same region. In operational terms, a solution of this sort is one in which drivers have well-deﬁned territories: a driver travels from the depot to his or her service area, carries out his or her work there, and then returns to the depot. This picture is to be contrasted with the one that emerges from the heuristic insertion framework, which usually results in routes that form a petal structure: in general, it creates routes in the form of intersecting loops, in which stops appear in a roughly uniform way.

To construct a solution in which drivers are assigned to territories in this way, it is appropriate to adopt the cluster-ﬁrst, route-second strategy mentioned earlier. Thus, we proceed by ﬁrst assigning stops to drivers, thereby partitioning the service area. We then construct a sequence for the stops assigned to each driver. This strategy represents a departure from the heuristic insertion framework, according to which clustering and routing proceed in parallel.

One way of implementing a cluster-ﬁrst strategy is as follows. Suppose that, on a given day, we wish to construct k routes. We can proceed by (heuristically) solving a k-median problem (Daskin 1995); we then carry out the initial clustering by assigning each stop to its closest median. Having created the clusters, we then construct a route for each cluster individually by solving the resulting TSPTW. Unfortunately, it is often impossible to construct a feasible route for each cluster. When feasible routes cannot be constructed, we have to shift stops between clusters in such a way as to achieve feasibility while maintaining well-deﬁned territories as much as possible.

If we begin by solving a new k-median problem each day, then we may succeed in producing well-deﬁned territories for drivers; but we are unlikely to achieve consistency from one day to the next in assigning customers to drivers. A natural way of extending this approach to achieve consis- tency is to take historical information into account. Thus, we can solve a weighted k-median problem over the set of all locations that have required service over a speciﬁed number of past days, where the weight of a location is proportional to the number of times it has actually required service. We would then consistently use these medians as the basis for clustering. There may well be days in which the initial clusters thus constructed are signiﬁcantly unbalanced with respect to numbers of customers per driver; in this case, we have to shift stops between clusters, as described above.

Whether the procedure just outlined can be applied successfully in the presence of time windows depends in part on the nature of those time windows. For some applications, time windows are one- sided, and there are only a few different service levels: for example, delivery by 9:00 am for express packages, delivery by 11:00 am for priority packages, and so on. For such applications, it is plausible to suppose that the sort of strategy just described, which emphasizes the spatial aspects of the problem, can be implemented successfully. If, on the other hand, there is a variety of different, overlapping, two-sided time windows, then we are faced with what is really a three-dimensional problem, with time as the third dimension. In such a case, where the temporal aspect of the problem predominates, the prospects for a successful cluster-ﬁrst strategy of the type described here are considerably less promising.

An alternative heuristic strategy is to employ a sweep method for clustering, introduced by Gillet and Miller (1974); see also Fisher and Jaikumar (1981) and Hall et al. (1994). According to this strategy, one begins by dividing the service area into annuli centered at the depot, using some heuristic method for determining the radius of each annulus. For each annulus, one then sorts the set of customers by increasing polar angle and then builds routes sequentially, inserting stops in order into the current route.

As in the k-median method, the prospects for successful application, in the presence of time windows, of what is essentially a spatial method depend on the nature of those time windows. Again as in the k-median method, one would have to take historical data into account in order to achieve assignments of customers to drivers that are reasonably consistent over time.

Implementation Issues

It is evident, on the basis of the discussion in this section, that for vehicle-routing applications one may require a suite of algorithms, each of which best serves a somewhat different objective. Fur- thermore, to make the best use of these algorithms, it is important that the actual user be specially trained for the application.

Accuracy of the input data is very important in this problem (and in optimization problems in general). Because the objective is to minimize cost, the model is very sensitive to data that affect cost calculations. Because trafﬁc conditions change with the time of day, weather conditions, and so on, travel times are generally estimated even when the best data are available. When longitude and latitude values are used as the basis for travel time estimates, a further loss of accuracy results. This indicates that the extra cost of getting provably optimal solutions may not be justiﬁed, and also that effort needs to be made to develop methodologies that are robust with respect to data inaccuracies. One must certainly take into account the possibility of such inaccuracies when one reports the output routes. It is especially important to do so if the intention is to provide precise directions to drivers who are inexperienced in their assigned areas. Obvious inaccuracies may generate distrust for the model by the users.

The pickup-and-delivery problem discussed in this section is static in the sense that all demand is known before any service begins. But one can also consider real time dispatching problems, in which demand is generated in real time and routing decisions are made after the driver has left the depot. Advances in communications technology make it feasible to implement real-time systems of this sort. They also make feasible the implementation of hybrid systems, in which drivers are given predetermined routes but these routes may be modiﬁed dynamically as new demand arises during the workday. Dynamic problems of this sort will require new algorithmic techniques to supplement those presented in this section.

Search This Blog

Operation Research course