The Vehicle Routing Problem (VRP) is one of the most popular combinatorial optimization problems which is closely related to the real-life optimization challenges. Being developed for more than 60 years the problem has been considered in many di erent formulations. In real-life goods distribution such constraints as eet size and mix, sitedependency constraints, hard and soft time windows, vehicle capacity constraints are very important. In this paper we consider Capacitated Vehicle Routing Problem with hard Time Windows. We propose a hybrid heuristic algorithm which contains elements of ant colony optimization strategy and tabu search technique. Our algorithm shows good performance and results for the well-known Solomon dataset.
The Vehicle Routing Problem (VRP) is one of the most popular
combinatorial optimization problems which is closely related to the real-life optimization
challenges. The problem's community is quite large - various VRP challenges
and knowledge databases can be found all over the Internet. In everyday life
many distribution companies use speci c algorithms and software to solve
different variations of VRP. The importance of the problem grows today with the
achievements in drone delivery and unmanned vehicles popularization. Modern
VRP formulations usually contain many di erent types of constraints. To our
experience in case of distribution companies the most critical constraints are
hard and soft time windows (VRPTW). Other research papers also con rm the
vitality of time windows constraints [
Copyright c by the paper's authors. Copying permitted for private and academic purposes. In: S. Belim et al. (eds.): OPTA-SCL 2018, Omsk, Russia, published at http://ceur-ws.org
There are many heuristic algorithms with promising results. Jawarneh &
Abdullah [
Hybrid algorithms where several heuristics or metaheuristics ideas are
combined are widely used for solving various combinatorial optimization problems
[
In this paper we consider the Capacitated Vehicle Routing with Time Windows
(CVRPTW). In this formulation we are given a limited number of vehicles with
the same capacity to serve customers in the speci ed time intervals. In practice
these intervals called time windows may refer to customer working hours or
concrete hour when it is convenient for a customer to unload a vehicle. Time
window constraints are known to be the hardest part of VRPTW [
According to CVRPTW formulation each customer i has an associated pair of values [ei; li] which represent the earliest and the latest time when unloading can be started. However, if a vehicle arrives before a customer i is ready to start service we assume that the vehicle waits for the beginning of the time window ei. On the other hand, any vehicle is allowed to nish servicing customer i even after the right bound of time window li.
We consider the CVRPTW formulation in which we have a set K of identical vehicles with capacity Q. The number of vehicles is jKj, but it is not required to use all of them.
A straightforward mathematical formulation for CVRPTW is given in [
0; otherwise wik = (service start time, if customer i appears in the route of vehicle k 0; otherwise
With all the variables and parameters above we can now formulate the problem considered in this paper as follows (CVRPTW):
min
X
X k2K (i;j)2A
cij xijk X
X k2K j2 +(i)
X j2 +(0) X
(n+1) i2 xijk
X i2 +(k)
X i2 (j) xijk = 1
8i 2 V; x0jk = 1
8k 2 K; xi;n+1;k = 1
8k 2 K; xjik = 0
8k 2 K; j 2 V xijk(wik + si + tij wjk) 0
8k 2 K; (i; j) 2 A; ei li
X j2 +(i)
X j2 +(i) xijk xijk wik wik 8k 2 K; i 2 V; 8k 2 K; i 2 V; w0k
E
8k 2 K; wn+1;k
L
8k 2 K; X qi xijk (11) xijk 2 f0; 1g 8k 2 K; (i; j) 2 A: (12)
Objective function (1) minimizes the total cost of all the routes in the solution. Constraint (2) ensures that each customer is assigned to exactly one route. Constraints (3), (4) and (5) guarantee that we have only one outcoming edge from the start depot vertex, only one incoming edge to the end depot vertex and each customer has the same number of incoming and outcoming edges. Inequality (6) prohibits service to start earlier than the earliest possible arrive time from the previous customer taking into account service and travel times. Inequalities (7), (8), (9), (10) provide feasibility with respect to the given time windows. Finally, constraint (11) prohibits overloaded routes with the total demand greater than vehicle capacity Q. 3
During the recent years metaheuristic algorithms have become a popular way to solve any combinatorial optimization problem. The so called hybrid methods which incorporate strategies from di erent metaheuristic approaches are widely used. In this paper we present a hybrid heuristic algorithm which contains Ant Colony Optimization (ACO) and Tabu Search (TS) with the possibility of visiting infeasible solutions during the search. In section 3.3 we provide empirical results which con rm that our hybrid algorithm outperforms separate runs of TS and ACO procedures. The e ect of visiting infeasible areas during the search is discussed in Section 3.4.
Algorithm 1 Ant Colony - Tabu Search approach 1: procedure ACO-TS() 2: maxIterations 30 3: candidateAco ; 4: candidateT S ; 5: bestSolution ; 6: for i 1; maxIterations do 7: candidateACO runACO(candidateT S) 8: updateIfBetter(bestSolution; candidateACO) 9: if hasUnserved(candidateACO) = T rue then 10: fixUnserved(candidateACO) 11: end if 12: candidateT S runTS(candidateACO) 13: updateIfBetter(bestSolution; candidateT S) 14: end for 15: return bestSolution 16: end procedure
Algorithm 1 provides the top level procedure of our approach. Here we have the main loop which sequentially runs the ant colony algorithm and then tabu search. Variables candidateACO, candidateT S and bestSolution represent best solutions found by ACO, TS and overall best respectively. Variable maxIterations limits the number of iterations of the main loop. Inside the loop runACO(candidateT S) is called and the best solution found by this function is saved to candidateACO. runACO(candidateT S) receives the best solution found by the previous TS function run and uses it to update initial pheromone values. For the rst time when candidateT S is empty all pheromones are initialized with the same value that will be discussed later. Then the algorithm calls updateIfBetter(bestSolution; candidateACO) which replaces the best solution found so far with candidateACO if candidate solution is better. Our ACO solution is constructed by adding routes one by one. This sometimes leads to infeasible solutions where some customers are unserved. Since the TS function cannot work with such kind of infeasibilities we run fixUnserved(candidateACO) procedure to x it. This procedure transforms all unserved customers into onecustomer routes using additional vehicles. Such transformation in its turn can lead to using more vehicles than we have. However, this type of violations can be easily xed in tabu search function. Then candidateACO solution is passed to runTS(candidateACO) function and used as a starting solution for the search. After TS function is nished the results are saved to candidateT S variable and the best solution is updated if necessary inside updateIfBetter() . 3.1
Ant colony optimization strategy is used to obtain an initial solution and then to escape from the local optimum obtained by the tabu search part. In this algorithm each ant constructs a solution in a probabilistic manner using pheromone values associated with every single arc. Initially all pheromone values are set to the same value equal to the total cost of the solution where every customer is served with its own vehicle. This means that initially all the arcs can become a part of the solution under construction with the same probability. Here we use the solution with one-customer routes to ll initial pheromone values. The algorithm for our ACO stage is presented in Algorithm 2. The detailed description is provided below.
Algorithm 2 starts with de ning some variables. The rst variable which is called maxIterationsW ithoutImprovement de nes how many iterations without improving the current best solution we can run. The next variables which are iterations, colonySize and best de ne current iteration counter, number of ants generated in each iteration and the best solution found so far respectively. At rst procedure updatePheromones(startSolution) is called. This procedure gets a solution startSolution (or generally a list of solutions), iterate over it and increase current pheromone values for every edge in a solution by 1=c(startSolution) where c(startSolution) is the cost of startSolution. As a result, it allows us to connect the parts of our approach by passing the TS result to ACO part and letting ACO search to prioritize elements of TS solution.
After that the main loop of ACO algorithm starts. The stopping criterion in this case is reaching maxIterationsW ithoutImprovement iterations without Algorithm 2 Ant Colony Optimization algorithm improving the best solution. Inside the main loop we have variables oldBest, localBestList and current which represent the best solution in the previous iterations, the list of best solutions in the current iteration and the current solution under consideration. Variable oldBest is needed to compare current iteration solutions only to the solutions from the previous iterations, localBestList is used to update pheromone values at the end of iteration.
Then an inner loop starts where a colony of ants is formed. Every single solution for the problem which is represented by a single ant is constructed by calling current runSingleAnt(). Then we have to update the current best solution if necessary and add current solution for future pheromone update if this solution is good enough. Both of these actions are done with the help of isBetter(solution1; solution2; gap) function which gets two solutions and gap value as parameters. If solution1 has a lower cost than solution2 or solution1 cost is within the gap percent from solution2 the function returns true. Since runSingleAnt() can produce solutions where some customers are unserved, isBetter(solution1; solution2; gap) returns true value immediately if the number of unserved customers in solution1 is strictly less than in solution2.
We call isBetter(current; best; 0) to test if a better solution than the current best is found. Also isBetter(current; bestLocal; 5) is called when the algorithm determines which solutions in the current iteration can be used for future pheromones update. If a solution's cost is within 5% from the best one obtained in the previous iterations or it has less unserved customers - it is added to localBestList list. After the whole colony is generated we update the pheromone values in updatePheromones(bestLocalList). Then the pheromone evaporation procedure evaporate() is called. It reduces the pheromone value on every edge: pheromoneij = pheromoneij . Here is the evaporation rate parameter empirically set to 0:8.
Algorithm 3 Creating a single ant solution 1: procedure runSingleAnt() 2: solution ; 3: repeat 4: isInserted addNewRoute(solution) 5: until isInserted == T rue & getRoutesNumber(solution) < jKj 6: return solution 7: end procedure
Every candidate solution in our ACO approach is constructed using runSingleAnt(), addNewRoute() and insertNextCustomer() procedures. These procedures are described in Algorithm 3, Algorithm 4 and Algorithm 5 respectively. Function runSingleAnt() from Algorithm 3 forms a new solution from scratch. Step by step it adds a new route by calling addNewRoute(solution). The solution construction terminates when addNewRoute(solution) returns false (there are no possible routes to add) or when the total number of routes equals to the number of vehicles available. Algorithm 4 describes a new route creation process. At rst we check if there are unserved customers in the solution and set the current route under creation as an empty route. Then we call procedure insertNextCustomer(route; unservedCustomers) to extend route until there is a customer who can be added without any constraint violations. Finally, addRoute(solution; route) is called to append a new route to the solution.
Procedure insertNextCustomer(route; unservedCustomers) which is presented in Algorithm 5 appends a new customer to route with some probability. This probability depends on the current pheromone values for the arc from the last customer to a new one and the cost of this arc. The list of probabilities for every customer is initially empty. Then the algorithm iterates over all the unserved customers. If the customer c can be inserted to the end of route without time window and load violations we de ne its probability to be chosen as pheromones[prev][c] . After iterating over all the unserved costs[prev][c] customers we check if there is a non-null value in probs for at least one customer by calling isEmpty(probs). Strictly speaking values in probs cannot be called probabilities so we normalize all these values with normalize(probs). Then we choose a customer to be added to the route using probs as probabilities inside getRandom(probs; unservedCustomers) and then add it in addCustomer(nextCustomer; route).
Algorithm 5 Customer insertion procedure 1: procedure insertNextCustomer(route; unservedCustomers) 2: probs ; 3: prev getLastCustomer(route) 4: for c 2 unservedCustomers do 5: if isFeasibleInsertion(c; route) = T rue then 6: probsc phercoosmtso[nperse[vp]r[ce]v][c] 7: end if 8: end for 9: if isEmpty(probs) then 10: return F alse 11: end if 12: normalize(probs) 13: nextCustomer getRandom(probs; unservedCustomers) 14: addCustomer(nextCustomer; route) 15: return T rue 16: end procedure 3.2
After ant colony part is nished we use its best solution to improve it with
tabu search technique. Our algorithm is inspired by the uni ed tabu search from
[
One of the features of our algorithm is the possibility of forming new routes, which is de ned as moving a customer from its current route to a new route. Also we allow all kind of constraints to be violated at some cost. Let c(S) be the total cost of solution S, load(r) be the total load of some route r inside S, tw(r) be the total lateness time for route r. For each type of infeasibility (time windows, load, routes number) we introduce a control coe cient. These coe cients are ; ; for time windows, load and routes number violations respectively. The key goal of these control coe cients is to force the tabu search algorithm to decrease infeasibilities when we stay in the infeasible area for too long. This goal is achieved by adding penalties for each type of violations to the cost function. Therefore total solution cost is de ned as: cost(S) = c(S) +
X tw(r) +
X max(0; load(r) r2S r2S
Q) + max(0; jSj jKj) (13) where jSj is the total number of routes in the solution S. To prevent the search from visiting only infeasible solutions we control the time spent inside infeasible area by using dynamically adjusted control parameters ; ; . Initially all these parameters are set to the starting value equal to 1. Each time we move from solution Sm to solution Sm+1 while, for example, tw(Sm) < tw(Sm+1), the control parameter is multiplied by a xed scaling factor which is set to 1.4. If we move to a solution where violation is increased comparing to the previous one, the corresponding control parameter is always multiplied by the scaling factor. On the other hand, if we move to a solution where violation is decreased the control parameter stays the same. Only when a violation value becomes equal to 0 the control parameter for this particular violation type is reset to 1. This way the search is allowed to visit infeasible areas, but the exponential growth of ; ; parameters forces the algorithm to move back to feasible regions.
As a part of tabu search technique we use short term memory to avoid the search moving within some loops. We append moves to a tabu list structure and they become prohibited for a xed numbertabuT enure = 10 of iterations. For long term memory strategy we store the number of times each edge has been transited to a solution. Each time we evaluate a move, the algorithm estimates how many times the edges we want to include has been transited to the solution before. The resulting value is also added to the cost function as a penalty. Such an approach allows us to prevent some edges to be transited to a solution too often and let the algorithm to consider other options. It provides global diversi cation for the search.
The pseudocode for the TS procedure is presented in Algorithm 6. Algorithm 6 starts with de ning iterations, maxIterationsW ithoutImprovement and best variables which represent iterations counter, stopping criterion for the main loop and the current best solution respectively. Inside the main loop we declare bestDelta which is the best cost di erence found between the current solution and a possible candidate solution. Variable bestM ove stores the best move found so far. Function fillPossibleMoves(currentSolution) looks for all possible moves from the current solution. Then the algorithm iterates over all possibleM oves from the previous step. getCost(currentSolution; move) is run for each move to compute the cost delta. If this delta is better than bestDelta found so far and move is not in the tabu list bestDelta is updated. Here we use the rst descent strategy and perform the rst improving move found. This way we leave the inner loop immediately when an improving move Algorithm 6 Tabu Search algorithm is found. updateTabuList(bestM ove) marks the customer and the source route from bestM ove as tabu active elements. We prohibit any moves in which a customer and a destination route are tabu active for tabuT enure iterations, where tabuT enure equals to 10. Long term memory is updated by updateTransitions(). Then we apply the best move found with applyMove(currentSolution; bestM ove) and adjust the control coe cients ; ; . 3.3
We have performed several computational experiments to test our hybrid approach in comparison to separate runs of ACO and TS algorithms. Our hybrid approach termination criterion has been set to 100 iterations without improvement for ACO part and 500 iterations without improvement for TS. Then we run the hybrid approach for 30 times, nd the longest run and set this value as the time limit for a single ACO run. For a fair comparison with a separate ACO algorithm we have run ACO also for 30 times, each time with the determined time limit. For TS algorithm we have started with one-customer routes solution and limited its running time to the total time of 30 hybrid algorithm runs. The results of our experiments are very similar for almost all instances from Solomon's dataset, so we provide only some examples in Table 1. The best results among all the algorithms are in bold. Here we can conclude that on all problems from Solomon's dataset our hybrid approach shows a good performance in comparison with separate ACO and TS runs.
Visiting infeasible solutions has been considered for many combinatorial
optimization problems. Cordeau et al. [
In this paper we have presented a new hybrid heuristic approach for solving
the Capacitated Vehicle Routing Problem with Time Windows. Our algorithm
combines Ant Colony Optimization (ACO) approach and Tabu Search (TS)
technique. A move neighborhood with possibility of creating new routes and visiting
infeasible areas has been considered to improve the search process. The idea of
sequential usage of ACO and TS parts gives major improvements comparing
to separate runs of these algorithms. Computational experiments show better
results on 41 of 56 considered test instances comparing to the recent results of
Jawarneh & Abdullah [
Acknowledgement. The research was funded by Russian Science Foundation (RSF project No. 17-71-10107).