Convoy movement problem: a civilian perspective Sadeghnejad-Barkousaraie, Azar; Batta, Rajan; Sudit, Moises
The Journal of the Operational Research Society,
20/1/1/, Letnik:
68, Številka:
1
Journal Article
Recenzirano
We study the convoy movement problem in peacetime from a civilian perspective by seeking to minimize civilian traffic disruptions. We develop an exact hybrid algorithm that combines the k-shortest ...path algorithm along with finding a minimum weighted k-clique in a k-partite graph. Through this coupling scheme, we are able to exactly solve large instances of the convoy movement problem without relaxing many of its complicating constraints. An experimental study is performed based on pseudo-transportation networks to illustrate the computational viability of the method as well as policy implications.
We consider the problem of searching for a single, uniformly distributed immobile entity on an undirected network. This problem differs from edge-covering problems, e.g., the Chinese Postman Problem ...(CPP), since the objective here is not to find the minimum length tour that covers all the edges at least once, but instead to minimize the expected time to find the entity. We introduce a heuristic algorithm to deal with the search process given that the entity is equally likely to be at any point on the network. Computational results are presented.
Sensors in a data fusion environment over hostile territory are geographically dispersed and change location with time. To collect and process data from these sensors, an equally flexible network of ...fusion beds (i.e., clusterheads) is required. To account for the hostile environment, we allow communication links between sensors and clusterheads to be unreliable. We develop a mixed-integer linear programming (MILP) model to determine the clusterhead location strategy that maximizes the expected data covered minus the clusterhead reassignments, over a time horizon. A column generation (CG) heuristic is developed for this problem. Computational results show that CG performs much faster than a standard commercial solver, and the typical optimality gap for large problems is less than 5%. Improvements to the basic model in the areas of modeling link failure, consideration of bandwidth capacity, and clusterhead changeover cost estimation are also discussed.
Aeromedical and ground ambulance services often team up in responding to trauma crashes, especially when the emergency helicopter is unable to land at the crash scene. We propose location-coverage ...models and a greedy heuristic for their solution to simultaneously locate ground and air ambulances, and landing zones (transfer points). We provide a coverage definition based on both response time and total service time, and consider three coverage options; only ground emergency medical services (EMS) coverage, only air EMS coverage, or joint coverage of ground and air EMS in which the patient is transferred from an ambulance into an emergency helicopter at a transfer point. To analyze this complex coverage situation we develop two sets of models, which are variations of the Location Set Covering Problem (LSCP) and the Maximal Covering Location Problem (MCLP). These models address uncertainty in spatial distribution of motor vehicle crash locations by providing coverage to a given set of both crash nodes and paths. The models also consider unavailability of ground ambulances by drawing upon concepts from backup coverage models. We illustrate our results on a case study that uses crash data from the state of New Mexico. The case study shows that crash node and path coverage percentage values decrease when ground ambulances are utilized only within their own jurisdiction.
This paper proposes a logistics model for delivery of prioritized items in disaster relief operations. It considers multi-items, multi-vehicles, multi-periods, soft time windows, and a split delivery ...strategy scenario, and is formulated as a multi-objective integer programming model. To effectively solve this model we limit the number of available tours. Two heuristic approaches are introduced for this purpose. The first approach is based on a genetic algorithm, while the second approach is developed by decomposing the original problem. We compare these two approaches via a computational study. The multi-objective problem is converted to a single-objective problem by the weighted sum method. A case study is presented to illustrate the potential applicability of our model. Also, presented is a comparison of our model with that proposed in a recent paper by Balcik et al.
6. The results show that our proposed model outperforms theirs in terms of delivering prioritized items over several time periods.
In this paper, we consider ambulance allocation and reallocation models for a post-disaster relief operation. The initial focus is on allocating the correct number of ambulances to each cluster at ...the beginning of the rescue process. We formulate a deterministic model which depicts how a cluster grows after a disaster strikes. Based on the model and given a number of ambulances, we develop methods to calculate critical time measures, e.g., the completion time for each cluster. Then we present two iterative procedures to optimize the makespan and the weighted total flow time, respectively. The second problem analyzes the ambulance reallocation problem on the basis of a discrete time policy. The benefits of redistribution include providing service to new clusters and fully utilizing ambulances. We consider the objective of minimizing the makespan. A complication is that the distance between clusters needs to be factored in when making an ambulance reallocation decision. Our model permits consideration of the travel distance between clusters. Results of our allocation method are illustrated via a case study, which is based on an earthquake scenario in Northridge, CA.