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.

Abstract For nearly 50 years, Networks has been at the forefront of routing research and practice with more than 140 articles in print with tens of thousands of citations. These articles span the development of solution procedures to reporting practical applications. We identify key areas of contribution including exact algorithms, heuristics, arc routing, and periodic routing, and provide detailed annotations for important articles in each area. Our survey reveals the rich heritage of published routing work that continues to influence the field today.

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 .

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 (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

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

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

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.

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.

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.