Better Delivery/Pick Up in the Presence of Uncertainty

Many industrial applications deal with the problem of routing a fleet of vehicles from a depot to service a set of customers that are geographically dispersed. This type of problem is faced daily by courier services, local trucking companies, and demand responsive transportation services, just to name a few. In many cases, in addition to a regular uncertain demand, these industries are faced with sporadic, tightly constrained, urgent requests. For example, courier services typically have a deadline (say 5pm) for the overnight delivery service because of local logistics. Requests for overnight deliveries that come in after the deadline are not accommodated, although it is possible that through some low cost re-routing these packages could make it to the long haul portion of the delivery on time. Another example is the delivery of medical specimens in a health care provider. Even if hospitals and clinics have a regular delivery system for medical specimens to a lab, there are circumstances in which a faster processing of a specimen could be the difference between life and death. Therefore, routing solutions capable of providing better customer service by satisfying more urgent requests, reducing operational costs, or both, are essential in these competitive industries. Current industry routing methods provide solutions that either optimize the expected routing cost or perform well on likely demand and transit condition scenarios. Urgent requests are currently ignored or handled on a one on one basis with a dedicated vehicle at a high expense. If the possible emergency requests were included in the regular demand, the tight constraints of these unlikely realizations could overly influence the optimality criteria, leading to solutions that in most situations are too costly. The development of methods to combine regular routing operations and urgent requests must take into account: 1) a multi-period time horizon to compare the low frequency of urgent requests with regular demands, 2) mechanisms to split the fleet capacity between satisfying the regular demand and urgent requests, and 3) criteria to include or reject urgent requests. The aim of this research is to develop better vehicle routing solutions that can efficiently satisfy random demand over time and rapidly adjust to satisfy these sporadic, tightly constrained, urgent requests. Routing models will be developed that would provide a plan or master route to satisfy the regular demand over multiple periods, knowing that this solution will be adapted on each uncertainty realization. Furthermore, the model would help decide how to best address emergency routing requests within the modifications to the routing plan or with dedicated vehicles. Also, This research will develop efficient solution methods that will allow the solution of real world industry sized problems. This research will investigate the use of warm start methods in the development of exact methods for the multi-period master problem under uncertainty and efficient insertion and tabu heuristics for the adaptation of the master plan to specific routes given the uncertainty outcomes. Finally these models and algorithms will enable a study that would shed insights into the impact of the urgent requests on day-to-day operations and what are the best methods to address them for different problem conditions.