Canadian Prize Collection Problem Becker, John; Batta, Rajan
Military operations research (Alexandria, Va.),
01/2023, Letnik:
28, Številka:
2
Journal Article
Recenzirano
This paper introduces the Canadian prize collection problem and demonstrates its application for assessing the impact of a disaster event on a region, which can arise in either a military or a ...humanitarian logistics context. The key difference between the Canadian prize collection problem and the "standard" prize collection problem is that some edges are obstructed. These impassable edges are not known a priori; rather, they are discovered by the vehicle as it traverses the network. Three heuristic solution approaches are developed for this problem: a prize collection focused method, a shortest path focused method, and a hybrid method. These three heuristic solution approaches are implemented on a case study that is aimed at assessing the impact of a hurricane event in the Washington, DC-New York City-Boston area. The case study is evaluated at four probability levels of edge obstruction and considering a wide range of available budgets. Results indicate that the shortest path heuristic approach outperforms the prize collection heuristic in most cases for smaller budgets. Also, the shortest path heuristic performs increasingly well compared to the prize collection heuristic as the probability of edge obstruction increases.
The school bus routing problem (SBRP) is crucial because of its impact on economic and social objectives. A single bus is assigned to each route, picking up students and arriving at the school within ...a specified time window. SBRP aims to find the fewest buses needed to cover all of the routes while minimizing the total travel distance and meeting required constraints. We propose a mathematical formulation responding to the overbooking policies applied in a real-world school district. According to our empirical studies, the probability of a student riding a bus varies from 22% to 77%, opening the opportunity to overbook the buses to improve utilization of their capacity. However, SBRP with overbooking has not attracted much attention in previous studies. In this work, overbooking is modeled via chance constrained programming. Additionally, to account for the uncertainty of the total travel time of the buses, a constraint limiting the probability of being late to school is also proposed in this paper. As a result of the NP-hard nature of the problem, a cascade simplification algorithm is proposed to partition the multiple stage SBRP problems into multiple multi-depot and one-school subproblems that are solved sequentially, where the results for one are data inputs for the next. Furthermore, we develop column-generation-based algorithms to solve the scheduling problem, and different instances of the problem are examined. Our computational experiments on a real-world school district demonstrate desirable cost savings in terms of the total number of buses used.
Unmanned aerial vehicles (UAVs) have been proved to be successful and efficient for information collection in a modern battlefield, especially in areas that are considered to be dangerous for human ...pilots. Currently, a UAV is remotely controlled by a ground station through frequent data communications, which make the current system vulnerable in a threat environment. We propose a decentralized control strategy while requiring UAVs to maintain radio silence during the entire mission. The strategy is analyzed based on a scenario where a fleet of vehicles is assigned to search and collect uncertain information in a set of regions within a given mission time. We demonstrate that a region-sharing strategy is beneficial even when there is no extra reward gained from additional information collection. Implementing a region-sharing strategy requires solving a decentralized time allocation problem, which is computationally intractable. To overcome this, an approximate formulation is developed under an independence assumption for information collected by different vehicles. This approximate formulation allows us to decompose, by vehicle, the time allocation problem, and obtain an easily implementable policy that takes on a Markovian form. We develop a sufficient condition under which the approximate formulation becomes exact. A numerical study establishes the computational efficiency of the method; only a few CPU seconds are needed for problems with a planning horizon of 300 time units and 40 regions. We further present a case study to illustrate region-sharing behaviors among UAVs while using practical parameter values. Finally, we compare the obtained policy with the optimal policy found using a complete enumeration method for small instances. Under different parameter settings, the average optimality gap ranges from 0.23% to 19.90%.
The e-companion is available at
https://doi.org/10.1287/opre.2017.1590
.
Gasoline shortages and long lines at the pump spread at stations is a well-known challenge during large-scale evacuations ahead of hurricanes. One of the reasons for this problem is that evacuees ...rush to fuel up in a panic. Therefore, they attempt to get as much gas as they can without considering their true need and without considering other evacuees. An idealized management of gasoline supply is one in which each evacuee that needs gasoline to successfully evacuate is assigned to a specific gas station along an evacuation route where they would be permitted to fill gas. Each gas station is restricted to a specific amount of gasoline per vehicle. This paper develops a mathematical formulation for such an idealized framework. The objective of the formulation is to maximize the number of evacuees that successfully reach the safe zone. The model takes into account different initial fuel level of evacuees, different evacuation starting times, and dynamic flow demand volume for each path over time. The superiority of the idealized evacuation over a simulated uncontrolled evacuation, in different scenarios, is verified on a small example. The idealized evacuation model is also applied to a real-world hurricane evacuation scenario in the evacuation network of St. Johns County, Florida. A creative efficient solution methodology (simplifying the complex constraints) is developed to solve the model to the optimality for the case study. The model’s objective function and solving time are stress-tested over key input parameters. The results show that the idealized evacuation model manages a high percentage of evacuees to successfully reach the safe zones, even with a short amount of gasoline supplies available in the gas stations.
This paper introduces a Value-at-Risk (VaR) model to generate route choices for a hazmat shipment based on a specified risk confidence level. VaR is a threshold value such that the probability of the ...loss exceeding the VaR value is less than a given probability level. The objective is to determine a route which minimizes the likelihood that the risk will be greater than a set threshold. Several properties of the VaR model are established. An exact solution procedure is proposed and tested to solve the single-trip problem. To test the applicability of the approach, routes obtained from the VaR model are compared with those obtained from other hazmat objectives, on a numerical example as well as a hazmat routing scenario derived from the Albany district of New York State. Depending on the choice of the confidence level, the VaR model gives different paths from which we conclude that the route choice is a function of the level of risk tolerance of the decision-maker. Further refinements of the VaR model are also discussed.
Military reconnaissance missions often employ a set of unmanned aerial vehicles (UAVs) equipped with sensors to gather intelligence information from a set of known targets. UAVs are limited by the ...number of sensors they can hold; also attaching a sensor adds weight to the aircraft which in turn reduces the flight time available during a mission. The task of optimally assigning sensors to UAVs and routing them through a target field to maximize intelligence gain is a generalization of the team orienteering problem studied in the vehicle routing literature. This work presents a mathematical programming model for simultaneous sensor selection and routing of UAVs, which solves optimally using CPLEX for simple missions. Larger missions required the development of three heuristics, which were augmented by Column Generation. Results from a performance study indicated that the heuristics quickly found good solutions. Column Generation improved the solution in many instances, with minimal impact on overall solution time. The rapid nature of the overall solution approach allows it to be used in other mission planning tasks. A fleet sizing application is discussed as an example of its flexible usage.
We extend the hazardous-materials (hazmat) network design problem to account for the time-dependent road closure as a policy tool to reduce hazmat transport risk by altering carriers’ departure times ...and route choices. We formulate the time-dependent network design problem using an alternative-based model with each alternative representing a combined path and departure-time choice. We also present an extended model that can not only account for consecutive time-based road closure policies but also allow stopping at the intermediate nodes of the network in the routing/scheduling decisions of the carriers. Heuristic algorithms based on column generation and label setting are presented. To illustrate the advantages that can be gained through the use of our methodology, we present results from numerical experiments based on a transportation network from Buffalo, New York. To investigate the impact of the extensions, we consider three versions of the problem by gradually refining the model. We show that under consideration of extensions, the design policies are more applicable and effective.
The online appendix is available at
https://doi.org/10.1287/trsc.2016.0698
.
Delivering essential pharmaceuticals to consumers in low- and middle-income countries (LMICs) is a complex global challenge that requires equitable solutions in the last mile of pharmaceutical supply ...chains. This paper proposes using a mobile pharmacy to alleviate the burden due to pharmaceutical stock-outs among rural communities from an equity lens. The Stock-out Severity Index (SSI) is used to assess inequity and is used as the equity objective in a mobile facility routing model. We develop two mathematical programming approaches for routing of the mobile pharmacy so as to minimize the mean absolute deviation of the SSI. The first is a mixed integer program (MIP) modeling approach, based on an approximation of the SSI. The second is an implicit enumeration approach that is implemented within a chronological decomposition heuristic. To help establish its applicability potential, the paper describes a case study that demonstrates how a mobile pharmacy can effectively reduce inequity in a section of rural Uganda. In the case study, costs associated with improving equity are evaluated. This paper finds that optimizing for equity only is associated with high operational costs, and demonstrates approaches that achieve equitable solutions though constrained cost increases.
•Uses a novel equity measure for pharmaceutical distribution in areas of stock-outs.•Focuses on low-resource settings aligned with UN Sustainable Development Goals.•Mathematical methods include an exact solution and a mixed integer program.•Fieldwork based case study is presented for a group of rural communities in Uganda.•Costs associated with improving equity are evaluated.
Our focus is on the development of an unmanned aerial vehicle (UAV) path to maximize the collected amount of information from the area of operation (AO) within a specified fuel limit. Different ...regions of the AO have different monitoring requirements, achieved through visitation at an appropriate altitude. A mixed integer programming (MIP) formulation is developed to solve the path-planning problem with UAV turning radius factored in. Furthermore, a simulated annealing heuristic is developed to solve large problems where the MIP approach is not feasible. Through computational testing we verify that the heuristic generates acceptable results in terms of solution quality (when compared to the exact MIP method) for small to medium size problems, and further verify that it generates results for large problems in acceptable computational time. We empirically test the impact of the fuel limit on the information gained. We explore two methods for increased information gain, using a single UAV with a higher fuel capacity or multiple UAVs with lower fuel capacity. This analysis aims to aid in decision making of the number of UAVs to be deployed and model type selection for military operations.
Just before a hurricane is predicted to strike an urban area, millions of people evacuate from impact zones to safer regions. This paper provides a mass-evacuation strategy using public ...transportation before the strike of a hurricane. The assumptions made are that the evacuation zones, shelter locations, and the time of strike of the hurricane are pre-determined. The evacuation operations commence when the warnings are issued and end when the hurricane strike is predicted to occur. We propose a multi-stage approach. At the first stage is the planning framework, where pickup locations are determined and assigned to shelters, and an initial set of routes is generated along these locations. This is done by weighing each location based on the accumulated demand, and favoring multiple routes to pass through a location with higher demand. In the next stage, each route is assigned a trip number such that 1) routes with higher demand require more trips, and 2) two successive trips to a route are spaced evenly. A simulation tool has been developed to model the dispatching of the given number of buses, stochastic arrival of evacuees, queueing effects at the pickup locations, and the transportation of evacuees to the safety regions. The results from the simulation presented in this paper serve as an evaluation tool for a route design, and a local search heuristic is proposed to effect positive changes in the route design.
•A comprehensive transit planning framework for hurricane evacuation is presented.•Targeted at car-less population groups, the focus is on using buses to setup an accessible and efficient evacuation process.•The complex planning model is divided into subproblems to identify pickup locations, design transit route and dispatch buses.•A dynamic simulation tool is built to study evacuation efficiency in the presence of queueing, and self-evacuation behaviors.•An iterative heuristic is presented to find better route design decisions.
