Search

Utility companies collect usage data from meters on a regular basis. The usage data are collected automatically using radio-frequency identification (RFID) technology. Each meter transmits signals from an RFID tag that are read by a vehicle-mounted reading device within a specified distance. Routing the vehicles can be modeled by a close-enough vehicle routing problem on a street network. In practice, there is uncertainty while reading meters. The signal transmitted by an RFID tag is discontinuous, and the range that each meter can be read is different and stochastic due to weather conditions, surrounding obstacles, interference, and decreasing battery life of the RFID tags. These factors can lead to meters not being read. A vehicle has to be sent at a later time to read the missed meters, and this leads to increased costs for a utility company due to additional operational costs and overtime payments to drivers. Our aim is to address the uncertainty issues of the RFID technology by generating routes that are both cost-effective and robust (we seek to minimize the number of missed reads). We use data analytics, optimization, and Bayesian statistical models to address the uncertainty. Simulation experiments using real data show that the hierarchical Bayesian statistical model gives better results compared to other Bayesian statistical models. Utility companies can potentially integrate the results from the hierarchical Bayesian statistical model into their route generating software as a decision-support tool to produce routes that are more cost-effective and robust than the routes that they currently generate.

Author(s): Ren, Ai; Golden, Bruce; Alt, Frank; Wasil, Edward; Bjarnadottir, Margret; Hirshon, Jon Mark; Pimentel, Laura | Abstract: Introduction: On January 1, 2014, the State of Maryland implemented the Global Budget Revenue (GBR) program. We investigate the impact of GBR on length of stay (LOS) for inpatients in emergency departments (ED) in Maryland.Methods: We used the Hospital Compare data reports from the Centers for Medicare and Medicaid Services (CMS) and CMS Cost Reports Hospital Form 2552-10 from January 1, 2012–March 31, 2016, with GBR hospitals from Maryland and hospitals from West Virginia (WV), Delaware (DE), and Rhode Island (RI). We implemented difference-in-differences analysis and investigated the impact of GBR implementation on the LOS or ED1b scores of Maryland hospitals using a mixed-effects model with a state-level fixed effect, a hospital-level random effect, and state-level heterogeneity.Results: The GBR impact estimator was 9.47 (95% confidence interval [CI], 7.06 to 11.87, p-valuel0.001) for Maryland GBR hospitals, which implies, on average, that GBR implementation added 9.47 minutes per year to the time that hospital inpatients spent in the ED in the first two years after GBR implementation. The effect of the total number of hospital beds was 0.21 (95% CI, 0.089 to 0.330, p-value = 0 .001), which suggests that the bigger the hospital, the longer the ED1b score. The state-level fixed effects for WV were -106.96 (95% CI, -175.06 to -38.86, p-value = 0.002), for DE it was 6.51 (95% CI, -8.80 to 21.82, p-value=0.405), and for RI it was -54.48 (95% CI, -82.85 to -26.10, p-valuel0.001).Conclusion: Our results indicate that GBR implementation has had a statistically significant negative impact on the efficiency measure ED1b of Maryland hospital EDs from January 2014 to April 2016. We also found that the significant state-level fixed effect implies that the same inpatient might experience different ED processing times in each of the four states that we studied. [West J Emerg Med.

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 .

We present an open source, arc routing Java library that has a flexible graph architecture with solvers for several uncapacitated arc routing problems and the ability to dynamically generate and visualize real-world street networks. The library is hosted at https://github.com/Olibear/ArcRoutingLibrary ( https://doi.org/10.5281/zenodo.2561406 ). We describe the algorithms in the library, report computational performance, and discuss implementation issues.

We construct empirically based regression models for estimating the tour length in the Close Enough Traveling Salesman Problem (CETSP). In the CETSP, a customer is considered visited when the salesman visits any point in the customer’s service region. We build our models using as many as 14 independent variables on a set of 780 benchmark instances of the CETSP and compare the estimated tour lengths to the results from a Steiner zone heuristic. We validate our results on a new set of 234 instances that are similar to the 780 benchmark instances. We also generate results for a new set of 72 larger instances. Overall, our models fit the data well and do a very good job of estimating the tour length. In addition, we show that our modeling approach can be used to accurately estimate the optimal tour lengths for the CETSP.

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 a variant of the Traveling Salesman Problem (TSP) known as the Close-Enough Traveling Salesman Problem (CETSP). A salesman does not have to visit the exact location of each customer. Instead, the salesman needs only to get close enough to each customer. This feature allows savings from the classic TSP solution, but also adds complexity to the problem. We develop a Steiner Zone Variable Neighborhood Search heuristic (SZVNS) to solve the CETSP. We conduct computational experiments on 842 instances. SZVNS often produces optimal solutions to the small instances where optimal solutions are known. On the larger instances, SZVNS produces shorter or similar solutions in less time when compared to the solutions produced by state-of-the-art heuristics.

Optimization algorithms and heuristic procedures for arc-routing problems often use benchmark instances to validate and demonstrate performance. Ideally, these benchmark instances capture the features of real-world street networks. Typically, benchmark instances are artificially generated and only approximate real-world networks. We develop a software tool that allows users to generate arc-routing instances directly from an open-source, user-driven map database. Our tool gives the user the ability to edit the instances by hand or by using configurable parameters. The instances generated by our tool can then be exported for use by researchers. In addition, our tool has a visualization capability that can produce images of routes overlaid on the instance. The online supplement is available at https://doi.org/10.1287/ijoc.2017.0785.

The event of high emergency department (ED) utilization or inaccessibility to the ED may result in hospital after hospital in a city not accepting new patients in need of urgent medical care. We call this a cascading event. In this paper, we investigate cascading events among 11 EDs in Baltimore City in 2018 and 2019 using a two-state Markov model. Additionally, the transition probabilities are used to monitor the evolution of cascading events. Meanwhile, we predict the expected remaining hours in each state. After we calculate and compare the probabilities of having a cascading event for each ED, we finally identify the similarity and heterogeneity among EDs using cluster analysis. The findings of our study reveal that the continuous yellow alerts at Johns Hopkins Hospital, Johns Hopkins Bayview Medical Center (JH Bayview), Sinai Hospital, and the University of Maryland Medical Center (UMMC) are associated with a large chance of having a cascading event in the city that affects all 11 hospitals. Weekdays dramatically increased chances of having a cascading event.

In arc routing applications, some streets may require service along both sides of the street. For a subset of these streets, the vehicle operator may choose to service both sides during a single traversal. We refer to this as zigzag service. In contrast to servicing each side separately, the vehicle stops more frequently and incurs a traversal cost, two service costs, and a penalty cost associated with the slowed travel time required to perform the zigzag service. The tradeoff is that the vehicle only needs to service the street once on its route. However, for other streets zigzag service is only possible during the early part of a day when there is very little traffic. This scenario is modeled by the Windy Rural Postman Problem with Zigzag Time Windows (WRPPZTW). We develop a hybrid heuristic for the WRPPZTW that combines standard insertion and local search techniques with integer programming. We compare the computational performance of our heuristic to an exact procedure from Nossack et al. (2017) on a set of small instances with 28 edges and test the scalability of our heuristic on a set of larger grid instances with as many as 1200 edges.

Introduction On January 1, 2014, the financing and delivery of healthcare in the state of Maryland (MD) profoundly changed. The insurance provisions of the Patient Protection and Affordable Care Act (ACA) began implementation and a major revision of MD’s Medicare Waiver ushered in global budget revenue (GBR) structure for hospital reimbursement. Our objective is to analyze the impact of these policy changes on Emergency Department (ED) utilization, admission practices, insurance profiles, and professional revenue. We stratified our analysis by the socioeconomic status (SES) of the ED patient population. Methods Monthly mean data including patient volume, admission and observation percentages, payer mix, and professional revenue were collected from January 2013 through December 2015 from a convenience sample of 11 EDs in Maryland. Using regression models, we compared each of the variables 18 months after the policy changes and a six-month washout period to the year prior to ACA/GBR implementation. We included the median income of each ED’s patient population as an explanatory variable and stratified our results by SES. Results Our 11 EDs saw an annualized volume of 399,310 patient visits during the study period. This ranged from a mean of 41 daily visits in the lowest volume rural ED to 171 in the highest volume suburban ED. After ACA/GBR, ED volumes were unchanged (95% Confidence Interval (CI): (-1.58, 1.24), p=.817). Admission plus observation percentages decreased significantly by 1.9% from 17.2% to 15.3% (95% CI: (-2.47%, - 1.38%), p

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. 693, 290-303 2017

The min-max Split Delivery Multi-Depot Vehicle Routing Problem with Minimum Service Time Requirement (min-max SDMDVRP-MSTR) is a variant of the Multi-Depot Vehicle Routing Problem. Each customer requires a specified amount of service time. The service time can be split among vehicles as long as each vehicle spends a minimum amount of service time at a customer. The objective is to minimize the duration of the longest route (where duration is the sum of travel and service times).We develop a heuristic (denoted by MDS) that solves the min-max SDMDVRP-MSTR in three stages: (1) initialize a feasible solution without splits; (2) improve the longest routes by splitting service times; (3) ensure all minimum service time requirements are satisfied. The first stage of MDS is compared to an existing heuristic to solve the min-max Multi-Depot Vehicle Routing Problem on 43 benchmark instances. MDS produces 37 best-known solutions. We also demonstrate the effectiveness of MDS on 21 new instances whose (near) optimal solutions can be estimated based on geometry. Finally, we investigate the savings from split service and the split patterns as we vary the required service times, the average number of customers per route, and the minimum service time requirement. HighlightsA new variant of the Multiple Depot Vehicle Routing Problem is described.We develop a heuristic that generates high-quality solutions to benchmark and new instances.Our heuristic could be used by managers in applications such as newspaper delivery and disaster relief routing.

According to data from the Surveillance, Epidemiology, and End Results (SEER) program in the United States, approximately 15% of men will be diagnosed with prostate cancer during their lifetimes. Over the past 15 years, the battle against prostate cancer has been joined by researchers and practitioners who have used a wide variety of operations research (OR) models and methods to investigate decisions involving screening, detection, and treatment of prostate cancer. We provide a narrative review of articles falling into the following five categories: decision analysis, machine learning, optimization, simulation, and statistics. We identified a total of 523 archival journal articles describing the use of methods in these categories in the context of prostate cancer since 2000. We categorize and annotate 49 of these articles in order to provide representative examples of the use of OR models and methods in each of these areas. We conclude with a summary of the trends in research using OR methods in the context of prostate cancer over the past 15 years, and a discussion about how these trends will influence future research.

The percentage of patients leaving before treatment is completed (LBTC) is an important indicator of emergency department performance. The objective of this study is to identify characteristics of hospital operations that correlate with LBTC rates.The Emergency Department Benchmarking Alliance 2012 and 2013 cross-sectional national data sets were analyzed using multiple regression and k-means clustering. Significant operational variables affecting LBTC including annual patient volume, percentage of high-acuity patients, percentage of patients admitted to the hospital, number of beds, academic status, waiting times to see a physician, length of stay (LOS), registered nurse (RN) staffing, and physician staffing were identified. LBTC was regressed onto these variables. Because of the strong correlation between waiting times measured as door to first provider (DTFP), we regressed DTFP onto the remaining predictors. Cluster analysis was applied to the data sets to further analyze the impact of individual predictors on LBTC and DTFP.LOS and the time from DTFP were both strongly associated with LBTC rate (P.001). Patient volume is not significantly associated with LBTC rate (P=.16). Cluster analysis demonstrates that physician and RN staffing ratios correlate with shorter DTFP and lower LBTC.Volume is not the main driver of LBTC. DTFP and LOS are much more strongly associated. We show that operational factors including LOS and physician and RN staffing decisions, factors under the control of hospital and physician executives, correlate with waiting time and, thus, in determining the LBTC rate.

The split delivery vehicle routing problem (SDVRP) is a relaxed version of the classic capacitated vehicle routing problem (CVRP). Customer demands are allowed to split among vehicles. This problem is computationally challenging and the state-of-the-art heuristics are often complicated to describe and difficult to implement, and usually have long computing times. All these hinder their application by practitioners to solve real-world problems. We propose a novel, efficient, and easily implemented approach to solve the SDVRP using an a priori split strategy, that is, each customer demand is split into small pieces in advance. Our computational experiments on 82 benchmark instances show that our algorithm is overall much more efficient and produces results that are comparable to those from the state-of-the-art approaches.

In the multi-depot vehicle routing problem (MDVRP), there are several depots where vehicles can start and end their routes. The objective is to minimize the total distance travelled by all vehicles across all depots. The min-max multi-depot vehicle routing problem (Min-Max MDVRP) is a variant of the standard MDVRP. The primary objective is to minimize the length of the longest route. We develop a heuristic (denoted by MD) for the Min-Max MDVRP that has three stages: (1) simplify the multi-depot problem into a single depot problem and solve the simplified problem; (2) improve the maximal route; (3) improve all routes by exchanging customers between routes. MD is compared with two alternative heuristics that we also develop and an existing method from the literature on a set of 20 test instances. MD produces 15 best solutions and is the top performer. Additional computational experiments on instances with uniform and non-uniform distributions of customers and varying customer-to-vehicle ratios and with real-world data further demonstrate MD’s effectiveness in producing high-quality results.

In this paper, we consider the Directed Rural Postman Problem with Turn Penalties (DRPP-TP). A solution is a tour that traverses all required arcs of the graph. The total cost of the tour is the sum of the lengths of the traversed arcs plus the penalties associated with the turns. One solution approach involves transforming the arc routing problem into an equivalent node routing problem. An alternative direct approach (without graph transformation) that involves two stages has been proposed in the literature. In the first part of this paper, we investigate the applicability of the direct approach. We identify several characteristics of the input instance that make this approach effective and present several limitations of this approach. In the second part of this paper, we describe an integer linear program that is combined with a local search algorithm. This combination produces high-quality solutions to the DRPP-TP in a reasonable amount of computing time.

Background: In emergency departments (EDs), the implementation of electronic health records (EHRs) has the potential to impact the rapid assessment and management of life threatening conditions. In order to quantify this impact, we studied the implementation of EHRs in the EDs of a two hospital system. Methods: using a prospective pre–post study design, patient processing metrics were collected for each ED physician at two hospitals for 7 months prior and 10 months post-EHR implementation. Metrics included median patient workup time, median length of stay, and the composite outcome indicator "processing time." Results: median processing time increased immediately post-implementation and then returned to, and surpassed, the baseline level over 10 months. Overall, we see significant decreases in processing time as the number of patients treated increases. Conclusions: implementation of new EHRs into the ED setting can be expected to cause an initial decrease in efficiency. With adaptation, efficiency should return to baseline levels and may eventually surpass them. Implications: while EDs can expect long term gains from the implementation of EHRs, they should be prepared for initial decreases in efficiency and take preparatory measures to avert adverse effects on the quality of patient care.

We propose a method of diagnosing prostate cancer using magnetic resonance imaging data. Logistic regression and nearest neighbor classification are combined to identify the risk of cancer. Our method performs well, having 79 % predictive accuracy, and an area under the ROC curve of 0.85. It identifies the most aggressive cancers with 82 % accuracy.

In winter, a common problem is to determine a set of routes for snow plows that minimize the maximum route length. Typically, this is modelled as an arc routing problem. We begin with a variant that is motivated by the fact that deadhead travel over streets is significantly faster than the time it takes to plow the street. We incorporate the use of multiple plows and the observation that, on steep streets, it is much more difficult, or impossible, to plow uphill. Therefore, we want to design routes that try to avoid plowing uphill on steep streets and take advantage of the faster traversal time for deadheading. We generalize this problem to include multiple plows and seek to minimize the maximum route length. We present a heuristic that generates solutions with costs that are very close to a lower bound.

In winter, a common problem is to determine the route that a snowplow should take in order to minimize the distance traveled. We propose a variant of this arc routing problem that is motivated by the fact that deadhead travel over streets that have already been plowed is significantly faster than the time it takes to plow the street. This problem differs from most arc routing problems because the cost of traversing a street changes depending on the order of the streets on a route. We develop a method that generates near-optimal solutions to instances as large as 200 nodes.

We investigate the transmission of infectious diseases in hospitals using a network-centric perspective. Patients who share a healthcare worker are inherently connected to each other and those connections form a network through which transmission can occur. The structure of this network can be a strong determinant of the extent and rate of transmission. We explore the effects of healthcare worker behavior, including sharing patients and incorporating the ability for healthcare workers to infect each other. Finally, we examine how patient turnover can affect transmission dynamics in a patient network under the influence of other effects. Our results show that all of these factors can affect transmission significantly, and that this model can be used to provide additional insight to hospital administrators who are looking to improve their ability to control infections.

In the vehicle routing problem (VRP), a fleet of vehicles must service the demands of customers in a least-cost way. In the split delivery vehicle routing problem (SDVRP), multiple vehicles can service the same customer by splitting the deliveries. By allowing split deliveries, savings in travel costs of up to 50 % are possible, and this bound is tight. Recently, a variant of the SDVRP, the split delivery vehicle routing problem with minimum delivery amounts (SDVRP-MDA), has been introduced. In the SDVRP-MDA, split deliveries are allowed only if at least a minimum fraction of a customer’s demand is delivered by each visiting vehicle. We perform a worst-case analysis on the SDVRP-MDA to determine tight bounds on the maximum possible savings.

The distribution of relief aid is a complex problem where the operations have to be managed efficiently due to limited resources. We present a routing problem for relief operations whose primary goal is to satisfy demand for relief supplies at many locations taking into account the urgency of each demand. We have a single vehicle of unlimited capacity. Each node (location) has a demand and a priority. The priority indicates the urgency of the demand. Typically, nodes with the highest priorities need to be visited before lower priority nodes. We describe a new and interesting model for humanitarian relief routing that we call the hierarchical traveling salesman problem (HTSP). We compare the HTSP and the classical TSP in terms of worst-case behavior. We obtain a simple, but elegant result that exhibits the fundamental tradeoff between efficiency (distance) and priority and we provide several related observations and theorems.

The multi-depot split delivery vehicle routing problem combines the split delivery vehicle routing problem and the multiple depot vehicle routing problem. We define this new problem and develop an integer programming-based heuristic for it. We apply our heuristic to 30 instances to determine the reduction in distance traveled that can be achieved by allowing split deliveries among vehicles based at the same depot and vehicles based at different depots. We generate new test instances with high-quality, visually estimated solutions and report results on these instances.

We develop a heuristic for the period vehicle routing problem that uses an integer program and the record-to-record travel algorithm. Our heuristic produces very high-quality results on standard benchmark instances. We extend our heuristic to handle real-world routing considerations that involve reassigning customers to new routes and balancing the workload among drivers across routes. We demonstrate how these new variants can be used by managers to generate effective routes in practice.

We investigate the discharge practices at a large medical center. Specifically, we look for indications that patients are being discharged sooner because of hospital bed-capacity constraints. Using survival analysis techniques, we find statistically significant evidence to indicate that surgeons adjust their discharge practices to accommodate the surgical schedule and number of available recovery beds. We find higher discharge rates on days when utilization is high. We also find an increased discharge rate on days when more surgeries are scheduled. Our findings suggest that discharge decisions are made with bed-capacity constraints in mind. We discuss possible explanations for this, as well as the medical and managerial implications of our findings.

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.

When operating room schedules in hospitals are produced, the constraints and preferences of surgeons and hospital workers are a primary consideration. The downstream impact on post-operative bed availability is often ignored. This can lead to the boarding of patients overnight in the post-anesthesia care unit (PACU) because intensive care unit beds are unavailable. In this paper, we apply integer programming and simulation to develop improved surgical scheduling assignments. We want to balance new surgeries with hospital discharges in order to reduce the variability of occupied beds from one day to the next and, as a result, to reduce boarding in the PACU.

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.

In the vehicle routing problem, a fleet of vehicles must service the demands of customers in a least-cost way. By allowing multiple vehicles to service the same customer (i.e., splitting deliveries), substantial savings in travel costs are possible. However, split deliveries are often an inconvenience to the customer who would prefer to have demand serviced in a single visit. We consider the vehicle routing problem in which split deliveries are allowed only if a minimum fraction of a customer’s demand is serviced by a vehicle. We develop a heuristic method for solving this problem and report computational results on a wide range of problem sets.

The vehicle routing problem (VRP) is a difficult and well-studied combinatorial optimization problem. Real-world instances of the VRP can contain hundreds and even thousands of customer locations and can involve many complicating constraints, necessitating the use of heuristic methods. We present a software library of local search heuristics that allows one to quickly generate solutions to VRP instances. The code has a logical, object-oriented design and uses efficient data structures to store and modify solutions. The core of the library is the implementation of seven local search operators that share a similar interface and are designed to be extended to handle additional options with minimal code change. The code is well-documented, straightforward to compile, and is freely available online. The code contains several applications that can be used to generate solutions to the capacitated VRP. Computational results indicate that these applications are able to generate solutions that are within about one percent of the best-known solution on benchmark problems.

In the small package shipping industry (as in other industries), companies try to differentiate themselves by providing high levels of customer service. This can be accomplished in several ways, including online tracking of packages, ensuring on-time delivery, and offering residential pickups. Some companies want their drivers to develop relationships with customers on a route and have the same drivers visit the same customers at roughly the same time on each day that the customers need service. These service requirements, together with traditional constraints on vehicle capacity and route length, define a variant of the classical capacitated vehicle routing problem, which we call the consistent VRP (ConVRP). In this paper, we formulate the problem as a mixed-integer program and develop an algorithm to solve the ConVRP that is based on the record-to-record travel algorithm. We compare the performance of our algorithm to the optimal mixed-integer program solutions for a set of small problems and then apply our algorithm to five simulated data sets with 1,000 customers and a real-world data set with more than 3,700 customers. We provide a technique for generating ConVRP benchmark problems from vehicle routing problem instances given in the literature and provide our solutions to these instances. The solutions produced by our algorithm on all problems do a very good job of meeting customer service objectives with routes that have a low total travel time. In the paper “The Consistent Vehicle Routing Problem,” published in Manufacturing & Service Operations Management, ePub ahead of print December 4, 2008, http://dx.doi.org/10.1287/msom.1080.0243, the authors have amended the original text published online to correct an oversight in conveying the real-world problem studied in this article.

In the open vehicle routing problem (OVRP), a vehicle does not return to the depot after servicing the last customer on a route. The description of this variant of the standard vehicle routing problem appeared in the literature over 20 years ago, but has just recently attracted the attention of practitioners and researchers. Today, the OVRP is encountered in practice in the home delivery of packages and newspapers. Contractors who are not employees of the delivery company use their own vehicles and do not return to the depot. In the last five years, tabu search, deterministic annealing, and large neighborhood search have been applied to the OVRP with some success. In this paper, we review OVRP algorithms, develop a variant of our record-to-record travel algorithm for the standard vehicle routing problem to handle open routes, and report computational results on test problems taken from the literature. Finally, we develop a set of eight large-scale problems that range in size from 200 to 480 nodes and report solutions generated by our record-to-record travel algorithm on this test set.

In the heterogeneous fleet vehicle routing problem (HVRP), several different types of vehicles can be used to service the customers. The types of vehicles differ with respect to capacity, fixed cost, and variable cost. We assume that the number of vehicles of each type is fixed and equal to a constant. We must decide how to make the best use of the fixed fleet of heterogeneous vehicles. In this paper, we review methods for solving the HVRP, develop a variant of our record-to-record travel algorithm for the standard vehicle routing problem that takes a heterogeneous fleet into account, and report computational results on eight benchmark problems. Finally, we generate a new set of five test problems that have 200-360 customers and solve each new problem using our record-to-record travel algorithm.

The pantheon of 20th century US Army generals contains many great wartime commanders. Military historians have written about their leadership qualities but have not ranked the best generals. We asked 10 experts in US military history to evaluate seven generals—Omar Bradley, Dwight Eisenhower, Douglas MacArthur, George Marshall, George Patton, John Pershing, and Matthew Ridgway—using the analytic hierarchy process in a group setting. We developed a ratings hierarchy, and each participant scored each general. We combined individual pairwise comparisons using the geometric-mean method and a new method based on linear programming and obtained a clear, three-tier ranking of generals with George Marshall judged the best US Army general of the 20th century, closely followed by Dwight Eisenhower.

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

Classification trees are widely used in the data mining community. Typically, trees are constructed to try and maximize their mean classification accuracy. In this paper, we propose an alternative to using the mean accuracy as the performance measure of a tree. We investigate the use of various percentiles (representing the risk aversion of a decision maker) of the distribution of classification accuracy in place of the mean. We develop a genetic algorithm (GA) to build decision trees based on this new criterion. We develop this GA further by explicitly creating diversity in the population by simultaneously considering two fitness criteria within the GA. We show that our bicriterion GA performs quite well, scales up to handle large data sets, and requires a small sample of the original data to build a good decision tree.

Data visualization techniques have become important tools for analyzing large multidimensional data sets and providing insights with respect to scientific, economic, and engineering applications. Typically, these visualization applications are modeled and solved using nonlinear optimization techniques. In this paper, we propose a discretization of the data visualization problem that allows us to formulate it as a quadratic assignment problem. However, this formulation is computationally difficult to solve optimally using an exact approach. Consequently, we investigate the use of a local search technique for the data visualization problem. The space in which the data points are to be embedded can be discretized using an n × n lattice. Conducting a local search on this n × n lattice is computationally ineffective. Instead, we propose a divide-and-conquer local search approach that refines the lattice at each step. We show that this approach is much faster than conducting local search on the entire n × n lattice and, in general, it generates higher quality solutions. We envision two uses of our divide-and-conquer local search heuristic: (1) as a stand-alone approach for data visualization, and (2) to provide a good approximate starting solution for a nonlinear algorithm.

We present an approach based on linear programming (LP) that estimates the weights for a pairwise comparison matrix generated within the framework of the analytic hierarchy process. Our approach makes sense for a number of reasons, which we discuss. We apply our LP approach to several sample problems and compare our results to those produced by other, widely used methods. In addition, we extend our linear program to include applications where the pairwise comparison matrix is constructed from interval judgments.

The standard vehicle routing problem was introduced in the OR/MS literature about 45 years ago. Since then, the vehicle routing problem has attracted an enormous amount of research attention. In the late 1990s, large vehicle routing problem instances with nearly 500 customers were generated and solved using metaheuristics. In this paper, we focus on very large vehicle routing problems. Our contributions are threefold. First, we present problem instances with as many as 1200 customers along with estimated solutions. Second, we introduce the variable-length neighbor list as a tool to reduce the number of unproductive computations. Third, we apply record-to-record travel with a variable-length neighbor list to 32 problem instances and obtain high-quality solutions, very quickly.

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.