Online versus Rolling Horizon Algorithms for Dynamic Service Fleet Operations

Final Report – Summary

Amelia Regan
Assistant Professor, Civil Engineering
Institute of Transportation Studies
Social Science Tower 523
University of California
Irvine, CA 92697
aregan@uci.edu
949-824-1074
949-824-8385

Sandra Irani
Associate Professor, Information and Computer Science
360B Computer Science
University of California
Irvine, CA 92697
ssirani@uci.edu

University of California Transportation Center Year 12  (1999-2000)

Project Description

Online algorithms, in which data is supplied to the algorithm incrementally and in which responses to the data are developed and implemented incrementally are of significant interest to the computer science community.  Recently, there has been an interest in applying these techniques to the analysis of dynamic transportation problems.  The most natural application of this work is to dynamic commercial vehicle operations.   For example, a classical on-line problem, the k-server problem, is that of planning the motion of k mobile servers on the vertices of a graph under a sequence of requests for service.   The problem of assigning urban service or pickup and delivery fleets to a set of dynamically arriving requests for pickups or service is in fact a k-server problem, albeit with additional operational complexity.  This research compares the performance of rolling horizon optimization algorithms (i.e. stochastic programming) to classical online approaches which react to current information but do not make probabilistic assumptions about the future. In addition, we develop algorithms which combine the benefits of these approaches but like the online algorithms, are suitable for real-time implementation.  Where appropriate, we apply the technique of competitive analysis to algorithms for the service fleet operations.

Results

The last several years has witnessed a sharp increase in interest in stochastic and dynamic routing and scheduling problems. Several factors are driving this increase.  The first is an increase in both computational power and the availability of information technologies capable of providing dispatchers with real-time updates on vehicle and customer status and location as well as traffic network conditions. The second is an increase in customer service expectations, driven in part, by the promises made by a few aggressive companies (FedEx, Cox Cable, Home Grocer, to name a few).  

Improving the overall efficiency of the freight transportation systems reduces costs to consumers, improves the ability of companies to meet customer service desires and improves national and regional economic strength. Improving the efficiency of emergency and police dispatching saves lives.  Improving the efficiency of utility repair fleets saves money and improves the quality of life for affected consumer customers and businesses.

Dynamic and stochastic routing and scheduling models are playing an increasingly important role because by definition, decisions must be made before all information needed is known (Powell, Jaillet and Odoni, 1995).  Once made, these decisions must be modified as new information becomes available.  The stochastic nature of these problems takes many forms.  The timing, location and level of demand may vary.  The availability of resources may vary as well due to service times, dock times, and operations in other zones, regions or areas of operation.  The increasing role of on-line freight marketplaces, increases in customer service expectations and the availability of real-time information on traffic network conditions have all led to a dramatic rise in the number of freight and fleet management systems that are operating under explicit dynamic conditions. To a certain degree, algorithm development has lagged behind implementation.  Typical real-time fleet management systems employ static algorithms developed in the 1980’s and early 1990’s.  In order to fully leverage advances in information technologies, algorithms which explicitly consider dynamic and stochastic factors should be examined.  Of particular interest is an examination of conditions under which static or a priori algorithms perform well in a stochastic environment. 

There are two main classes of models.  The first class of models deals with a priori optimization in which a solution is generated for stochastic problems prior to the receipt of information regarding the realization of its random elements.  The general approach is to generate an a priori solution that has the least cost in the expected sense.  The second set of applications involves making decisions and observing outcomes on a continuous, rolling horizon basis.

This research examines both approaches for several key problems.  Its focus is more theoretical than applied though theoretical analyses of this sort do lead to practical application.  Theoretical analysis of algorithms forms the basis for later development of practical implementable algorithms and heuristics.  The main problems examined in this research are the probabilistic traveling salesman problem (PTSP, Jaillet, 1988) and the dynamic traveling salesman problem (DTSP, Psaraftis, 1988) which arise in repair fleet operations and package pickup and delivery, and the traveling salesman location problem (TSPL Berman et al., 1988) and the dynamic traveling repairman problem (Bertsimas et al.1996, Powell et al., 1995) which arises in the problems just mentioned and also in emergency vehicle and police operations.   These problems are at the very heart of research in dynamic and stochastic logistics systems analysis.

Of particular interest is an examination of the trade-offs associated with the two approaches mentioned when applied to these related problems.  In addition, the goal of this research is to develop and share new insights into which factors in stochastic and dynamic problems best inform the decision about which methods should be used to solve them.

Research Approach

Our research began with an examination of the probabilistic traveling salesman problem and the related traveling salesman location problems. Both of these problems model static or a priori versions of dynamic systems.  The next phase of our research has focused on the dynamic traveling salesman problem and the dynamic traveling repairman problem represents true dynamic stochastic problems.  For the dynamic problems, we are concerned with when to visit each node, how long to remain during each visit, and which node(s) to use as a depot if possible when no demands have materialized. To make decisions in these problems we have to strike a balance between the present (known demands) and the future (uncertain demands).  All the decisions are made on-line.  The next step in our research is to analyze this problem using the techniques and ideas developed for the computer science field of on-line algorithms (Irani and Karlin, 1997). In an online problem, data is supplied to the algorithm incrementally and the online algorithm must also produce the output incrementally. Dynamic fleet and freight management problems share many of the characteristics of commonly studied online problems in computer science.

The PTSP problem is a very important problem.  It represents an instance of a strategic planning model in which stochastic factors are considered explicitly. These types of problems are of central importance in many logistics and transportation planning applications where heuristics, which perform well over a wide range of demand realizations, are needed and where re-optimization may be infeasible either for computational or operational reasons. A second motivation is the examination of robustness of optimal solutions to deterministic problems when the instances upon which these problems have been solved are modified (Jaillet 1993).

We combine stochastic optimization, queuing theory analysis and static optimization to develop and analyze algorithms for the PTSP, DTSP and DTRP problems and to estimate the performance of systems under any specific strategy.  A typical performance measure is the wait time for service in these systems under varying assumptions about demand arrival patterns.  The goal of our analysis is to provide bounds for this performance measure.  Another goal is to use competitive analysis to provide a bound on the performance of on-line strategy when compared to the optimal on-line strategy (which is usually not known).  We provide the lower bound and upper bound on the average waiting time (DTSP and DTRP), average distance traveled per demand served (DTRP). For the PTSP, we develop a mathematical reduction by comparing the expected length of an a prior tour to the optimal a priori tour though we do not know what the best a priori tour is. Such a reduction is a typical way to approach analysis of a NP-hard problem. The next step in our research is to test the efficiency of the heuristic algorithms for which we have developed bounds in a simulation framework and to extend single vehicle results to systems involving fleets of vehicles.

In this project report we present our primary findings.  Detailed results are found in the publications listed at the end of this report, which are also available as UCI ITS working papers.

Before presenting the findings we summarize them here.  For the probabilistic traveling salesman problem we develop a quasi-polynomial c-approximation algorithm and also develop a set of heuristics and evaluate these in a simulation framework.  For the dynamic traveling salesman problem we identify an algorithm that is asymptotically optimal for a special case, and demonstrate empirically that it has good performance on the general problem.  For the dynamic traveling repair problem, we prove the asymptotic optimality of a specific algorithm.

The Probabilistic Traveling Salesman Problem

The probabilistic traveling salesman problem is a fundamental stochastic network problem in which in each problem instance only a subset of the nodes requires a visit.  There are n potential customers located in a given area.  Each customer has an associated probability of requiring a visit (referred to as the coverage probability). Let S be the set of all the nodes.  Let s be a subset of S, in an individual problem instance, which specifies the nodes that require a visit. For all nodes, the likelihood of requiring service is independent.  The probability associated with each set of nodes s is p(s)= . Assume we have an a priori tour , let  be the length of the tour in which we visit all the nodes in s in the order given by the a priori tour, simply skipping the rest. We let  represent the expected length of the prior tour . . The problem of finding the a priori tour with the least expected length was defined by Jaillet as the Probabilistic Traveling Salesman Problem (1988). The problem itself is NP-hard. Laporte, Louveaux and Mercure (1994) developed an exact stochastic programming based algorithm for this problem.

Using the same notation as Jaillet, we let represent the expected length of the optimal a prior tour, i.e.      and use  to represent the expected length of the solution provided by heuristic algorithm H and  to represent the expected length of the TSP generated using a re-optimization technique. , Where is the length of the TSP tour over the nodes in s.  For a given heuristic algorithm H, if there exists a constant c such that for any set S, , we call the heuristic algorithm H a c-approximation algorithm. 

Bertsimas and Grigni (1989) have shown that = O(logn). The result, O(logn) comes from the spacefilling algorithm. The existence of a c-approximation heuristic algorithm for the Euclidean PTSP remains an open question.

We use partition idea to provide a heuristic algorithm. We use a “clustering” algorithm to do the partition.  We use stochastic analysis to prove the following theorem.

Theorem 1. If we have a c₁ guarantee algorithm for the k-capacitated median problem, from reduction 1, we have a c₂-approximation algorithm for PTSP.

Dynamic Traveling Salesman Problem

The dynamic traveling salesman problem concerns the development of a routing policy for a single mobile server providing service to customers whose positions are known.  Service requests are generated according to a Poisson process, which is uniform across customer locations.  We assume that the mean service time is known and its variance is bounded.  Service time is independent of customer location.   At this stage we examine some special cases of this problem.   The special case involves underlying networks for which the TSP solution for the network involves only links of identical length for example, three nodes with equal links from each other.  For this special, we analyze a related queue model, M/G/1 with switch cost and then show that a priori tour generated by the “providing service along traveling along the optimal TSP tour” which is known as “Cyclic Polling” algorithm is almost the best algorithm for this problem when the traffic intensity is very high. We do this by providing a lower bound on the waiting time for service under any algorithm and then showing that under certain, relatively unrestrictive conditions the wait time under cyclic polling is arbitrarily close to the lower bound.  For the general case, we introduce some heuristic algorithms.

Letting represents the number nodes in the network, , the average on-site service time and its variance for each demand served, the parameter for the Poisson process at each node and the fraction of time the server provides on-site service.   For networks in which the optimal TSP tour involves only links of equal length, we assume all the link involved in the optimal TSP tour has length of one and the travel speed is , so  is the switching time between the adjacent nodes, let  be the average waiting time for Cyclic Polling algorithm and let  be the average waiting time for the optimal algorithm.

Theorem 2. .

Corollary 1. For the special graph in which the links in the optimal TSP tour are of identical length, when , or if the ratio of the total switching cost per cycle and the on-site service time for a single customer, , the cyclic polling algorithm is almost the best algorithm. 

For the M/G/1 with switch cost, the average waiting for any algorithm and for the cyclic algorithm satisfying:

Theorem 3. .and = .

In general, the priori tour provides a worst-case ratio very close to 2, relative to the optimal average waiting time.

The Dynamic Traveling Repair Problem

We examine the dynamic traveling repair problem (DTRP) and address a conjecture originally made by Bertsimas and van Ryzin (1993). The problem addressed is the following: 

Service requests (demands) arrive over time according to a Poisson process.  Upon arrival, the service requests are distributed to a bounded region A in the Euclidean plane independently according to a probability density function f(x).  Requests are served by one of m identical mobile servers.  The servers spend some time traveling to the location of the requests and some time providing on-site service.   Servers move at the same constant speed.

As in Bertsimas and van Ryzin (1991) we assume that demands are uniformly distributed over the area A. The conjecture of interest concerns the asymptotic optimality of the following service policy:  The overall area is partitioned into areas of fixed size.  Arrivals are assigned to these areas.  When batches of fixed size form in the partitions, they are deposited into a queue in a first come first serve manner as in a GI/G/m queue.  In every partition, demands are served in order of the optimal TSP tour.

We define  to represent the fraction of time the vehicle spends during on-site service where is the average on-site service time. Letting A represent the service area, m the number of mobile servers, k the number of partitions, l the arrival rate for the area A, v the (constant) travel speed of the vehicles, b the TSP constant, be the average waiting time for the above algorithm, Bertsimas and van Ryzin showed that under heavy traffic conditions (as approaches 1), expression (*) below provides an upper bound on the average waiting time and they conjecture that this policy is optimal.

                                                                                 (*)

We give two assumptions. One concerns the spatial distribution of consecutively served customers and the other is that the average waiting time of any group of 2N consecutively served requests is close to the expected waiting time, where N is the average number of customers in the queue for any specific algorithm. Under these two assumptions, we provide a lower bound on the average waiting time and by comparing our lower bound and the known upper bound and we prove the conjecture by Bertsimas and van Ryzin (1993). Finally, we find that the optimal algorithm should serve almost all the known demands in that area prior to departing for another area when the server enters a service area. The formal results are stated in the following theorems.

Theorem 4: Let d be the average distance traveled per demand served and let N be the average number of demands awaiting service and .  All strategies satisfying the two assumptions will also satisfy the following: .  Where is the TSP constant defined earlier as in (*).

Theorem 5: Under the same conditions as theorem 1, we have .

Theorem 6:  For the DTRP under heavy traffic intensity, if we know the best strategy for the single vehicle case, we can extend this to the m vehicle case easily by partitioning the service area into m partitions and assigning each of the m to serve the demands from one specific partition. Each vehicle simply applies the single vehicle strategy to its service region.

Conclusions

Our research to date seems very promising/ For the PTSP we provide a reduction and a heuristic algorithm; for the DTSP, we examine some special case and characterize the asymptotic optimal algorithm for some special case; for DTRP, by proving the conjecture of Bertsimas and van Ryzin, we charactering the asymptotically optimal algorithm for DTRP; in addition, we have shown that the algorithm which is asymptotically optimal for the single vehicle case can be readily extended to the multiple vehicle case.

Our results demonstrate how powerful the partition algorithm can be.  Karp (1985) has shown that a partitioning algorithm can provide asymptotically optimal results for the TSP problem.  We here show that it also works for the DTRP and PTSP by proving the conjecture of Bertsimas and van Ryzin and introducing a reduction respectively. For the dynamic problem, our result shows that the connection frequently observed between static and dynamic problems exists for the DTRP and DTSP. It demonstrates that if we apply the optimal deterministic static solution properly, we can obtain the asymptotically optimal solution for the dynamic problem.

References

Berman, O., and D. Simchi-Levi  (1988), Finding the optimal a priori tour and location of traveling salesman with non-homogeneous customers. Transportation Science 22(2), pp. 148-154.

Bertsimas, D. and M Grigni (1989). Worst-case examples for the spacefilling curve heuristic for the Euclidean traveling salesman problem, operations Research Letters pp. .241-244.

Bertsimas, D. and D. Simchi-Levi (1996) A new generation of vehicle routing research: Robust algorithms, addressing uncertainty, Operations Research, 44, pp. 286-304.

Bertsimas, D., and G. van Ryzin (1990), A Stochastic and dynamic vehicle routing problem in the Euclidean Plane, Operations Research, 39, pp.601-615.

Bertsimas, D., and G. van Ryzin (1993), Stochastic and dynamic vehicle routing problem in the Euclidean Plane with multiple capacitated vehicles, Operations Research, 41, 60-76.

Irani, S, X. Lu and A.C. Regan (2000), Competitive analysis of algorithms for the Dynamic Traveling Salesman Problem, Proceedings, in preparation for submission to the 2001 meeting of the Symposium on Discrete Algorithms.

Irani, S. and A. Karlin (1997) Online computation, in Approximation Algorithms for NP-hard problems, edited by Dorit Hochbaum, PWS publishing company, pp. 521-564.

Jaillet, P.  (1988), A priori solution of a traveling salesman problem in which a random subset of the customers are visited. Operations Research, 36(6), pp. 929-936.

Jaillet, P.  (1993), Analysis of probabilistic combinatorial optimization problems in Euclidean spaces. Mathematics of Operations Research, pp. 51-70.

Laporte G.  F. Louveaux and H. Mercure. (1994), A priori optimization of the probabilistic traveling salesman problem. Operations Research, 42(3), pp. 543-549.

Powell, W.B., P. Jaillet and A. Odoni (1995), Stochastic and Dynamic Networks and Routing, In Ball, M.O., T.L. Magnanti, C.L. Monma and G.L. Nemhauser eds. Handbooks in Operations Research and Management Science, Vol. 8., Network Routing, Elsevier, Amsterdam, pp. 141-296.

Psaraftis, H. (1988), Dynamic Vehicle Routing Problems, In Vehicle Routing: Methods and Studies, Golden, B.L. and A.A. Assad (eds.). North-Holland, Amsterdam, pp. 223-248.

Acknowledgements

In addition to the funding received from the UCTC, this research was partially supported by the US National Science Foundation (NSF) under Grants No. CMS-9875675 and No. CCR-9625844. The authors gratefully acknowledge this generous support.  Any opinions, findings and conclusions or recommendations expressed in this report are those of the authors and do not necessarily reflect the views of the UCTC or the NSF. 

Papers Prepared as Part of this Project

Lu, X., A.C. Regan and S. Irani (2002), An Asymptotically Optimal Algorithm for the Dynamic Traveling Salesman Problem, Transportation Science, under review.

Lu, X., S., S Irani, and  A.C. Regan  (2001a),  An Algorithm for the  Probabilistic Traveling Salesman Problem, Math of OR, under review. 

Lu, X., S. Irani and A.C. Regan (2001b), The Dynamic Traveling Repair Problem: An examination of alternative heuristics, Networks, under review.

Lu, X., A.C. Regan and S. Irani (2002), The M/M/1 Queue with Switching Costs: An examination of alternative heuristics, Queueing Systems, under review.

Lu, X, A.C. Regan and S. Irani (2002), Dynamic Traveling Repair Problem: Examination of an Asymptotically Optimal Algorithm, proceedings of the 81st meeting of the Transportation Research Board.

Regan, A.C., J. Herrmann, and X. Lu (2002), The Relative Performance of Heuristics for the Dynamic Traveling Salesman Problem, proceedings of the 81st meeting of the Transportation Research Board.

Irani,S, X. Lu and A.C. Regan (2002), Competitive Analysis of Algorithms for the Dynamic Traveling Salesman Problem,  proceedings of the 2002 meeting of the Symposium on Discrete Algorithms, San Francisco, January.

Lu, X. A.C. Regan and S. Irani (2001), Dynamic and Stochastic Fleet and Freight Management: Algorithm Development and Performance Analysis, Proceedings of the 2001 TRISTAN Conference, San Pablo, June. 

Presentations

Dynamic and Stochastic Routing and Scheduling: Recent Developments and On-going Research, invited presentation, Northwestern University, February, 2002.

Dynamic and Stochastic Routing and Scheduling: Recent Developments and On-going Research, invited presentation, University of Southern California, February, 2002.

An Asymptotically Optimal Algorithm for the Dynamic Traveling Repair Problem, presented at the 81st meeting of the Transportation Research Board, January, 2002

The Relative Performance of Heuristics for the Dynamic Traveling Salesman Problem presented at the 81st meeting of the Transportation Research Board, January, 2002

Dynamic and Stochastic Network Optimization: Recent Developments and On-going Research, Presented at the University of Texas, September, 2001

Dynamic and Stochastic Fleet Management, presented at the 4th international TRISTAN meeting, Sao Miguel, Portugal, June, 2001.

Assignment models for local truckload trucking problems with stochastic service times and time window constraints, presented at the 80th meeting of the Transportation Research Board, January, 2001.

An Approximation Algorithm for Real-Time Application to Time-Constrained Vehicle Routing &

Scheduling, INFORMS, Salt Lake City, May, 2000.

An Integer Programming Formulation of the Probabilistic TSP in which All Nodes have Equal Probability of Coverage, INFORMS, Salt Lake City, May, 2000.