When designing a patrol route, it is often necessary to pay more attention to locations with high crime rates. In this paper, we study a patrol routing problem for a fleet of patrol cars patrolling a region with a high-crime neighborhood (HCN) consisting of multiple hot spots. Considering the disorder and chaos in the HCN, at least one patrol car is required in the HCN at any given time during the patrol. We call this routing problem the hot spot coverage patrol problem (HSCPP). In the HSCPP, the importance of a patrol location is quantified by a prize, and the prize is collected if a patrol car visits the location. Our objective is to maximize the sum of prizes collected by the patrol cars, obeying all operational requirements. We propose mathematical formulations and develop several solution approaches for the HSCPP. The global approach consists of finding the routing solution for all patrol cars with a single integer programming (IP) formulation. The partition approach involves first partitioning the region geographically and solving the routing problem in each subregion with two IP formulations. Next, we strengthen the partition approach by developing a column generation (CG) approach in which the initial columns of the CG approach are the solutions generated from the partition approach. We conduct a detailed computational case study using instances based on real crime data from Montgomery County, Maryland. To further understand the computational tractability of our solution approaches, we also perform a sensitivity analysis using synthetic instances under various scenarios. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0192 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0192 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Abstract In recent years, the usage of drones in last‐mile logistics has stirred great interest in the operations research community. Many papers have considered schemes of hybrid truck‐and‐drone delivery. In this paper, we focus on the Multivisit Drone Routing Problem with Edge Launches (MVDRP‐EL) which assumes: a heterogenous set of packages, a drone capable of carrying multiple packages at a time and that can be launched and retrieved along an edge, a flexible launch/retrieval site set, and a user‐defined energy depletion function. We believe this paper is the first to exploit edge launch ability through a global continuous approach. In this context, we propose an original formulation based on the Covering Salesman Problem to compute a valid lower bound for the problem and an iterative solution method to determine a MVDRP‐EL solution with quality launch/retrieval sites along the road network edges. Each iteration of the solution method consists of two phases. In the first phase, the road network edges are discretized to obtain launch/retrieval sites, and a first solution is determined. In the second phase, the truck route is set and we reduce the completion time by carefully synchronizing truck and drone routes by solving an original Mixed Integer Second Order Cone Program. The lower bound formulation and the proposed method have been tested on several instances and results indicate the effectiveness of the proposed method and the potential value of launching along an edge, respectively.

Local governments inspect roads to decide which segments and intersections to repair. Videos are taken using a camera mounted on a vehicle. The vehicle taking the videos proceeds straight or takes a left turn to cover an intersection fully. We introduce the intersection inspection rural postman problem (IIRPP), which is a new variant of the rural postman problem (RPP) that involves turns. We develop integer programming formulations of the IIRPP based on two different graph transformations to generate least-cost vehicle routes. One formulation is based on a new idea of transforming a graph. A second formulation is based on a graph transformation idea from the literature. Computational experiments show that the formulation involving the new graph transformation idea performs much better than the other formulation. We also develop an RPP-based heuristic and a heuristic based on a modified RPP. Heuristic solutions are improved by solving integer programming formulations on an induced subgraph. Computational experiments show that the heuristics based on the modified RPP perform much better than the RPP-based heuristics. The best-performing heuristic generates very good quality IIRPP-feasible routes on large street networks quickly. Summary of Contribution. Our paper addresses a real-world problem faced by local governments during road inspections. The real-world problem that we solve and the methodologies that we use fall at the intersection of computing and operations research. We introduce the intersection inspection rural postman problem, which is a new variant of the rural postman problem that involves turns to capture this real-world scenario. The rural postman problem is an important problem in vehicle routing. Studying new variants of this problem is key to extending the practice and theory of vehicle routing. We develop an integer programming formulation based on a new idea of transforming a graph and also develop heuristics based on the rural postman problem.

This paper addresses the close-enough traveling salesman problem, a variant of the Euclidean traveling salesman problem, in which the traveler visits a node if it passes through the neighborhood set of that node. We apply an effective strategy to discretize the neighborhoods of the nodes and the carousel greedy algorithm to appropriately select the neighborhoods that, step by step, are added to the partial solution until a feasible solution is generated. Our heuristic, based on these ingredients, is able to compute tight upper and lower bounds on the optimal solution relatively quickly. The computational results, carried out on benchmark instances, show that our heuristic often finds the optimal solution, on the instances where it is known, and in general, the upper bounds are more accurate than those from other algorithms available in the literature. Summary of Contribution: In this paper, we focus on the close-enough traveling salesman problem. This is a problem that has attracted research attention over the last 10 years; it has numerous real-world applications. For instance, consider the task of meter reading for utility companies. Homes and businesses have meters that measure the usage of gas, water, and electricity. Each meter transmits signals that can be read by a meter reader vehicle via radio-frequency identification (RFID) technology if the distance between the meter and the reader is less than r units. Each meter plays the role of a target point and the neighborhood is a disc of radius r centered at each target point. Now, suppose the meter reader vehicle is a drone and the goal is to visit each disc while minimizing the amount of energy expended by the drone. To solve this problem, we develop a metaheuristic approach, called (lb/ub)Alg, which computes both upper and lower bounds on the optimal solution value. This metaheuristic uses an innovative discretization scheme and the Carousel Greedy algorithm to obtain high-quality solutions. On benchmark instances where the optimal solution is known, (lb/ub)Alg obtains this solution 83% of the time. Over the remaining 17% of these instances, the deviation from the optimality is 0.05%, on average. On the instances with the highest overlap ratio, (lb/ub)Alg does especially well.

The mothership and drone routing problem (MDRP) considers the routing of a two-vehicle tandem. The larger vehicle, which may be a ship or an airplane, is called the mothership; the smaller vehicle, which may be a small boat or unmanned aerial vehicle, is called the drone. We assume that there exists a set of target locations T. For each t in T, the drone must launch from the mothership, visit t, and then return to the mothership to refuel. The drone has a limited range of R time units. In the MDRP, we assume that both mothership and drone operate in the “open seas” (i.e., using the Euclidean metric). We also introduce the mothership and infinite-capacity drone routing problem (MDRP-IC), where a drone launches from the mothership and visits one or more targets consecutively before returning to the mothership. Our exact approach uses branch and bound, where each node of the branch-and-bound tree corresponds to a potential subsequence of the order of target visits. A lower bound at each node is given by solving a second-order cone program, which optimally chooses a launch point and landing point for each target in the subsequence. A set of heuristics that also uses a second-order cone program as an embedded procedure is presented. We show that our schemes are flexible to accommodate a variety of additional constraints and/or objective functions. Computational results and interesting variants of the MDRP and MDRP-IC are also presented.

The Traveling Salesman Problem with a Drone (TSP-D) is a hybrid truck and drone model of delivery, in which the drone rides on the truck and launches from the truck to deliver packages. Our approach to the TSP-D uses branch and bound, whereby each node of the branch-and-bound tree corresponds with a potential order to deliver a subset of packages. An approximate lower bound at each node is given by solving a dynamic program. We provide additional variants of our heuristic approach and compare solution quality and computation times. Consideration is given to various input parameters and distance metrics. The online supplement is available at https://doi.org/10.1287/ijoc.2018.0826 .

Unmanned aerial vehicles (UAVs), or aerial drones, are an emerging technology with significant market potential. UAVs may lead to substantial cost savings in, for instance, monitoring of difficult‐to‐access infrastructure, spraying fields and performing surveillance in precision agriculture, as well as in deliveries of packages. In some applications, like disaster management, transport of medical supplies, or environmental monitoring, aerial drones may even help save lives. In this article, we provide a literature survey on optimization approaches to civil applications of UAVs. Our goal is to provide a fast point of entry into the topic for interested researchers and operations planning specialists. We describe the most promising aerial drone applications and outline characteristics of aerial drones relevant to operations planning. In this review of more than 200 articles, we provide insights into widespread and emerging modeling approaches. We conclude by suggesting promising directions for future research.

The aesthetic quality of routes is a feature of route planning that is of practical importance, but receives relatively little attention in the literature. Several practitioners have pointed out that the visual appeal of a proposed set of routes can have a strong influence on the willingness of a client to accept or reject a specific routing plan. While some work has analyzed algorithmic performance relative to traditional min‐sum or min‐max objective functions and aesthetic objective functions, we are not aware of any work that has considered a multi‐objective approach. This work considers a multi‐objective variant of the Min‐Max K‐Vehicles Windy Rural Postman Problem, discusses several formulations of the problem, and presents computational experiments with a heuristic algorithm. After exploring several formulations, we choose to study the problem with a bi‐objective function that includes contributions from the route overlap index and average task distance aesthetic measures. The heuristic extends the cluster‐first procedure presented in Lum et al. (Networks 69 (2017), 290–303) by incorporating the new objective function into the improvement phase and adding a perturbation routine. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 70(3), 216–232 2017

In practice, it is often desirable for the routes of vehicles to be compact and separate. A set of routes is compact if the streets serviced by each route are geographically clustered, and separated if the routes overlap minimally. We consider the Min–Max K Windy Rural Postman Problem (MMKWRPP), in which the objective is to route a homogeneous fleet of K vehicles such that the cost of the longest route is minimized. We develop a heuristic that is algorithmically simple, produces solutions that are comparable in quality to those produced by an existing approach, and performs well with respect to metrics that quantify compactness and separation. Our heuristic uses a partitioning scheme in which the weight of a vertex includes contributions from both incident streets requiring service and the distance needed to travel to a vertex. We present computational results for a set of instances that we generate from real‐world street networks and for a set of artificial instances. Our code is part of the Open‐source Arc Routing Library (OAR Lib) at https://github.com/Olibear/ArcRoutingLibrary . © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 69(3), 290–303 2017

The vehicle routing problem with drones (VRPD) is inspired by the increasing interest in commercial drone delivery by companies such as Amazon, Google, DHL, and Walmart. In our model, a fleet of m homogeneous trucks each carries k drones with a speed of α times that of the truck. Each drone may dispatch from the top of the truck and carry a package to a customer location. The drone then returns to the top of its truck to recharge or swap batteries (we assume instantaneously). The truck itself is allowed to move and deliver packages, but must be stationary at a delivery location or the depot when launching or retrieving drones. The goal is to minimize the completion time to deliver all packages and return all vehicles back to the central depot. In this article, we review and extend several worst‐case results from an earlier paper and we make connections with another practical variant of the vehicle routing problem and with Amdahl's Law. We find that the VRPD model offers some important practical advantages. The drones allow the truck to parallelize tasks and they are able to take advantage of crow‐fly distances. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 70(1), 34–43 2017

This paper presents a heterogeneous computing solution for an optimized genetic selection analysis tool, GenSel. GenSel can be used to efficiently infer the effects of genetic markers on a desired trait or to determine the genomic estimated breeding values (GEBV) of genotyped individuals. To predict which genetic markers are informational, GenSel performs Bayesian inference using Gibbs sampling, a Markov Chain Monte Carlo (MCMC) algorithm. Parallelizing this algorithm proves to be a technically challenging problem because there exists a loop carried dependence between each iteration of the Markov chain. The approach presented in this paper exploits both task-level parallelism (TLP) and data-level parallelism (DLP) that exists within each iteration of the Markov chain. More specifically, a combination of CPU threads using OpenMP and GPU threads using NVIDIA's CUDA paradigm is implemented to speed up the sampling of each genetic marker used in creating the model. Performance speedup will allow this algorithm to accommodate the expected increase in observations on animals and genetic markers per observation. The current implementation executes 1.84 times faster than the optimized CPU implementation.

An increasing number of companies focus on customer satisfaction to increase the lifetime value of each customer. In vehicle routing, customer satisfaction is often a result of consistent service. Customers appreciate service at regular times of the day provided by the same driver each time. Additionally, drivers become more familiar with their tasks if they visit the same customers and service regions repeatedly. In this article, we survey literature that addresses service consistency in vehicle routing. We present early solution approaches, starting from the 1970s, that focus on reducing the operational complexity resulting from planning and executing new routes each day. One side benefit of these approaches is service consistency; therefore, many recent solution approaches devised for improving customer satisfaction are based on previous achievements. We classify the literature according to three consistency features: arrival time consistency, person-oriented consistency, and delivery consistency. For each feature, we survey different modeling concepts and measurements, demonstrate solution approaches, and examine the increase in cost of improving service consistency. We close the article by presenting challenging ideas for future research. © 2014 The Authors Networks Published by Wiley Periodicals, Inc. NETWORKS, Vol. 64(3), 192–213 2014

Given a graph G = (N, E), the covering salesman problem (CSP) is to identify the minimum length tour “covering” all the nodes. More specifically, it seeks the minimum-length tour visiting a subset of the nodes in N such that each node i not on the tour is within a predetermined distance di of a node on the tour. In this paper, we define and develop a generalized version of the CSP, and we refer to it as the generalized covering salesman problem (GCSP). Here, each node i needs to be covered at least ki times, and there is a cost associated with visiting each node. We seek a minimum-cost tour such that each node i is covered at least ki times by the tour. We define three variants of the GCSP. In the first case, each node can be visited by the tour at most once. In the second case, visiting a node i more than once is possible, but an overnight stay is not allowed (i.e., to revisit a node i, the tour has to visit another node before it can return to i). Finally, in the third case, the tour can visit each node more than once consecutively. In this paper, we develop two local search heuristics to find high-quality solutions to the three GCSP variants. To test the proposed algorithms, we generated data sets based on traveling salesman problem library instances. Because the CSP and the generalized traveling salesman problem are special cases of the GCSP, we tested our heuristics on both of those problems as well. Overall, the results show that our proposed heuristics find high-quality solutions very rapidly.

The vehicle routing problem (VRP) is a difficult and well-studied combinatorial optimization problem. We develop a parallel algorithm for the VRP that combines a heuristic local search improvement procedure with integer programming. We run our parallel algorithm with as many as 129 processors and are able to quickly find high-quality solutions to standard benchmark problems. We assess the impact of parallelism by analyzing our procedure's performance under a number of different scenarios.

Methicillin-resistant Staphylococcus aureus (MRSA) is a significant ongoing problem in health care, posing a substantial threat to hospitals and communities as well. Its spread among patients causes many downstream effects, such as a longer length of stay for patients, higher costs for hospitals and insurance companies, and fatalities. An agent-based simulation model is developed to investigate the dynamics of MRSA transmission within a hospital. The simulation model is used to examine the effectiveness of various infection control procedures and explore more specific questions relevant to hospital administrators and policy makers. Simulation experiments are performed to examine the effects of hand-hygiene compliance and efficacy, patient screening, decolonization, patient isolation, and health-care worker-to-patient ratios on the incidence of MRSA transmission and other relevant metrics. Experiments are conducted to investigate the dynamic between the number of colonizations directly attributable to nurses and physicians, including rogue health-care workers who practice poor hygiene. We begin to explore the most likely threats to trigger an outbreak in hospitals that practice high hand-hygiene compliance and additional preventive measures.

Abstract Utility companies typically send their meter readers out each day of the billing cycle in order to determine each customer's usage for the period. Customer churn requires the utility company to periodically remove some customer locations from its meter‐reading routes. On the other hand, the addition of new customers and locations requires the utility company to add new stops to the existing routes. A utility that does not adjust its meter‐reading routes over time can find itself with inefficient routes and, subsequently, higher meter‐reading costs. Furthermore, the utility can end up with certain billing days that require substantially larger meter‐reading resources than others. However, remedying this problem is not as simple as it may initially seem. Certain regulatory and customer service considerations can prevent the utility from shifting a customer's billing day by more than a few days in either direction. Thus, the problem of reducing the meter‐reading costs and balancing the workload can become quite difficult. We describe this Balanced Billing Cycle Vehicle Routing Problem in more detail and develop an algorithm for providing solutions to a slightly simplified version of the problem. Our algorithm uses a combination of heuristics and integer programming via a three‐stage algorithm. We discuss the performance of our procedure on a real‐world data set. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

We are proud to announce the winners of the Glover-

Abstract In the split delivery vehicle routing problem (SDVRP), a customer's demand can be split among several vehicles. In this article, we review applications of the SDVRP including the routing of helicopters in the North Sea and solution methods such as integer programming and tabu search. We develop a new heuristic that combines a mixed integer program and a record‐to‐record travel algorithm. Our heuristic produces high‐quality solutions to six benchmark problems that have 50–199 customers and generally performs much better than tabu search. On five other problems for which lower bounds exist, our heuristic obtains solutions within 5.85%, on average. Finally, we generate 21 new test problems that have 8–288 customers. A near‐optimal solution can be visually estimated for each problem. We apply our heuristic to these new problems and report our computational results. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 49(4), 318–329 2007

In this paper, we consider the multilevel capacitated minimum spanning tree (MLCMST) problem, a generalization of the well-known capacitated minimum spanning tree (CMST) problem, that allows for multiple facility types in the design of the network. We develop two flow-based mixed integer programming formulations that can be used to find tight lower bounds for MLCMST problems with up to 150 nodes. We also develop several heuristic procedures for the MLCMST problem. First, we present a savings-based heuristic. Next, we develop local search algorithms that use exponential size, node-based, cyclic and path exchange neighborhoods. Finally, we develop a hybrid genetic algorithm for the MLCMST. Extensive computational results on a large set of test problems indicate that the genetic algorithm is robust and, among the heuristics, generates the best solutions. They are typically 6.09% from the lower bound and 0.25% from the optimal solution value.

Given a connected, undirected graph G whose edges are labeled, the minimum label (or labeling) spanning tree (MLST) problem seeks a spanning tree on G with the minimum number of distinct labels. Maximum vertex covering algorithm (MVCA) is a well-known heuristic for the MLST problem. It is very fast and performs reasonably well. Recently, we developed a genetic algorithm (GA) for the MLST problem. The GA and MVCA are similarly fast but the GA outperforms the MVCA. In this paper, we present four modified versions of MVCA, as well as a modified GA. These modified procedures generate better results, but are more expensive computationally. The modified GA is the best performer with respect to both accuracy and running time

The generalized minimum spanning tree (GMST) problem occurs in telecommunications network planning, where a network of node clusters needs to be connected via a tree architecture using exactly one node per cluster. The problem is known to be NP-hard, and even finding a constant factor approximation algorithm is NP-hard. In this paper, we present two heuristic search approaches for the GMST problem: local search and a genetic algorithm. Our computational experiments show that these heuristics rapidly provide high-quality solutions for the GMST and outperform some previously suggested heuristics for the problem. In our computational tests on 211 test problems (including 169 problems from the TSPLIB set), our local-search heuristic found the optimal solution in 179 instances and our genetic-algorithm procedure found the optimal solution in 185 instances (out of the 211 instances, the optimal solution is known in 187 instances). Further, on each of the 19 unsolved instances from TSPLIB, both our local-search heuristic and genetic-algorithm procedure improved upon the best previously known solution.

Given a connected, undirected graph G whose edges are labeled (or colored), the minimum labeling spanning tree (MLST) problem seeks a spanning tree on G with the minimum number of distinct labels (or colors). In recent work, the MLST problem has been shown to be NP-hard and an effective heuristic [maximum vertex covering algorithm (MVCA)] has been proposed and analyzed. We use a one-parameter genetic algorithm (GA) to solve the problem. In computational tests, the GA clearly outperforms MVCA.

In dealing with a very large data set, it might be impractical to construct a decision tree using all of the points. Even when it is possible, this might not be the best way to utilize the data. As an alternative, subsets of the original data set can be extracted, a tree can be constructed on each subset, and then parts of individual trees can be combined in a smart way to produce an improved final set of feasible trees or a final tree. In this paper, we take trees generated by a commercial decision tree package, namely, C4.5, and allow them to crossover and mutate (using a genetic algorithm) for a number of generations in order to yield trees of better quality. We conduct a computational study of our approach using a real-life marketing data set. In this study, we divide the data set into training, scoring, and test sets, and find that our approach produces uniformly high-quality decision trees. In addition, we investigate the impact of scaling and demonstrate that our approach can be used effectively on very large data sets.

Recently, several general optimization algorithms based on the demon algorithm from statistical physics have been developed and tested on a few traveling salesman problems with encouraging results. In this paper, we conduct an extensive computational study of 11 annealing-based heuristics for the traveling salesman problem. We code versions of simulated annealing, threshold accepting, record-to-record travel and eight heuristics based on the demon algorithm. We apply each heuristic to 29 traveling salesman problems taken from a well-known online library, compare the results with respect to accuracy and running time and provide insights and suggestions for future work.

On behalf of the Editorial Board, Bruce L. Golden, Editor-in-Chief thanks the individuals listed for having acted as referees for papers considered for publication during 1998.

In this paper, we introduce the concept of fine-tuned learning which relies on the notion of data approximation followed by sequential data refinement. We seek to determine whether fine-tuned learning is a viable approach to use when trying to solve combinatorial optimization problems. In particular, we conduct an extensive computational experiment to study the performance of fine-tuned-learning-based heuristics for the traveling salesman problem (TSP). We provide important insight that reveals how fine-tuned learning works and why it works well, and conclude that it is a meritorious concept that deserves serious consideration by researchers solving difficult problems.

Abstract In the period vehicle routing problem, each customer requires a certain number of deliveries per week. Given these frequency requirements, customers must be allocated to days. A vehicle routing problem is solved over each day. We have improved upon best‐known solutions to problems from the literature using a new heuristic procedure. The heuristic also works well on 19 newly generated test problems.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

No abstract available. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

No abstract available. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

No abstract available. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Abstract When a statistical agency, such as the United States Bureau of the Census, publishes tabular data, it must withhold certain data elements that contain confidential information associated with the data respondents. Cell suppression is a technique commonly used in the publishing of economic data in tabular formats. The sensitive entries, which are called primary suppressions, need to be suppressed. However, the suppression of the primary cells alone still allows one to estimate a range for each of the missing values by considering the published entries. Additional entries in the table must be suppressed to ensure that these ranges are not too narrow. Traditionally, the protection required is defined by an interval centered around the value of each primary suppression. This paper formulates and develops solution techniques for the traditional problem as well as for a relaxation of the problem where sliding protection ranges are allowed. In the relaxed problem, the protection ranges have fixed widths but are free to slide; the only restriction is that each range must contain the value of the primary suppression. We present network flow‐based heuristics for both versions of the cell suppression problem and use a lower‐bounding procedure to evaluate the performance of the heuristics. Extensive computational results based on real‐world and randomly generated tables demonstrate that sliding protection ranges can significantly reduce the total amount of suppressed data, as compared to the traditional suppression scheme. Furthermore, the heuristics produce optimal or near‐optimal solutions for real‐world problems.

Controlled rounding is a procedure whereby tabular data gathered from respondents is perturbed in such a way as to preserve the anonymity of the respondents while maintaining the integrity of the data. This paper describes an algorithm for solving three-dimensional controlled rounding problems which is based on simulated annealing, linear programming, and binary search procedures. Numerical results obtained from processing 32,500 randomly generated tables and 292 real-life tables have demonstrated that this algorithm can efficiently find controlled roundings, provided they exist. The algorithm is significantly faster than any previously known solution procedure for this class of problems. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Abstract In this paper, we examine the problem of finding k‐shortest paths between an origin and destination pair when distances are Euclidean. Two versions of a generalized Dijkstra algorithm are compared. Computational results show that the advantage of the adaptive version (measured by total number of permanent labels) grows with both k and the network size. For large networks, the adaptive algorithm exhibits a 100:1 advantage in the number of permanent labels set.

This book provides a compact survey of selected topics in NLP at an ideal level for advanced undergraduates, especially engineering students. There are a number of fine books on NLP but, to our knowledge, no text designed specifically for a one-semester course is quite as nice. The book consists of five chapters. In Chapter 1, the classical theory of optimization including convexity, Lagrange multipliers, and the Kuhn- Tucker conditions is presented. Chapter 2 examines methods for finding a minimum in the unconstrained case. Chapter 3 studies the theory behind linear programming and, of course, the simplex method. In Chapter 4, applications of linear programming such as the transportation problem, an allocation problem, and game theory are discussed. Finally, in Chapter 5, methods for solving constrained optimization problems are presented; projection methods, quadratic programming methods, penalty and barrier function methods, and Lagrangian methods are described in detail. The book is terse and suffers from a lack of illustrative examples. The instructor should planon providing motivation in order to overcome this limitation.

Abstract A capacitated node routing problem, known as the vehicle routing or dispatch problem, has been the focus of much research attention. On the other hand, capacitated arc routing problems have been comparatively neglected. Both classes of problems are extremely rich in theory and applications. Our 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. In addition, we identify several related routing problems and develop tight lower bounds on the optimal solution.

Abstract This paper considers the problem of finding the shortest path between an origin and destination pair in networks whose arc lengths are Euclidean distances. Dijkstra's algorithm and a modified version of Dijkstra's algorithm which is more adaptive to network topology are compared. We demonstrate on the infinite lattice network with diagonal arcs (a prototype of more general sparse Euclidean networks) that on the average the adaptive algorithm expands less than 8.3% the area that would be expanded by the Dijkstra algorithm and in the worst case it expands less than 10.7%. In addition, we present computational results for more general networks.

Abstract This paper is an example of the growing interface between statistics and mathematical optimization. A very efficient heuristic algorithm for the well‐known NP‐complete TSP is presented, from which statistical estimates of the optimal tour length can be derived. Assumptions, along with computational experience and conclusions are discussed.

"7-102-77." Includes author index. Cover title.

Abstract Heuristic programming algorithms frequently address large problems and require manipulation and operation on massive data sets. The algorithms can be improved by using efficient data structures. With this in mind, we consider heuristic algorithms for vehicle routing, comparing techniques of Clarke and Wright, Gillett and Miller, and Tyagi, and presenting modifications and extensions which permit problems involving hundreds of demand points to be solved in a matter of seconds. In addition, a multi‐depot routing algorithm is developed. The results are illustrated with a routing study for an urban newspaper with an evening circulation exceeding 100,000.

Abstract This paper develops an algorithm for handling nonlinear minimum‐cost multicommodity flow problems and applies it to a specific large‐scale network. The commodities will be imports and exports; the cost functions will be quadratic and convex. The setting will be a Port Planning Model which will seek to find optimal simultaneous routings through the network while fulfilling requirements both at foreign ports and at domestic hinterlands. The computer program written solves such a problem. The algorithm involves linearizing the cost function and solving the resulting linear program, which is, in fact, a series of shortest route problems. Negative cycles are studied in depth.