Abstract: Vehicle routing problems with time windows (VRPTW for short) is an NP-hard problem and an extension of vehicle routing problems. This study presented a heuristic algorithm (ABC-T) to deal with vehicle routing problems with time windows. The ABC-T algorithm employed the artificial bee colony algorithm (known as ABC) and improved the global search capacity with tournament selection strategy. In this algorithm, the employed bees generated the new solutions by the neighborhood search; then, based on the tournament selection strategy, the food source selection probability was settled. Finally, the new solution was generated by the onlooker bees. The tournament selection strategy was used here to enhance the global search capacity of the ABC. Compared with the state-of-the-art algorithms available in the literature, the effectiveness of this approach was showed on the Solomon’s R102 problem.
INTRODUCTION
The Vehicle Routing Problem (VRP) is a classical NP-hard problem in scheduling which is first proposed by Dantzig and Ramser (1959). The problem is widely applicable in modern logistics, such as the post deliver problem, power scheduling problem and production scheduling. The objective here is to find the determination of the optimal set of routes to be performed by a series of vehicles to serve a given set of customers (Solomon, 1987). Previous studies (Sharma et al., 2006; Ibrahim, 2007; Ghoseiri and Ghannadpour, 2009; Chang and Huang, 2011) have proposed several meta-heuristics which have been successfully applied to solve VRP problems with better robustness and higher calculating speed.
Due to the enormous complexity of the constraints in reality, the classical method for the VRP often turns out to be unsatisfactory. As an extension of the VRP, the VRP with Time Windows (VRPTW for short) (Solomon, 1987) which is always considered in practical problems. The VRPTW is a combinatorial optimization problem with constraints. It is customary to resort to heuristic methods to solve such an NP-hard problem (Bramel and Simchi-Levi, 1996) and a satisfactory solution will be obtained within a limited time. Previous studies have proposed several meta-heuristics to solve the VRPTW problems with better robustness and higher calculating speed (such as Genetic Algorithm, Scatter Search, Ant Colony Algorithm, etc.) (Russell and Chiang, 2006; Zhen et al., 2008; Liu and Huang, 2010) are widely used in VRPTW problems for high efficiency. Moccia and Cordeau (2011) proposed an improved Tabu search algorithm for the VRPTW problem and the test results demonstrated the effectiveness of the employed algorithm. Balseiro et al. (2011) presented an hybrid ant colony algorithm for the Time-Dependent Vehicle Routing Problem with Time Windows which was confirmed by the experimental results. In study Chen (2010), a mixed binary integer programming model was developed for solving the job scheduling with delivery vehicles routing problem. Bettinelli et al. (2011) put forward a branch-and-cut-and-price algorithm with different pricing and cutting techniques for the VRPTW. The studies (Sadouni, 2006; Pavone et al., 2009; Baldacci et al., 2011; Cordeau and Maischberger, 2011; Pureza and Morabito, 2011) had presented other strategies for the VRPTW problems. In our previous studies (Wu et al., 2011), fuel consumption optimization based on the common objectives of VRPTW was put forward. A model was built for fuel consumption with two steps for the fuel consumption objective. The test results showed that the suggested method had a better performance for the VRP problems. Different from the previous research, this study attempts to show the feasibility and effectiveness of a modified artificial bee colony algorithm (ABC-T for short) for the VRPTW problems.
Artificial Bee Colony (ABC) Algorithm is proposed by Karaboga (2005) which is a random optimization algorithm based on bee colony intelligent search behavior. With the local searching of each bee, the global optimal solution will be obtained quickly. Rather than deterministic rules, the probabilistic rules employed by the ABC algorithm, achieve great robustness and wide applicability for solving NP-hard problems. In view of characteristic of the ABC algorithm, the ABC algorithms have been used to deal with the constrained optimization problems. Abu-Mouti and El-Hawary (2011) presented a new optimization approach that employed the ABC algorithm to confirm the optimal DG-unit's size, power factor and location in order to minimize the total system real power loss. Zielonka et al. (2011) presented an improved ABC algorithm for solving the inverse heat conduction problems, with the state function and some boundary conditions consisted. Karaboga and Ozturk (2009) successfully applied the ABC algorithm for the neural networks training problem in the machine learning community. Shi et al. (2011) proposed a modified artificial bee colony algorithm (ABC-G for short) to deal with a satellite module layout design problem, with the target for arranging a set of components in the simplified satellite module. The difference from the above research is that this study attempted to provide an improved version of ABC algorithm for the VRPTW problem by employing Tournament Selection. In our proposed ABC-T algorithm, the Tournament Selection strategy was employed to guarantee the global convergence as well as the converging rate and the stability effectively. The experimental tests can show the feasibility and effectiveness of the proposed ABC-T algorithm.
BRIEF DESCRIPTION FOR THE VRPTW PROBLEM
The VRPTW can be formally described as follows: A number of vehicles are assigned to serve for consumers at different positions with different demands for goods and they must arrive at the destinations within the allowed service access time windows (ei, li). At the same time, each consumer can only call for one vehicle but the same vehicle is allowed to serve more than one consumer. All the vehicles must return distribution center before closing time. It’s assumed that all the vehicles are same with the load capacity q. On the conditions above, the objective function of the VRPTW is how to minimize the delivery cost. cij, denotes the travel cost from consumer i to consumer j, i.e. the distance between them; C and A represent the consumer set and the edge set, respectively. V is the vehicle set; the demand of consumer i is di; the travel time from consumer i to consumer j is tij, the start time when vehicle k serve for consumer i is bik. The mathematical model can be described as follows:
Equation (1) gives the objective function that is as follows:
| (1) |
| (2) |
It constrains that each consumer can only be served once:
| (3) |
It makes up the capacity restriction:
| (4-6) |
Equations 4-6 ensure that each vehicle starts serving from distribution center and returns distribution center after finishing its work:
| (7) |
It prohibits the vehicle which running from consumer i to consumer j from arriving at the consumer j before the time bik+tij:
| (8) |
It is the constraint of the time window:
| (9) |
Eq. 9 is the integer constraint.
THE ABC-T ALGORITHM
The original ABC algorithm
The artificial bee colony consists of the following three parts:
Employed bees, onlookers and scouts in the ABC algorithm. The number of employed
bees is equal to number of onlookers, the number of scouts is 1 in each cycle.
Both the employed bees and the onlookers have the responsibility to execute
exploitation; however the responsibility of scouts is to perform exploration.
So the ABC algorithm combines the global hunt and local hunt methods which allows
the bees in the two aspects of the exploration and exploitation of food sources
to achieve a better balance.
When the ABC algorithm is employed for solving problems, the location of food sources is abstract as the point in the solution space and the process of bee seeking honey is the procedure of finding optimal solution. As the global optimization problem (P), min{f(X);XεS⊂Rn}, the set of several feasible solution of the problem (P) is called a population and each element in the population (feasible solution) is known as a food source. The performance of each food source depends on fitness value of the optimization problem and the solution number (SN) is equal to number of employed bees or onlookers. The d-dimensional vector Xi(xi1, x2,....,SN) is adopted to represent the position of the ith food sources. First, the ABC algorithm generates the initial population of containing the SN solutions and each solution Xi (i = 1,2,...,SN) is a d-dimensional vector. Then, the bees make cyclic searching of all the food sources with the number of cycles C (C = 1,2,...,MCN). First of all, the employed bees have a neighborhood search for the corresponding food source (solution). If the nectar’s quality (fitness) of the searched food source (solution) is better than that of the former, then this new food source position is adopted to replace the old food source position; otherwise to maintain the old food source location. After the whole employed bees completed search, they will get back to the dance area and bring the information of nectar’s quality to onlookers via waggle dance. Onlookers will select food source according to the selection probability on the basis of information obtained. The more nectar of food sources, the bigger probability to be selected. Once the onlookers select food source, they also have a neighborhood search and retain a better solution. The ABC algorithm is such a loop search and ultimately obtains the optimal solution.
The original ABC algorithm adopts Proportional Fitness Selection strategy (Karaboga, 2005) as the selection approach. That means the bigger the individual fitness is, the higher the selected probability is and vice versa. However, is rather small, some extraordinary individuals are generated sometimes. These extraordinary individuals are too competitive to control the selection operation and the global search capacity is restricted. Conversely, if the fitness of individuals is equivalent or close, the elite individuals maybe not have a better opportunity, so that the convergence of the algorithm slows down. In order to deal with this drawback, this study proposes a modified the ABC algorithm using the Tournament selection strategy (ABC-T for short) for solving the VRPTW problem.
The ABC-T algorithm
(1) Representation and decoding procedure for the ABC-T algorithm: The
VRPTW problem is a kind of combinatorial optimization problem based on sequence.
In order to reduce the invalid solutions, the following representation and decoding
procedure is adopted: the Natural Number Progression (Tan
et al., 2001) is generated at random and then the routes are decoded
by employing a route decoding operator based on Greedy approach (Cormen
et al., 1990). Take the progression “2 7 6 1 5 8 4 3” as
an example. The decoding operator put “2” in the first route to judge,
whether it meets the constraints. If “2” meets the constraints, try
to put “7” in the first route. Then decoding procedure judges whether
“7” meets the constraints, if not, begin to hew out the second route
with “7”. Continue the judgment until decoding procedure is finished.
Taking N as population size, the initial population is formed by generating
N individuals at random. Owing to a mass of constraints in VRPTW problems, most
of the randomly generated solutions are infeasible. Using the above representation
and decoding procedure not only ensures the number of feasible solutions but
also describes the characteristics of VRPTW more intuitively.
(2) Fitness calculation: According to the target function, this study chooses the shortest distance as the target, so the fitness function f (i) is the reciprocal of the distance. The longer the distance is, the lower the fitness value. As for the onlookers, the lower the gains of food source, the smaller probability to choose that food source.
(3) Search strategy: In the original ABC algorithm, based on the traditional neighborhood search, the results usually are numbers with a fraction. Due to the non-integer results are not suitable for Natural Number coding of the VRPTW problem, this paper adopts the neighborhood search approach as follows: an appointed solution firstly generates an interval (k, j) randomly and then the numbers of the interval are poured preface alignment.
(4) Tournament selection strategy: Selection strategy used by the original ABC algorithm requires that fitness function value is bigger than zero. However, in Tournament Selection Miller and Goldberg (1996) adopted the diversified principles. Tournament selection involves running several “tournaments” among a few individuals chosen at random from the population. This selection strategy has been employed for strengthening algorithms performances, such as in of study (Wasan, 2008; Luo et al., 2009; Chiu, 2010; Dong-Feng and Feng, 2010). Its major concept is selecting k individuals in population randomly and selecting the one whose fitness value is the biggest. Parameter k is called the competition size. Using the Tournament selection, this algorithm carries out the multiple comparisons between the fitness values of the two individuals in the tth generation. If the current value of the individual is better than another one, then the individual is awarded one point every time and repeat this process for each individual. The one who gets the highest mark, its weight is also the largest. This selection way makes the individual which has a better fitness has a greater survival opportunity. At the same time, by the reason of the Tournament selection takes the relative value of the fitness as the criteria, therefore, it’s not direct proportional to the fitness value. This treatment reduces the influence of the super individual in algorithm and avoids the premature convergence and stagnation phenomenon to a certain extent. According to the principles above, the selection probability of fi is:
ai is the final mark of ith individual after the comparisons and SN is the number of the whole solutions.
(5) Food source update strategy: If a solution has not reached the requirement after limit times loops, this solution should be abandoned and a new solution will be randomly generate. In order to ensure the convergence of the algorithm, the ABC-T algorithm carries out the following operation in the scout stage. When the abandoned solution is current optimum, if the generated new solution has better fitness value, the new one will replace the abandoned one as the new current optimum. Otherwise, current optimum maintains at present and the inner circulation is reset. When the abandoned solution is not the current optimum, a new solution is randomly generated to replace the abandoned solution. This method ensures that the current optimum solution is not discarded and avoids convergence failure. Furthermore, the scouts have not been confined looking for a new food source to help the algorithm avoid sinking into the local optimal solution.
Main process of the ABC-T algorithm:
| Step 1 | : | Population initialization and the solutions of initial population are xi, i = 1,2,...,SN. Then calculate the fitness value of each solution xi |
| Step 2 | : | The employed bees generate the new solutions vi by the neighborhood search and the fitness values of vi are calculated separately |
| Step 3 | : | If vi has better fitness value, vi replaced as xi the current optimum, otherwise keeping xi unchanged |
| Step 4 | : | Based on the Tournament selection, calculate probability Pi associated with xi |
| Step 5 | : | Onlookers choose their food source (solution) on the basis of Pi and generate new solutions ri by the neighborhood search with their fitness values being calculated |
| Step 6 | : | Carry out the calculation to judge whether ri should replace xi based on the fitness values |
| Step 7 | : | Determine the current solution should be discarded and if necessary, the scouts will produce a new solution ti to replace it |
| Step 8 | : | Record the best solution so far |
| Step 9 | : | Meeting the end condition and output the best result, otherwise return Step 2 |
EXPERIMENTS
The ABC-T algorithm was applied to the standard instance R102 from Solomon’s benchmark short horizon problems (Solomon, 1987). The R102 benchmark can be described as follows: there is only one distribution center to serve for 100 consumers at different positions with different demands for goods; all the vehicles are same with the load capacity 200; the earliest departure time of each vehicle is 0 and the latest time is 230; the time for serving each consumer is 10. The detailed data of R102 is listed in Table 1.
The ABC-T algorithm was implemented in MATLAB R2010b and all the experiments were performed on a computer with 1.99 GHz CPU and 2 GB RAM running the Windows XP operating system. In the preliminary experiments, trial-and-error approach was used to obtain suitable control parameters values for the proposed algorithm. Some control parameters were settled as followings: the number of the population, = 100; the number of both the employed bees and the onlooker bees is 25; limit = 10. Running the program for 8 times and Table 2 listed the results of the proposed ABC-T algorithm for R102 problem.
The performances of ABC-T and several approaches from the literature with R102 benchmark were shown in Table 3. This study compared ABC-T with Zhen et al. (2008), Hashimoto et al. (2008), Liu and Huang (2010) and Figliozzi (2010).
| Table 1: | The detailed data of R102 |
| Table 2: | The results of the proposed ABC-T algorithm for R102 problem with 8 times |
| Table 3: | The performances of ABC-T and several approaches |
Figliozzi (2010) employed the Iterative Route Construction and Improvement (IRCI) Algorithm for R102 benchmark which obtained the best effect so far. Make comparisons with others’ results, the ABC-T algorithm ranked 2nd with the shortest distance. The ABC-T ranked 2nd for R102 showed that ABC-T can produce better solutions for the VRPTW problems. That is to say, the ABC-T algorithm can solve the large-scale VRPTW problems effectively.
The reason for the improved performance is that ABC-T combines the advantages of the ABC algorithm and the Tournament selection approach. The artificial bee colony algorithm is based on the local optimization of each bee individual behavior and ultimately achieves the global optimum of the group with a fast convergence rate. The positive feedback mechanism between the employed bees and the onlooker bees can accelerate the evolutionary process to a certain extent. Furthermore, with the persisting information exchange among the bees, it is imperative in finding better resolution. What is worth mentioning is that the original ABC algorithm adopts Proportional fitness selection strategy as the selection approach and some extraordinary individuals are generated sometimes. These extraordinary individuals are too competitive to control the selection operation and the global search capacity is restricted. Since using the Tournament selection approach, the ABC-T algorithm has been guaranteed the global convergence as well as the converging rate and the stability effectively.
CONCLUSIONS
This study proposed a heuristic algorithm combining the artificial bee colony algorithm (ABC-T) and the tournament selection strategy to solve the vehicle routing problems with time windows. The computational results of the ABC-T algorithm were compared with the state-of-the-art heuristics on the standard benchmark. The experimental results showed that, ABC-T performed well compared with other algorithms for the VRPTW problems. This study also showed that the ABC-T is a promising method for solving the VRPTW problems. Further studies will focus on such as the theory of convergence, the improvements combining with other algorithms, the application in the complex field and so on. Enhancing the applicability and efficiency of the proposed ABC-T algorithm for various complex real-world scheduling problems still need further research.
ACKNOWLEDGMENT
This work was supported by National Natural Science Foundation of P.R. China (Grant No. 50975039).