|
Article Excerpt
1. Introduction
During the observation of the operations of a number of carrier companies, we realized that many unexpected delays occurred during the execution phase of their vehicle routing schedules. Most of these delays are caused by customers' distribution centers not being ready to receive their goods. However, delays can occur at the carrier's depot when the loading of the delivery trucks is not completed at the scheduled starting time. When confronted with unanticipated delays, the trucks are forced to wait until the customer is ready. This is mainly because the trucks are filled in a particular order that reflects the delivery schedule and hence altering a truck's schedule will imply going back to the depot and/or rearranging the filling order which is costly from an operational standpoint. Consequently, the carrier companies did not want to update their schedules online in compliance with these delays but would rather have a schedule that is better protected against this specific type of time delay.
The above described situation is translated into a specific vehicle routing problem (VRP), which takes into account time-dependent information with regards to travel times. In essence, this means that the travel time between two consecutive customers not only depends on the distance, but also on the starting time. In this time-dependent scheduling setting, unanticipated delays at a customer will influence the starting time of going to subsequent customers and thus on the expected travel time between these customers. Consequently, assessing the impact of these delays is less straightforward than in a time-independent environment (with constant speeds or travel times).
This paper focuses on Time-Dependent Vehicle Routing Problems (TDVRPs). We model traffic by discrete speed zones, where speeds are derived from real-life data and translated into travel time functions that satisfy the First-In First-Out (FIFO) principle (see also Ichoua et al. (2003)). In addition to this, we build a TDVRP model that optimizes the routing costs subject to unanticipated delays which are modeled as perturbations. We refer to this model as the perturbed TDVRP (P-TDVRP). We explore the existence of routing schedules that perform well and identify the structural properties of these schedules which minimize the resulting weighted cumulative delay. Bertsimas and Simchi-Levi (1996) argue that an analytical analysis of the VRP brings new insights into the algorithmic structure and it makes performance analysis of classical algorithms possible. Therefore, we pay specific attention to the analysis of the properties of the generated routes.
The main contributions of this paper are the following.
1. This paper proposes a P-TDVRP approach for dealing with unexpected delays at the various nodes in a TDVRP setting. An optimization procedure is proposed to trace solutions that perform well under perturbations. We show that these solutions in many cases differ substantially from the ones obtained by the TDVRP (i.e., not taking into account these delays). The proposed optimization technique is, to our knowledge, the first application of the methodology proposed by Tsutsui and Ghosh (1997) to a discrete problem coupled with a Tabu Search heuristic.
2. We identify situations capable of absorbing delays, i.e., where inserting a delay will lead to an increase in travel time that is less than or equal to the expected delay length itself. This is generally observed when there is a speed increase, since a delay at a customer might imply starting at a zone with a higher speed. We evaluate the cost-benefit trade-off when using P-TDVRP routing schedules. We weigh the costs and gains of the P-TDVRP routing schedules compared to the TDVRP ones. In the majority of the tested cases, the results show higher gains than costs.
3. The specific characteristics and behavior of the P-TDVRP routing schedules arc identified. We observe and statistically show that the P-TDVRP routing schedules have higher absorption potential, and are comprised of less disperse routes, i.e., more evenly lengthened tours and more links are likely to be in the vicinity of absorption zones. These properties are formulated into hypotheses that are evaluated against the benchmark of the obtained TDVRP routing schedules. The hypotheses are statistically confirmed, with variable degrees depending mostly on the size of the delay: larger perturbations lead to more substantial differences in the solutions' structure.
This paper is organized as follows. In Section 2, we present a literature survey, focusing on the TDVRP. In Section 3, we present our TDVRP model, and in Section 4, we define the PTDVRP model. In Section 5, we present an analysis of solution structures that are likely to perform better under perturbations. Our chosen experimental setting is presented in Section 6. In Section 7 we formulate hypotheses, with respect to the solution structure, and show the results. Finally in Section 8, we highlight the main findings and discuss directions for future research.
2. Literature review
A considerable amount of literature exists on VRPs. For a comprehensive overview, the reader is referred to Laporte (1992, 2007). The vast majority of research focuses on a constant-speed environment, i.e., where speeds remain constant throughout the day. Realizing that speeds and their associated travel times depend on the time of day, more and more research is dealing with VRPs in a time-dependent setting (the TDVRP). This literature review will focus on these time-dependent environments, i.e., where travel limes change as a result of traffic congestion.
In the context of time-dependent vehicle routing, we mention the work of Bertsimas and Van Ryzin (1991, 1993a, 1993b), Hill and Benton (1992) and Malandraki and Dial (1996). Modeling time-dependent travel times in routing, has been mostly done by partitioning the planning horizon into a number of zones, where a different speed is associated with each of these time zones. Malandraki and Daskin (1992) argued that while one component of fluctuation in travel time is due to accidents, another is the temporal variation that results from hourly, daily, weekly or seasonal cycles in the average traffic volumes, they proposed a mixed-integer programming approach. In Malandraki and Dial (1996) a dynamic programming approach was presented to solve the time-dependent Traveling Salesman Problem (TSP). Both these papers modeled the variability in travel time by discrete step functions, meaning that different travel times were associated with different time zones. The limitation of using such functions was highlighted by Fleischmann et al. (2004) in that it leads to the undesired effect of passing. That is, a later start time might lead to an earlier arrival time, where speed increases occur. Constructing models that comply with the FIFO principle, meaning that they do not permit passing, was further emphasized by Ichoua et al. (2003) and Van Woensel et al. (2008) as fundamental in modeling time-dependent travel times in VRPs. In this paper we model time-dependent travel times in a manner that adheres to the FIFO assumption. Furthermore, we use functions similar to those used by Ichoua et al. (2003) and couple them with disruptions in our perturbed setting.
The VRP with stochastic travel times was introduced by Laporte et al. (1992). Gendreau et al. (1996a) addressed the fact that stochasticity may arise in a number of VRP parameters. Consequently, they deal with variability by considering corrective actions, based on the realization of stochastic variables in the setting. This was done by first constructing a planned a priori schedule, and in a later stage amending it based on the realization. Brown et al. (1987) and Shen and Potvin (1995) used a rough approximation of travel time by manually reconstructing the routes taking into account congestion. Kenyon and Morton (2003) approached the VRP with stochastic travel and services times by minimizing the expected route completion time coupled with maximizing the probability that the route is completed before a given threshold. Haghani and Jung (2005) solved a time-dependent VRP where the solution was adjusted at certain times in the planing horizon, and changes were made to accommodate for travel time variability as well as incoming customer demand.
In this paper, we choose to model the travel time by discretizing the day into a number of periods (e.g., morning, midday and afternoon) with a distinct speed associated with each zone. Ichoua et al. (2003) modeled the VRP with time dependency by depicting three time epochs, where the speed differences due to congestion were modeled by using correction factors on the weights of the links. The authors did not mention the source of the data used for the various speeds. Fleischmann et al. (2004) presented a general framework for integrating time-dependent travel times in a number of VRP routing algorithms. Moreover, they survey traffic information systems whose collected data could help in the modeling of time-dependent travel in a more realistic manner. Based on actual traffic data, queueing models were developed by Van Woensel (2003) to model congestion, where the queue parameters were set to model weather conditions and different traffic flows. The analysis yielded average speeds for different time zones (sec also Van Woensel and Vandaele (2006)). These models were later used in Van Woensel et al (2008) to handle TDVRPs, that were solved by Tabu Search. Jung and Haghani (2001) proposed a genetic algorithm to solve the TDVRP.
Over the past years optimizing under uncertainty has attracted considerable attention. This is driven by the realization that in a modeling process, parameters are assessed and are inserted in the given constraints. However, in many cases a great deal of uncertainty lies in their assessments. In principle this means that, although sufficiently good solutions are found for a specific parameter set, their applicability is limited, because they do not take into account parameter uncertainty. Robust optimization as presented by Ben-Tal and Nemirovski (1998, 1999), is essentially defined over a convex space. Sungur et al. (2008) applied this framework to a VRP with uncertain demand on a set of fixed customers. While this area has dramatically evolved in recent years, it would not fit our problem since disruptions are not part of the travel time distribution. They are caused by exogenous factors, namely customer delays. Moreover, their impact on the costs is not straightforward. Montemanni et al. (2007) addressed uncertainty in travel time in a TSP by applying a robust deviation criterion.
Sorenson (2004) defined robustness as the insensitivity of a solution with respect to changes in the environment in which this solution is implemented. He further noted that although there are a number of powerful tools to obtain robust solutions, they are very hard to implement using local search techniques such as Tabu Search. Based on the work of Tsutsui and Ghosh (1997), he proposed an approach that incorporates perturbations on given solutions which are then evaluated through the objective function. This approach was presented in the context of robust continuous optimization using local search. We choose to adapt this approach to our discrete TDVRP setting (due to its simplicity, relevance and adaptability to Tabu Search). We show that significant gains can be obtained by using solutions produced under perturbations.
3. TDVRPs
Formally, the VRP can be represented by a complete directed graph G = (V, A) where V = {0, 1, ..., n} is a set of vertices and A = {(i, j) : i j [member of] V} is the set of directed links. The vertex denotes the depot; the other vertices of V represent customers and the number of available vehicles is N. For each customer, a non-negative demand [d.sub.i] is given where [d.sub.0] = 0. The non-negative weights T[T.sub.ijt], associated with each arc (i, j) represent the travel time between i and j starting at time t.
The objective is to find for the given number of vehicles N the minimum costs where the following conditions hold: (i) every customer is visited exactly once by exactly one vehicle; (ii) all vehicle routes start and end at the single depot; and (iii) every route has a total demand not exceeding the vehicle capacity Q.
We define a solution as a set S with s routes {[R.sub.1], [R.sub.2], ..., [R.sub.s]} where s [less than or equal to] N, [R.sub.r] = (0, ..., i, ..., 0), i.e., each route r begins and ends at the depot. We write i, [member of] [R.sub.r] if the vertex i [greater than or equal to] 1 is part of the route [R.sub.r], where each vertex belongs to exactly one route....
|
