Routing problems: A bibliography
Annals of Operations ResearchPublished 1 December 1995
Gilbert Laporte, Ibrahim H. Osman
Citations315
SJR quartileQ1
SJR score1.09
SNIP1.62
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This bibliography contains 500 references on four classical routing problems: the Traveling Salesman problem, the Vehicle Routing Problem, the Chinese Postman Problem, and the Rural Postman problem.
Abstract
This bibliography contains 500 references on four classical routing problems: the Traveling Salesman Problem, the Vehicle Routing Problem, the Chinese Postman Problem, and the Rural Postman Problem. References are presented alphabetically under a number of subheadings.
Keywords
Engineering
Management ScienceThe Truck Dispatching Problem
4,873 Citations1959George B. Dantzig, J. H. Ramser
A procedure based on a linear programming formulation is given for obtaining a near optimal solution to the optimum routing of a fleet of gasoline delivery trucks between a bulk terminal and a large number of service stations supplied by the terminal.
Operations ResearchAlgorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints
4,181 Citations1987Marius M. Solomon
This paper considers the design and analysis of algorithms for vehicle routing and scheduling problems with time window constraints and finds that several heuristics performed well in different problem environments; in particular an insertion-type heuristic consistently gave very good results.
Journal of the Operational Research SocietyOR-Library: Distributing Test Problems by Electronic Mail
1,862 Citations1990J. E. Beasley
A system (OR-Library) that distributes test problems by electronic mail (e-mail) that has available test problems drawn from a number of different areas of operational research.
European Journal of Operational ResearchThe vehicle routing problem: An overview of exact and approximate algorithms
1,701 Citations1992Gilbert Laporte
In this paper, some of the main known results relative to the Vehicle Routing Problem are surveyed.
Solution of a Large-Scale Traveling-Salesman Problem
1,273 Citations2009Vašek Chvátal, William J. Cook +3 more
The RAND Corporation in the early 1950s contained “what may have been the most remarkable group of mathematicians working on optimization ever assembled”: Arrow, Bellman, Dantzig, Flood, Ford, Fulkerson, Gale, Johnson, Nash, Orchard-Hays, Robinson, Shapley, Simon, Wagner, and other household names.
PolyPublie (École Polytechnique de Montréal)A Tabu Search Heuristic for the Vehicle Routing Problem
1,231 Citations1994Michel Gendreau, Alain Hertz +1 more
Operations ResearchA New Optimization Algorithm for the Vehicle Routing Problem with Time Windows
1,180 Citations1992Martin Desrochers, Jacques Desrosiers +1 more
This paper presents a new optimization algorithm capable of optimally solving 100-customer problems of the vehicle routing problem with time windows VRPTW and indicates that this algorithm proved to be successful on a variety of practical sized benchmark VRPTw test problems.
SIAM ReviewA Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
1,061 Citations1991Manfred Padberg, Giovanni Rinaldi
An algorithm is described for solving large-scale instances of the Symmetric Traveling Salesman Problem (STSP) to optimality using a “polyhedral” cutting-plane procedure that exploits a subset of the system of linear inequalities defining the convex hull of the incidence vectors of the hamiltonian cycles of a complete graph.
NetworksA generalized assignment heuristic for vehicle routing
1,060 Citations1981Marshall L. Fisher, Ramchandran Jaikumar
This paper presents a heuristic for this problem in which an assignment of customers to vehicles is obtained by solving a generalized assignment problem with an objective function that approximates delivery cost and shows that it has outperformed the best existing heuristics on a sample of standard test problems.
Transportation ScienceThe General Pickup and Delivery Problem
1,034 Citations1995Martin Savelsbergh, María Sol
Several characteristics that distinguish pickup and delivery problems from standard vehicle routing problems are discussed and a survey of the problem types and solution methods found in the literature is presented.
Annals of Operations ResearchMetastrategy simulated annealing and tabu search algorithms for the vehicle routing problem
1,022 Citations1993Ibrahim H. Osman
Approximate methods based on descent, hybrid simulated annealing/tabu search, and tabu search algorithms are developed and different search strategies are investigated and an estimate for the tabu list size is statistically derived.
Mathematical ProgrammingMatching, Euler tours and the Chinese postman
987 Citations1973Jack Edmonds, Ellis L. Johnson
The solution of the Chinese postman problem using matching theory is given and the convex hull of integer solutions is described as a linear programming polyhedron, used to show that a good algorithm gives an optimum solution.
European Journal of Operational ResearchThe traveling salesman problem: An overview of exact and approximate algorithms
938 Citations1992Gilbert Laporte
Some of the main known algorithms for the traveling salesman problem are surveyed and the definition and applications of these algorithms are explained.
Naval Research Logistics (NRL)The orienteering problem
762 Citations1987Bruce Golden, Larry Levy +1 more
Annals of Operations ResearchLocal search in routing problems with time windows
660 Citations1985Martin Savelsbergh
This work develops local search algorithms for routing problems with time windows based on thek-interchange concept and considers the problem of finding initial solutions.
Transportation ScienceA Dynamic Programming Solution to the Single Vehicle Many-to-Many Immediate Request Dial-a-Ride Problem
588 Citations1980Harilaos N. Psaraftis
An investigation of the single-vehicle, many-to-many, immediate-request dial-a-ride problem is developed, with a Dynamic Programming approach which exhibits a computational effort which is asymptotically lower than the corresponding effort of the classical Dynamic Programming algorithm applied to a Traveling Salesman Problem of the same size.
NetworksCapacitated arc routing problems
568 Citations1981Bruce Golden, Richard T. Wong
The intent in this paper is to define a capacitated arc routing problem, to provide mathematical programming formulations, to perform a computational complexity analysis, and to present an approximate solution strategy for this class of problems.
Journal of the Operational Research SocietyHeuristic Methods Applied to Orienteering
568 Citations1984T. Tsiligirides
A ‘good’, if not ‘optimal’ solution by means of an efficient and computationally feasible method is derived and discussed and this solution is obtained by the use of either of two algorithms based on approximate methods.
NetworksThe prize collecting traveling salesman problem
564 Citations1989Egon Balas
This paper identifies several families of facet defining inequalities for this polytope, the convex hull of solutions to the PCTSP, and uses these inequalities either as cutting planes or as ingredients of a Lagrangean optimand.
Transportation ScienceSurvey Paper—Time Window Constrained Routing and Scheduling Problems
540 Citations1988Marius M. Solomon, Jacques Desrosiers
Having surveyed the state-of-the-art in this area, the aim of this paper is to survey the significant advances made for the following classes of routing problems with time windows: the single and multiple traveling salesmanproblem, the shortest path problem, the minimum spanning tree problem, and the generic vehicle routing problem.
Transportation ScienceTime Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms
536 Citations1992Chryssi Malandraki, Mark S. Daskin
Mixed integer linear programming formulations of the TDVRP and the TDTSP are presented that treat the travel time functions as step functions that preclude modification of most of the algorithms that have been developed for the vehicle routing problem.
Computers & Operations ResearchThe fleet size and mix vehicle routing problem
534 Citations1984Bruce Golden, Arjang A. Assad +2 more
This work describes several efficient heuristic solution procedures as well as techniques for generating a lower bound and an underestimate of the optimal solution to the problem of routing a fleet of vehicles from a central depot to customers with known demand.
Mathematical ProgrammingExact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations
520 Citations1981N.D. Christofides, Aristide Mingozzi +1 more
Transportation Research Part B MethodologicalA heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows
515 Citations1986Jang-Jei Jaw, Amedeo R. Odoni +2 more
A heuristic algorithm is described for a time-constrained version of the advance-request, multi-vehicle, many-to-many Dial-A-Ride Problem (DARP).
Operations ResearchOptimal Solution of Vehicle Routing Problems Using Minimum K-Trees
512 Citations1994Marshall L. Fisher
This work shows that the vehicle routing problem can be modeled as the problem of finding a minimum cost K-tree with two K edges incident on the depot and subject to some side constraints that impose vehicle capacity and the requirement that each customer be visited exactly once.
NetworksNetworks and vehicle routing for municipal waste collection
502 Citations1974Edward Beltrami, Lawrence Bodin
Vehicle routing for municipal waste collection encompasses a variety of problems and the techniques developed for solving some of these problems are explored.
INFORMS Journal on ComputingFast Algorithms for Geometric Traveling Salesman Problems
469 Citations1992Jon Jouis Bentley
Efficient algorithms for computing approximate traveling salesman tours in multidimensional point sets and three local optimizations are described, which are able to solve uniform planar million-city traveling salesman problems to within a few percent of optimal in several midicomputer CPU hours.
INFORMS Journal on ComputingThe Vehicle Routing Problem with Time Windows: Minimizing Route Duration
449 Citations1992Martin Savelsbergh
This work investigates the implementation of edge-exchange improvement methods for the vehicle routing problem with time windows with minimization of route duration as the objective and shows how this effort can be reduced to a constant.
Transportation Research Part A GeneralThe multiple vehicle routing problem with simultaneous delivery and pick-up points
435 Citations1989Hokey Min
A model and a solution procedure efficient enough to handle real-world variants of simultaneous deliveries and pickups at the same node is developed and a case study dealing with a public library distribution system in Franklin County, Ohio indicates that substantial time/distance savings can be achieved.
Operations ResearchA Combined Vehicle Routing and Inventory Allocation Problem
416 Citations1984Awi Federgruen, Paul Zipkin
Computational results using one such adaptation of the deterministic vehicle routing problem show that the algorithm is fast enough for practical work, and that substantial cost savings can be achieved with this approach.
Transportation ScienceSavings by Split Delivery Routing
416 Citations1989Moshe Dror, Pierre Trudeau
This paper examines a relaxed version of the generic vehicle routing problem, in which a delivery to a demand point can be split between any number of vehicles, and demonstrates the potential for cost savings through split deliveries.
Discrete Applied MathematicsThe selective travelling salesman problem
412 Citations1990Gilbert Laporte, Silvano Martello
Operations ResearchA Vehicle Routing Problem with Stochastic Demand
398 Citations1992Dimitris Bertsimas
This work considers a natural probabilistic variation of the classical vehicle routing problem (VRP), in which demands are stochastic, and proposes heuristics and algorithms to construct an a priori sequence among all customers of minimal expected total length.
Operations Research LettersOptimization of a 532-city symmetric traveling salesman problem by branch and cut
392 Citations1987Manfred Padberg, Giovanni Rinaldi
Annals of Operations ResearchGenetic algorithms for the traveling salesman problem
389 Citations1996Jean‐Yves Potvin
A simple genetic algorithm is introduced, and various extensions are presented to solve the traveling salesman problem, using randomized search techniques that simulate some of the processes observed in natural evolution.
Lecture notes in computer scienceLocal optimization and the Traveling Salesman Problem
376 Citations2005David S. Johnson
This paper surveys the state of the art with respect to the TSP, with emphasis on the performance of traditional local optimization algorithms and their new competitors, and on what insights complexity theory does, or does not, provide.
Mathematics of Operations ResearchBounds and Heuristics for Capacitated Routing Problems
375 Citations1985M. Haimovich, A. H. G. Rinnooy Kan
Asymptotically optimal bounds and heuristics are developed for a capacitated routing problem that will find a solution with relative error at most (epsilon) in time polynomial in the number of customers.
OmegaRoute first—Cluster second methods for vehicle routing
365 Citations1983J. E. Beasley
Extensions to the basic route first--cluster second method both to improve its effectiveness and to enable it to cope with practical constraints are described.
European Journal of Operational ResearchThe effect of ignoring routes when locating depots
361 Citations1989Saı̈d Salhi, Graham K. Rand
This work evaluates the effect of ignoring routeing when locating depots by using a two stage process (location and routeing), and it is shown that the best solution after the location stage does not necessarily generate the lowest cost Solution after the routeing stage.
Transportation ScienceSolving a Family of Multi-Depot Vehicle Routing and Location-Routing Problems
359 Citations1988Gilbert Laporte, Yves Nobert +1 more
This paper examines a class of asymmetrical multi-depot vehicle routing problems and location-routing problems, under capacity or maximum cost restrictions, by using an appropriate graph representation, and then a graph extension.
Repository Technological University of Pereira (Technological University of Pereira)Construcción de aplicativo web para la gestión y prestación del servicio de ambulancias en la ciudad de Pereira, utilizando inteligencia artificial
351 Citations2021H. A. Eiselt, Michel Gendreau
NetworksThe period routing problem
344 Citations1984N.D. Christofides, J. E. Beasley
The solution obtained for the period vehicle routing problem, the problem of designing vehicle routes to meet required service levels for customers and minimize distribution costs over a given several-day period of time, shows an improvement of 13% over the previous best solution.
Operations ResearchAn Optimal Algorithm for the Traveling Salesman Problem with Time Windows
340 Citations1995Yvan Dumas, Jacques Desrosiers +2 more
New elimination tests are presented which greatly enhance the performance of a relatively well established dynamic programming approach and its application to the minimization of the total traveling cost for the traveling salesman problem with time windows.
NetworksState‐space relaxation procedures for the computation of bounds to routing problems
325 Citations1981Nicos Christofides, Aristide Mingozzi +1 more
This paper gives a survey of a general relaxation procedure whereby the state-space associated with a given dynamic programming recursion is relaxed in such a way that the solution to the relaxed recursion provides a bound which could be embedded in general branch and bound schemes for the solution of the problem.
Operations ResearchA Priori Solution of a Traveling Salesman Problem in Which a Random Subset of the Customers Are Visited
323 Citations1988Patrick Jaillet
This work first derive closed form expressions for computing efficiently the expected length of any given tour under very general probabilistic assumptions and provides, in a unified way, a unified approach to finding a priori a tour through all n points.
North-Holland mathematics studiesExact Algorithms for the Vehicle Routing Problem
304 Citations1987Gilbert Laporte, Yves Nobert
Operations ResearchOptimal Routing under Capacity and Distance Restrictions
301 Citations1985Gilbert Laporte, Yves Nobert +1 more
An integer linear programming algorithm for vehicle routing problems involving capacity and distance constraints using constraint relaxation and a new class of subtour elimination constraints is described.
Mathematische AnnalenUeber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren
286 Citations1873Carl Hierholzer, Chr Wiener
Operations ResearchA Tabu Search Heuristic for the Vehicle Routing Problem with Stochastic Demands and Customers
279 Citations1996Michel Gendreau, Gilbert Laporte +1 more
A tabu search heuristic is developed for a version of the stochastic vehicle routing problem where customers are present at locations with some probabilities and have random demands and produces an optimal solution in 89.45% of cases.
Transportation ScienceAn Exact Algorithm for the Vehicle Routing Problem with Stochastic Demands and Customers
277 Citations1995Michel Gendreau, Gilbert Laporte +1 more
The stochastic vehicle routing problem, where each customer has a known probability of presence and a random demand, is considered and is solved for the first time to optimality by means of an integer L-shaped method.
Mathematical ProgrammingSolution of large-scale symmetric travelling salesman problems
273 Citations1991Martin Grötschel, Olaf Holland
The implementation is based on a fast LP-solver (IBM's MPSX) and makes effective use of polyhedral results on the symmetric travelling salesman polytope and describes the important ingredients of the code.
Operations ResearchSequencing of Insertions in Printed Circuit Board Assembly
263 Citations1988Michael O. Ball, Michael J. Magazine
A particular problem that arises from an application to a middle sized electronics firm is modeled and solved, and the specific problem to determine the best sequence of insertion operations is formulated as a type of directed postman problem.
NetworksA fundamental problem in vehicle routing
261 Citations1974Clifford S. Orloff
The classical Traveling Salesman Problem and the Chinese Postman Problem are shown to be special limiting cases of the General Routing Problem, and the algorithm provides a unified approach to both node and arc oriented routing problems.
European Journal of Operational ResearchThe vehicle routing problem with backhauls
258 Citations1989Marc Goetschalckx, Charlotte Jacobs‐Blecha
An extensive computational analysis of several initial solution algorithms is presented, which identifies the tradeoffs between solution quality and computational requirements and concludes that the greedy procedure reduces the required number of trucks and increases the truck utilization.
Operations ResearchA Priori Optimization
252 Citations1990Dimitris Bertsimas, Patrick Jaillet +1 more
The idea of a priori optimization as a strategy competitive to the strategy of reoptimization, under which the combinatorial optimization problem is solved optimally for every instance is introduced.
INFOR Information Systems and Operational ResearchAn Efficient Transformation Of The Generalized Traveling Salesman Problem
250 Citations1993Charles E. Noon, James C. Bean
This paper shows how to efficiently transform a GTSP into a standard asymmetric Traveling Salesman Problem (TSP) over the same number of nodes and allows certain routing problems which involve discrete alternatives to be modeled using the TSP framework.
Transportation ScienceHybrid Heuristics for the Vehicle Routing Problem with Time Windows
248 Citations1995Robert A. Russell
The hybrid construction/improvement heuristic is more effective in reducing vehicle fleet size requirements than previously reported heuristics.
American Journal of Mathematical and Management SciencesA Dynamic Programming Solution of the Large-Scale Single-Vehicle Dial-A-Ride Problem with Time Windows
236 Citations1986Jacques Desrosiers, Yvan Dumas +1 more
The single-vehicle dial-a-ride problem with time window constraints for both pick-up and delivery locations, and precedence and capacity constraints, is solved using a forward dynamic programming algorithm.
Annals of Operations ResearchSolving real-life vehicle routing problems efficiently using tabu search
229 Citations1993Frédéric Semet, Éric D. Taillard
This paper presents a tabu search based method for finding good solutions to a real-life vehicle routing problem that takes the heterogeneous character of the fleet into account and obtains solutions that are significantly better than those previously developed and implemented in practice.
Lecture notes in computer scienceGenetic local search algorithms for the traveling salesman problem
220 Citations1991Nico L. J. Ulder, Emile Aarts +3 more
Experimental approaches to Genetic Local Search with 2-Opt neighbourhoods and Lin-Kernighan neighbourhoods are compared with the corresponding classical multi-start Local Search algorithms, as well as with Simulated Annealing and Threshold Accepting.
European Journal of Operational ResearchModels and exact solutions for a class of stochastic location-routing problems
214 Citations1989Gilbert Laporte, François Louveaux +1 more
A family of stochastic location-routing problems which consist of simultaneously locating a depot among a set of potential sites, of determining the vehicle fleet size and of designing collection routes through aSet of customers having random supplies is described.
Discrete Applied MathematicsA parallel tabu search algorithm for large traveling salesman problems
212 Citations1994Claude-Nicolas Fiechter
An efficient algorithm for getting almost optimal solutions of large traveling salesman problems is proposed, which uses the intermediate- and long-term memory concepts of tabu search as well as a new kind of move.
Naval Research Logistics QuarterlyUsing simulated annealing to solve routing and location problems
206 Citations1986Bruce Golden, Christopher C. Skiścim
This paper implements the analogy between the statistical mechanics of large multivariate physical systems and combinatorial optimization, applies it to the traveling salesman problem and the p‐median location problem, and test the approach extensively.
Operations Research LettersLarge-step markov chains for the TSP incorporating local search heuristics
199 Citations1992Olivier Martin, Steve W. Otto +1 more
A new class of optimization heuristics which combine local searches with stochastic sampling methods, allowing one to iterate local optimization heURistics is considered, improving 3-opt by over 1.6% and Lin-Kernighan by 1.3%.
Annals of Operations ResearchSerial and parallel simulated annealing and tabu search algorithms for the traveling salesman problem
198 Citations1989Miroslaw Malek, Mohan Guruswamy +2 more
Results indicate that tabu search consistently outperforms simulated annealing with respect to computation time while giving comparable solutions to traveling salesman problem problems.
European Journal of Operational ResearchInteger programming formulations of vehicle routing problems
197 Citations1985R.V. Kulkarni, Pramod R. Bhave
Annals of Operations ResearchA computational comparison of algorithms for the inventory routing problem
186 Citations1985Moshe Dror, Michael O. Ball +1 more
Algorithms for the inventory routing problem, a distribution problem in which each customer maintains a local inventory of a product such as heating oil and consumes a certain amount of that product each day, are described and compared.
European Journal of Operational ResearchA classification scheme for vehicle routing and scheduling problems
185 Citations1990Martin Desrochers, Jan Karel Lenstra +1 more
A classification scheme is proposed for a class of models that arise in the area of vehicle routing and scheduling and illustrated on a number of problems that have been considered in the literature.
Vehicle Routing with Time Windows using Genetic Algorithms
182 Citations1995Sam R. Thangiah
GIDEON, a genetic algorithm heuristic for solving vehicle routing problems with time windows, consists of a global customer clustering method and a local post-optimization method that obtained 41 new best known solutions.
European Journal of Operational ResearchThe fleet size and mix problem for capacitated arc routing
182 Citations1985Gündüz Ulusoy
Annals of Operations ResearchAn exact algorithm for solving a capacitated location-routing problem
180 Citations1986G. Laporte, Yves Nobert +1 more
Journal of the ACMApproximation Algorithms for Some Postman Problems
178 Citations1979Greg N. Frederickson
Approxtmatton algorithms for several NP-complete edge-covermg routing problems are presented and analyzed and a worst-case bound of 2 is proved for the mixed postman algortthm of Edmonds and Johnson.
Transportation ScienceAn Optimization-Based Heuristic for Vehicle Routing and Scheduling with Soft Time Window Constraints
177 Citations1992Yiannis A. Koskosidis, Warren B. Powell +1 more
A new formulation based on the treatment of the time window constraints as soft constraints that can be violated at a cost and heuristically decompose the problem into an assignment/clustering component and a series of routing and scheduling components is presented.
European Journal of Operational ResearchStochastic vehicle routing with modified savings algorithm
176 Citations1986Moshe Dror, Pierre Trudeau
The effects of route failure on theexpected cost of a route, as well as the impact the direction of a designed route can have on the expected cost, are illustrated.
Research Padua Archive (University of Padua)Delivery man problem and cumulative matroids
171 Citations1993Fischetti Matteo, Laporte Gilbert +1 more
RAIRO - Theoretical Informatics and ApplicationsThe complexity of the travelling repairman problem
170 Citations1986Foto Afrati, Stavros S. Cosmadakis +3 more
Le probleme du reparateur itinerant consiste en la donnee d'un ensemble fini de points, and des temps de parcours entre ces points, mais il peut etre resolu avec un algorithme pseudo-polynome.
Large scale systemsAnalysis of a large scale vehicle routing problem with an inventory component
170 Citations1984Bruce Golden, Arjang A. Assad +1 more
Description d'un systeme de distribution integre base sur l'optimisation, couramment developpe pour une grande entreprise commerciale.
European Journal of Operational ResearchImprovement heuristics for the Vehicle Routing Problem based on simulated annealing
169 Citations1995Alex Van Breedam
The simulated annealing-based improvement methods are compared against their descent alternatives as well as other metaheuristics implementations on a set of classical test problems.
Transportation ScienceAn Integrated Inventory Allocation and Vehicle Routing Problem
168 Citations1989Ting-Hsuan Chien, Anantaram Balakrishnan +1 more
This work addresses the problem of distributing a limited amount of inventory among customers using a fleet of vehicles so as to maximize profit by developing a Lagrangian-based procedure to generate both good upper bounds and heuristic solutions.
OR SpectrumA branch and bound algorithm for the capacitated vehicle routing problem
167 Citations1983G. Laporte, Yves Nobert
Journal of the ACMOn the complexity of edge traversing
163 Citations1976Christos H. Papadimitriou
It is shown that the Chinese Postman Problem, although tractable in the totally directed and the totally undirected cases, is NP-complete in the mixed case.
Transportation ScienceOptimizing Single Vehicle Many-to-Many Operations with Desired Delivery Times: I. Scheduling
162 Citations1985Thomas R. Sexton, Lawrence Bodin
A heuristic routing and scheduling algorithm is shown to produce high quality solutions in reasonable computation time by testing on moderately sized real data bases from both Gaithers-burg, Maryland, and Baltimore, Maryland.
NetworksThe Capacitated Arc Routing Problem: Lower bounds
160 Citations1992Enrique Benavent, Vicente Campos +2 more
New lower bounds are developed for the Capacitated Arc Routing Problem, in which a fleet of vehicles must service a subset of the edges of a graph, with minimum total cost and such that the load assigned to each vehicle does not exceed its capacity.
Management ScienceReal-Time Dispatch of Petroleum Tank Trucks
158 Citations1981Gerald G. Brown, Glenn W. Graves
A highly automated, real-time dispatch system is described which uses embedded optimization routines to replace extensive manual operations and to reduce substantially operating costs for a nation-wide fleet of petroleum tank trucks.
NetworksAn exact algorithm for the asymmetrical capacitated vehicle routing problem
158 Citations1986Gilbert Laporte, Hélène Mercure +1 more
An exact algorithm for the asymmetrical capacitated vehicle routing problem, i.
Management ScienceHeuristics Based on Spacefilling Curves for Combinatorial Problems in Euclidean Space
155 Citations1988John J. Bartholdi, Loren K. Platzman
A family of heuristics to solve combinatorial problems such as routing and partitioning that exploit geometry but ignore specific distance measures are described, which seem well-suited to operational problems where time or computing resources are limited.
Transportation ScienceA Request Clustering Algorithm for Door-to-Door Handicapped Transportation
154 Citations1995Irina Ioachim, Jacques Desrosiers +3 more
A new approximate method to mini-clustering that involves solving a multi-vehicle pick-up and delivery problem with time windows by column generation and a heuristic to reduce the size of the network, while incurring only small losses in solution quality is presented.
Operations ResearchTwo-Echelon Distribution Systems with Vehicle Routing Costs and Central Inventories
146 Citations1993Shoshana Anily, Awi Federgruen
It is shown under mild probabilistic assumptions that the generated solutions and bounds come asymptotically within a few percentage points of optimality (within the considered class of strategies) for problems of moderate size.
Computers & Operations ResearchA parallel implementation of the Tabu search heuristic for vehicle routing problems with time window constraints
144 Citations1994Bruno-Laurent Garcia, Jean‐Yves Potvin +1 more
A parallel Tabu search heuristic for the Vehicle Routing Problem with Time Windows, which is synchronous and runs on a Multiple-Instruction Multiple-Data computer architecture.
NetworksA branch and bound algorithm for the multiple depot vehicle scheduling problem
142 Citations1989G. Carpaneto, Mauro Dell’Amico +2 more
NetworksSet partitioning based heuristics for interactive routing
142 Citations1981Frank H. Cullen, John J. Jarvis +1 more
The human aided optimization procedure was tested on the standard 50- point, 75-point, and 100-point test problems of Eilon, Watson-Gandy, and Christofides and a better solution was generated than the current best known solution.
Lecture notes in computer scienceOn solving travelling salesman problems by genetic algorithms
139 Citations2006Heinrich Braun
A genetic algorithm for solving the traveling salesman problem by genetic algorithms to optimality for traveling salesman problems with up to 442 cities is presented.
GIDEON: a genetic algorithm system for vehicle routing with time windows
133 Citations2002Sam R. Thangiah, Kendall E. Nygard +1 more
GIDEON, a genetic algorithm system to heuristically solve the vehicle routing problem with time windows, consists of two distinct modules: a global clustering module that assigns customers to vehicles by a process called genetic sectoring and a local route optimization module (SWITCH-OPT).
Operations ResearchParallel Savings Based Heuristics for the Delivery Problem
132 Citations1991Kemal Altınkemer, Bezalel Gavish
The paper presents parallel savings algorithms PSAs for generating feasible solutions to the delivery problem, and the average quality of solutions generated by PSAs is shown to be significantly superior on large sets of test problems.
American Journal of Mathematical and Management SciencesA New Heuristic for the Multi-Depot Vehicle Routing Problem that Improves upon Best-Known Solutions
131 Citations1993I‐Ming Chao, Bruce Golden +1 more
In this paper, the multi-depot vehicle routing problem is reviewed and a new heuristic is presented that is fast and simple and improves upon previous best-known solutions.
Computers & Operations ResearchTabu search performance on the symmetric traveling salesman problem
130 Citations1994J.R. Knox
The performance of tabu search is compared to the K-OPT procedure using six test problems drawn from the literature and some factors which influence the performance oftabu search are provided.
Mathematical ProgrammingFacet identification for the symmetric traveling salesman polytope
130 Citations1990Manfred Padberg, Giovanni Rinaldi
Exact and heuristic shrinking conditions for the input graph are given that yield efficient procedures for the identification of simple and general comb inequalities and of some elementary clique tree inequalities.
Practica Oto-Rhino-LaryngologicaDer Saccus endolymphaticus bei Entzündungsprozessen
129 Citations2009J.P. Secrétan
Computers & Operations ResearchHeuristic approaches to vehicle routing with backhauls and time windows
128 Citations1996Sam R. Thangiah, Jean‐Yves Potvin +1 more
A route construction heuristic for the VRPBTW, as well as different local search heuristics to improve the initial solutions are described, which are within 2.5% of the known optimal solutions on average.
Operations ResearchTechnical Note—An Exact Algorithm for the Time-Constrained Traveling Salesman Problem
127 Citations1983Edward K. Baker
The dual of the formulation is shown to be a disjunctive graph model, which is well known from scheduling theory, and a longest path algorithm is used to obtain bounding information for subproblems in a branch and bound solution procedure.
…