Vehicle Routing Problems with Soft Time Windows

2012 7th International Conference on Electrical and Computer Engineering 634 20-22 December, 2012, Dhaka, Bangladesh Vehicle Routing Problems With Soft Time Windows Sumaiya Iqbal, and M. Sohel Rahman AℓEDA Group Dept. of CSE, BUET, Dhaka, Bangladesh {sumaiya,msrahman}@cse.buet.ac.bd Abstract—The Vehicle Routing Problem with Time Windows using ABC metaheuristic. Section VI shows our result and the (VRPTW) is to serve a set of customer demands with time comparison with previous work is given in Section VII. And, constraints and vehicle with limited capacity. This has practical finally Section VIII presents the future work and conclusion applications in container truck routing, delivery service schedul- ing, garbage collection, fleet network design etc. In this paper, we briefly. consider one of its variants where the time constraint is ’soft’, that is it can be violated with a penalty cost. In this paper, we present III. P ROBLEM D EFINITION the Artificial Bee Colony (ABC) metaheuristic based approach The problem can be modelled by a directed graph, G = for solving the VRPTW problem with soft timing constraint. We (V, E), where, V is a set of n + 1 vertices and E is a set have shown our experimental results for different parameters, compared with previous results and shown that our algorithm of edges representing the connections between the depot and gives better result for many instances of the problem. customers and among the customers. Here, |V | = |C| + 1, where, C = 1, 2, . . . , n is the set of customers and Vertex 0 represents both the starting and ending depot. Every customer Index Terms—VRPSTW, Soft time window, Artificial bee colony, Metaheuristic, Travelling cost, Number of window breaks, has a fixed demand. Every vehicle has to start its journey from penalty coefficient. the depot (Vertex 0) and also has to return back to the depot. We assume that the fleet is homogenous. The capacity and I. I NTRODUCTION the speed of all vehicles are same. Here, Ti denotes a vehicle. The Vehicle Routing Problem (VRP) is a combinatorial Tq and Ts denote the capacity and the speed of each of optimization problem seeking to service a number of cus- the vehicles respectively. The cost associated with each edge tomers with a fleet of vehicles. The Vehicle Routing Problem e(i, j) is denoted by cij , si is the service time, di is the demand with Time Windows (VRPTW) is one of the variants of and [ai , bi ] is the time window associated to a Customer i. VRP problems which has been extensively studied in the Since here the time window is relaxed, there is an allowable Computer Science and Transportation Engineering literature violation of time windows denoted by Pmax ≥ 0. So for where, each customer has a time window within which the Customer i, the relaxed time window is [ai − Pmax , bi + customer is to be served. The Vehicle Routing Problem with Pmax ] = [ari , bri ]. An early penalty pe (ai − yi ), where yi Hard Time Windows (VRPHTW) is an well studied variant ∈ [ari , ai ], is added to the service cost if any vehicle arrives of VRPTW problem where this time windows can not be earlier. And, a late penalty pℓ (yi − bi ), where yi ∈ [bi , bri ], is violated. And, the Vehicle Routing Problem with Soft Time added to the service cost if any vehicle arrives late. Here, both Windows (VRPSTW) is a relaxation of VRPHTW problem the pe and pℓ is penalty coefficient, 0 < pe /pℓ < 1. where, the time windows can be violated if a penalty is paid. It is assumed that Tq , Ts , ai , bi , di , cij are non-negative inte- The VRPSTW has many practical applications. For example, gers and si are positive integers. The goal is to design a set of the delivery of fuel/box to service stations do not require hard routes that minimizes total cost and window breaks satisfying time windows. Also in many cases, relaxing the time window the constraints: (1) Each customer is serviced exactly once and may be more appropriate. all the customers must be served, (2) every route originates and ends at vertex 0 and (3) the time windows of the customers II. L ITERATURE R EVIEW and capacity constraints of the vehicles are obeyed. Vehicle Routing problem (VRP) is an NP-complete prob- Our objective functions for the VRPSTW problem is (1) the lem [1]. There have been both exact and heuristic approaches minimization of the number time window violations and (2) for solving VRP and its variants. VRPHTW has been tack- the minimization of total time or distance including penalties. led using neighborhood-based heuristic [2], improved ant colony optimization (ACO) [3], hybrid ant colony optimiza- IV. T HE A RTIFICIAL B EE C OLONY (ABC) tion [4], bee colony inspired approach [6], etc. Early works M ETAHEURISTIC on VRPSTW include using Bender’s decomposition [5], using The artificial bee colony algorithm is a new population- generalized assignment problem [7], applying construction based metaheuristic proposed by Karaboga [12], which is heuristic [8], using tabu serach heuristic [9], combining a tabu motivated by the foraging behavior of honey bees. In the ABC search approach with a mixed neighborhood structure [10], and algorithm, each food source for a bee represents a possible applying a goal programming approach [11]. This paper aims solution of the problem under consideration and the nectar to apply a new metaheuristic, Artificial Bee Colony (ABC) to amount of a food source represents the quality of the solution solve VRPSTW problem. The rest of the paper is organized represented by that food source. There are three types of bees as follows. In Section III, we formally define the VRPSTW in this metaheuristic: (1) Employed Bee, (2) Onlooker Bee and problem. In Section IV, ABC metaheuristic is described and (3) Scout Bee. First half of the bees of the colony comprises in Section V, we present the steps to solve the problem employed bees, whereas the latter half is the onlookers. 978-1-4673-1436-7/12/$31.00 ©2012 IEEE  635 The ABC algorithm is an iterative algorithm. It assumes • Like this, for each vector (vehicle/route), customers are that the number of food sources are same as the number of randomly chosen (excluding the one that have been employed bees because each employed bee is assigned to a chosen already) and the demand of everyone is added single food source. It starts by assigning all employed bees to the demand record, until the total demand, Td exceeds to randomly generated food sources (solution). Then during the vehicle capacity, Tq , of the vehicle Ti . each iteration, every employed bee determines a food source • Then, the total number of customers is reduced by total in the neighborhood of its current food source and evaluates its number of customers chosen already. nectar amount (fitness). If its nectar amount is better than that • The customers for a vector is chosen in a way, so that no of its current food source then it moves to this new food source customer number is repeated in a solution. leaving the old one; otherwise it retains its old food source. • This process is repeated for each vector in a solution to When all employed bees have finished this process, they share create a complete solution. the nectar information of the food sources with the onlookers. Each onlooker selects a food source according to a probability B. Determination of a food source in the neighborhood proportional to the nectar amount of that food source. The VRPSTW is a discrete optimization problem. And here, we probability pi of selecting a Food Source i is determined by represent each solution by a set of routes (vectors) for a fixed pi = mfi , where fi is the fitness of the solution represented number of vehicles. Again, each of that route consists of some X fj integers corresponding to the consecutive customer numbers j=1 served by a vehicle. So, there is an ordering between these by the Food Source i and m is the total number of food numbers, following which, the customers are served. Initially, sources. Clearly, with this scheme, good food sources will get some random new solutions (maintaing all the constraints) are more onlookers than the bad one. After all onlookers have given to some employed bee. Then, it is desirable to utilize selected their food sources, they become employed bee. If the information gathered by those employed bee about the a solution represented by a particular food source does not food sources while generating a neighboring solution. This improve for a predetermined number of iterations then that may help in producing a good neighborhood solution. In our food source is abandoned by its associated employed bee and algorithm, we have made the following two modifications the bee becomes a scout, i.e., then it start searching for a on the random solution for employed bee to produce the new food source randomly. This is tantamount to assigning neighborhood solutions. a randomly generated food source (solution) to this scout Step 1: Note that, each customer must be present in a solution and changing its status again from scout to employed. After exactly once. We randomly select a customer, say, (m) from of the new location of each food source is determined, another a solution, say, (Sm ) from which a new neighborhood solution, iteration of ABC algorithm begins. The whole process is say, Sn will be generated. Then, we randomly choose another repeated again and again until the termination condition is solution from which we select another random customer, say, satisfied. Here, Scout bees can be visualized as performing (n), where m 6= n. Now, replace m by n. But, n must be the job of exploration, whereas employed and onlooker bees already present in Sm , which is allowed. So, just exchange can be visualized as performing the job of exploitation. the position of m and n within Sm which converts Sm into Sn . V. S TEPS OF S OLVING VRPSTW P ROCEDURE Step 2: Now, the order of customers being served is important. In the VRPSTW problem, the number of vehicle is fixed. Varying this order can also vary the travelling cost. We have Our objective is to reduce the total transportation cost (time) utilized this observation for generating a new neighborhood needed to serve all the customers exactly once by any of the solution Sn from the solution Sm . We select a block of vehicles. So, for each vehicle, Ti , there will be a route, Ri , customer numbers from any route of Sm and replace that that starts at the Depot 0 and after serving some customers block by a random permutation of the selected numbers which (1 ≤ xi ≤ |C|), again ends at Depot 0, where, |C| is the total generates the Sn . number of customers. Now, the steps of our ABC algorithm for Altogether these two steps generate new neighborhood solving the VRPSTW problem (ABC VRPSTW) is described solutions in our problem. in the following subsections. C. Probability of Selecting a Food Source A. Initialization In ABC VRPSTW, we are minimizing the travelling cost We represent each solution as a collection of integer- (time) of the vehicles. And, the probability pi of selecting valued vectors. Each vector correspondds to a vehicle and a Food Source i is determined using the expression, pi = the elements in each vector is the customer served by that 1/W (i) , where, W (i) is the cost of the Food Source i vehicle. Therefore, each vector represents a route consisting X m 1/W (i) of sequentially served customer numbers, with Depot 0 fixed j=1 at the staring and ending position respectively. and m is the total number of food sources. The initialization process starts by assigning a randomly gen- D. Cost Evaluation erated solution to every employed bee. The steps of generating In ABC VRPSTW, the traveling cost of each solution a single initial solution maintaining all the constraints is listed is the summation of the cost of all the routes within it, below : including the penalties (if applicable) and the total number of • For a vehicle Ti , a random customer, i, is chosen and the window breaks is the summation of the number of customers demand of that customer is recorded. which are not served within the actual (i.e., unrelaxed) time  636 TABLE I window. Now, for each possible pair of customers, i and j, R ESULT OF ABC VRPSTW FOR P ROBLEM I NSTANCES R1 the cost to travel between them is fixed (cij ), which is the euclidian distance between customer i and j. This process is Problem Plan: 1 Plan: 2 Plan: 3 Instance done for all the routes within a solution. In this way, cost of R1 01 TTC = 702.832 TTC = 693.547 TTC = 685.425 initial solution and also for all newly generated neighborhood (V/R = 19) WB = 38 WB = 40 WB = 46 solution is evaluated. While evaluating the cost and deciding R1 02 TTC = 845.308 TTC = 843.145 TTC = 809.078 (V/R = 17) WB = 34 WB = 17 WB = 33 for selecting/discarding a solution, some important constraints R1 03 TTC = 760.591 TTC = 741.229 TTC = 720.608 must be considered: (V/R = 13) WB = 25 WB = 31 WB = 23 R1 04 TTC = 716.544 TTC = 716.92 TTC = 701.904 (V/R = 9) WB = 23 WB = 22 WB = 27 (1) Vehicle Capacity Constraint: Suppose k ∈ Ri denote a R1 05 TTC = 730.871 TTC = 681.056 TTC = 689.407 customer in the route Ri . For any route, Ri the Xsummation (V/R = 14) WB = 48 WB = 44 WB = 48 of demands of the customers on that route ( dk ) must R1 06 TTC = 774.15 TTC = 727.513 TTC = 721.074 (V/R = 12) WB = 39 WB = 42 WB = 38 k∈Ri be less than or equal to the capacity of the vehicle (Tq ). R1 07 TTC = 720.334 TTC = 726.048 TTC = 706.759 (V/R = 10) WB = 24 WB = 35 WB = 31 Otherwise, that solution is then abandoned. R1 08 TTC = 714.485 TTC = 693.932 TTC = 692.312 (V/R = 9) WB = 21 WB = 14 WB = 23 (2) Time Window Constraint: If a vehicle comes at R1 09 TTC = 732.423 TTC = 702.394 TTC = 705.68 (V/R = 11) WB = 44 WB = 47 WB = 33 any customer, i, within ari to ai or bi to bri , the customer can R1 10 TTC = 719.845 TTC = 688.768 TTC = 680.106 be served by the vehicle in exchange of penalty (due to the (V/R = 10) WB = 33 WB = 28 WB = 36 relaxation of time window). But if a vehicle comes before ari R1 11 TTC = 702.832 TTC = 693.547 TTC = 685.425 (V/R = 10) WB = 40 WB = 42 WB = 39 or after bri , the vehicle is not allowed to serve the customer R1 12 TTC = 713.885 TTC = 708.846 TTC = 694.521 and that solution is abandoned. (V/R = 9) WB = 18 WB = 17 WB = 21 VI. E XPERIMENTAL RESULTS TABLE II A. Experimental Platform R ESULT OF ABC VRPSTW FOR P ROBLEM I NSTANCES R2 Our code is written in C++ which is complied by Visual Problem Plan: 1 Plan: 2 Plan: 3 C++ complier. The program was run on a PC with Windows 7 Instance R2 01 TTC = 1048.266 TTC = 1033.272 TTC = 1013.48 operating system. The processor of the machine is Intel Core (V/R = 4) WB = 72 WB = 71 WB = 70 2 Duo with 2.0 GHz CPU having 3GB, RAM. R2 02 TTC = 1047.271 TTC = 996.663 TTC = 994.913 (V/R = 3) WB = 65 WB = 63 WB = 61 B. Instances of the Experiment R2 03 TTC = 924.348 TTC = 892.307 TTC = 890.59 (V/R = 3) WB = 49 WB = 51 WB = 46 Our algorithm is tested by the instances derived from the R2 04 TTC = 840.812 TTC = 840.812 TTC = 840.812 well known Solomons VRPTW benchmark problems. The 56 (V/R = 2) WB = 29 WB = 29 WB = 29 Solomon benchmark problems are divided into six groups (C1, R2 05 TTC = 1011.133 TTC = 1002.607 TTC = 1013.525 (V/R = 3) WB = 76 WB = 67 WB = 70 R1, RC1, C2, R2, RC2) of problem instances. They have R2 06 TTC = 944.149 TTC = 929.999 TTC = 927.861 been designed to put in evidence different factors which can (V/R = 3) WB = 53 WB = 54 WB = 54 make VRPTW instances more or less difficult. The customers’ R2 07 TTC = 889.948 TTC = 889.948 TTC = 889.948 (V/R = 2) WB = 45 WB = 45 WB = 45 positions are generated at random in Groups R1 and R2; they R2 08 TTC = 810.416 TTC = 810.416 TTC = 810.416 are clustered in Groups C1 and C2; and they are hybrid in (V/R = 2) WB = 22 WB = 22 WB = 22 Groups RC1 and RC2. R2 09 TTC = 907.421 TTC = 887.421 TTC = 885.173 (V/R = 3) WB = 52 WB = 53 WB = 52 C. Resuts R2 10 TTC = 1007.89 TTC = 927.984 TTC = 906.752 (V/R = 3) WB = 70 WB = 60 WB = 55 To do our experiments, we have to set the values of some R2 11 TTC = 923.154 TTC = 923.154 TTC = 923.154 inputs to the algorithm. On the basis of this values different (V/R = 2) WB = 55 WB = 55 WB = 55 experimentation plan is set up. These input parameters include, Number of Employed Bee, Number of Onlooker bee and the Number Iteration as the termination condition. The value of For each of the 56 problem instances, we have run Pmax is same for all the plans which 5% of the total route ABC VRPSTW algorithm for 30 times for all the three plans. duration (time window of the Depot). Since the VRPSTW But due to the shortage of space, we present only the average is a relaxation of VRPHTW, a new constraint that limits the of the 30 results for each case. We are giving the total maximum waiting time is clearly opposite to the spirit of the travelling cost and the number of window breaks in the result. VRPSTW [13]. So, the waiting time is ignored. The penalty The path cost and the penalty are not shown separately for coefficient is set equal to 1, i.e. a unit of time of time window space constraints. Table I to Table VI show the result of violation is assumed to be equivalent to a unit of distance ABC VRPSTW for all the six types of problem instance. travelled. Follwing are the other parameters of the 3 plans: Here, V /R means number of Vehicle (Route), T T C denotes • Plan 1: Number of Employed Bees = 250, Number of the Total Travelling Cost including penalty (if applicable) and Onlooker Bees = 50, Number of iterations = 500 W B is the number of Window Breaks. • Plan 2: Number of Employed Bees = 400, Number of VII. C OMPARISON WITH P REVIOUS R ESULTS Onlooker Bees = 150, Number of iterations = 1000 • Plan 3: Number of Employed Bees = 600, Number of For comparing our result with other results, we have mainly Onlooker Bees = 250, Number of iterations = 2000 followed a recent work (an iterative algorithm) on VRPSTW  637 TABLE VI R ESULT OF ABC VRPSTW FOR P ROBLEM I NSTANCES C2 TABLE III R ESULT OF ABC VRPSTW FOR P ROBLEM I NSTANCES RC1 Problem Plan: 1 Plan: 2 Plan: 3 Instance Problem Plan: 1 Plan: 2 Plan: 3 C2 01 TTC = 552.492 TTC = 541.204 TTC = 555.102 Instance (V/R = 3) WB = 83 WB = 84 WB = 80 RC1 01 TTC = 734.822 TTC = 662.116 TTC = 685.425 C2 02 TTC = 541.204 TTC = 545.275 TTC = 547.375 (V/R = 14) WB = 46 WB = 42 WB = 35 (V/R = 3) WB = 68 WB = 68 WB = 62 RC1 02 TTC = 726.541 TTC = 707.638 TTC = 686.768 C2 03 TTC = 549.445 TTC = 543.275 TTC = 541.204 (V/R = 12) WB = 38 WB = 36 WB = 34 (V/R = 3) WB = 38 WB = 44 WB = 40 RC1 03 TTC = 736.418 TTC = 693.801 TTC = 688.366 C2 04 TTC = 541.204 TTC = 541.204 TTC = 541.204 (V/R = 11) WB = 29 WB = 29 WB = 38 (V/R = 3) WB = 27 WB = 27 WB = 27 RC1 04 TTC = 784.583 TTC = 714.777 TTC = 723.93 C2 05 TTC = 547.347 TTC = 541.204 TTC = 539.347 (V/R = 10) WB = 20 WB = 24 WB = 20 (V/R = 3) WB = 76 WB = 80 WB = 74 RC1 05 TTC = 761.788 TTC = 777.822 TTC = 754.045 C2 06 TTC = 547.644 TTC = 545.275 TTC = 545.275 (V/R = 13) WB = 36 WB = 50 WB = 38 (V/R = 3) WB = 80 WB = 78 WB = 78 RC1 06 TTC = 726.772 TTC = 689.253 TTC = 655.299 C2 07 TTC = 453.275 TTC = 541.204 TTC = 540.204 (V/R = 11) WB = 42 WB = 30 WB = 33 (V/R = 3) WB = 74 WB = 74 WB = 72 RC1 07 TTC = 762.343 TTC = 710.73 TTC = 682.073 C2 08 TTC = 549.445 TTC = 541.204 TTC = 541.204 (V/R = 11) WB = 32 WB = 28 WB = 20 (V/R = 3) WB = 69 WB = 73 WB = 71 RC1 08 TTC = 695.782 TTC = 671.184 TTC = 660.81 (V/R = 10) WB = 18 WB = 17 WB = 17 TABLE VII C OMPARISON WITH SOME R1 INSTANCES Method BAL TS AR UTS IRCL ABC R1-01 V/R 17 16 14 14 14 12 TABLE IV %WB 72 65 24 45 68 32 R ESULT OF ABC VRPSTW FOR P ROBLEM I NSTANCES RC2 TTC 1885 1491 1370 1438 1633 1355.788 * R1-02 Problem Plan: 1 Plan: 2 Plan: 3 V/R 15 13 12 12 12 11 Instance %WB 83 69 47 61 63 17 * RC2 01 TTC = 1513.274 TTC = 1325.303 TTC = 1492 TTC 1636 1322 1265 1339 1404 1494.704 (V/R = 4) WB = 87 WB = 77 WB = 82 R1-03 RC2 02 TTC = 1418.888 TTC = 1401.51 TTC = 1398.89 V/R 13 11 11 11 11 10 (V/R = 3) WB = 87 WB = 78 WB = 78 %WB 86 77 59 73 93 24 * RC2 03 TTC = 1186.154 TTC = 1188.774 TTC = 1117.516 TTC 1452 1184 1066 1168 1374 1346.573 * (V/R = 3) WB = 79 WB = 79 WB = 70 R1-09 RC2 04 TTC = 800.1 TTC = 988.399 TTC = 996.638 V/R 13 12 11 11 11 10 (V/R = 3) WB = 51 WB = 61 WB = 65 %WB 95 84 60 75 93 28 * RC2 05 TTC = 1409.935 TTC = 1282.244 TTC = 1230.794 TTC 1445 1154 1084 1168 1393 1359.701 * (V/R = 4) WB = 81 WB = 72 WB = 73 RC2 06 TTC = 1046.34 TTC = 1343.431 TTC = 1441.98 (V/R = 3) WB = 50 WB = 76 WB = 78 RC2 07 TTC = 845.514 TTC = 1141.701 TTC = 1141.701 problem [13]. Our result is compared with the work by (V/R = 3) WB = 37 WB = 63 WB = 63 Balakrishnan (1993) [8] (denoted BAL), Chiang and Russell RC2 08 TTC = 845.025 TTC = 798.672 TTC = 829.881 (2004) [10] which use two solution methods, tabu search (V/R = 3) WB = 41 WB = 33 WB = 40 (TS) and advance recovery (AR) (denoted by TS and AR) respectively, Fu et al. (2008) [14] using the unified tabu search method (denoted UTS) and An iterative route construction solution(2010) proposed by Miguel Andres Figliozzi [13] TABLE V (denoted IRCL). R ESULT OF ABC VRPSTW FOR P ROBLEM I NSTANCES C1 For this comparison, we reran ABC VRPSTW assuming a reduced number of vehicles (than in the datasets) to match Problem Plan: 1 Plan: 2 Plan: 3 Instance with the other results. We could only consider a subset of C1 01 TTC = 701.046 TTC = 730.508 TTC = 609.673 the instances for comparison with all the previous solutions (V/R = 10) WB = 68 WB = 64 WB = 67 because not all datasets were considered in those works. This C1 02 TTC = 707.075 TTC = 707.638 TTC = 666.554 comparison is given in Table VII and Table VIII for some (V/R = 10) WB = 50 WB = 54 WB = 48 C1 03 TTC = 614.069 TTC = 544.423 TTC = 501.667 instances of R1 and RC1 data respectively. In the Table, “*” (V/R = 10) WB = 34 WB = 38 WB = 34 is used to indicate the improvement of the solution. C1 04 TTC = 887.610 TTC = 588.929 TTC = 551.564 (V/R = 10) WB = 20 WB = 19 WB = 17 C1 05 TTC = 726.826 TTC = 641.041 TTC = 555.041 (V/R = 10) WB = 64 WB = 69 WB = 60 C1 06 TTC = 634.823 TTC = 550.415 TTC = 545.012 VIII. F UTURE W ORKS AND C ONCLUSION (V/R = 10) WB = 61 WB = 65 WB = 62 C1 07 TTC = 715.479 TTC = 618.656 TTC = 602.208 In this paper we have considered a variant of the VRPTW (V/R = 10) WB = 55 WB = 60 WB = 55 where the time window is soft, i.e., it can be violated with C1 08 TTC = 746.830 TTC = 689.983 TTC = 605.208 some penalty cost. It would be interesting to apply our method (V/R = 10) WB = 56 WB = 54 WB = 50 C1 09 TTC = 707.618 TTC = 626.299 TTC = 595.505 on another variant where the time window is hard, that is it (V/R = 10) WB = 45 WB = 36 WB = 31 cannot be violated at any cost. Also in all of our experiments the number of vehicles in the fleet was an input to the problem. Optimizing the number of vehicles as well as the  638 TABLE VIII C OMPARISON WITH SOME RC1 INSTANCES [4] C.-H. Chen. and C.-J. Ting, “A HYBRID ANT COLONY SYSTEM FOR VEHICLE ROUTING PROBLEM WITH TIME WINDOWS,” Method BAL TS AR UTS IRCL ABC Journal of the Eastern Asia Society for Transportation Studies, vol. 6, RC1-01 pp. 28222836, 2005. V/R 14 14 13 13 13 11 [5] M.-C. Lai, “A hybrid genetic/benders’ algorithm with applications to %WB 56 71 39 64 93 32 * vehicle routing and scheduling problems,”Doctoral Dissertation, pp. 209, TTC 1839 1521 1424 1529 1778 1305.142 * 2004. RC1-02 [6] P. Dippold and S. H¨ ackel, “The bee colony-inspired algorithm (BCiA): V/R 13 13 11 12 12 10 a two-stage approach for solving the vehicle routing problem with time %WB 88 76 58 81 98 27 * windows,”Annual conference on Genetic and evolutionary computation, TTC 1850 1384 1375 1413 1635 729.182 * pp. 25-32, 2009. [7] Y. A. Koskosidis, W. B. Powell and M. M. Solomon, “An RC1-03 Optimization-Based Heuristic for Vehicle Routing and Scheduling with V/R 12 11 10 11 10 10 Soft Time Window Constraints,” Transportation Science, vol. 26, pp. %WB 82 92 69 86 83 16 * 6985, May 1992. TTC 1496 1243 1183 1254 1256 1284.448 [8] N. Balakrishnan, “Simple Heuristics for the Vehicle Routeing Problem RC1-06 with Soft Time Windows,” Journal of the Operational Research Society, V/R 12 12 11 11 11 10 vol. 44, pp. 279287, 1993. %WB 71 81 61 81 80 23 * ´ Taillard, [9] P. Badeau, M. Gendreau, F. Geurtin, J.-Y. Potvin and E. TTC 1496 1338 1223 1336 1522 1303.646 * “A tabu search heuristic for the vehicle routing problem with soft time windows,” Transportation Science, vol. 31, pp. 170186, May 1997. [10] W.-C. Chiang. and R. A. Russell, “A metaheuristic for the vehicle- total travelling cost is our next goal. And it would be worth routening problem with soft time windows,” Journal of the Operational Research Society, vol. 55, pp. 12981310, Dec. 2004. experimenting applying this metaheuristic on other variants of [11] H. I. Calvete, C. Gal´ e, M.-J. Oliveros and B. S´ anchez-Valverde, Vehicle Routing Problem also. “A goal programming approach to vehicle routing problems with soft time windows,” European Journal of Operational Research, vol. 177, pp. R EFERENCES 17201733, Nov. 2005. [12] D. Karaboga, “An Idea Based on Honey Bee Swarm for numerical [1] J. K. Lenstra and A. H. G. R Kan, “Complexity of vehicle routing optimization,” Technical Reports, TR06, Oct. 2005. and scheduling problems,” Networks, vol. 11, pp. 221227, Oct. 2006. [13] M. A. Figliozzi, “An iterative route construction and improvement [2] A. Imran, S. Salhi and N. A. Wassan, “Avariableneighborhood-based algorithm for the vehicle routing problem with soft time windows,” heuristic for the heterogeneous fleetvehicleroutingproblem,” European Transportation Research Part C, vol. 18, pp. 668679, Oct. 2010. Journal of Operational Research, vol. 197, pp. 509518, July 2008. [14] R. Eglese, Z. Fu and L. Y. O. Li, “A unified tabu search algorithm [3] Z. Z. Yang and B. Yu, “An Ant Colony Optimization Model: the Period for vehicle routing problems with soft time windows,” Journal of the Vehicle Routing Problem with Time Windows,” Transportation Research Operational Research Society, vol. 59, pp. 663673, 2008. Part E: Logistics and Transportation Review, vol. 47, pp. 166181, Oct. 2010.