Localized genetic algorithm for vehicle routing problem with time windows

Abstract

This paper introduces the Localized Optimization Framework (LOF). This framework is an iterative procedure between two phases, Optimization and De-optimization. Optimization is done on the problem parts rather than the problem as a whole, while de-optimization is done on the whole problem. To test our hypothesis, we have chosen a genetic algorithm as an optimization methodology and Vehicle Routing Problem with Time Windows (VRPTW) as a domain space. We call this new scheme the Localized Genetic Algorithm (LGA). We demonstrate that the LGA is, on average, able to produce better solutions than most of the other heuristics on small scale problems of VRPTW. Furthermore the LGA has attained several new best solutions on popular datasets.

Introduction

In this paper, we present our Localized Optimization Framework (LOF). This framework consists of a problem decomposition strategy in which a problem is decomposed into sub-problems and optimization is done on those sub-problems independent of each other. This framework also consists of a de-optimization phase in which a solution is de-optimized under controlled conditions. To verify its effectiveness, we present an example domain and methodology. We have chosen GA as an optimization method and have adapted it to fit within our framework, forming the Localized GA. We have chosen the Vehicle Routing Problem with Time Windows as a problem domain, as it is a fairly complex combinatorial optimization problem. This builds on earlier work, as the localized GA has already been applied to its predecessor problem, the Capacitated Vehicle Routing Problem (CVRP) [1], [2], which is a simpler problem in comparison to VRPTW. The huge difference between the level of constraints in CVRP and VRPTW caused many procedural changes in our scheme, these will also be a subject of discussion in this paper. This section is divided into 2 sub-sections. The first sub-section gives background about VRPTW, genetic algorithm and discusses related literature and motivation, while the second sub-section presents the general idea of LOF.

VRPTW is one of the popular routing problems present in the literature. The simplest routing problem is the travelling salesman problem (TSP) [3], in which a travelling salesman has to visit a number of cities before returning to its original city to distribute goods. In this problem, it is assumed that the travelling salesman has unlimited capacity to carry goods, therefore one travelling salesman can visit all of the cities in a single tour. If we put limits to the carrying capacity, then this problem turns into the Capacitated Vehicle Routing Problem (CVRP) [4]. In CVRP, vehicles of limited capacity are considered, therefore multiple vehicles and/or multiple tours are required to satisfy the demand of customers. However in CVRP we assume that each vehicle can travel an unlimited distance in a single tour. If we put limits to the distance, then it becomes distance constrained VRP, DVRP [5]. Therefore in DVRP we deal with two constraints, i.e. a limit on the vehicle capacity to carry goods and a limit on the distance it can travel in a single tour. However, in DVRP we do not consider any time limits on the demand delivery for any customer. If we consider such limits, then this problem turns into VRPTW [6]. In VRPTW each customer has a time bound within which its demand is to be delivered. Therefore VRPTW can be defined as a problem of finding a minimum cost route for a number of homogeneous vehicles stationed at a depot, which have the task of delivering goods to a number of customers, such that:

• the route of each vehicle must start and end at a depot

• each customer must be serviced once by only one vehicle

• the demand of all customers must be delivered

• the route of no vehicle should contain a customer demand sum greater than the vehicle capacity

• no vehicle route distance should exceed the route limit

• each vehicle must arrive at the customer delivery sites within the time horizons associated with them, it may arrive earlier, but then must wait

The definition of the lowest cost route is not agreed upon as yet for this problem [7]. This is so, because the great majority of heuristic methods have chosen reducing the number of vehicles as their primary objective [8], while the great majority of exact methods have chosen reducing the total distance as their primary objective [9]. Also, in some papers [10], [11], VRPTW is taken as a multi-objective problem. Hence we can base our heuristic on any one of these objectives. In practice, it differs, depending upon each situation. If we have a vehicle fleet with capacity not much greater than the demand, then reducing the number of vehicles may be taken as the primary objective, but if we have orders requiring goods in much lesser quantity than the capacity of the available fleet of vehicles, then in such a situation reducing the overall distance can be made the primary and only objective. In this paper, we have made reducing the overall distance as the sole objective.

VRPTW was first introduced by Solomon [12] and since then it has remained a test domain for various meta-heuristics, mainly because of its relevance to the real world, its difficult fitness landscape and its potential to deliver in economic terms [5].

The Genetic Algorithm is a popular meta-heuristic, which mimics the natural biological evolution of species [13], in order to solve combinatorial optimization problems. It was first introduced by Holland [14]. A genetic algorithm deals with a population of solutions subjected to reproductive processes. Those processes occur under the direct influence of each individual's relative fitness. The fitness of each individual of a population is defined by the quality of its solution with respect to the objective under consideration. Such a setup contributes to increasing the average fitness of a population in each subsequent generation. After a certain number of generations, we are likely to get a solution of the quality we need. For further insight into GAs, the reader is referred to [15]. The applicability of genetic algorithms is spread over a wide variety of fields, such as single to multi-objective optimization [16], [17], Engineering [18], bin packing [19], multidimensional numerical optimization [20], Pattern Recognition [21] and routing [22], [23]. However, genetic algorithms have obtained very limited success in the area of Vehicle Routing, due to their high computational cost. It should be noted, that this problem has been tackled by the evolutionary computation community for many years, and hence consequently there is a large body of literature present about this. However, this literature is about versions of this problem which have the primary objective of minimizing the number of vehicles. Therefore we do not intend to discuss that literature, as to our understanding that constitutes an entirely different problem. We discuss some of the GA based approaches, which are applied to this problem, with a substantive emphasis on the objective of minimizing the distance, and to which we have compared our algorithm, along with some other methods.

A route directed hybrid GA approach was proposed by Berger et al. [24]. That algorithm consisted of two populations. The first population aimed at minimizing the total distance, while the second population was aimed at minimizing temporal constraint violations. There was occasional interaction between the two populations. A roulette wheel selection scheme was used to select the individuals for the reproductive processes of the next generation. Heuristic genetic operators were used, consisting of some key features borrowed from the insertion heuristic [12], namely large neighborhood search [25] and the route neighborhood based two-stage meta-heuristic (RNETS) [26]. Recombination operators were based upon the principle of vicinity of routes. The vicinity of routes was decided by the nearness of route centroids. In this operator, the genetic makeup of routes in the vicinity of each other was exchanged. Mutations were based upon the removal and reinsertion of a number of customers from the routes. The reinsertion consisted of customer visits under a variable ordering scheme through a branch and bound search process. This algorithm produced the best results in terms of number of vehicles.

The multi-objective genetic algorithm for VRPTW was presented by Ombuki et al. [10]. A Pareto ranking procedure was proposed to rank the individuals as per the established criteria. A weighted sum objective function was also devised as an alternate approach. The tournament strategy with elite retaining model was used for the selection of individuals for their participation in the genetic operations meant for development of next generation. The novelty of this approach was to provide a variety of solutions, giving flexibility to the software user to select one of them as per her requirements.

Another multi-objective genetic algorithm for VRPTW was proposed by Tan et al. [11]. The main features of this algorithm included a variable length chromosome, i.e. chromosome consisting of separate route lists, which was first introduced by Pereira et al. [27] with the name “Genetic Vehicle Representation” (GVR). Another main feature was specialized genetic operators, including Route-exchange crossover, which exchanges routes between the chromosomes. This crossover is a version of the previously introduced crossover by Tavares et al. [28], in that crossover, one parent was a donor and another was a receiver of the route. Another specialized genetic operator introduced was Multimode mutation. This mutation actually comprises 3 different mutations with a probability of occurrence assigned to them. These mutations were Partial-Swap [29], Split-Route and Merge-Routes. For split route and merge route mutations, the author has referred to the paper about VLSI design [30]. This algorithm has managed to offer competitive solutions on popular datasets.

A genetic and set partitioning two phase approach was proposed by Alvarenga et al. [7]. In this approach an initial population was generated using the proposed stochastic PFIH for a number of GAs using an island model of evolution [31] to produce a number of local minima. The solutions were then put into a set partitioning model to improve the quality of solution. The approach was called the column generation approach, because the reduced problem, called column, was generated from a global problem, and was then reinserted into the global problem after some treatment. This scheme has produced the best results so far in terms of distance minimization objective.

Cooperative parallel meta-heuristic with a solution warehouse strategy was introduced by Bouthilier and Crainic [32]. The solution warehouse consists of several solutions produced through various meta-heuristics, mainly GA and Tabu Search. The solutions in warehouse then cooperate and exchange information for post optimization and further improvements. Two different tabu search algorithms, i.e. tabu route [33] and unified tabu search [34], [35] and two evolutionary algorithms, one with order crossover, and another with edge recombination crossover, were used to generate solutions to be collected in the warehouse. This method has produced good results on the vehicle number minimization objective, but not the best results.

A hybrid of simulated annealing, tabu search and genetic algorithms was presented by Thangiah [36]. In this paper the λ-interchange mechanism previously used in Osman and Christofied [37], [38] for CVRP was modified for VRPTW, this is a mechanism for generating a neighborhood. A Genetic algorithm and PFIH were used to generate initial solution, while simulated annealing and tabu search were used to search an λ-interchange neighborhood for further optimization. This hybrid mechanism was able to produce several new best solutions at that time.

Further reading on these approaches can be obtained from [39], [40], [41], [42]. The problem with all these approaches is their high computational cost. The main reason behind the high computational cost is that GA, as so far used, has followed a holistic approach to the problem, while other heuristic methods break down the problem into parts and work with each part separately. Examples for such an approach can be seen in [43], [44], [45], [46]. However all these methods are inherently localized. They do not need any specific decomposition strategy for localized optimization. On the contrary, GA is an inherently globalized method. Hence this necessitates the development of some localized optimization mechanism for the localized application of GA. Keeping this in mind, we have proposed the generalized Localized Optimization Framework (LOF), which provides a mechanism for localized optimization. We have used a genetic algorithm in this framework and called it Localized GA. We have chosen GA to show that it can also be used with problem decomposition strategies. We have produced competitive results on popular datasets of VRPTW through this scheme. We will further discuss this in the next sub-section.

Problem decomposition schemes have been in place for quite some time. The most popular method using this scheme is called Dynamic Programming, introduced by the mathematician Richard Bellman [47]. This scheme works in the following manner.

• Break the problem into smaller sub-problems.

• Solve the sub-problems.

• Construct the global problem from the sub-problems.

• Repeat the above 3 steps iteratively.

The same strategy was used by Taillard in the Tabu Search for the VRP in 1993 [48]. He partitioned a large problem into independent sub-problems, optimized the sub-problems, then joined them together to construct the global solution, only to partition it again, into different sets of sub-problems. However, different partition methods were proposed for different types of datasets. The same procedure was extended in [49] with a modified partition method which ensured different partitions in each iteration. We have further generalized this strategy into the Localized Optimization Framework (LOF) for all types of datasets [50], [51]. LOF proposes an automated problem decomposition strategy, which automatically adopts to various dataset types. The LOF consists of the following steps.

• Break the problem into smaller isolated sub-problems.

• Construct the larger overlapping sub-problems from isolated sub-problems.

• Solve the overlapping sub-problems.

• Break overlapping sub-problems into isolated sub-problems.

• Repeat steps 2–4 iteratively until we stop getting cost benefits.

• Construct the global problem from the sub-problems.

• De-optimize the global problem within certain bound.

• Repeat the above 7 steps iteratively until the termination condition occurs.

Step 3 of LOF consists of an optimization procedure. Logically it should not prevent any optimization methodology including Tabu Search [52], Simulated Annealing [53] and Ant Colony System [54], to be used in it. We have used a genetic algorithm in this scheme of LOF and have called it the Localized Genetic Algorithm (LGA). We can see that the scheme of LOF has some additional steps which previous decomposition schemes do not have. Especially those steps are the construction of overlapping sub-problems and the de-optimization of global solutions. These features are very interesting and make LOF a more powerful scheme than other decomposition schemes already in place. Due to these features, LOF becomes a mechanized scheme, which without any use of random parameters, can produce sub-problems with entirely different point sets. The scheme of LOF can be represented through a flowchart, shown in Fig. 1. In Fig. 1, we can see that a solution is decomposed immediately after its generation (step 1), which is then followed by formation of overlapping sub-problems (step 2). The overlapping sub-problems are then optimized (step 3) and separated back into isolated sub-problems (step 4). We continue the process of formation and separation of overlapping sub-problems while we continue to get benefit in terms of the objective function through optimization (step 5). In the case where we stop getting improvement in the solution, then we construct a global problem from the isolated sub-problems (step 6). The whole solution is then de-optimized, which means deteriorating the quality of the solution under controlled conditions (step 7). Here we complete the first iteration of the problem. The solution is again decomposed into isolated sub-problems (step 1) to start the second iteration. The LOF goes through a number of iterations before reaching the termination condition.

It should be noted that this work is an extension of our previous work, where we applied LGA on CVRP [1], [2]. In this paper, we have redefined LGA as a part of our larger framework, called LOF. Furthermore we have brought about considerable modifications into our scheme to suit the structure of the new problem. We will discuss those modifications when we go through the steps of LOF in detail, one by one, from Sections 2 Initial solution generation, problem representation and decomposition, 3 Formation and optimization of overlapping sub-problems, 3.1 Generation of population of solutions, 4 Separation of overlapping sub-problems, 4.1 Representation and evaluation of BMGA, 4.2 Parameter settings of BMGA, 5 De-optimizing the complete solution, 6 Experiments and results. In particular, Section 2 describes step 1 of LOF, which consists of problem decomposition. In addition to this it also discusses problem representation and initial solution generation. Section 3 explains steps 2–3 of LOF, which consists of formation and optimization of overlapping sub-problems. Section 4 defines steps 4–6 of LOF, which constitutes separation of overlapping sub-problems, algorithm flow controls and formation of complete solution. Section 5 states steps 7–8 of LOF, which comprises de-optimization procedure and termination condition. Experiments and results are presented in Section 6. Finally we have made some conclusions about our work, followed by references and appendices.