A multiple-depot, multiple-vehicle, location-routing problem with stochastically processed demands

Abstract

We formulate a multiple-depot, multiple-vehicle, location-routing problem with stochastically processed demands, which are defined as demands that are generated upon completing site-specific service on their predecessors. When a factory is re-supplied with manufacturing materials, for example, demand for raw materials surfaces only after the existing inventory has been exhausted. A special separable case of the problem was solved, wherein probable demands are estimated by stochastic processes at the demand nodes (the factories) before the vehicle location-routing decisions. Posterior solutions to the complete 90-day instances of the problem help to gauge the performance of the a priori stochastic model. The 90 day-by-day instances also provide researchers with a benchmark data-set for future experimentation. It was shown that the a priori optimization solution provides a robust location-routing strategy for real-time decision-making in a medical-evacuation case study of the U.S. Air Force. Given this modest success, the same methodology can possibly be applied toward “pure” just-in-time deliveries in supply-chain management, where inventory storage is totally eliminated.

Scope and purpose

In resupplying a factory from a central depot, there are several considerations. First, one has to locate the distribution centers. Second, a delivery-vehicle fleet of the right size has to be stationed at each of these centers. Third, deliveries need to be made on a timely basis in response to demands for raw materials. While this problem is well known, only part of it is solved satisfactorily to date. We propose a comprehensive model and a solution method for this class of problems. A unique feature of this model is that we recognize that in today's just-in-time deliveries, one wishes to order exactly what is anticipated to avoid surplus inventory or stock out. However, demands are often highly uncertain since the manufacturing process is plagued with uncertainty. This paper has an innovative way of representing this phenomenon that is a departure from the traditional literature.

Introduction

Recently, there has been keen interest in a priori or robust optimization, defined here as procedures that one performs ahead of time to anticipate future events. A fair amount of activities have surfaced in logistics where delivery routes and depot locations need to be planned in uncertainty [1]. Here we address a complex example, consisting of multiple depots, multiple vehicles, and involving both locational and routing decisions. Demands are not stochastic in the traditional usage of the word; rather, they are generated through a queuing process at the demand sites. Most dynamic travelling repairmen problems treat the vehicles as servers which respond to uncertain demands in the network, and the vehicles are queued for additional demands awaiting service. Here the demands are served at a demand node not by a vehicle, but by a facility at that node. The vehicles simply drop off additional demands when the existing inventory at the node have been duly processed. In a manufacturing plant, for example, raw-material inventory is being depleted stochastically and requires replacement. It is in the best interest of the company to re-supply these raw materials in order to have uninterrupted, full use of the machinery. Agile logistics require that raw materials are to be stored at supply depots and surplus inventory is strictly disallowed at the processing plants. Under these circumstances, we refer to the requirement for raw materials as “stochastically processed demands”. To the best of our knowledge, the complete problem solved here in this paper has not been addressed previously. We marshal available formulations and extend them to this unique class of problems and show progress in solving a special separable case, in which the probable demands can be estimated via the queuing network before location-routing decisions are made. We hope that the effort and progress reported here will stimulate further work in this most exciting field.

Literature pertaining to this study fall under the subject of stochastic location-routing. The demand at a plant is uncertain. Until raw material is consumed, the next delivery cannot be entertained. This results in varying loads for vehicles to deliver from a central depot to these processing facilities, where the depot serves as the storage or waiting area for the deliveries. This results in a queuing network, of which analytical results are extremely limited [2]. For simple stochastic demands and ignoring the service requirement at demand points, there is some existing literature. According to Dror et al. [3], this type of stochastic vehicle-routing problems (SVRP) is divided into two types. The “wait and see” situations are problems where the routes are determined after the demands have been observed. They tend to degenerate into a deterministic vehicle-routing problem (DVRP). The second situation, “here and now,” is when routes are set on anticipated demands. It is also referred to as a priori optimization [4] or probabilistic optimization [5]. This is the situation for our study. Of the two types of “here and now” problems, the relevant one here is the chance-constrained model (Stewart and Golden, as cited in Dror et al. [3]). Here the routes are strictly based on probable demand.

Once demand is known, the DVRP can be solved by a variety of different well-known techniques [6]. Of particular interest is the venerable Clarke–Wright heuristic. Mandl [7] extended the original procedure to include maximum number of nodes on a route in addition to maximum-distance savings. This results in minimizing the number of vehicles needed to service the demand points. Naddef [8] provides a mixed-integer linear-programming formulation for the DVRP based on maximizing the Clarke–Wright triangular savings. Recently, savings by split-delivery routing receive some attention. Dror and Trudeau [9] detail the properties of the split-delivery heuristic. Briefly, the heuristic checks the solution to the classic vehicle-routing problem for split-delivery possibilities. If any are found, the heuristic chooses those with positive distance-savings.

Stochastic location-routing problems (SLRP), the main subject of this paper, are highly complex embellishments of the SVRP. As a result, satisfactory solution procedures are still evolving. Bertsimas et al. [4] suggest that it is much easier to solve the equivalent deterministic version of the problem than every instance of the probabilistic formulation. One of the more practical techniques is the space-filling curve (SFC), wherein the two-dimensional location-routing network is transformed into a single dimension or the SFC, with the nodes correspondingly located on this curve. Bartholdi and Platzman [10] and Bowerman et al. [11] suggest partitioning the curve into a desired number of subintervals defining the distribution-service region that a single vehicle can serve within its ‘range’ (or maximum travel distance). The node closest to the median in each of these subintervals serves as depot location. Routes can then be generated from this depot to the demand points in the subintervals. SFC is not just a two-dimensional concept. A third dimension, in addition to the two dimensions of latitude and longitude, can be added representing the demand at each location. The three dimensions can again be transformed into a single dimension [12]. The nodes located on this curve are now sorted and the closest points are grouped once again to identify either a service region or a route. Adding vehicle capacity complicates the routing procedure slightly, but the fast execution speed of the SFC heuristic obviates such a complication, as we will show below.