Network Design for Load-driven Cross-docking Systems



Network Design for Load-driven Cross-docking Systems

H. Donald Ratliff John Vande Vate

Georgia Institute of Technology, Industrial and Systems Engineering

765 Ferst Drive, Atlanta, GA 30332-0205

Mei Zhang

John Vande Vate

Mei Zhangi2 Technologies, Inc. One i2 Place, MD 1-6B, 11701 Luna Rd.

Dallas, TX 75234

DRAFT: DO NOT DISTRIBUTE

ABSTRACT

Schedule-driven cross-docking systems dispatch transportation units (e.g., railroad cars, trucks, etc.) on a channel according to a fixed schedule regardless of the volume of goods awaiting transportation on that channel. These systems are designed to provide a guaranteed level of service at the cost of potentially low vehicle utilization. Load-driven cross-docking systems, on the other hand, dispatch transportation units on a channel only when a sufficient volume of goods is awaiting transportation on that channel. These systems ensure high vehicle utilization, but provide a reduced level of service. This paper explores a mixed-integer linear programming model for determining the number and location of cross-docks in a load-driven system and allocating flow through them. The model is similar in structure to the uncapacitated facility location model in which the linear programming relaxation often provides an integral optimal solution. We motivate and test our model in the context of North American automobile delivery systems.

1. INTRODUCTION

Cross-docking is an operating strategy that moves items through flow consolidation centers or cross-docks without putting them into storage. With the exception of a companion paper (Donaldson, 1998), which deals with schedule-based driven cross-docking systems, research on cross-docking has focused on the schedule driven systems common to LTL carriers (for example Daganzo, 1987; Powell and Sheffi, 1983; and Powell and Sheffi 1989) or the design of the cross-dock itself (for example, Reducing Labor Costs in an LTL Cross-docking Terminal by Bartholdi and Gue, 20001999). This Our research, on the other hand, focuses on the design of load-driven distribution networks in which vehicles are dispatched only when a specified minimum load is available. that include cross-docks. In particular, this paper we develops a mixed-integer linear programming model to determine the ideal number and location of cross-docks in athe load-driven network and how shipments should flow among them.

We focus on “load-driven” systems in which vehicles are dispatched only when a specified minimum load is available, as opposed to schedule-driven systems considered in Donaldson et al. (1998), which dispatch vehicles on a fixed schedule. We motivate and test our models in the context of aFord Motor Company's North American automobile delivery systems.

2. AUTOMOBILE DELIVERY

Most new automobiles manufactured in the US are transported by rail from manufacturing plants to special railroad centers called ramps and then by truck to local dealers. This is typically a load-driven system. Newly assembled automobiles are parked in load lanes at the plant according to their destination ramp. Whenever a sufficient number of vehicles destined for a single ramp accumulates in a load lane, the vehicles are loaded onto a railcar, which is dispatched into the “loose car network”. Typically, the railcars used to transport automobiles to the ramps are tri-levels capable of carrying 15 sedans, 5 on each deck.

The “loose car network” is itself a load-driven cross-docking system for railcars, rather than automobiles.. The cCross-docks in this system are switching yards where railcars headed in the same direction are sorted into trains. In While crossing the country, a railcar may pass through half a dozen switching yards before reaching its final destination. The average transit time is about 15 days.

At the final destination ramps, vehicles are off-loaded from the railcars and parked to await delivery to their designated dealerships. When a sufficient number of vehicles destined for dealerships in a given area accumulatess, the vehicles are loaded on a rig and delivered. Car hauling rigs typically carry between 8 and 12(Check this with Allied) sedans.

Note the distinction in our use of the terms “ramps” and “load lanes”. A ramp refers to a destination rail facility where vehicles are transferred from rail to car hauling rigs for local delivery. A load lane is a designated area at a plant or elsewhere in the distribution network, where we collect vehicles bound for the same ramp.

RecentlyIn 1996, Ford ran a pilot study to examine the potential for special cross-docking centers (called mixing centers) in the rail network. The pilot included 5 plants in the eastern US and 15 rail ramps in the west and mid-west (see Figure 1). Prior to the pilot, each plant dispatched railcars to each ramp via the loose car network. In an effort to reduce the 1214 to 15-day average delivery time from the plants to the dealerships, Ford introduced a mixing center in Kansas City, Missouri and routed all vehicles from the 5 plants to the 15 ramps through this mixing center.

We will show how the mixing center promised to reduce the total inventory of vehicles at the 5 plants destined for the 15 rail ramps from over 500 to under 150 (35 at the plants and about 105 at the mixing center). This anticipated reduction in inventory at the plants of approximately $7 million is not nearly enough to justify the approximately $75 million price tag for construction of the Kansas City mixing center. The real motivation for the mixing center concept arose from the anticipated reduction in the average days required to deliver vehicles.

Ford reported selling approximately 4.8 million vehicles in North America in 1999. At an average value of approximately $20,000 per vehicle[1], each single day reduction off their average delivery time amounts to an approximately $260 million reduction in pipeline inventory.

Ford subsequently built four additional mixing centers: in Fosteria, OH, Shelbyville, KY and two in Chicago, IL. Nevertheless, in December 1999, their average delivery time had risen to 15.8 days. Industry experts lay much of the blame for this initial failure of the mixing center concept to other factors including:

• Delays in service associated with railroad mergers,

• The significant increase in the average size of vehicles with the growth in popularity of minivans and SUV’s,

• Unionization of the mixing center labor force.

In February, 2000, Ford announced an alliance with UPS Logistics group with a goal of reducing by 40% the time required to get vehicles to dealerships. In February, 2001, Ford announced that it’s average delivery time had reduced by 4 days, a reduction in finished vehicle inventory of over $1 billion.

We introduce and test our model in the context of the Ford pilot. In this paper, we analyze the potential of the mixing center concept in terms of faster transportation modes and reduced inventories. We exploit this analysis to develop a mixed-integer programming model for determining the ideal number and location of cross-docks in a load-driven network like the Ford new car distribution system.

Figure 111111: Ford Pilot Study

2.1 1.4 Plant Operations

In a system operating without any mixing centers, newly produced automobiles are parked in load lanes at the plant according to their destination ramps. The vehicles are already sold to a dealer when they leave the assembly line so each vehicle identification number (VIN) is assigned to the destination ramp that serves its dealer. When a full railcar load of c automobiles accumulates in a load lane, these vehicles are loaded onto a railcar, which is and dispatched into the loose car network. Consequently, if the production rate of vehicles destined for the ramp is relatively constant, the average inventory of vehicles in the load lane at the plant is (c-1)/2. It is perhaps surprising to observeNote that this number is independent of the volume of vehicles shipped to the ramp.

To better understand why the average number of vehicles in a load lane is independent of the volume of vehicles shipped to the corresponding destination ramp, consider the following example. Suppose a given plant produces p1 vehicles per day destined tofor ramp 1 and, p2 vehicles per day for destined to ramp 2 and p3 vehicles per day for ramp 3. Figure 2 illustrates the inventory of vehicles at the plant in the load lanes for these twohree ramps over time. Assuming a railcar carries c automobiles, the number of automobiles waiting in a load lane never exceeds c-1, for once it reaches c, the vehicles are loaded into a railcar. Consequently, the inventory at the plant is a function of the railcar capacity c and the number of load lanes. Consolidating shipments through mixing centers reduces this inventory by reducing the number of load lanes.

With a small supply rate (e.g., p1)) it takes a longer time to build up a load. In particular, vehicles destined for ramp i (with supply rate pii vehicles per day)) will wait ((c-1)/2)/pi days on average for a load to accumulate. Thus, while the average number of vehicles in each of the three two load lanes will be the same, (c-1)/2, the average times vehicles in these load lanes spend waiting for a load to accumulate will be quite different. The total delay per day incurred waiting in a load lane, however, is the product of the average delay per vehicle and the number of vehicles incurring that delay. Thus, we have the following key observationwe observe:

Observation 1: In a load-driven cross-docking system, lane, the total delay per day incurred waiting for transportation in a lane depends only on the capacity of the transportation units vehicles used on the lane.

In our example, the total time delay per day incurred waiting for transportation is the same in all threeboth load lanes. It is simply (c-1)/2 vehicle-days.

Figure 222222: Inventory in a Load Lane

2.21 Mixing Center Operations

At the mixing center, automobiles are unloaded from arriving railcars into load lanes according to their destination ramps. When sufficient vehicles accumulate for a given destination ramp, they are loaded onto an empty railcar and sent on. Any remaining vehicles wait at the mixing center.

Thus, a mixing center serves as a load-driven cross-dock. Like all cross-docks, it introduces additional handling of the product in order to reduce overall transportation costs and, more importantly in this case, it introduces additional transportation timedistance.

Routing shipments through a mixing center can, nevertheless, reduce transportation time and cost in two ways:

Faster Mode: Consolidating shipments out of each plant destined for a number of ramps to a single mixing center can generate sufficient volume on the channel to warrant using faster unit trains. Unit trains, consisting of 20 or more railcars with a common destination, move directly from the plant to the destination ramp, bypassing the switching yards. A mixing center serving several plants can have a similar effectconsolidate on shipments to destination the ramps. Consolidating the different plants’ shipments to a ramp can facilitatinge the use of unit trains on outbound shipments as well.

Reduced Wait: Because the daily supply rates to some ramps (e.g., Laurel, Montana) are much smaller than the capacity of a railcar, automobiles destined for these ramps may wait several days for a full load to accumulate. Consolidating shipments through a mixing center can eliminate these delays. Further, the number of vehicles waiting at the plant influences both the average delivery time and the size of the lot at the plant. Typically, automobile manufacturing plants are surrounded by suppliers’ facilities and, as a result, land is scarce and expensive. Reducing the number of vehicles waiting at the plant frees up valuable land for more productive uses.

In the remainder of this section, we discuss the effects of different operating policies at the mixing center.

2.32 Equipment Balance Strategy

The equipment balance strategy is not a true load-driven strategy. It strives to avoid bringing empty railcars into the mixing center by balancing outbound volumes with inbound volumes. It is designed to This strategy ensures a predictable workload and to simplifiesy the handling of railcars at the mixing center. We say that a mixing center is fully balanced if each arriving railcar that is unloaded can be completely reloaded with vehicles all destined for a common ramp. In this way, no empty railcars are brought into or taken out of the mixing center (i.e., railcars come in full and depart full). Note that if a mixing center is operated in a fully balanced manner it will maintain a constant inventory level. The following lemmas characterizes the inventory of vehicles at the mixing center required to ensure the center can be fully balanced.

Lemma 1: Let mc be the smallest multiple of c at least as great as (r-1)(c-1), where c is the capacity of a railcar and r is the number of ramps the center serves. A mixing center with mc vehicles can be operated in a fully balanced manner.

Proof. Consider a mixing center with mc vehicles in inventory. After a railcar is unloaded, the number of vehicles at the center increases to mc + c = (m+1)c > r(c-1) and so there must be at least c vehicles destined for some ramp. Once we load c vehicles destined to this ramp onto the railcar, the inventory at the mixing center returns to mc. □

Lemma 1 shows that a mixing center with an inventory of mc vehicles can operate in a fully balanced manner. Observe that we could have equivalently defined mc as the greatest multiple of c not exceeding r(c-1). Lemma 2 shows that the inventory of vehicles at the mixing center will eventually grow to this limit under the following assumptions:

Assumption 1. We start with no inventory at the mixing center.

Assumption 2. Each railcar arrives with exactly c vehicles.

Assumption 3. Each railcar either departs with exactly c vehicles or, if no load lane has at least c vehicles, departs empty.

Assumption 4. For each vector of non-negative integers n = {ni: i = 1, 2, …, r} such that

Σ(ni: i = 1, 2, …, r) = c

there is a positive probability, prob(n), that the next railcar contains exactly ni vehicles destined for each ramp i = 1, 2, …, r.

Lemma 2: Let mc be the smallest multiple of c at least as great as (r-1)(c-1), where c is the capacity of a railcar and r is the number of ramps the center serves. Under Assumptions 1-4, inventory at the mixing center will, with probability 1, grow to mc vehicles. Thereafter, the mixing center will operate in a fully balanced manner and the inventory will remain at mc vehicles.

Proof. We first observe that since the mixing center starts with no vehicles in inventory and vehicles always arrive and depart in multiples of c, there will always be a multiple of c vehicles at the mixing center. Further, since each railcar arrives fully loaded, inventory at the mixing center can never decrease.

We now show that for each possible configuration with fewer than mc vehicles in inventory, a sequence of railcar loads that occurs with positive probability will increase the number of vehicles in inventory. This shows that the number of vehicles in inventory grows to mc with probability 1.

Suppose there is a total of k ≤ (m-1)c vehicles in inventory in all the load lanesat the mixing center.

Case 1. There are vi < c vehicles destined for each ramp i = 1, 2, …, r.

In this case, we demonstrate a single railcar load that will increase the inventory to k + c vehicles.

Since Σ(vi: i = 1,2, …, r) = k ≤ (m-1)c and mc ≤ r(c-1),

Σ(c-1-vi: i = 1, 2, …r) = r(c-1) – k ≥ r(c-1) – mc + c ≥ c.

Thus, we can choose a set of c vehicles to load on the next railcar in such a way that after unloading the vehicles, there are at most c-1 vehicles destined for each ramp – simply choose a load with ni ≤ c-1-vi vehicles destined for each ramp i = 1, 2, …, r. After unloading this railcar, we will not be able to load it again as no load lane will have c vehicles and so the inventory will increase.

Case 2. There are vi ≥ c vehicles in inventory destined for each ramp i in a subset J of the ramps. In this case, we demonstrate a railcar load that will reduce the number of vehicles in inventory destined for ramps in J without creating a full load for any of the other ramps. After a sequence of such railcar loads, the inventory of vehicles destined for each ramp will be less than c and we can use Case 1 to construct a railcar load that will increase the inventory.

Renumber the ramps so there are vi ≥ c vehicles in inventory destined for each ramp i = 1, 2, …, s and vi < c vehicles in inventory destined for each ramp i = s + 1, s + 2, …, r.

By assumption there is a total of at most (m-1)c vehicles in inventory and at least c vehicles in inventory destined for each ramp i = 1, 2, …, s. Thus, there is a total of k ≤ (m-s-1)c vehicles in inventory destined for ramps s + 1, s + 2, …, r. Further, since (m-s)c ≤ (r-s)(c-1), the arguments of Case 1 tell us how to construct a railcar load of vehicles all destined for ramps s + 1, s + 2, …, r so that we do not accumulate a full load of vehicles destined for any of these ramps. Thus, the railcar will depart with a load of vehicles destined for one of the ramps in 1, 2, …, s. □

It may take a long time to build up an inventory of mc vehicles at a mixing center operating in accordance with Assumptions 1-4, but in the meantime, we only need to deal with empty railcars leaving the mixing center. We will never have to worry about delivering empty railcars to the center.

When operating in a fully balanced manner, we will be able to unload and reload every railcar on each arriving train. This greatly simplifies the problem of forecasting the workload at the mixing center – we do not need to know what vehicles are on each railcar, just how many railcars will arrive each day.

A mixing center operating in a fully balanced manner will generally have a number of destinations with more than a full railcar load of vehicles waiting in inventory. This will influence both the average delivery time of vehicles and the size of the lot required to operate the mixing center.

The average delay per vehicle incurred waiting for transportation at the mixing center will be mc/P days, where P is the number of vehicles arriving at the center each day. The total delay incurred each day waiting for transportation at the mixing center will simply be mc vehicle-days – the number of vehicles sitting at the mixing center each day.

If instead of beginning with no vehicles in inventory at the mixing center, we begin with b (mod c) vehicles then, under Assumptions 2 – 3, there will always be b (mod c) vehicles at the mixing center. In this case, the mixing center will become fully balanced with an inventory of m’c + b vehicles, where m’ is the smallest integer such that m’c + b ≥ (r-1)(c-1).

At the Kansas City mixing center, vehicles are also trucked in from the local plant and trucked out for local delivery. A mixing center like Kansas City, served by transportation units of various capacities, will operate in a fully balanced manner with respect to each type of transportation unit if it has an inventory of (r-1)(cmax-1) vehicles, where cmax is the capacity of the largest transportation units that serve it.

2.4 Minimum Inventory Strategy

The minimum inventory strategy is a true load-driven strategy. It attempts to minimize the inventory of vehicles at the mixing center by bringing in empty railcars whenever necessary to handle all available full loads. The minimum inventory strategy satisfies Assumptions 1, 3, 4 and

Assumption 2’. Each railcar arrives with exactly c vehicles or arrives empty.

Lemma 3 shows that the maximum inventory at the mixing center under this strategy is exactly the inventory level required to support operating in a fully balanced manner, namely mc vehicles.

Lemma 3: Under the minimum inventory strategy, the inventory at a mixing center serving r ramps with railcars of capacity c can reach, but not exceed, mc, the smallest multiple of c at least as great as (r-1)(c-1).

Proof. Under Assumptions 1, 2’ and 3, there will always be a multiple of c vehicles at the mixing center. If there are (m+1)c > r(c-1) vehicles at the mixing center, then there must be at least c vehicles waiting in inventory destined for one of the ramps and the minimum inventory strategy would bring in an empty rail car to deliver them. So, the inventory at the mixing center cannot exceed mc.

To see that the inventory can eventually reach mc, note that the arguments of Case 1 in Lemma 2 demonstrate a possible sequence of railcars leading from every possible inventory configuration to a configuration with mc vehicles in inventory. □

We next argue that the average inventory level at a mixing center operating under the minimum inventory strategy will be r(c-1)/2. We offer two arguments, one intuitive and the other technical. The intuitive argument is simply by analogy to the situation at the plant where, by assumption, vehicles are completed and enter inventory one-by-one and at a relatively constant rate. The technical argument is given in the proof of Lemma 4., which we defer to the Appendix as it is a rather long digression from our main point.

Lemma 4: Under Assumptions 1, 2’, 3 and 4, the average inventory level at a mixing center operating under the minimum inventory strategy is r(c-1)/2.

Proof. To calculate the average inventory level at a mixing center operating under the minimum inventory strategy, we model the system as a Markov Process and show that it has a doubly stochastic transition matrix from which we can conclude that each state is equally likely. The technical portion of the argument involves calculating the average inventory at the mixing center from the steady state probabilities.TO BE FIGURED OUT.□

Argument by symmetry here – point out the incorrect independence assumption.

Note that although the average inventory level of the minimum inventory strategy will be significantly smaller than that of the equipment balance strategy, the center must be large enough to handle mc vehicles under both strategies. Further, under the minimum inventory strategy, neither the inventory at the mixing center nor the workload is easy to predict.

Under the minimum inventory strategy, the center will also need to maintain an inventory of empty railcars. We will add to this inventory when there are insufficient loads at the mixing center to fill all the newly arrived railcars and draw from it whenever extra empty railcars are required to handle the loads.

Lemma: A mixing center with (c-1)r vehicles, where c is the capacity of a railcar and r is the number of ramps the center serves, can be operated in a fully balanced manner.

Proof. Consider a mixing center with (c-1)r vehicles in inventory. After a railcar is unloaded, the number of vehicles at the center increases to (c-1)r +ccr. Since there are only r destination ramps, there must be at least one to which c or more vehicles are headed. Once c vehicles destined to this ramp are loaded on the railcar, the inventory at the mixing center returns to (c-1)r. □

Starting with no vehicles in inventory at the mixing center, one natural method for building up the inventory required to support fully balanced operations is to take a railcar away empty if there is no destination ramp with at least c waiting vehicles. It may take a long time to build up an inventory of (c-1)r vehicles, but in the meantime, we only need to deal with empty railcars leaving the mixing center. We will never have to worry about delivering empty railcars to the center.

When operating in a fully balanced manner, every railcar on each arriving train will be unloaded and then reloaded. To predict the workload at the mixing center, we only need to know the number of railcars arriving. Thus, operating in a fully balanced manner ensures a predictable workload at the mixing center without requiring detailed knowledge of the vehicles on arriving trains. Note however, that operating in a fully balanced manner, we may actually have a number of destinations with more than a full railcar load of vehicles waiting at the mixing center. This will influence both the average delivery time of vehicles and the size of the lot at the mixing center.

The average delay per vehicle incurred waiting for transportation at the mixing center will be (c-1)r/P, where P is the total rate at which vehicles arrive at the center. The total delay incurred waiting for transportation at the mixing center will simply be (c-1)r.

2.43 Minimum Inventory Strategy

The minimum inventory strategy is a true load-driven strategy. It attempts to minimize the inventory of vehicles at the mixing center by bringing in empty railcars whenever necessary to handle all available full loads. The maximum inventory at the mixing center under this strategy is clearly exactly the inventory level required to support operating in a fully balanced manner, namely (c-1)r. Typically, the inventory level at a mixing center operating under the minimum inventory strategy will be close to half this maximum level or (c-1)r/2. From our Observation, we know that the total delay incurred waiting for transportation to each ramp served by the mixing center will be (c-1)/2.

Note that although the average inventory level of the minimum inventory strategy will be significantly smaller than that of the equipment balance strategy, the center must be large enough to handle (c-1)r vehicles under both strategies. Further, under the minimum inventory strategy, neither the inventory at the mixing center nor the workload will be easily predictable.

The center will also need to maintain an inventory of empty railcars. We will add to this inventory when there are insufficient loads at the mixing center to fill all the newly arrived railcars and draw from it whenever extra empty railcars are required to handle the loads.

3. MIXED INTEGER PROGRAMMING MODEL

There are two basic sets of decisions in designing a “load-driven” cross-docking network: the location decisions, which deal with the number and positioning of cross-docks, and the routing decisions, which deal with how flow should be routed through the selected cross-docks. Our objective is to minimize the average delay between the time a vehicle is produced and the time it reaches its destination ramp. The two components of this delay are the transportation delay (i.e., the time spent travelling) and the loading delay (i.e., the time spent on waiting to be loaded on transportation units).

The total transportation delay incurred on a lane is simply the product of the transportation time on that lane and the number of vehicles incurring that time.

As we have seen, with a constant supply rate, the total loading delay in each load lane at the plant is (c-1)/2 vehicle-days per day. The total loading delay in each load lane at the mixing center, on the other hand, depends on the operating strategy. Under a minimum inventory strategy, the average is (c-1)/2 vehicle-days per day. Under the equipment balance strategy, however, we can only describe the total over all the load lanes: It will be (c-1)rmc, the smallest multiple of c not smaller than (r-1)(c-1) vehicle-days per day. If we approximate the total delay on each load lane to be (c-1) vehicle-days per day, we will accurately capturealways be within c vehicle-days per day of the total delay incurred at the mixing center under this strategy.

In this section, we model the problem of designing a load-driven cross-docking network in which the mixing centers operate under the minimum inventory strategy as a variant of the fixed charge design model (Magnanti, 1984). Our model assumes that vehicles are either routed directly from the plant to the ramp or are routed from the plant to a mixing center and from there to the ramp. Later, in Section 5, we generalize the model to multi-tiered distribution systems in which vehicles may pass through several mixing centers.

We let tij denote the travel time and fij the total loading delay per day incurred by vehicles moving from point i to point j. Further, we assume the average supply rate in vehicles per day from plant p to ramp r, denoted by spr, is known. This assumption is consistent with North American automobile distribution in so far as typically all or nearlybecause all production of a given model occurs at a single plant. In other settings, this assumption is justified when demand through each distribution center is assigned to a single plant.

The variables in our model are:

• xpr, the number of vehicles moving directly from plant p to ramp r per unit time,

• ypcr, the number of vehicles moving from plant p to ramp r via mixing center c per unit time and

• zij, indicating whether or not any vehicles move directly from point i to point j.

The objective of our model is to minimize the average delay between the time a vehicle is produced and the time it reaches its destination ramp. The first constraint ensures that all deliveries are made. Constraints (2)-(4) enforce lane selection: no vehicles can be shipped on a lane unless the delay on that lane is incurred.

[pic] Σ{fpr zpr + tpr xpr: all plants p and ramps r} +

Σ{fpc zpc : all plants p and centers c} + Σ{fcr zcr : all centers c and ramps r} +

Σ{(tpc + tcr)ypcr : all plants p, centers c and ramps r}

[pic]

Σ {ypcr : all centers c} + xpr = spr for each plant p and ramp r (1)

ypcr ≤ spr zpc for each plant p, center c and ramp r (2)

ypcr ≤ spr zcr for each plant p, center c and ramp r (3)

xpr ≤ spr zpr for each plant p and ramp r (4)

xpr, ypcr ≥ 0 for each plant p, center c and ramp r (5)

zij ({0, 1} for each lane ij (6)

The objective of our model is to minimize the average delay between the time a vehicle is produced and the time it reaches its destination ramp. The first constraint ensures that all deliveries are made. Constraints (2)-(4) enforce lane selection: no vehicles can be shipped on a lane unless the delay on that lane is incurred.

Given potential sites for cross-docking centers, the model determines which of the centers should be open and routes the flows from each plant to each rail ramp to minimize the overall average delay.

4. COMPUTATIONAL RESULTS

To test the model, sample problems approximating the Ford new car network were randomly generated. In these examples, the transportation delay was assumed to be proportional to Euclidean distance. Random flow rates were generated for each supply/demand pair again trying to be consistent with Ford production rates. Table 1 shows the computational results for a representative set of the problems tested. Of the 5 problems presented here, one problem required 3 branch-and-bound nodes to reach optimality. For the rest, the LP relaxation provided an integral optimal solution.

Table 111111: Example Problems in Single Transportation Mode Network

Problems 1 and 2 have the same number of plants, centers and the ramps but they differ in the actual locations of the nodes. The same is true for Problem 3 and Problem 4. The fifth column in Table 1, indicates the number of continuous variables and the number of binary variables, e.g., Problem 1 has 4,800 continuous variables and 900 binary variables. The seventh column is the MIP optimal obtained using CPLEX 5.0. The next column is the number of open centers in an optimal solution followed by the number of branch-and-nodes required to find and prove the optimality of that solution. The last column is the CPU time on an IBM RS6000 (Series 590) workstation. Problems 3 and 4 most closely approximate Ford’s new car distribution system in 1996. Branch-and-bound requires so so few nodes to solve these problems because the binary variables are strongly interrelated. Figure 3 illustrates the strength of these interrelations.

Figure 33: Interrelations among the binary variables

In Figure 3(a), the dashed lines represent fractional flows. The supply from plant S1 to ramp D1 is split with half on the direct route and half on the route through cross-docking center CDC 1. The supply from plant S2 to ramp D1 is similarly split. The supply from plant S3 to ramp D1 is split with half on the route through CDC1 and half on route through CDC2 as is the supply from plant S4 to ramp D1. In this fractional solution, the values of the binary variables on the dashed lines are all ½. If the binary variable on the link from CDC1 to ramp D1 is forced to 0 preventing flow on this route, the other binary variables will all be forced to 1, see Figure 6(b). The supplies from plant S1 to ramps D1 and D2 must flow on the direct routes and the supply from plant S4 to ramp D1 must flow through CDC2.

The structure of the formulation for the load-driven systems is essentially the same as the uncapacitated facility location problem, for which the LP relaxation often gives an integral optimal solution. For further discussion of this problem see Discrete Location Theory (Mirchandani, (1990).

5. EXTENSIONS

As we mentioned earlier, consolidating flow on a channel in the automobile delivery network can facilitate the use of faster unit trains. This faster transportation mode involves more inventory (albeit on loaded railcars) and a longer loading delay as the train cannot depart until a sufficient number of railcars are loaded. The average inventory of waiting automobiles is approximately one-half the capacity of the train. The model above extends in a straight forwardstraightforward way by simply allowing additional arcs for each link where building a unit train is possible.

The following is the result of some randomly generated problems for the automobile distribution system with optional unit trains between every pair of ship points. Unit trains typically take 25-50 railcars and can travel up to 5 times faster than individual railcars in the loose car network. For a unit train with 25 railcars, the fixed delay for a link using a unit train is (25*15-1)/2 = 187 vehicle-days per day. The problems in Table 2 are the same as those in Table 1 but with both unit trains and loose cars allowed between every pair of ship points in the network. The objective values of all problems are reduced because in some part of the network unit trains are used. Because the multi-mode networks are much bigger larger than that those of the single mode problems, the problems all required more CPU time, especially the two larger problems.

Table 222222: Example Problems with Two Transportation Modes

Figure 444444: Multi-level Cross-docking

Our model extends in the natural way to distribution systems with more than one tier of cross-docks, as illustrated in Figure 4. To accommodate the possibility of passing through more than one cross-dock in moving from a plant to a ramp, we extend the variables ypcr to include all paths from the plants to the ramps including those that use more than one ramp. For larger problems, these variables can be generated via standard column generation techniques. Table 3 contains computational results for this extension of our model to networks with up to two tiers of cross-docks. In all of these problems the LP relaxation provided an optimal integral solution. The optimal solutions to Problem 1 and Problem 2 include paths using both levels of cross-docking as well as paths using only a single level of cross-docking. The last column of Table 3 is the CPU time on the same IBM RS6000 (Series 590) workstation.

Table 333333: Example Problems with Two Levels of Cross-docking

Acknowledgements: The authors would like to thank Biff Wilson and the people at Allied Systems for bringing the Ford pilot study to our attention and for providing advice and data supporting the development and testing of our model. We would also like to thank Ellen Ewing at UPS Logistics for providing statistics on the performance of Ford’s delivery network since 1999.

APPENDIX

Proof of Lemma 4. To calculate the average inventory level at a mixing center operating under the minimum inventory strategy, we model the system as a Markov Process and show that it has a doubly stochastic transition matrix from which we can conclude that each state is equally likely.

An integer vector v = (vi) represents a state of the mixing center in which there are vi vehicles in lane i. The vector v is a feasible if

1) 0 ≤ vi ≤ c-1 for i = 1, 2, …, r

2) Σ(vi: i = 1, 2, …r) = kc for some integer k and

3) 0 ≤ k ≤ m.

We define a Markov process on the feasible vectors in the following way. When a new rail car loaded with ni vehicles for each lane i arrives, the mixing center moves from its current state v = (vi) to a new state v’ = (vi’), where vi’ = vi + ni mod c. This represents the arrival of ni new vehicles to each load lane i and the dispatching of any full rail cars to ramp i.

Note that the set N of all possible loads is defined by

N = {(ni): 0 ≤ ni ≤ c for i = 1, 2,…, r and Σ (ni: i = 1, 2, …, r) = c}.

and Σ (prob(n): n in N) = 1.

The transition matrix T = (p(v, v’)) of the Markov process is defined by

p(v, v’) = Σ (prob(n): n in N and vi + ni = vi’ mod c for each i = 1, 2, …, r).

To show that T is doubly stochastic we show that for each n in N, there is one and only one feasible state v such that vi + ni = vi’ mod c for each i = 1, 2, …, r.

First, observe that a vector v satisfying vi + ni = vi’ mod c for each i = 1, 2, …, r is can only satisfy 0 ≤ vi ≤ c-1 for i = 1, 2, …, r if

[pic]

and this uniquely defines v. Furthermore, since Σ(vi’: i = 1, 2, …r) and Σ(ni: i = 1, 2, …r) are multiples of c, it is clear that Σ(vi: i = 1, 2, …r) is a multiple of c.

It remains then only to show that Σ(vi: i = 1, 2, …r) is at most mc. If vi’ ≥ ni for each i = 1, 2, …r, then Σ(vi: i = 1, 2, …r) = Σ(vi’: i = 1, 2, …r) - Σ(ni: i = 1, 2, …r) ≤ mc. Suppose vi’ < ni for each i = 1, 2, …s and vi’ ≥ ni for each i = s + 1, s + 2, …r, then

Σ(vi: i = 1, 2, …r) = Σ(vi’: i = 1, 2, …r) - Σ(ni: i = 1, 2, …r) + sc

= Σ(vi’: i = 1, 2, …s) - Σ(ni: i = 1, 2, …r) + Σ(vi’: i = s + 1, s + 2, …r) + sc

≤ (c – s) - c + Σ(vi’: i = s + 1, s + 2, …r) + sc

≤ (c – s) - c + (r-s)(c-1) + sc = r(c-1)

and so Σ(vi: i = 1, 2, …r) is an integer multiple of c not exceeding r(c-1), proving that v is a unique feasible state.

It follows that Σ(p(v, v’): v a feasible vector) = 1, implying that T is doubly stochastic and the steady state probabilities for the Markov process ensure the process is equally likely to be in each feasible state v.

We next argue that the average number of vehicles in each load lane is the same across all the lanes regardless of the fraction of vehicles destined for the corresponding ramp. This is essentially the Observation 1 of Section 2.1 and can be argued by symmetry. It follows from the fact that all states are equally likely and so, simply observing the numbers of vehicles in load lanes at a random time provides no information about which lanes serve higher volume ramps and which serve lower volume ramps. The numbers of vehicles in the different load lanes follow a common distribution. We therefore need only show that the average number of vehicles in the first load lane is (c-1)/2.

To reach this conclusion, we establish a bijection or one-to-one and onto mapping between feasible states v with v1 < (c-1)/2 and feasible states v’ with v1’ = c-1-v1. This proves that the average number of vehicles in load lane 1 is (c-1)/2.

For each feasible state v with v1 ( (c-1)/2, define f(v) = v’ in the following way. If v1 < (c-1)/2, then

i) v1’ = c-1-v1

ii) vi’ = vi for i = 2, 3, …, r-1

iii) vr’ = vr + 2v1 +1 mod c.

If v1 > (c-1)/2, then

iv) v1’ = c-1-v1

v) vi’ = vi for i = 2, 3, …, r-1

vi) vr’ = vr - 2v1 -1 mod c.

We argue that f defines a bijection between the feasible vectors v with v1 < (c-1)/2 and feasible vectors v’ with v1’ > (c-1)/2. Further, f maps each feasible vector v with v1 ( (c-1)/2, to a feasible vector v’= f(v) such that v1 + v1’ = c-1, proving that the average number of vehicles in lane 1, and hence in each lane, is (c-1)/2.

To see that f is a bijection it is enough to observe that f(f(v)) = v and to show that for each feasible vector v with v1 ( (c-1)/2, v’= f(v) is a feasible vector.

Consider a feasible vector v with v1 < (c-1)/2. Clearly v’= f(v) satisfies 0 ≤ vi’ ≤ c-1 for i = 1, 2, …, r. Thus, we need only show that Σ(vi’: i = 1, 2, …r) = kc for some integer k ≤ m. If vr + 2v1 +1 > c, then

Σ(vi’: i = 1, 2, …r) = c – 1- v1 + Σ(vi: i = 2, 3,…r-1) + vr + 2v1 +1 - c

= c – 1- 2v1 + Σ(vi: i = 1, 2,…r) + 2v1 +1 – c

= Σ(vi: i = 1, 2,…r)

proving that f(v) is a feasible vector in this case. The case for a vector v with v1 > (c-1)/2 is analogous. □

REFERENCES

Bartholdi III, John J., and Kevin R. Gue (1999), “Reducing Labor Costs in an LTL Cross-docking Terminal”, working paper Operations Research, forthcoming, (1999).

1. Bartholdi III, John J., and Kevin R. Gue , “Reducing Labor Costs in an LTL Cross docking Terminal”, Operations Research, forthcoming, (1999).

2. Daganzo, C.F., “The Break-Bulk Role of Terminals in Many-to-Many Logistics Networks”, Operations Research, 35(4) 543-555. (1987).

3. Donaldson, Harvey, Ellis L. Johnson, H. Donald Ratliff, and Mei Zhang (1998), “Network Design for Schedule-Driven Cross-Docking Systems”, Georgia Tech TLI Report, (1998).

4. Magnanti, T. L., (1984) “Network Design and Transportation Planning: Models and Algorithms,” Transportation Science 18(1), 1-55 (1984).

5. Mirchandani, Pitu B., and Richard L. Francis, (1990) “The Uncapacitated Facility Location Problem,” in Discrete Location Theory, John Wiley & Sons, Inc., (1990).

6. Powell, W.B. and Y. Sheffi, “Design and Implementation of an Interactive Optimization System for Network Design in the Motor Carrier Industry,” Operations Research, 37(1), 12-29 (1989)

7. Powell, W.B. and Y. Sheffi, “The Load Planning Problem of Motor Carriers: Problem Description and a Proposed Solution Approach,” Transportation Research, 17A(6), 471-480, (1983).

-----------------------

[1] Ford reported revenues of $137 billion on world-wide auto sales of 7 million vehicles or just under an average of $20,000 per vehicle.

-----------------------

c-1

[pic]

[pic]

[pic]

[pic]

vi’ – ni if vi’ e" ni

[pic]

[pic]

(c/-1)/2

c-1

(c-1)/2c/2

Time

Time

vi [pic]

[pic]

(c/-1)/2

c-1

(c-1)/2c/2

Time

Time

vi’ – ni + c, otherwise.

# autos

p2

vi’ – ni + c, otherwise.

p1

vi’ – ni if vi’ ≥ ni

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download