Route optimization while improving safety using escort vehicles
Yie Pinedo, Ruben D.
MetadataShow full item record
The edges in a transportation network can be exposed to certain events that compromise the safety of a vehicle, e.g. landslides, terrorist attacks, icy ground, etc. It is possible to reduce the likelihood of an event on an edge by developing resources, e.g. police protection to deter a potential terrorist threat. This dissertation considers the problem of routing several vehicles from multiple origins to multiple destinations in such an unsafe environment. Two cases are considered. In the first case, the level of danger to which vehicles are exposed is not extreme, so both movement with protection (safe) and without protection (unsafe) is permitted. We model protection via escort vehicles and limit this resource, i.e. there are a limited number of escort vehicles available. In the second case, most of the network is safe for travel without an escort, but certain danger zones are unsafe and cannot be traversed by a vehicle without an escort. Each danger zone has a limited number of escorts available and these escorts cannot travel to other danger zones to assist with their vehicle travel. The main objective of this dissertation is to minimize the average threat level for the first model while respecting the time and number of escort limitations. Two bender's decomposition approaches are used to solve this model. For the second model the main objective is to minimize the lateness for all the shipments in the problem. For this formulation the network is modeled as a shop and the problem is solved as a job-shop scheduling problem. Several procedures to formulate the job-shop problem are shown and several experiments are performed to find which approach works better and for which set of problem parameters.