Abstract: This study presents a tabu search heuristic for solving Heterogeneous Fleet Vehicle Routing Problems with Time windows and Nonlinearly Penalized Delays (HFVRPTWNLPD) in distribution systems. The HFVRPTWNPD can be justified in practice and includes the well-known Vehicle Routing Problem with time windows (VRPTW) as a special case. For HFVRPTWNPD problems the objective cost function is expressed as the weighted sum of the number vehicles used, the total distance travelled and the nonlinear penalty function of delays. Preliminary computational results on well known benchmark test problems indicate that our heuristic is robust and can handle medium to large problems.
INTRODUCTION
The Vehicle Routing Problem (VRP) studied by Clarke and Wright (1964), Gendreau et al. (1994), Rochat and Taillard (1995), Vogt et al. (2005) and Wassan (2006), has received much attention in recent years due to their wide applicability and economic importance in determining efficient strategies to reduce operational cost in distribution networks. The classical heterogeneous fleet vehicle routing problem (HFVRP) developed by Desrochers and Verhoog (1991), Gendreau et al. (1999), Gheysens et al. (1984), Golden et al. (1984), Ochi et al. (1998), Osman and Salhi (1994), Renaud and Boctor (2002), Salhi and Rand (1993), Taillard (1999) and Wassan and Osman (2002), is an extension of the VRP for determining simultaneously the composition and routing of mix fleet of vehicles. The Vehicle Routing Problem with Time Windows (VRPTW) investigated by Chiang and Russell (1997), Garcia et al. (1994), Taillard et al. (1997), Thangiah et al. (1994) and Tan et al. (2001), is another extension of the VRP obtained by imposing time window constraints on the non central depots (called also customers) and the central one, in addition to the vehicle capacity constraint. It is characterized by a fixed or variable number of vehicles, identical vehicle capacities and the aim is to minimize the total distance travelled by all vehicles. The heterogeneous fleet vehicle routing problem with time windows (HFVRPTW) was shown by Liu and Shen (1999) to be a generalization of the classical vehicle routing problem with time windows (VRPTW). Some HFVRPTW or VRPTW models (soft time window models) allow for early or late window service, but with some form of linear penalty terms. Although most researchers have focused on the hard time window models, soft time windows models have been using linear penalty terms to express the soft nature of the penalty cost incurred. To the best of our knowledge, the Heterogeneous Fleet of Vehicle Routing Problem with Time Windows and Nonlinearly Penalized Delays (HFVRPTWNLPD) has not been tackled in the literature. It can be considered as a generalization of the well known HFVRPTW by introducing different forms of nonlinear penalty for modelling the delays. The importance of HFVRPTWNLPD is two fold: on one hand, its ability to model practical situations such as that encountered in high agglomerations where traffic of some type of vehicles is forbidden beyond certain time periods and the penalty incurred depends nonlinearly of the time violation. On the other hand, using nonlinear penalty functions models in a unified framework the transition between soft and hard time windows. The HFVRPTWNLPD whose typical distribution network is shown in Fig. 1, can be described as the problem of designing least cost routes for a fleet of mixed vehicles, from the central depot to a set of geographically scattered depots. The routes must be designed in such a way that each depot is visited only once by exactly one vehicle with a given time interval. All routes start and end at the central depot and the total demands of all depots on one particular route must not exceed the vehicle capacity. In addition, it is assumed that each vehicle is affected to only one route. The principal objective of the HFVRPTWNLPD is to minimize the number vehicles required, the total traveled distance and the cost incurred from the delays.
| Fig. 1: | Typical distribution network |
Although the classical Heterogeneous Fleet of Vehicle Routing Problem (HFVRP) has been the subject of intensive research since the 80s, most of the algorithms proposed are heuristic in nature because the problem is known to be NP-hard and even harder than the notorious Travelling Salesman Problem. Golden et al. (1984) considered the case of an objective function as a sum of variable costs for all vehicles which are unlimited in number. Salhi and Rand (1993) used modification of the classic Clarke and Wright (1964) saving heuristic to generate good initial solutions. Gheysens et al. (1984) investigated the performance of several techniques for handling the problem of the fleet size and mix vehicle routing problems. Desrochers and Verhoog (1991) proposed a new heuristic for the above problem based on successive route fusions, where the best fusion is selected by solving a weighted matching problem. Osman and Salhi (1994) developed the local search strategies for the vehicle fleet mix problem. Ochi et al. (1998) proposed a parallel evolutionary algorithm for the VRP with heterogeneous fleet. Taillard (1999) suggested a heuristic based on column generation for the heterogeneous fleet vehicle routing problem (HFVRP). Gendreau et al (1999), Wassan and Osman (2002) proposed a tabu search heuristic for heterogeneous fleet vehicle routing problem (HFVRP). Renaud and Boctor (2002) introduced a sweep based algorithm for the fleet size and mix vehicle routing problem.
The present study focuses on HFVRPTWNLPD (Heterogeneous Fleet Vehicle Routing Problem with Time Windows and Nonlinearly Penalized Delays). The study is motivated by both the practical significance of penalizing nonlinearly the delays which may represent a real cost for the fleet designer imposed by city regulations and the theoretical desire of building a framework which unifies soft and hard time windows modelling.
MATERIALS AND METHODS
Problem definition and notation: The HFVRPTWNLPD can be formally defined as follows. Let G (N,A) be graph with N = D ∪ {0, n+1} and A = {(I, j)/ I ε D, j ε D, j ε D, I≠ j} where the node set D = {1, 2,….n} represents the depots set and the nodes 0 and n+1 denote the central depot. The arc set A corresponds to possible connections between the nodes. No arc terminates at node 0 and no arc originates at node n+1. All routes start at 0 and terminate at n+1. Each depot has a demand d, i ε D. At each depot, the start of service must be within a given time interval, called a time window [ai, bi]. We assume that k different types of vehicles are available at the central depot, k ε V, V = {1,.., K}. A vehicle of type k has a carrying capacity Qk and a fixed cost Fk. The number of vehicles of type k available is nk and it is not limited (nk= + ∞) in our case. Tkij and tkij denote the travel cost and travel time of vehicle of type k from depot i to j (i, j ε N), respectively. The travel time tkij includes a service time at depot i. In case of hard time windows, each vehicle of type k must also leave the central depot within the time window [ako, bko] and return empty during the time window [akn+1, bkn+1]. For formulation, studied herein, this requirement was related and imposed an additional cost which depends nonlinearly with the delays weighted by two coefficients α1 and α2. In this type of models, it is generally assumed that a vehicle must wait for service if it arrives too early at a depot. ako, bko are assumed to be equal to zero which means that the starting time is the same for all routes.
This model contains two types of decision variables. The decision variable Xkij (defined for ∀ i, jε N, ∀ k ε V) is equal to 1 if vehicle of type k goes from depot i to depot j, 0 otherwise. The decision variable Ski (defined for ∀ i, jε N, ∀ k ε V) denotes the starting time for vehicle of type k, k ε V, at depot i, i ε D. If vehicle of type k does not service depot i, Ski is meaningless. Assume that Sko = 0, ∀ k ε V and denote the arrival time of vehicle of type k at the central depot by Skn+1.
Given the earlier mentioned notations and assumptions, the HFVRPTWNLPD can be formulated as:
| (1) |
| (2) |
| (3) |
| (4) |
| (5) |
| (6) |
| (7) |
| (8) |
The objective function (1) states that total cost should be minimized. This cost includes a fixed part which represents the vehicles cost, the travel cost and the cost of the delay of serving a depot or returning to the central depot. The constraint set (2) states that each depot must be assigned to exactly one vehicle. The set of constraints (3), (4), (5) model the flow constraints which ensure that each vehicle leaves from the central depot noted by 0, each vehicle departs from the depot visited and finally each vehicle must return to the central depot n+1. The constraint set (6) states that the vehicle capacity should not be exceeded. The nonlinear constraint (7) (which can be easily linearized) states that a vehicle of type k cannot arrive at j before Ski+ tkij when travelling from i to j. Constraint (8) expresses that the variables are Boolean.
TABU SEARCH HEURISTICS
Related work: Tabu Search (TS) is a local search meta-heuristic introduced by Glover (1986). Details about tabu search can also be found in Glover (1989), Glover (1990), Glover and Laguna (1993, 1997) and Glover et al. (2000). Tabu search explores the solution space by moving at each iteration, from solution s to the best solution in a subset neighbourhood N (s). The aspiration criterion happens for example when tabu solution is better than any previously seen solution. Also various techniques are often employed to diversify or to intensify the search process. Osman (1993) developed a standard classical tabu search algorithm that uses insert and swap types of moves in a generalized way to generate the candidates list of solutions. Gascia et al. (1994) described an improvement heuristic based on the mechanisms of trading. Taillard et al. (1997) proposed tabu search heuristic for VRP with soft time windows. Chiang and Russell (1997) developed a reactive tabu search that dynamically varies the forbidden moves list’s size to avoid cycles as well as an overly constrained search path. Gendreau et al. (1994) presented a rather more sophisticated tabu search implementation that considers 1-insert type moves coupled with the GENI (Generalized Insertion procedure) algorithm. Tan et al. (2001) suggested a tabu search algorithm based on λ-interchanges with an accept strategy test. The initial solution is generated with the cheapest insertion heuristics by Thangiah et al. (1994). Rochat and Taillard (1995) proposed a probabilistic diversification and intensification in local search for vehicle routing. Liu and Shen (1999) developed a method for VRPTW with mix fleet. They considered several insertion based savings heuristics. The main idea underlying this method is the generalization of traditional insertion in order to avoid constructing too many short routes. Wassan (2006) proposed a reactive tabu search for solving the VRP with a new escape mechanism, which manipulates different neighbourhood schemes in a very sophisticated way based on balanced intensification and diversification continuously during search process. Hoong et al. (2003) presented a tabu search approach for solving VRPTW and limited number of vehicles. Their is characterized by a holding a list and mechanism to force dense packing with in a route. They also allow time windows to be relaxed by introducing the notion of penalty for lateness. Customer jobs are inserted based on hierarchical objective function that captures multiple objectives. Vogt et al (2005) describe a tabu search algorithm for the single vehicle routing allocation problem. In their model, they assume a single vehicle, together with a set of customers. The problem becomes then of deciding a route for the vehicle (starting and ending at given locations) such that it visits some of the customers. Customers not visited can either be allocated to a customer on the vehicle route, or can be isolated.
Implementation details of the Tabu Search Heuristic for HFVRPTWNLPD: Clearly, any implementation of Tabu search requires initial solution generation and a neighbourhood search procedure. For the HFVRPTWNLPD problem, these are implemented as follows:
| • | Initial solution generation: The initial solution in our case is generated through a hybrid operation of the modified savings method of Clarke and Wright (1964) and that of Golden et al. (1984) heuristic .A subset of twenty four saving solutions using different values of the route is generated for each problem. Each solution is then further refined by a series of the move operators shown in Fig. 2. These move operators are: |
| • | Create: Builds larger routes from pairs of routes. |
| • | Affect: Transfers a depot from one route to another. |
| • | Permute: Exchanges two depots between a pair of routes at a time. |
| • | Delete: Removes empty routes from the system. |
| Fig. 2: | Four move operators |
| Table 1: | Total routing cost using Tabu search for nonlinearly penalized delays for different values of p |
The routes are then harmonized by applying well-known 2-opt and 3-opt procedures.
| • | Neighbourhood search procedure: The study used a neighbourhood heuristic that is based on exchanging depots between a given set of initial vehicle routes as follows: |
The 1-exchange affects a depot from one route to another and permutes two nodes between two given routes.
The 2-exchange affects two consecutive depots from one route to another and permutes four depots between two given routes by taking two consecutive depots from each of the routes.
RESULTS
In order to test the effectiveness of the methods discussed earlier and following Liu and Shen (1999), a subset of the benchmark data associated with 12 sample problems, consisting of 100 depots (customers) (appendix), is used in our experiments. The following table reports the results, in terms of the total routing cost, obtained on the test problems for different values of the parameter p. Results of the state of the art heuristic MROS of Liu and Shen (1999) are presented in the last column (Table 1).
DISCUSSION
The results show that the total cost obtained by our nonlinearly penalized formulation of the VRP with time windows is similar to state of art models for p = -1. This phenomenon can be attributed on one hand to the ability of the model to handle soft time constraints. On the hand to the efficiency of Tabu search heuristics which outperform in general other heuristics.
However for larger values of p, the total cost becomes larger due to the nonlinearity of the penalties which is acceptable in realistic situations and illustrates the utility of our model to handle complex situations.
CONCLUSION
In this study introduced HFVRPTWNLPD a new and a more realistic formulation of VRPTW which capable of modelling real life situations where the delays are nonlinearly penalized. A variant of tabu search meta-heuristic for its solution is implemented and tested on some benchmark data sets. The model is capable of handling a heterogeneous fleet and nonlinear penalty function of delays caused by violating time windows. The study convinced that model is realistic in modern situations where the penalties are not proportional to the delays. From a practical viewpoint, the HFVRPTWNLPD is worth further studying which may be a fruitful future study direction especially, in third world countries whose major cities are overcrowded. In such situations, vehicle routing should be carefully planned to not only minimize the total cost but must also not violate time windows so that traffic becomes acceptable. Another direction of future research is to develop more efficient methods for finding better solutions for the HFVRPTWNLPD. Finally, this study has provided novel and more realistic formulations of Heterogeneous Fleet Vehicle Routing Problem with Time Windows and Nonlinearly Penalized Delays.
Appendix: Problem data
|