Classification of time windows in vehicle routing problems

Classification of Time Windows in the Vehicle Routing Problem

The work of Bramel and Simchi-Levi (1992) entitled: "Probabilistic Analyses and Practical Algorithms for the Vehicle Routing Problem with Time Windows" reports that the Vehicle Routing Problem with Time Windows (VRPTW) can be stated as follows: "... A set of customers dispersed in a geographical regions has to be served by a fleet of vehicles initially located at a given depot. Each customer has a load that must be picked up, and the customer specifies a period of time, called a time window, in which this pick up must occur. The customers are served by vehicles of limited capacity, that is, total load carried by each vehicle can be no more than the vehicle capacity. The objective of to find a set of routes for the vehicles, where each route begins and ends at the depot, serves a subset of the customers without violating the capacity and time window constraints, while minimizing the total length of the routes." (Bramel and Simchi-Levi, 1992)

The work of Wolsey (2006) entitled: "Lot-Sizing with Production and Delivery Time Windows" reports a study of two lot-sizing problems with time windows." p.471 in each of these cases it is stated by Wolsey (2006) that the demand data "...consists of a set of orders" and those are stated as follows: "...k = 1, . . ., K consisting of a quantity Dk and a time interval [bk, ek] lying within the time horizon [1, n]." (p.471) Wolsey reports that the production time window "is the interval during which the order must be produced, while delivery of the order takes place in a period 'ek'. P.471 Wolsey goes on to state that this problem involves consideration of two variant: (1) in the first each order is distinct (client-specific) whereas in the second; (2) orders are indistinguishable (non-specific). " (Brahimi, Dauzere-Peres, et al. in: Wolsey, 2006) p.471

It is however held by Lee et al. that the deliver time window for an order "is the time interval in which the order must be delivered to the client." (in Wolsey, 2006) p.471 Wolsey states for the problem that is client-specific with production time windows that the approach taken is one in which polynomial time optimization algorithms and also tight mixed integer programming formulations possibly with additional variables are sought and in some cases "this means that we have a description of the convex hull of feasible solutions." (2006) p.472

Multi-item problems are stated to require the use of: (1) column generation; or (2) Lagrangian relaxation approaches in which one requires the optimization algorithms to solve the subproblems, or one can use a direct mixed integer programming approach and provide an initial MIP formulation including the tight formulations of the subproblems. Stated to be the primary results in the work of Wolsey (2006) are those as follows:

(1) the presentation of several mixed integer programming formulations and the relationship between them, including those of Brahimi et al. And Lee et al.

(2) for the production time window problem with constant capacities and Wagner-Whitin costs, WW ? CC ? TWP, we derive a tight O (n2) x O (n2) extended formulation. For the uncapacitated version WW ? U ? TWP, we obtain a tight formulation in the original production, stock and set-up variables with O (n2) constraints.

(3) We show that the restricted production time window problem with non-inclusive time windows, or equivalently the production time window problem with indistinguishable orders, is also equivalent to the standard lot-sizing problem with upper bounds on stocks. For the problem with general cost structure, we derive an O (n2) DP algorithm and an O (n2) x O (n2) tight extended formulation for the uncapacitated problem LS ? U ? TWP (I) by using the restricted time window structure. On the other hand for the constant capacity version LS ?CC ?TWP (I) we derive an O (n3) DP algorithm and an O (n3) x O (n3) tight extended formulation by using the stock upper bound viewpoint. (Wolsey, 2006) p.472

The work of Savelsbergh (1992) entitled: "The Vehicle Routing Problem with Time Windows: Minimizing Route Duration" reports the investigation of the implementation of "edge-exchange improvement methods for the vehicle routing problem with time windows with maximization of route duration as the objective." During the past decade, researchers investigating vehicle routing and scheduling have highlighted use of algorithms for problems in real-life however, the problems have increased in size and constraints of practicality are no longer brushed aside in consideration of the research in this area of study.

Stated as one such constraint is "the specification of time window at customers, i.e., time intervals during which they must be served. These lead to mixed routing and scheduling problems." (Savelsbergh, 1992) p.146 the introduction of time windows at customers is stated to allow "the specification of more realistic objective functions, compared to minimizing distance, such as minimizing waiting time, minimizing completion time, and minimizing route duration." (Savelsbergh, 1992)

Savelsbergh states that edge-exchange improvement methods are that which form both an important as well as a popular class or algorithms in the area of vehicle routing problems. (1992, paraphrased) Previous studies in this area focus on efficient implementations of edge-exchange improvement methods for the vehicle routing problem with time windows...." however, Savelsbergh states that these studies focus completely on the aspect of feasibility and fail to identify "profitable exchanges for realistic objective functions." (1992) p.146

Salvesbergh states that the growing importance of 'side constraints as well as realistic objectives in practical distribution management and the need for fast implementation of algorithms in the context of interactive planning systems justify the current research." (1992) p.153 More realistic objective functions are critically needed. The model presented by Salvesbergh is one in which "the iterative improvement methods were embedded in a two phase approximation algorithm for the VRPTW." (1992) p.153 Salvesbergh states: (1) the relevant iterative improvement methods are applied to all possible combinations of two routes; and (2) the relevant iterative improvement methods are applied to all separate routes. (1992) p.154