Competitive Analysis for Dynamic Multiperiod. Uncapacitated Routing Problems Enrico Angelelli and M. Grazia Speranza

We study a dynamic multiperiod routing problem where, at the beginning of each time period, a set of orders arrive that have to be fulfilled either that time period or the next. Thus, in each time period there are customers that have to be served and customers whose service may be postponed. Once it has been decided which customers to serve, an optimal route is constructed and executed. The objective of the problem is to minimize the total distance traveled during the planning horizon. Deciding which customers to serve in a time period is done on the basis of incomplete information, analyzing simultaneously customers in two consecutive periods. No knowledge is available about customers requiring service in future time periods. We introduce simple algorithms, ones which naturally arise in practice, and analyze these algorithms by studying their competitive ratio.

© 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 49(4), 308–317 2007

Keywords: dynamic vehicle routing; dispatch policies; competitive analysis

1.  INTRODUCTION

Dynamic routing problems are concerned with situations in which information about the customers to be visited is not revealed all at once, but rather is revealed dynamically over time. The importance of dynamic routing problems has always been recognized (see [15] for an early discussion on the topic), but they are becoming increasingly important due to the technological advances that are transforming the transportation sector. In the near future, it will be commonplace that planners will know the exact position of every vehicle in their fleet at every moment in time, will have the capability to communicate with each of the vehicles at all times,

Received July 2005; accepted November 2006 Correspondence to: M. W. P. Savelsbergh; e-mail: mwps@isye.gatech.edu DOI 10.1002/net.20180 Published online in Wiley InterScience (www.interscience.wiley. com). © 2007 Wiley Periodicals, Inc. NETWORKS—2007—DOI 10.1002/net

and thus will be able to reroute vehicles, if needed and desirable, when new information about customers to be visited becomes available. Unfortunately, the decision technology to effectively exploit the opportunities provided by these technological advances for dynamic routing is still in its infancy. Relatively little research has been done on dynamic routing problems compared to the huge amount of time and effort invested in analyzing and solving static routing problems.

As mentioned earlier, in dynamic routing problems customer demands are not known in advance but become available incrementally over time. A typical approach is to construct a routing plan based on the known demands and modify this plan when new demands become available (e.g., [7–9,13,14,18]). The performance of dynamic routing algorithms is often analyzed by studying their competitive ratio (e.g., [1,5,10–12]), as introduced in [16], for the analysis of online algorithms. The competitive ratio measures the price that has to be paid for the lack of information. As such it provides insight in the sensitivity of algorithms to the availability of information. In stochastic routing problems, which are related but quite different, the goal is to find, given a set of customers with stochastic demand, an a priori routing plan that minimizes the expected delivery costs. This approach often incorporates a recourse function to correct the routing plan when vehicle capacity constraints are violated (e.g., [6]). Routing environments with both dynamic and stochastic aspects have also been studied (e.g., [2–4,17]).

We study and analyze algorithms for a dynamic multiperiod routing problem motivated by a routing environment we encountered in practice, and that is often found at companies involved in service delivery management. The situation arises due to contracts guaranteeing a certain service level (often referred to as service level agreements or SLAs), measured in terms of the number of days within which the service has to be provided. In our motivating application, the company receives orders each day, but has the flexibility to fulfill the orders within the next two days, i.e., on the day after the order was received or on the day after that. Consequently, eachdaythedistributionplanneratthecompanyhastodecide which orders to fulfill on the basis of partial information. The distribution planner has no knowledge of or insight in the orders that will arrive in the next few days. Obviously, orders that were received two days before and have not yet been served have to be served today. The other orders, however, can be served today but can also be postponed.