# 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]. # 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(6 The 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 # 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. ![(a) Each customer is being served by vehicle exactly once. (b) Every route starts at the vertex 0 and ends at vertex n+1. (c) The time windows of the customers and capacity constraints of the vehicles are being observed carefully.](image-2.png "") Any problem will be lie in the class NPC-and we refer toit as being NP-complete-if the problem is in NP and isas "hard" as any problem in NP. The first NP completeproblem is the circuit-satisfiability problem, in which weare given a Boolean combinational circuit which is beingconsists of AND, OR, and NOT gates and the questionis to know whether there is any set of Boolean inputs tothis circuit that causes its output to be 1.It is well knownfact that the concept of NP-complete was firstlyintroduced by Stephen Cook in 1971 in a paper entitled"The complexity of theorem-proving procedures" onpages 151-158 of the Proceedings of the 3rd AnnualACM Symposium on Theory of Computing, Although theterm NP-complete did not appear anywhere in hispaper. At that conference, there was a debate amongthe computer researchers about whether NP-completeproblems could be solved in polynomial time on adeterministic Turing machine or not. At that time, JohnHopcroft brought everyone at the conference to aconsensus that the question of whether NP-completeproblems are solvable in polynomial time or not must beput off to be solved at some later time ,since nobodyhad any formal proofs for their claims. No any scientisthas yet been able to prove conclusively whether NP-complete problems are solvable in polynomial time ornot. Also The Clay Mathematics Institute is offering aUS$1 million reward to any researcher who has a formalproof that P=NP or that P?NP. Researchers arecontinuously doing hard work in this field to give theformal prove of either P=NP or P?NP but did notachieve success in this field till date. Also In thecelebrated Cook-Levin theorem, Cook proved that theBoolean satisfiability problem is NP-complete problem.In 1972, Richard Karp proved that several otherproblems are also NP-complete; So it shows that thereis a class of NP-complete problems. Satisfiability,0-1Integer Programming, Clique, Set ,Vertex Cover, SetCovering, 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 otherxijk ?{0,1} ? i,j?N, ? k?V(9) Hamiltonian-cycle problem is in class NP because In Hamiltonian-cycle problem, directed graph G = (V, E) is being given, and then certificate of this problem would be a sequence problems have been shown to be NP-complete problems by reductions from other problems previously shown to be NP-complete. There is no any algorithm which can solve Vehicle Routing Problem with time windows in the polynomial time in the worst case. It is well known fact that Vehicle Routing Problem with time windows is NP complete problem. © 2011 Global Journals Inc. (US) Towards The Solution of Variants of Vehicle Routing Problem * EMReingold JNievergelt NDeo Combinatorial Algorithms: Theory and Practice Prentice-Hall 1977 * A review of scheduling research involving setupconsiderations JAllahverdi TGupta Aldowaisan Omega, Int. Journal of Management Science 27 1999 * Resource-constrained geometric network optimization EMArkin JS BMitchell GNarasimhan Symposium on Computational Geometry 1998 * Improved approximation guarantees for minimumweight k-trees and prizecollecting salesmen BAwerbuch YAzar ABlum SVempala Siam J. Computing 28 1 1999 * On approximating a geometric prize-collecting traveling salesman RBar-Yehuda GEven SShahar Proceedings of the European Symposium on Algorithms the European Symposium on Algorithms 2003 * Approximation algorithms for orienteering and discounted-reward tsp SBlum DChawla TKarger ALane MMeyerson Minkoff Proceedings of the 44th Foundations of Computer Science the 44th Foundations of Computer Science 2003 * Complexity of task sequencing with deadlines, set-up times and changeover costs JBruno PDowney SIAM Journal on Computing 7 4 1978 * Approximation algorithms for the traveling repairman and speeding deliveryman problems with unit-time windows GNFrederickson BWittman Proceedings of APPROX-RANDOM APPROX-RANDOM 2007 4627 * A new optimization algorithm for the vehicle routing problem with time windows MDesrochers JDesrosiers MSolomon Operations Research 40 1992 * Vehicle routing with time windows: optimization and approximation MDesrochers JLenstra MSavelsbergh FSoumis Vehicle Routing: Methods and Studies BLGolden AAAssad North-Holland, Amsterdam 1988 * The orienteering problem BGolden LLevy RVohra Naval Research Logistics 34 1987 * Scheduling jobs in a alcan aluminium factory using a genetic algorithm MGravel WPrice CGagn International Journal of Production Research 38 13 2000 * A two-phase genetic algorithm to solve variants of the batch sequencing problem CJordan International Journal of Production Research (UK) 36 3 1998 * The orienteering problem with time windows MKantor MRosenwein Journal of the Operational Research Society 43 1992 * A 2-approximation algorithm for the multi-vehicle scheduling problem on a path with release and handling times YKaruno HNagamochi Proceedings of the European Symposium on Algorithms the European Symposium on Algorithms 2001 * Vehicle routing with time windows ARKolen HKan Trienekens Operations Research 35 1987 * Vehicle Routing with Time Windows using Genetic Algorithms, Application Handbook of Genetic Algorithms: New Frontiers SThangiah II. Lance Chambers 1995 CRC Press * Heuristic methods for vehicle routing problem with time windows KTan LLee KZhu Proceedings of the 6th AI and Math the 6th AI and Math 2000 * Local search for routing problems with time windows MSavelsbergh Annals of Operations Research 4 1985 * Algorithms for the vehicle routing problems with time deadlines SRThangiah IHOsman RVinayagamoorthy TSun American Journal of Mathematical and Management Sciences 13 3&4 1993 * Special cases of traveling salesman and repairman problems with time windows JTsitsiklis Networks 22 1992 * A survey of u.s. manufacturing practices in make-to-order machine shops JWisner SSiferd Production and Inventory Management Journal 1 1995 * Survey of scheduling research involving setup times WYang CLiao International Journal of Systems Science 30 2 1999 * Approximation algorithms for deadline-TSP and vehicle routing with time-windows NBansal ABlum SChawla AMeyerson Proceedings of the 36th Annual ACM Symposium on Theory of Computing the 36th Annual ACM Symposium on Theory of ComputingNew York, NY, USA ACM 2004 * RKAhuja TLMagnanti JBOrlin Network Flows: Theory, Algorithms, and Applications * PrenticeHall 1993 Upper Saddle River, New Jersey * Resource-constrained geometric network optimization EMArkin JS BMitchell GNarasimhan Symposium on Computational Geometry 1998 * A 2 + ? approximation algorithm for the k-MST problem SArora GKarakostas Preliminary version in Proc. of ACM-SIAM SODA 2006. 2000 107 * Improved approximation guarantees for minimumweight k-trees and prizecollecting salesmen BAwerbuch YAzar ABlum SVempala Proc. of ACM STOC of ACM STOC 1998. 1995 28 * The prize collecting traveling salesman problem EBalas Networks 19 6 1989 * On the worst-case performance of some algorithms for the asymmetric traveling salesman problem AMFrieze GGalbiati FMaffioli Networks 12 1 1982 * On approximating a geometric prize-collecting traveling salesman problem with time windows RBar-Yehuda GEven SShahar Preliminary version in Proc. Of ESA 2005. 2003 55 * A 3-approximation for the minimum tree spanning k vertices NGarg Proceedings of the 37th Annual Symposium on Foundations of Computer Science the 37th Annual Symposium on Foundations of Computer Science IEEE Computer Society 1996 * A Constant-Factor Approximation Algorithm for the k-MST Problem RBlum SRavi Vempala Preliminary version in Proc. Of ACMSTOC 1999. 1996 58 * Paths, trees, and minimum latency tours KChaudhuri BGodfrey SRao KTalwar 44th Annual Symposium on Foundations of Computer Science IEEE Computer Society 2003 * Maximum coverage problem with group budget constraints and applications CChekuri AKumar Proceedings of APPROXRANDOM APPROXRANDOM 2004 * A recursive greedy algorithm for walks in directed graphs CChekuri M Proceedings of the 46th Annual Symposium on Foundations of Computer Science the 46th Annual Symposium on Foundations of Computer Science IEEE Computer Society 2005 * An O(log n) Approximation for the Asymmetric Traveling Salesman Path Problem Theory of Computing CChekuri M Preliminary version in Proc. of APPROX 2007. 2005 3 * Saving an epsilon: a 2-approximation for the k-MST problem in graphs NGarg Proceedings of the 37th Annual ACM Symposium on Theory of computing the 37th Annual ACM Symposium on Theory of computing ACM 2005 * A general approximation technique for constrained forest problems MXGoemans DPWilliamson SIAM Journal on Computing 24 1995 * The orienteering problem BLGolden LLevy RVohra Naval Research Logistics 34 3 1987 * The traveling salesman problem and its variations GGutin APPunnen 2002 Springer Berlin * Improved Algorithms for Orienteering and Related Problems CChekuri NKorula MP´al * Proc. of ACM-SIAM SODA of ACM-SIAM SODA January 2008 * Nagarajan and R. Ravi. Poly-logarithmic approximation algorithms for directed vehicle routing problems ELLawler AH GKan JKLenstra DBShmoys Proceedings of APPROXRANDOM APPROXRANDOM John Wiley & Sons Inc 1985. 2007 44 The Traveling salesman problem: a guided tour of combinatorial optimization * PToth DVigo The vehicle routing problem. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial Mathematics Philadelphia PA 2001 * Special cases of traveling salesman and repairman problems with time windows JNTsitsiklis Networks 22 3 1992 * The orienteering problem in the plane revisited KChen SHar-Peled Preliminary version in Proc. of ACM SoCG 2008. 2006 38 * Fundamental of Computer Algorithms EHorowitz SSahni 1982 Computer Science Press * Introduction to Algorithms TCormen CLeiserson RRivest 1991 MIT Press * The Design and Analysis of Computer Algorithms AVAho JEHopcroft JDUllman 1974 Addison-Wesley * AVAho JEHopcroft JDUllman Data Structures and Algorithms 1984 Addison-Wesley * Computer Algorithms: Introduction to Design and Analysis SBaase 1988 Addison-Wesley * Analysis of Algorithms and Data Structures LBanachowski AKreczmar WRytter 1991 Addison-Wesley * Teaching Algorithms RBaeza-Yates IV Iberoamerican Congress on Computer Science Education July 1995 * Introduction to Distributed Algorithms GTel Cambridge Univ. Press1995 * Algorithmics: Theory and Practice PG-Brassard Bratley 1988 Prentice-Hall * BruceLGolden ArjangAAssad EdwardAWasil Introduction. Computers & OR 13 2-3 1986 * Vehicle Routing with Time Windows: Optimization and Approximation -Desrochers, Lenstra et al. -1988 * DumasDesrosiers 1995 * A unified tabu search heuristic forvehicle routing problems with time windows GCordeau ALaporte Mercier Journal of the Operational Research Society 52 2001 * Parallelization of the Vehicle Routing Problem with TimeWindows JLarsen 1999 Lyngby, Denmark Institute of Mathematical Modelling, Technical University of Denmark Ph.D. thesis * A Parallel Cutting-Plane Algorithm for the Vehicle Routing Problems with Time Windows WCook JLRich 1999 Houston, U.S.A Department of Computational and Applied Mathematics, Rice University Working Paper * The vehicle routing problem with multiple use of vehicles BFleischmann 1990 Universitat Hamburg, Germany Working Paper. Fachbereich Wirtschaftswissenschaften * Vehicle routing with multiple use of vehicles EDTaillard GLaporte MGendreau Journal of the Operational Research Society 47 1996 * Efficient insertion heuristics for vehicle routing and scheduling problems AMCampbell MSavelsbergh Transportation Science 38 3 2004 * Simulated annealing metaheuristics for the vehicle routing problem with time windows WChiang RARussell Annals of Operations Research 63 1996 * Vehicle Routing Problem: Models and Solutions Journal of Quality Measurement and Analysis Liong Choong Yeun 2008 4 Wan Rosmanira Ismail, Khairuddin Omar2 & Mourad Zirour * Excess Travel: Causes, Extent and Consequences GFKing CFMast Transportation Research 1997. Record1111 * Planning Models for Freight Transportation TGCrainic GLaporte European Journal of Operational Research 97 1997 * Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms