@mastersthesis{Ara98a, author = "R.G.I. Arakaki", title = "O problema de roteamento de ve\'{\i}culos e algumas metaheur\'{\i}sticas", school = "Instituto Nacional de Pasquisas Espaciais", address = "Brazil", annote = "In this thesis, several different metaheuristics are proposed for the vehicle routing problem, including a {GRASP}. In the {GRASP} construction phase a distance function is used as the greedy function, while the local search tries to find a better allocation for a costumer at a time. In Portuguese.", month = "September", year = "1998" } @Article{ArgBarYu97a, AUTHOR = "M.F. Arg{\"u}ello and J.F. Bard and G. Yu", TITLE = "A {GRASP} for aircraft routing in response to groundings and delays", JOURNAL = "Journal of Combinatorial Optimization", VOLUME = "1", PAGES = "211--228", year = "1997", annote = "This paper presents a {GRASP} to reconstruct aircraft routings in response to groundings and delays experienced over the course of the day. The objective is to minimize the cost of reassigning aircraft to flights taking into account available resources and other system constraints. The proposed heuristic is a neighborhood search technique that takes as input an initial feasible solution, so that the construction phase is omitted. Two types of partial route exchange operations are described. The first type is the exchange of flight sequences with identical endpoints. In the second type, the sequence of flights being exchanged must have the same origination airport, but the termination airports are swapped.", } @Article{BakCar03a, author = "B.M. Baker and C.A.C. Carreto", title = "A visual interactive approach to vehicle routing", journal = "Computers and Operations Research", volume = "30", pages = "321--337", year = "2003", annote = "This paper describes a graphical-user-interface (with a Microsoft Windows interface) and a {GRASP} based heuristic for the basic vehicle routing problem. The proposed visual interactive system, CRUISE, provides high flexibility. Although the best known results on VRP benchmarks are obtained by tabu search and simulated annealing algorithms, none of them allows the user any control for combining their insights and knowledge.", } @Article{BarHuaJaiDro98a, author = "J.F. Bard and L. Huang and P. Jaillet and M. Dror", title = "A decomposition approach to the inventory routing problem with satellite facilities", journal = "Transportation Science", volume = "32", pages = "189--203", year = "1998", annote = "A methodology is presented that decomposes the inventory routing problem with satellite facilities over the planning horizon, and then solves daily rather than multi-day vehicle routing problems. Three heuristics are proposed for solving the vehicle routing problem with satellite facilities: randomized Clarke-Wright, {GRASP}, and modified sweep. The {GRASP} proposed is a modified version of the {GRASP} of Kontoravdis and Bard (1995).", } @Article{BarKonYu02a, author = "J.F. Bard and G. Kontoravdis and G. Yu", title = "A branch-and-cut procedure for the vehicle routing problem with time windows", journal = "Transportation Science", volume = "36", pages = "250--269", year = "2002", annote = "In this paper, the authors propose a branch-and-cut algorithm for finding the minimum number of homogeneous vehicles needed for visiting a set of costumers (nodes of the input graph) requiring the same type of service subject to time windows and capacity constraints. They obtain feasible solutions and/or upper bounds by applying a {GRASP}.", } @inproceedings{BauPer03a, author = {J. Bautista and J. Pereira}, title = {Procedimientos para la localizaci\'on de \'areas de aportaci\'on de residuos urbanos}, booktitle = {{27 Congreso Nacional de Estad\'{\i}stica e Investigaci\'on Operativa}}, address = {Lleida, Spain}, month = {April}, annote = {The authors address the problem of locating areas where to collect waste products. They show that it can be easily interpreted as a special Set Covering Problem. They propose an exact method, a Genetic Algorithm, and a {GRASP}. The two metaheuristics share the same local search strategy that simply looks for redudant elements to be removed from the solution. In Spanish.}, year = {2003} } @incollection{CarBak02a, author = "C. Carreto and B. Baker", title = "A {GRASP} interactive approach to the vehicle routing problem with backhauls", booktitle = "Essays and surveys in metaheuristics", editor = "C.C. Ribeiro and P. Hansen", publisher = "Kluwer Academic Publishers", pages = "185--200", year = "2002", annote = "The incorporation of interactive tools into heuristic algorithms is investigated. A {GRASP} is used in the route construction and improvement phase. The construction phase is implemented in a clustering heuristic that constructs the routes by clustering the remaining customers according to the vehicles defined by seeds while applying the $3$-opt heuristic to reduce the total distance traveled by each vehicle. The greedy function takes into account routes with smallest insertion cost and costumers with biggest difference between the smallest and the second smallest insertion costs and smallest number of routes they can traverse. As the local search phase, $3$-opt is used." } @Article{ChaKimPar03a, author = "W. Chaovalitwongse and D. Kim and P.M. Pardalos", title = "{GRASP} with a new local search scheme for vehicle routing problems with time windows", journal = "J. of Combinatorial Optimization", volume = {7}, pages = {179--207}, year = "2003", annote = "This paper deals with the vehicle routing problem with time windows and proposes a {GRASP} for minimizing the number of needed vehicles and the travel distances. The search method they propose uses a combination of random and greedy functions. The authors first try to eliminate surplus routes by applying pre-processing to the initial solution output of the construction phase. Then, to compensate the increasing surplus travel distance a saved distance search is applied. The authors also show that $2$-opt is effective for problems with time windows and that to reduce the high computational time, the local search phase can be applied only after every five iterations rather than to each feasible solution.", } @Article{CorMarSan02a, author = "A. Corber\'an and R. Mart\'{\i} and J.M. Sanch\'{\i}s", title = "A {GRASP} heuristic for the mixed {C}hinese postman problem", journal = "European Journal of Operational Research", volume = "142", pages = "70--80", year = "2002", annote = "Given a strongly connected mixed graph $G(V,E,A,c)$, where $V$ is the node set, $E$ is the set of undirected edges, $A$ is the set of directed arcs, and $c$ is a nonnegative cost function defined in $E\cup A$, then the mixed {C}hinese postman problem consists in finding a minimum cost tour passing through each link $e\in E\cup A$ at least once. The construction phase of the proposed {GRASP} uses a greedy function based on the definition of the degree of a node in terms of both incident oriented arcs and incident undirected edges. Each iteration of the local search procedure selects a pair of vertices $u,v\in V$ that are candidates for the move if they are joined by a path of duplications.", } @inproceedings{GarLozSmiGue01a, author = {J.M. Garc\'{\i}a and S. Lozano and K. Smith and F. Guerrero}, title = {{A comparison of {GRASP} and an exact method for solving a production and delivery scheduling problem}}, booktitle = {{First International Workshop on Hybrid Intelligent Systems (HIS'01), Adelaide, Australia}}, month = {December}, annote = {The production and delivery scheduling problem consists in selecting due dated orders to be processed by a manufacturing plant and immediately delivered to the customer. Moreover, a limited number of vehicles are available for delivery. To solve the problem, the authors propose an exact approach and a {GRASP}. The greedy criterion takes into account order weights, while the local search procedure uses an exchange neighborhood.}, year = {2001} } @phdthesis{Hjo95a, author = "C.A. Hjorring", title = "The vehicle routing problem and local search metaheuristics", school = "University of Auckland", address = "Auckland, New Zealand", year = "1995", annote = "Three metaheuristics for effectively searching through the space of cyclic orders are developed. They are based on {GRASP}, tabu search, and genetic algorithms. For tabu search, different schemes are investigated to control the tabu list length, including a reactive tabu search method. To obtain good solutions when using the genetic algorithm, specialized crossovers are developed, and a local search component is added. {GRASP} is used to construct an initial good solution.", } @Article{KonBar95a, author = "G. Kontoravdis and J.F. Bard", title = "A {GRASP} for the vehicle routing problem with time windows", journal = "ORSA Journal on Computing", volume = "7", pages = "10-23", year = "1995", annote = "A {GRASP} is proposed for minimizing the fleet size of temporarily constrained vehicle routing problems with two types of service. The greedy function of the construction phase takes into account both the overall minimum insertion cost and the penalty cost. Local search is applied to the best solution found every five iterations of the first phase, rather than to each feasible solution.", } @techreport{MarMig03a, author = "Y. Marinakis and A. Migdalas", title = "Expading neighborhood {GRASP} for the {T}raveling {S}alesman {P}roblem", institution = "Technical University of Crete", address = "Chania 73100, Greece", annote = {For the traveling salesman problem the authors of this paper propose a {GRASP} that includes tour improvement methods. One among the simplest tour improvement method is the nearest neighbor in which at each step the salesman moves to the city nearest to the current one.}, year = "2003" } @inproceedings{ResRes99a, author = "L.I.P. Resende and M.G.C. Resende", title = "A {GRASP} for frame relay {PVC} routing", booktitle = "Proc. of the Third Metaheuristics International Conference", city= "Angra dos Reis, Brazil", month = "July", year = "1999", pages = "397--402", annote = "This paper describes a {GRASP} for routing permanent virtual circuits (PVC) for frame relay in telecommunications systems. The objective is to minimize PVC delays while balancing trunk loads. The greedy choice selects from the set of not yet routed PVCs the one that minimizes the delay while balancing the trunk loads. The local search procedure reroutes each PVC, one at a time, checking each time if the new route taken together with the remaining fixed routes improves the objective function." }