1. INTRODUCTION
ransportation supports most of the social and economic activities. The annual cost of excess travel in U.S.A. has been estimated approximately 45 billion USD [68] and the turnover of transportation of goods in Europe is approximately 168 billion USD per year. In United Kingdom, France and Denmark transportation represents approximately 15%, 9% and 15% of national expenditures respectively [70]. It is well known fact that the vehicle routing problem is a combinatorial optimization and integer programming problem in which service to finite number of customers with a fleet of vehicles is being done. Vehicle routing problem was proposed by Dantzig and Ramser in 1959. Vehicle routing problem is an important optimization problem in the fields of distribution, transportation, and logistics. In Vehicle Routing problem, goods have to be delivered to the customers who have placed orders for such goods in such a way so that the total cost of the delivering of goods to the customers can be minimized. In VRP each and every customer has a given demand and no any vehicles can service more customers than its predefined capacity. Many algorithms have been designed by researchers for searching for good solutions to the problem, but no any polynomial time algorithms have been designed which can give the exact solution of Vehicle Routing problem with time windows in the polynomial time in the worst case. There are several variations of the vehicle routing problems. In Vehicle Routing Problem with Pickup and Delivery, a large number of goods have to be moved from certain pickup locations to other delivery locations and the goal is to find optimal routes for vehicles to visit the pickup and drop-off locations so that the cost of delivering the goods to the different locations can be minimmized. In Vehicle Routing Problem with LIFO pinciple, a large number of goods have to be moved from certain pickup locations to other delivery locations and the goal is to find optimal routes for vehicles to visit the pickup and drop-off locations so that the cost of delivering the goods to the different locations can be minimmized with the restriction of the item being delivered must be that item most recently picked up. The benefit of this scheme over the previous scheme is the reduction of the loading and unloading times at delivery locations because there is no need to temporarily unload items. In Vehicle Routing Problem with Time Windows, there are n numbers of cities. Each and every city has a particular time windows [R (v), D (v)]. Where R (v) represents the releasing time for a particular vertex and D(v) represents the deadline for a particular vertex and the goal is to visit the maximum number of cities with in their time windows. Time windows are when they can be considered non biding for penalty cost. Time windows are called hard when they cannot be violated, i.e. if any vehicle reaches to a particular city too early so it must wait unless and until the time windows opens and the vehicle is not allowed to arrive late. In Capacitated Vehicle Routing Problem, the vehicles have limited capacity of the goods that must be delivered. In Capacitated Vehicle Routing Problem with time windows [R(v),D(v)], the vehicles have limited capacity of the goods that must be delivered. The most important application of VPRTW includes deliveries to supermarkets, industrial refuse collection, routing of school bus, security patrol services, urban newspaper distribution etc. The Vehicle Routing Problem with Time Windows has already been studied in the literature of Operations Research ( [1,10]). Different heuristics [9,17,18,19] like Simulated Annealing, local search, Genetic algorithms, cutting plane and branch and bound methods [20,14,16] have been proposed to get the optimal solution of this problem. For general graphs, when there are a constant number of different time windows Chekuri and Kumar [8] gave a constant-factor T (MDVRP) customers get their deliveries from several depots. In VRP with Time Windows [71] each and every customer has time window (R[v], D[v]) where D [v] represents the deadline for a particular customer while R[v] represents the releasing time for a particular customer and the goal is to visit the maximum number of customers in their time windows (R[v], D [v]). In Stochastic VRP (SVRP) any customer may have a random behavior. In Periodic VRP (PVRP) delivery to the customer is being done in some days. In Split Delivery VRP (SDVRP) several vehicles serve a customer. In the split delivery vehicle routing problem (SDVRP) there is no any restriction of visiting each and every customer exactly visited once.
Additionally, the demand of each and every customer may be greater than the capacity of the vehicles. It is well known fact that the SDVRP is NP-hard problem, even under restricted conditions on the costs, when each and every vehicle have a capacity greater than two, But it can be solved in the time complexity of polynomial time when the vehicles have a maximum capacity of two. The cost saving that which can be obtained by allowing split deliveries can be up to 50% of the cost of the optimal solution of the VRP.
The variant of the VRP [71] in which the demand of a customer may be greater than the vehicle capacity, but vehicle has to serve every customer minimum number of the possible time. The cost saving which can be obtained by allowing more than the minimum number of required visits to each and every customer to be served by vehicle can be again up to 50%. Simple heuristics that serve the customers with demands greater than the vehicle capacity by full load out-andback trips until the demands become less than the vehicle capacity may be quite far from the optimal solution.
Three heuristic methods [71] have been already proposed for the solution of the SDVRP: The local search, a simple and effective tabu search algorithm and a sophisticated heuristic which uses the information collected during the tabu search, builds promising routes and solves MILP models to decide which routes to use and how to serve the customers through those routes to obtain the solution which is close to the optimal solution. The heuristics will be compared on a set of benchmark instances.
In VRP with Backhauls (VRPB) vehicle must pick something up from the customer after all deliveries are done to the customers. VRP with Backhauls (VRPB) is also known as the linehaul-backhaul problem which is an extension of the Capacitated VRP (CVRP) where the customer set is partitioned into two subsets. The first subset contains the linehaul customers; each requires a given quantity of product which has to be delivered. The second subset contains the backhaul customers, where a given quantity of inbound product must be picked up. This customer partition is extremely frequent in practical situations. Grocery industry is a common example, where supermarkets and shops are the linehaul customers and grocery suppliers are the backhaul customers. It has been widely recognized that in this mixed distribution-collection context a significant saving in transportation costs can be achieved by visiting backhaul customers in distribution routes. More precisely, the VRPB [71] can be stated as the problem of determining a set of vehicle routes visiting all customers, and (a) each vehicle performs exactly one route; (b) each route starts as well as finishes at the depot; (c) for each route the total load associated with linehaul and backhaul customers should never exceed, separately, the vehicle capacity; (d) on each route the backhaul customers, are visited after all linehaul customers; and (e) the total distance traveled by the vehicles to serve the customers is minimized. The constraint (d) is practically motivated by the fact that vehicles are rear loaded which proves that the onboard load rearrangement required by a mixed service is difficult to carry out at customer locations. The most important reason is that, in many applications, line haul customers have a higher service priority as compared to backhaul customers. In VRP with Pick-Ups and Deliveries (VRPPD) the vehicle picks something up and delivers it to the customer. There are two sets of decision variables x and s. For ?j, i?n+1, j?0 and each vehicle each edge (I,j) where i k we define x ijk as If V[72] represents set of vehicles and all vehicles are considered to be identical. C represents set of customers. G=(N, A) represents directed graph where N represents the set of vertices of graph while E represents the set of edges of graph. This particular directed graph consists of |C|+2 number of vertices, where customers are denoted 1,2,3,????,n and the depot is represented by the vertex "0"(the starting depot) and the vertex "n+1"(the returning depot). N is the set of vertices. There is no edge ending at the vertex "0" or originating from the vertex "n+1". c ij ( where i?j) represents the cost of traveling from the vertex I to the vertex j. t ij ( where i?j) represents the service time at the customer i. Each vehicle has a capacity q and each customer i has a demand d i . Each and every customer has a time window [a i , b i ] and a vehicle must arrive at the customer before b i . If any vehicle arrives to the customer before the time windows opens, that vehicle has to be wait until ai to service the customer. The time windows for both depots are assumed to be identical to [a 0 ,b 0 ] which represents the scheduling horizon. The vehicle cannot leave the depot before a 0 and must The decision variable s ik is defined for each and vertex i and each vehicle k and denoted the time when the vehicle k starts to service the customer i. When the vehicle k does not service to the customer i, sik has no meaning and consequently its value is considered irrelevant. As we have assumed a 0 =0 and therefore s 0k =0 for all k. The goal in the case of VRPTW is to design a set of routes that minimizes the total cost, such that 1, if vehicle k drives directly from vertex i to the vertex The above informal definition of VRPTW can be stated mathematically as a multicommodity network flow problem with time windows and the capacity constraints:
The main goal of the objective function ( 1) is to minimize the total travel cost. The constraint (2) ensures that each customer is visited exactly once while constraint (3) ensures that a vehicle can only be loaded up to its capacity. Equations 4 indicated that each and every vehicle must leave the depot 0. Equation 5indicates that when a vehicle arrives at a customer it must leave for another destination. Equation 6indicates that all vehicles must arrive at the depot n+1. Inequality (7) indicates the relationship between the departure time of vehicle from the customer and its immediate successor. Constraint (8) indicates the observation of time windows. Integrality constraints are shown by (9). The model for the representation of VRPTW can also incorporate a constraint giving an upper bound on the number of vehicles, as is the case in Desrosiers, Dumas, Solomon and Soumis [59].
2. III. VEHICLE ROUTING PROBLEM WITH TIME WINDOWS IS NP COMPLETE PROBLEM
Sorting algorithms like selection sort, bubble sort, insertion sort are known as quadratic sorting because these algorithms have time complexity of O(n 2 ) in the worst case where n is the size of input. Sorting algorithms like counting sort, radix sort and bucket sort have linear time complexity in the worst case So these algorithms are known as sorting in linear time. It is well known fact that all problems cannot be solved in polynomial time in the worst case. For example, Turing's famous "Halting Problem," which cannot be solved by any computer, no matter how much time is provided. Those problems that can be solved, but in time O(n k ) for any constant k are known as tractable problems or easy problems. For example sorting algorithms like selection sort, bubble sort, insertion sort, counting sort, radix sort and bucket sort can give sorted output in the time complexity of polynomial time so sorting problems are tractable problems or easy problems. Those problems that can not be solved, in polynomial time O(n k ) for any constant k but they require super-polynomial time for their executions are known as intractable problems or hard problems. No polynomial-time algorithm has yet been discovered for an NP-complete problem which can solve the problem in the polynomial time in the worst case nor anyone has been able to prove that no polynomial-time algorithm can exist for any one of NPcomplete problems. So P ? NP question has been one of the deepest, most perplexing open research problems in theoretical computer science since it was first proposed in 1971.
The class P consists of those problems which can be solved in polynomial time in the worst case. More specifically, they are problems that can be solved in time O(n k ) for some constant k, where n is the size of the input to the problem. Problems like sorting problem, searching problems are in class P. The class NP consists of those problems that are "verifiable" in polynomial time. If a "certificate" of a solution is being given, then we could verify that the certificate is correct in time polynomial in the size of the input to the problem. x ijk = { 1, if vehicle k drives directly from vertex i to the vertex 0, otherwise. min? ? ?c ij x ijk such that (1) As it well known fact that approximation algorithms give the approximation result which is close to the optimal value to a particular problem. Most of the problems of practical significance are NP-complete but we cannot avoid them. There are three approaches to getting around NP-completeness of the problems. First, if the size of inputs is small, an algorithm which has exponential running time may be a satisfactory algorithm to solve a problem. Second, we may isolate those special cases that are solvable in polynomial time. Third, we can find out the solution which is close to the optimal solution of the problem and that solution can be easily found out with the help of the polynomial time approximation algorithm. Suppose there is an optimization problem in which each potential solution has a positive cost. It is well known fact that the optimization problem can be divided in the two parts.
k?V i?N j?N ? ?x ijk =1 ? i? C (2) k?V j?N ? d i ?x ijk ?q ? k? V (3) i?C j?N ?x 0jk =1 ? k? V (4) j?N ? x ihk -?x hjk =0 ? h? C, ? k? V, (5) i?N j?N ?x i,n+1,k =1 ? k? V(6The maximization problem and the minimization problem. In maximization problem, we want to maximize the value of output to a problem and in minimization problem we want to minimize the value of output. If the size of the input of a problem is n. Let C* be the cost as being obtained by optimal solution of a problem and C is the cost as being obtained by approximation algorithm [49]. Then the approximation ratio ? (n) is defined as Maximum The definitions of approximation ratio and of ? (n)-approximation algorithm apply for both minimization and maximization problems. It is well known fact that for a maximization problem, 0 < C ? C*and the ratio C*/C gives the ratio by which the cost of optimization algorithm is larger than that of the cost of the approximate solution. Also, for a minimization problem, 0 < C* ? C, and the ratio C/C* gives the ratio by which the cost of the approximate solution is greater than the cost of an optimal solution. Since all solutions are assumed to have positive cost, these ratios are always well defined. Also the approximation ratio of an approximation algorithm [49] is never less than 1. For some problems, there are polynomial-time approximation algorithms which have small constant approximation ratios, but for other problems, the best known polynomial-time approximation algorithms have approximation ratios that grow as functions of the size of input of the problem.
An approximation scheme for an optimization problem [49] is defined as an approximation algorithm which takes as input an instance of the problem, along
3. IV. COMPARISON OF APPROXIMATION ALGORITHMS FOR VEHICLE ROUTING PROBLEM
Arkin, Mitchell and Narasimhan [26] gave first non-trivial (2+?) approximation algorithm for orienteering points in the Euclidean plane. A. Blum, S. Chawla, D. Karger, T. Lane, A. Meyerson, and M. Minkoff [6] gave the first approximation algorithm with a ratio of 4 for points in arbitrary metric spaces. After then N. Bansal, A. Blum., S. Chawla, and A. Meyerson [24] designed a new approximation algorithm for orienteering problem which improved this ratio to 3. A related problem to the orienteering problem is the minimum excess problem as being defined in [6]. In [6] the pseudo code for the orienteering problem depends upon the pseudo code of the min-excess problem. Also the min-excess problem can be approximated using algorithms for the k-stroll problem. In the k-stroll problem, the goal is to find a minimum length walk from source vertex s to target vertex t that visits at least k vertices. It is well known fact that k-stroll problem and the orienteering problem are equivalent to each other in terms of exact solvability because in both of these problems, the mission is to find the minimum length path from the source vertex s to the destination vertex t which covers maximum number of distinct vertices. The results in [6,24] are based on existing approximation algorithms for k-stroll in undirected graphs. N. Bansal, A. Blum, S. Chawla and A. Meyerson. [24] gave approximation algorithm for Deadline-TSP which has the time complexity of O(logn) and they gave approximation algorithm for Vehicle Routing problem with time windows which has time complexity of O (log n) . Further they gave a bicriteria approximation algorithm for Deadline-TSP as well as for Vehicle Routing problem with time windows. If ? > 0, their bicriteria approximation algorithm produces a log (1/?) approximation, while deadlines exceeds by a factor of (1+?). C. Chekuri, N. Korula, and M. Pal [42] designed (2+?) approximation for orienteering in undirected graphs, which improves upon the 3-approximation of [24]. C. Chekuri, N. Korula, and M. Pal [42] designed an improved O (log OPT) approximation for orienteering in directed graphs, where OPT<= n is the number of vertices visited by an optimal solution which improves over the previously result. Further it was being proved that for the time-window problem, an O (log OPT) approximation can be easily achieved even for directed graphs if the algorithm is allowed quasi-polynomial time.
If D(v) represents the deadline for a particular vertex v and R(v) represents the releasing time for a particular vertex v. Let L(v) = D(v) ? R(v) denotes the length of the directed graphs. C. Chekuri and N. Korula. Designed an O(alog Lmax) approximation when R(v) and D(v) both are integer valued for each v and they designed an O(a max{log OPT, log Lmax/Lmin }) approximation. They also designed an O(log Lmax/Lmin) approximation when there is no starting vertex and terminating vertex is being defined. Early surveys of solution techniques for the VRPTW [67] can be found in Golden and Assad [57], Desrochers et al. [58], and Chiang & Russell [66]. Desrosiers et al. [59] and Cordeau et al. [60] gave exact solution techniques for VRPTW. The complete explanation of these exact techniques can be found in Larsen [61] and Cook and Rich [62]. Researchers designed different approximation algorithms for VRPTW based on different designing techniques like Dynamic programming, Simulated Annealing etc. Fleischmann [63] and Taillard et al. [64] have used heuristic for VRP without time windows. In Taillard et al. [64], have designed solutions to the classical vehicle routing problem by using a TS heuristic. The routes which are obtained combine to produce workdays for the vehicles by solving a bin packing problem, an idea which is previously introduced in Fleischmann [63]. Compbell and Savelsbergh [65] has reported about insertion heuristics which can efficiently handle different types of constraints including time windows and multiple uses of vehicles. Compbell and Savelsbergh [65] introduced the home delivery problem which is the variant of Vehicle Routing problem and it is more closely related to realworld applications. Current VRPTW heuristics can be categorized as follows: (i) construction heuristics, (ii) improvement heuristics and (iii) meta-heuristics. Construction heuristics are sequential or parallel algorithms which aims at designing initial solutions to routing problems that can be easily improved upon by meta-heuristics or improvement heuristics. Sequential algorithms are being used to build a route for each vehicle, one after another with the help of decision functions for the selection of the customer which has to be inserted in the route and the insertion position within the route. Parallel algorithms build the routes for all vehicles in parallel by using a pre-computed estimate of the number of routes. As it has been already discussed that the best known polynomial time approximation ratios for Vehicle Routing problem with time windows are O (log OPT) for undirected graphs and O (log OPT) in directed graphs.
In this paper, a study on variants of vehicle routing problem is being done along with the difference in the approximation ratios of approximation algorithm as being given by researchers and it is found that Researchers are continuously applying their best efforts to design new approximation algorithms which have better approximation ratio as compared to the previously existing approximation algorithms. Researchers are proposing new heuristics for variants of Vehicle Routing problems.
| Any problem will be lie in the class NPC-and we refer to |
| it as being NP-complete-if the problem is in NP and is |
| as "hard" as any problem in NP. The first NP complete |
| problem is the circuit-satisfiability problem, in which we |
| are given a Boolean combinational circuit which is being |
| consists of AND, OR, and NOT gates and the question |
| is to know whether there is any set of Boolean inputs to |
| this circuit that causes its output to be 1.It is well known |
| fact that the concept of NP-complete was firstly |
| introduced by Stephen Cook in 1971 in a paper entitled |
| "The complexity of theorem-proving procedures" on |
| pages 151-158 of the Proceedings of the 3rd Annual |
| ACM Symposium on Theory of Computing, Although the |
| term NP-complete did not appear anywhere in his |
| paper. At that conference, there was a debate among |
| the computer researchers about whether NP-complete |
| problems could be solved in polynomial time on a |
| deterministic Turing machine or not. At that time, John |
| Hopcroft brought everyone at the conference to a |
| consensus that the question of whether NP-complete |
| problems are solvable in polynomial time or not must be |
| put off to be solved at some later time ,since nobody |
| had any formal proofs for their claims. No any scientist |
| has yet been able to prove conclusively whether NP- |
| complete problems are solvable in polynomial time or |
| not. Also The Clay Mathematics Institute is offering a |
| US$1 million reward to any researcher who has a formal |
| proof that P=NP or that P?NP. Researchers are |
| continuously doing hard work in this field to give the |
| formal prove of either P=NP or P?NP but did not |
| achieve success in this field till date. Also In the |
| celebrated Cook-Levin theorem, Cook proved that the |
| Boolean satisfiability problem is NP-complete problem. |
| In 1972, Richard Karp proved that several other |
| problems are also NP-complete; So it shows that there |
| is a class of NP-complete problems. Satisfiability,0-1 |
| Integer Programming, Clique, Set ,Vertex Cover, Set |
| Covering, Feedback Node Set ,Feedback Arc Set, |
| Directed Hamilton Circuit Undirected Hamilton Circuit j?N ,Satisfiability With At Most 3 Literals Per Clause, xijk (sik+ tij-sjk)?0 ? i,j?N, ? k?V (7) Chromatic Number ,Cover, Exact, Hitting, Steiner Tree, |
| (8) 3-Dimensional Matching Knapsack (Karp's definition of Knapsack is closer to Subset sum), Job Sequencing, ai?sik?bi ? i,?N, ? k?V Partition Max Cut. After then, thousands of other |