A capacitated vehicle routing problem for just-in-time delivery.

BHARATH S. VAIDYANATHAN [1]

JESSICA O. MATSON [2]

DAVID M. MILLER [1]

JACK E. MATSON [3]

This paper focuses on the formulation and solution of the problem of planning vehicle routes for material delivery within the premises of a plant working under a just-in-time

production system. The unique characteristic of this problem is that the quantity to be delivered at each of the demand nodes is a function of the route taken by the vehicle assigned to serve that node. The problem is modeled by adding a non-linear capacity constraint to the standard vehicle routing model, such that vehicle idle times and inventories at the customer locations are minimized. A heuristic solution procedure is outlined, and the formulation of a lower-bound relaxation is suggested. The performance of the heuristic solution procedure is evaluated in comparison to the lower-bound relaxation, and the heuristic procedure is shown to provide generally good results.

1. Introduction

Many assembly-type production scenarios work on a just-in-time basis with parts being delivered continuously from a central location. For example, the central location might be a sequencing area where parts delivered by sub-contractors are staged and sequenced according to the assembly sequence, with deliveries to assembly stations as needed. Another example might be a work center that produces parts required at many points in the assembly process. Such a situation exists at the Arvin exhaust system plant in Fayette, AL. As part of the plant's continuous improvement efforts, a research project was initiated with the University of Alabama's Productivity Center to develop a means of facilitating the plant's just-in-time system with minimal material handling cost, and this paper discusses the results of the project.

We present the underlying decision problem and its solution. More generally, this research focuses on the problem of developing vehicle routes for the delivery of parts from a central location to various customer locations (or nodes) under a Just-In-Time (JIT) production system. The unique characteristic of this problem, referred to hereafter as the JITCVRP, is that the delivery quantity required at a node is a function of the route taken by the vehicle assigned to serve that node.

2. Problem definition

The JITCVRP can be defined as follows. There is a central location (single depot) where all required parts are stocked. Demand points (customers) for the parts occur at specified locations in the production system. A fleet of identical vehicles with fixed capacities is available to deliver the parts to the demand points. All vehicles start from the depot and return to the depot at the end of the trip. Any vehicle can be assigned to any customer and is capable of carrying any part. The problem is to determine the route for each vehicle that will permit just-in-time delivery of parts to the demand locations in the production system, while minimizing the requirements for material handling equipment. The quantity delivered per trip should be just enough to meet the demand for the duration of the trip so that a vehicle will have no idle time between trips and inventories at the demand points are minimized.

The immediate objective of the JITCVRP is to minimize the total trip time of all available vehicles. Each vehicle is to be assigned a route such that the load per trip is as close to the capacity of the vehicle as possible. Each vehicle will repeat its route indefinitely or until there is a significant change in the production requirements. All customers assigned to a vehicle must be visited every trip, and a vehicle is not allowed to be idle between trips. Each vehicle may have a different trip time depending on its assigned route, and the cycle time, i.e., the time between consecutive trips, can be different for different vehicles.

Each customer requires a single part type to be delivered each trip. Each customer's demand is at a constant rate. For example, at Arvin the customers are workstations on several automated and semi-automated assembly lines with constant usage rates of component parts for a given product that is being assembled. Although the demand rate is constant for the component parts, the customer requirements will depend on the route assigned to the vehicle that delivers the parts. The customer uses component parts at a constant rate and is not allowed to run short of parts or hold more inventory than required; i.e., quantities in excess of a line-side safety stock are not allowed. Hence, the quantity delivered per trip should be just enough to meet the demand for the duration of the trip, which depends on the route assigned. For other Vehicle Routing Problems (VRPs) the customer demand is independent of the vehicle routes. In the JITCVRP, there is an interaction between the demand and the route. This characteristic dis tinguishes the JITCVRP from other VRP models discussed in the literature.

3. Example

Consider a situation using the data shown in Table 1, which shows the travel times in seconds and the customer requirements at the nodes in containers per minute. Note that the travel times include the associated load/unload times, and the matrix is asymmetric due to one-way aisles. Let the capacity of each vehicle be eight containers. Consider a proposed vehicle route as follows: Depot-A-B-C-D-Depot. For this route, the total trip time of the vehicle will be 130 seconds, or 2.17 minutes. Thus, the requirement at each of the nodes A through D will be 2.17 containers per trip, or three since an integer number of containers is required. Even ignoring the integer container requirement, the total trip load will exceed the vehicle capacity of eight containers. Thus, if this route is selected, two vehicles will be required to satisfy the requirements.

Suppose instead that the proposed route is Depot-C-D-B-A-Depot. The total trip time of a vehicle on this route will be 115 seconds, or 1.92 minutes, resulting in a requirement at each of the four nodes A through D of 1.92 containers per trip, or two containers per trip since an integer number of containers is required. Thus, this route does not exceed vehicle capacity, and only one vehicle is required for a feasible schedule.

This example illustrates that the required delivery quantities depend on the duration of the trip; in other words, customer requirements are a function of the vehicle route. The total customer requirements for route Depot-A-B-C-D-Depot exceeded the customer requirements for route Depot-C-D-B-A-Depot. The example also illustrates how the routes assigned to the vehicles affect the number of vehicles required.

4. Literature review

The VRP has generated extensive research, and we will not attempt to provide a comprehensive review. Summaries of the VRP and related problems can be found in Magnanti [1], Laporte and Nobert [2], Golden and Assad [3], Desrochers et al. [4], and Bodin et al. [5].

There are many different types of VRPs, each with its own unique features. Of these problems, the Inventory Routing Problem, or IRP as discussed by Federgruen and Zipkin. [6], Dror et al. [7], Bramel and Simchi-Levi [8], is the most closely related to the JITCVRP. The IRP deals with determining the quantity to be delivered to different locations such that the delivery costs and the inventory costs are minimized. The inventory cost depends on the replenishment frequency. If the time between deliveries (i.e., the cycle time) is small, the quantity to be delivered to cover the demand is also small resulting in lower inventory costs. Thus, the quantity delivered and the total cost depends on the vehicle routes. The solution procedure usually followed is to assume a fixed cycle time and determine the quantity that minimizes the inventory costs at each location. In the next stage of the procedure, the best vehicle routes to deliver these quantities are determined.

Using a fixed cycle time has several drawbacks in a just-in-time system. When the cycle time is too short, the vehicle capacity might have to be underutilized to achieve a trip time that is less than the cycle time. On the other hand, consider the problems resulting from cycle times that are too long:

(i) The quantity delivered per trip (transfer batch) may be large. Large transfer batches result in greater inventories at the demand points, and the supplying department also needs to produce more parts per trip.

(ii) Excessive inventories at the demand points require additional floor space, which is usually scarce in assembly areas. This could lead to congestion and product damage. Accumulation of large inventories also means that quality problems go undetected while bad parts are produced.

(iii) Large transfer batches may restrict the number of demand points a vehicle can visit per trip and potentially require additional vehicles to supply parts.

(iv) The vehicle may be idle between trips.

This paper focuses on an IP formulation of the JITCVRP. We have discussed the basic decision problem and previous related research. Next, the impact of the just-in-time philosophy on the various constraints of the JITCVRP is explored, and a simple relaxation of the problem that gives a lower bound to the optimal solution is presented. Finally, the solution procedure and experimental results are briefly described.

5. Problem formulation

The JITCVRP like most VRPs deals with a depot, customers and their demand, vehicle capacities, and travel times. The depot can be a single department that produces parts required by other departments or processes; or, it can also be a warehouse or a sequencing area where all the items supplied by sub-contractors are stocked and released for production when required.

The customers are departments or processes that use the parts available from the depot. The rate at which the parts are used will depend on the production rate of the department. Hence, the demand for the part is a constant rate that equals the production rate of the department. The demand rate used in the case of Arvin was based on calculations similar to the one used to determine the number of kanbans [9]. The vehicles travel on the route from the depot to the customers and back continuously without any idle time between trips. The quantity moved to a customer location should be just enough to meet the demand for the duration of the trip. The reasons for this are listed below.

(i) If the quantity moved is less than the demand for the duration of the trip, the customer (department or process) will have to wait for parts.

(ii) If the quantity moved is greater than the demand for the duration of a trip, there will be excess inventory at the customer's location. In the JIT system defined here, such unnecessary Work-In-Process (WIP) is not allowed. If WIP exists, the vehicle will also have to wait between trips while the WIP is being used. Hence, moving more parts to a customer than required results in some vehicle idle time and increased WIP; thus, it will be advantageous to move just enough to meet the demand.

(iii) In a JIT system, parts are moved in containers. When a customer uses a container of parts, a move card is generated that authorizes moving a full container of parts from the supplier to the customer. The customer will use parts at the rate of production. Thus, the rate at which the move cards are generated will be proportional to the rate of production, and the quantity moved must also equal the rate of production.

(iv) The quantity moved per trip is the transfer batch. Goldratt and Cox [10] point out other benefits of having smaller transfer batches. In the case of the JITCVRP, the smallest possible transfer batch will be the demand for the duration of the trip.

5.1. Assumptions

The constraints of the JITCVRP are all based on the operating rules of a JIT system. Some assumptions were made to incorporate these operating rules as they existed at Arvin (and are characteristic of other JIT implementations). These are listed below.

(i) The depot never runs out of stock, and hence no vehicles are starved for parts.

(ii) Each customer uses only one type of part. A customer using two types of parts can be considered to be two customers at the same location, each requiring a different part.

(iii) The customers use the parts at a constant rate that equals the production rate of the process. The usage rate is stationary; that is, it does not vary during the planning horizon. This assumption is justified since JIT production systems are most applicable to situations involving high-volume, stable demands.

(iv) The parts are moved in standard containers, and the vehicle capacity and the customer demand rate are defined in terms of number of containers.

(v) The number of containers delivered to a customer every trip is always an integer. This assumption can be made true regardless of the demand rate of the customers. For example, if a container can hold up to 100 pieces, and the demand per trip is 150 pieces, an integral number of containers can be achieved by packing 75 pieces per container.

(vi) All customers have to be visited every trip, with at least one container delivered to each customer.

(vii) The vehicle returns to the depot with empty containers and the associated move cards after dropping off parts at the customer locations. Since demand is stationary, the number of empty containers at any customer location (quantity consumed during the duration of the trip) is expected to be the same as the number of full containers dropped off at the same location. Thus, bringing back empty containers will not violate vehicle capacity.

(viii) It is assumed that the demand during a trip is great enough that the vehicles have to move materials continuously and the containers are substantially full. In a JIT assembly process the volume is usually high, and the material requirements are also high. Furthermore, the demands for different parts are also proportional. Assuming that the demand for parts is high is valid for many just-in-time systems.

(ix) Each customer can be assigned to only one vehicle. If the demand is too high for a single vehicle, a dedicated vehicle is assigned to this customer. Any excess demand can be met by another vehicle that can also service other customers. Thus, even high demand customers can be accommodated under the assumptions of this problem.

5.2. Model of the JITCVRP

The notation used in the formulation of the JITCVRP is summarized below. The notation is followed by the model, referred to as (P) hereafter, along with an explanation of the model.

Sets:

N = set of nodes;

A = set of arcs connecting the nodes;

Indices:

i = node index, i [epsilon]N;

j = node index, j [epsilon]N;

i = j = 1 is the depot;

k = vehicle index;

Parameters:

n = number of nodes = \N\;

K = number of vehicles;

[t.sub.ij] = travel time from node i to node j;

[d.sub.j] = demand rate at node j;

[[tau].sub.k] = trip capacity of a vehicle k;

[l.sub.j] = estimated loading/unloading time per trip at node j;

Decision variables:

[X.sub.ijk] = {1 if vehicle k is assigned to nodes i and j and travels along arc (i,j),

0 otherwise.

Model (P):

Minimize [Z.sup.p] = [[[sigma].sup.K].sub.k=1] [[[sigma].sup.n].sub.i=1] [[[sigma].sup.n].sub.[j=1.sub.j[not equal to]i]] ([t.sub.ij] + [l.sub.j])[X.sub.ijk]], (P1)

Subject to:

[[[sigma].sup.n].sub.[j=1.sub.j[not equal to]i]] [[[sigma].sup.K].sub.k=1] [X.sub.ijk] = 1 for i = 2,3,...,n, (P2)

[[[sigma].sup.n].sub.[i=1.sub.j[not equal to]i]] [[[sigma].sup.K].sub.k=1] [X.sub.ijk] = 1 for j = 2,3,...,n, (P3)

[[[sigma].sup.n].sub.j=2] [X.sub.1jk] = 1 [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]k, (P4)

[[[sigma].sup.n].sub.j=2] [X.sub.i1k] = 1 [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]k, (P5)

[[[sigma].sup.n].sub.[j=1.sub.j[not equal to]i]] ([X.sub.ijk] - [X.sub.jik]) = 0 [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]k,i, (P6)

[[[[sigma].sup.n].sub.i=1] [[[sigma].sup.n].sub.[j=1.sub.j[not equal to]i]] ([t.sub.ij] + [l.sub.j])[X.sub.ijk]] X [[[[sigma].sup.n].sub.i=1] [[[sigma].sup.n].sub.[j=1.sub.j[not equal to]i]] [d.sub.j][X.sub.ijk]] [less than or equal to] [[tau].sub.k] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]k, (P7)

[[[sigma].sup.n].sub.i=1] [[[sigma].sup.n].sub.[j=1.sub.j[not equal to]i]] [X.sub.ijk] [less than or equal to] [[tau].sub.k] + 1 [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]k, (P8)

[X.sub.k] [epsilon] S [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]k, (P9)

where:

S = {[X.sub.ijk]\[[sigma].sub.i[epsilon]Q] [[sigma].sub.j[epsilon]Q.sub.j[not equal to]i] [X.sub.ijk] [less than or equal to] \Q\ - 1, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] proper subset

Q of {2,...,n}, \Q\ [greater than or equal to] 2}

[X.sub.k] = {[X.sub.ijk]\[X.sub.ijk] [greater than] 0}

[X.sub.ijk] = 0 or 1 [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] I, j, k. (P10)

5.3. Explanation of model (F)

The objective of model (P) given in Equation (P1) is to minimize the total trip time for all the K vehicles. The trip time is a function of two components, namely, the travel time and the loading/unloading time. Equation (P1) can be rewritten as the sum of the travel time and the loading/unloading time as shown below.

Minimize [Z.sup.p] = [[[sigma].sup.K].sub.k=1] [[[sigma].sup.n].sub.i=1] [[[sigma].sup.n].sub.[j=1.sub.j[not equal to]i]] ([t.sub.ij][X.sub.ijk]) + [[[sigma].sup.K].sub.k=1] [[[sigma].sup.n].sub.i=1] [[[sigma].sup.n].sub.[j=1.sub.j[not equal to]i]] ([l.sub.ij][X.sub.ijk])

Only the travel time component is relevant to the solution. The loading/unloading time component has to be incurred regardless of the solution, since all the nodes have to be visited and the demand must be satisfied. Thus, ignoring the loading/unloading time in the objective function will not affect the vehicle assignments in the solution of (P) as long as the quantity per container remains constant.

Constraint sets (P2) and (P3) are the flow balance constraints for the customer nodes. These constraints ensure that the number of vehicles that travel to a node is the same as the number that travel from the node, thereby maintaining the flow balance. These constraints also ensure that each node is assigned to one and only one vehicle. Constraint sets (P4) and (P5) are the flow balance constraints for the depot. Unlike other nodes, the depot has K vehicles traveling to and from it. These constraint sets ensure that all K vehicles are assigned at least one customer node and that all K vehicles return to the depot. Constraint set (P6) is the trip continuity constraint set, which ensures that the same vehicle that arrives at a node departs from that node.

Constraint sets (P7) and (P8) are unique to the JITCVRP. Constraint set (P7) enforces trip capacity; it is a non-linear function of the trip time and the demand rate. Constraint set (P8) ensures that the number of nodes assigned to a vehicle, including the depot, does not exceed the quantity [[tau].sub.k]+ 1. This constraint is based on the assumption that at least one container has to be delivered to each customer every trip. This implies that a maximum of [[tau].sub.k] customers can be assigned to vehicle k. As the depot is part of every tour and has zero demand, the maximum number of nodes assigned to vehicle k should not exceed [[tau].sub.k] + 1.

Constraint set (P9) represents the sub-tour breaking constraints. Many implementations of these constraints can be found in the literature. This implementation was selected from Ahuja et al. [11]. For every vehicle k, the vector [X.sub.k] should be an element of the set S. The set S is the set of all possible vehicle route assignments and thus [X.sub.k] [epsilon] S implies that vehicle k has been assigned a valid route.

The formulation (P) will have [n.sup.2] K 0-1 integer variables and 2(n - 1) + [2.sup.n+l] K constraints, of which K constraints are non-linear. At the Arvin assembly plant, there were 71 nodes (n = 71) and the best solution found required six vehicles (K = 6). Such a model will involve 30 246 binary integer variables, with 2.83 x [10.sup.22] constraints of which six are non-linear. The JITCVRP is a Non-Linear Integer Programming (NLIP) problem; its size increases exponentially with n, the number of customers, and K, the number of vehicles. Based on its integer variable characteristics, the JITCVRP is difficult to solve, even for small values of n and K. Furthermore, the non-linear capacity constraints are an additional difficulty. However, relaxations of the model can be used to arrive at a lower bound on the number of vehicles required, as discussed in the following section. This lower bound will be used as a benchmark to evaluate the quality of heuristic solutions developed using the algorithm described i n Section 7.

6. Relaxed model

Several relaxations of the model (P) are possible. Constraints (P2), (P3), (P4) and (P5) constitute the generalized assignment problem that is known to be easy to solve. A relaxed model can be formulated, consisting of constraint sets (P2) and (P3) along with constraint sets (P6) and (P8) and modified forms of constraint sets (P4), (P5) and (P7). Although this relaxed model can be solved easily, the resulting solution may have sub-tours and may violate the trip capacity constraint. However, the solution can be used to determine a lower bound on the number of vehicles required.

Several assumptions were made in formulating the relaxed problem, as listed below.

(i) All vehicles are assumed to have the same capacity. (Note: the relaxed model tries to minimize the number of vehicles used. If vehicles have different capacities, using the vehicles with the largest capacities first can minimize the number of vehicles.)

(ii) A standard loading/unloading time per container for all parts is assumed. This assumption permits an easier estimate of the total loading/unloading time per vehicle.

(iii) The demand at the nodes is not high enough for the estimated quantity per trip to exceed trip capacity. In other words, the requirements during a period of time that includes the loading/unloading time of the vehicle plus round-trip travel time to a customer location does not exceed the trip capacity.

6.1. Relaxed model formulation

The formulation of the relaxed model (R) is given below. All sets, indices, decision variables, and parameters are identical to those for model (P) with the addition of the following two parameters and the exception that [l.sub.j] is omitted.

Parameters:

LUL = Estimated loading unloading time for one trip. For example, if the vehicle capacity is 10 containers, and the average loading/ unloading time per container is 1 minute, then LUL = 10 mm.

[C.sub.k] = Penalty for using a vehicle, which is any positive value chosen such that [C.sub.k] [less than] [C.sub.k+1]. For example, if the number of vehicles is three, then [C.sub.1] = 0, [C.sub.2] = 1, and [C.sub.3] = 2, will force vehicle 1 to be utilized to its maximum capacity before using vehicle 2.

Decision variables:

[X.sub.ijk] = {1 if vehicle k is assigned to nodes i and J and travels along arc (i,j),

0 otherwise.

Relaxed Model (R):

Minimize [Z.sup.R] = [[[sigma].sup.K].sub.k=1] [[[sigma].sup.n].sub.i=1] [[[sigma].sup.n].sub.[j=1.sub.j[not equal to]i]] [([t.sub.ij] + [C.sub.k])[X.sub.ijk]], (R1)

Subject to:

[[[sigma].sup.n].sub.[j=1.sub.j[not equal to]i]] [[[sigma].sup.K].sub.k=1] [X.sub.ijk] = 1 for i = 2, 3,..., n, (R2)

[[[sigma].sup.n].sub.[i=1.sub.j[not equal to]j]] [[[sigma].sup.K].sub.k=1] [X.sub.ijk] = 1 for j = 2, 3,.. .,n, (R3)

[[[sigma].sup.n].sub.j=2] [[[sigma].sup.K].sub.k=1] [X.sub.1jk] [greater than or equal to] [n - 1]/[tau], (R4)

[[[sigma].sup.n].sub.i=2] [[[sigma].sup.K].sub.k=1] [X.sub.i1k] [greater than or equal to] [n - 1]/[tau], (R5)

[[[sigma].sup.n].sub.[j=1.sub.j[not equal to]i]] ([X.sub.jik] - [X.sub.ijk]) = 0 [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] k, i, (R6)

[[[sigma].sup.n].sub.i=1] [[[sigma].sup.n].sub.j=1] ([d.sub.j](LUL + [t.sub.1i] + [t.sub.ij] + [t.sub.j1]))[X.sub.ijk] [less than or equal to] [tau] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] k, (R7)

[[[sigma].sup.n].sub.i=1] [[[sigma].sup.n].sub.[j=1.sub.j[not equal to]i]] [X.sub.ijk] [less than or equal to] [tau] + 1 [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] K, (R8)

[X.sub.ijk] = 0 or 1 [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] i, j, k. (R9)

6.2. Explanation of model (R)

The objective of the relaxed problem (R) given by Equation (R1) is to minimize the total travel time using the minimum number of vehicles. This function has two major differences compared to the objective of the original problem given by Equation (P1).

(i) (R1) is a function of the travel time and a penalty factor [C.sub.k]. The solution to (R) gives the lower bound on the number of vehicles required. The number of vehicles K actually required might be greater than this lower bound. By penalizing the addition of a vehicle, a new vehicle will be used only if required, thereby minimizing the number of vehicles. Note that if the lower bound equals K, all the vehicles would be used regardless of the actual values of the penalty factor [C.sub.k]. This is the case in (P), where the constraints require that all K vehicles be used and, hence, [C.sub.k] was not included as a cost in the objective function.

(ii) Equation (R1) does not include the loading/unloading time parameter. The objective of (R) is to minimize the number of vehicles, and the value of the objective function has meaning only in relative terms. The constant loading/unloading time factor will be the same for all solutions and thus can be ignored. The loading/unloading time has more significance as part of the objective of (P) as explained earlier.

Constraint sets (R2), (R3), (R4) and (R5) are the flow balance constraints, (R6) is the trip continuity constraint, and (R7) and (R8) are the trip capacity constraints. Of these seven constraint sets, (R2), (R3), (R6) and (R8) are identical to constraints (P2), (P3), (P6) and (P8) of the original problem (P).

Constraint sets (R4), (R5) and (R7) are modified forms of constraints (P4), (P5) and (P7) of (P). In (P) all K vehicles have to be used, and constraints (P4) and (P5) ensure that all vehicles are assigned a route. In problem (R), K is the maximum number of vehicles, but the nature of the demand may not require all of them to be used. The number of vehicles used in the solution to problem (R) is a lower bound, and it will be less than or equal to K. However, due to the assumption that at least one container is delivered to each customer every trip (enforced by constraint (R8)), at least [(n - 1)/[tau] vehicles will be required, and constraints (R4) and (R5) ensure that at least the minimum number of vehicles is used. These constraints yield a preliminary lower bound that is independent of the demand rate at the nodes.

Constraints in set (R7) consider the demand at the nodes. Due to the penalty factor [C.sub.k] in the objective function, each vehicle will be utilized to its maximum capacity before the next vehicle is assigned any route. Thus, each vehicle can be expected to incur a total loading/unloading time of LUL. Furthermore, [X.sub.ijk] = 1 implies that after the vehicle leaves the depot it will reach node i, then travel to node] j, and eventually return to the depot. In travelling to node i, the vehicle will incur a travel time of at least [t.sub.1i]. The vehicle then travels from node I to j and in doing so will incur a travel time of [t.sub.ij]. Also, since the vehicle returns to the depot, it will incur a travel time of at least [t.sub.j1]. The total trip time of the vehicle will be at least LUL + [t.sub.1i]+ [t.sub.ij] + [t.sub.j1]. Thus the demand rate at each node can be multiplied by this estimated trip time, LUL + [t.sub.1i] + [t.sub.ij] + [t.sub.j1], to arrive at a fixed demand quantity estimate for each n ode. This estimated demand is independent of the route, and the constraint is linear. However, in calculating the demand, the travel time between all other nodes in the route has been ignored, and the estimated demand for the relaxed problem will generally be less than the actual demand for the trip. The similarities and differences between formulations (P) and (R) are given in Table 2.

The solution to (R) will generally underestimate the number of vehicles required to solve (P) and can be used as a lower bound. The reasons why (R) underestimates the number of vehicles required (and, hence, provides a lower bound) are listed below.

(i) The solution to (R) may have one or more sub-tours, which are not allowed in (P). Eliminating the sub-tours to solve (P) will increase the travel time of the vehicles, which will in turn increase the demand at the nodes and thus require more vehicles. Therefore, the optimal solution of (P) will require at least the same number of vehicles as (R).

(ii) The demand at each node used to arrive at the solution for ER) is a fixed quantity that accounts for only a part of the total travel time of the vehicle. Thus, vehicles in the optimal solution to (P) will travel further and need to carry more units per trip. Additional vehicles may be required for a feasible solution to (P).

7. Solution

A heuristic two-stage procedure was used to solve the JITCVRP. The first stage is a tour-building stage where starting tours are developed. These tours are improved in the second stage. The solution procedure is described in the following sections.

7.1. Stage 1: tour building

In this stage, capacity-feasible starting tours are generated for vehicles using a modified version of the Nearest Neighbor (NN) algorithm [12]. The NN algorithm was used because of the nature of the problems usually solved. The JITCVRP is used to develop vehicle routes within assembly areas where travel is along aisles. It is logical for vehicles travelling along an aisle to visit consecutive demand points on either side of the aisle entering at one end and exiting through the other. Thus, the NN algorithm was expected to yield good starting solutions.

To implement the NN algorithm, certain modifications need to be made due to the nature of the demand. Adding a node can only increase the trip time of the vehicle. Since the requirement at the nodes is a function of the trip time, adding a node will increase the demand at all nodes already assigned to the vehicle. Hence, adding a node requires re-calculation of the demand at all nodes assigned to the vehicle to verify capacity feasibility. Other restrictions including integral number of containers per customer also need to be incorporated. The Modified Nearest Neighbor (MNN) algorithm shown in Fig. 1 generates feasible starting tours. The MNN takes as input two sets, namely, TOUR (a partial route that should contain at least the depot); and

LIST (the set of all unassigned nodes). The algorithm returns the complete route and the remaining unassigned nodes.

7.2. Stage 2: tour improvement

In this stage the starting tour developed using MNN is improved using the 3-opt heuristic. Golden et al. [13] have reported that the 3-opt heuristic yielded solutions within 0.5% of the best solution for a wide variety of test problems. A more detailed discussion of the implementation of the algorithm used to improve the starting tours can be found in Lin [14].

7.3. Procedure for solving the JITCVRP

The solution procedure involves generating starting tours for each vehicle using the MNN algorithm. This tour is then improved using the 3-opt procedure. Any improvement will reduce the demand per trip. Hence, an attempt is made to add more nodes to the vehicle's tour and the new tour is improved using the 3-opt procedure. This process is continued until no nodes can be added without violating capacity. At this point, the route for the next vehicle is determined using the remaining unassigned customer nodes. This process is continued until all customers have been assigned a vehicle. Please refer to Fig. 2 for more information.

8. Testing

The heuristic procedure described above was tested extensively using actual demand and customer location information at Arvin. The quality of the heuristic solution was evaluated by comparing the number of vehicles required in the heuristic solution to the lower bound on the number of vehicles determined by solving the relaxed problem (R). Experiments were designed to test the effects of differing levels of problem size (10--71 customer nodes), vehicle capacity (16--32 containers), and demand rate (50--150% of the actual production rates), or factors A, B, and C, respectively, and all possible interactions on the solution quality. A total of 270 different problems were solved. (See Vaidyanathan [15] for detailed information on the test problems, hypothesis tests, and analysis). The factors used in hypotheses tests and the results of the tests are summarized in Table 3.

In general, the heuristic solution results compared favorably with the lower-bound solution in terms of the number of vehicles required. On the average, the heuristic solution required 0.35 vehicles more than the lower bound. Several reasons were identified to explain why the main effect A (problem size), the interaction effects AB (problem size x vehicle capacity), and BC (vehicle capacity x demand rate) were significant.

The significant effect of problem size can be attributed mainly to the manner in which the non-linear capacity constraint of model (P) was approximated to determine a lower bound. The demand per trip was set at a fixed quantity based on the travel time of a partial tour that involved just the depot and the node. In an actual tour the vehicle will travel to other nodes increasing the trip time and hence the trip demand per node. This additional demand is ignored while calculating the lower bound. For larger problems the net effect of the "ignored" demand becomes quite substantial, resulting in greater inaccuracies in calculating the lower bound. In addition the lower bound is based on tours that may have sub-tours; eliminating the sub-tours can only increase the trip times and the demand per node. These reasons explain why the problem size significantly affects the solution quality.

Both the significant interaction effects involve the vehicle capacity. The deviation from the lower bound was found to be pronounced for problems involving small vehicles, large number of nodes, and high demand rates. This could be because smaller vehicles offer a smaller degree of freedom to schedule delivery quantities. When the demand rates are high, larger quantities need to be delivered to each node. Larger delivery quantities make it more difficult to find a combination of nodes that can utilize most of the vehicle's capacity, when the capacity is small. To validate this conclusion, the fill rates of the vehicles (capacity utilized per trip) were studied for problems with different vehicle sizes. It was found that the fill rates were significantly less for smaller vehicles. Smaller vehicles have greater unutilized capacity per trip and thus may require more vehicles.

9. Summary

This research has defined the vehicle routing problem in the context of an in-plant JIT system and developed an integer programming formulation of the problem. A relaxation of the problem was developed by estimating the demand per trip at each node to linearize the capacity constraint. Although the relaxation will usually underestimate the total load per trip and may result in infeasible routes having sub-tours, it can serve to provide a lower bound on the number of vehicles required. A heuristic solution procedure was outlined and shown to provide generally good results, although it is more reliable when vehicle capacities are large. The heuristic procedure provides a simple and effective way to determine vehicle routes for supplying a set of nodes just-in-time.

Substantial improvements to the lower bound can be achieved with other forms of the capacity constraint that are better approximations of the nonlinear constraint. Improvements to the lower bound may provide a better evaluation of the solution heuristic (and other procedures) and may show that some of the factors are no longer significant. A more important contribution would be improvements to the solution procedure. If the capacity constraint is linearized, column generation and other techniques could be used to solve reasonable sized problems. However, in real-world applications (as in the case of Arvin), solution times are very critical. Route assignments may need to be re-calculated when the production rate changes, a line goes down, or a line is changed to produce a different product. In these situations good quality solutions are required in a timely manner, and the solution algorithm described here was found to provide such a solution.

Biographies

Bharath S. Vaidyanathan is currently working towards a Ph.D. in the Department of Management Science and Statistics at the University of Alabama. He received a B.S. in Management Studies from the Birla Institute of Technology and Science in Pilani, India, and an M.S. in Industrial Engineering from the University of Alabama. His research interests include scheduling, optimization models, and discrete event simulation.

Jessica O. Matson is Professor and Chairman of the Industrial and Manufacturing Engineering Department at Tennessee Technological University. She holds Ph.D. and Master's degrees in Industrial Engineering from the Georgia Institute of Technology and a B.S. in Industrial Engineering from Mississippi State University. She has previously served on the faculties of Mississippi State and the University of Alabama. Her research interests are focused on problems in production and distribution systems.

David M. Miller is currently a Professor of Management Science at the University of Alabama and Director of the Alabama Productivity Center. His professional honors include appointment as the Reese Phifer Faculty Fellow in Manufacturing Management and selection as a Fellow in the World Academy of Productivity Sciences and a 1992 Malcolm Baldrige National Quality Award examiner. Dr. Miller holds a Ph.D. in Industrial Engineering and Operations Research from the Georgia Institute of Technology. He also holds a Master's in Industrial Engineering from Georgia Tech, along with a B.S. in Industrial Engineering from the University of Alabama. He has published over 45 professional articles in journals such as the Harvard Business Review and Management Science and a textbook on Industrial Engineering.

Jack E. Matson is an Associate Professor in the Decision Sciences and Management Department at Tennessee Technological University. He has over 12 years of industrial experience as a manager in MIS and strategic planning and 4 years as the owner of a small business. He has also served on the faculty of the Industrial Engineering Department at the University of Alabama and consulted with numerous industries. Dr. Matson received a Ph.D. in Management Science from the University of Alabama, an M.S. in Industrial Engineering from Mississippi State University, and a B.S. in Mathematics from Clemson University. His research interests are focused on discrete event simulation.

(1.) Department of Management Science and Statistics, University of Alabama, Box 870226, Tuscaloosa, AL 35487-0226, USA

(2.) Department of Industrial and Manufacturing Engineering, Tennessee Technological University, Box 5011, Cookeville, TN 38505, USA E-mail: jmatson@tntech.edu

(3.) Department of Decision Sciences and Management, Tennessee Technological University, Box 5022, Cookeville, TN 38505, USA

References

(1.) Magnanti, T.L. (1981) Combinatorial optimization and vehicle fleet planning: perspectives and prospects. Networks, 11, 179-213.

(2.) Laporte, G. and Nobert, Y. (1987) Exact algorithms for the vehicle routing problem. Annals of Discrete Mathematics: Surveys in Combinatorial Optimization, 31, 147-184.

(3.) Golden, B.L. and Assad, A.A., (eds.) (1988) Vehicle Routing: Method and Studies, North-Holland, Amsterdam.

(4.) Desrochers, M., Lenstra, J.K. and Savelsbergh, M.W.P. (1990) A classification scheme for vehicle routing and scheduling problems. European Journal of Operational Research, 46, 322-332.

(5.) Bodin, L.D., Golden, B.L., Assad, A.A. and Ball, M.O. (1983) Routing and scheduling of vehicles and crews: the state of the art. Computers and Operations Research, 10, 63-211.

(6.) Federgruen, A. and Zipkin, P. (1984) A combined vehicle routing and inventory allocation problem. Operations Research, 32, 1019-1037.

(7.) Dror, M., Ball, M. and Golden, B.L. (1985/6) A computational comparison of algorithms for the inventory routing problem. Annals of Operations Research, 4, 3-23.

(8.) Bramel, J. and Simchi-Levi, D. (1995) A location based heuristic for general routing problems. Operations Research, 43, 649-660.

(9.) Vollman, T.E., Berry, W.L. and Whybark, D.C. (1992) Manufacturing Planning and Control Systems, 3rd edn, Irwin, Chicago, IL.

(10.) Goldratt, E.M. and Cox, J. (1986) The Goal, North River Press, Croton-on-Hudson.

(11.) Ahuja, R.K., Magnanti, T.L. and Orlin, J.P. (1993) Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, Englewood Cliffs, NJ.

(12.) Rosenkrantz, D., Stearns, R, and Lewis, P. (1974) Approximate algorithms for the travelling salesman problem, Proceedings of the 15th Annual IEEE Symposium on Switching and Automation Theory, pp. 33-44.

(13.) Golden, B.L., Bodin, L.D., Doyle, T. and Stewart, W.R. (1979) Approximate travelling salesman algorithms. Operations Research, 28, 694-711.

(14.) Lin, S. (1965) Computer solutions of the travelling salesman problem. Bell Systems Technical Journal, 44, 2245-2269.

(15.) Vaidyanathan, B.S. (1996) A procedure to solve the N-customer, 1-depot capacitated vehicle routing problem for just-in-time delivery. Master's thesis, Department of Industrial Engineering, The University of Alabama, Tuscaloosa, AL.

                     Travel time and demand rate data
        Travel time (sec)             Demand rate
From\To      Depot         A  B  C  D  (totes/min)
Depot         --          20 40 40 50      0
A             20          -- 15 35 45      1
B             35          15 -- 20 30      1
C             55          35 20 -- 10      1
D             65          45 30 10 --      1
              Comparison of problem formulations (P) and (R)
Number of decision variables The number of decision variables is
                             the same
                             for both formulations.
Number of constraints        The relaxed formulation does not
                             include the
                             sub-tour breaking constraints and
                             hence will
                             have fewer constraints.
Feasible region              The feasible region of (P) will be a
                             proper
                             subset of the feasible region of (R).
Objective function           The objective function of (P)
                             represents the
                             total time required by all vehicles,
                             which is
                             to be minimized. The objective
                             function of (R)
                             also minimizes vehicle usage, but the
                             value of
                             the objective function has only
                             relative
                             significance.
Trip-capacity constraint     The trip-capacity constraint of (P) is
                             a non-linear
                             function of travel and
                             loading/unloading times.
                             The trip-capacity constraint of (R) is
                             a linear
                             approximation of trip load and usually
                             underestimates
                             the actual load per trip.
               Factors and their effects on solution quality
                              Factors
A                 Problem size (number of nodes)
B             Vehicle capacity (number of containers)
C                    Demand rate at the nodes
AB         Problem size and vehicle capacity interaction
AC           Problem size and demand rate interaction
BC         Vehicle capacity and demand rate interaction
ABC Problem size, vehicle capacity, and demand rate interaction
    Deviation of heuristic solution from
      lower bound (number of vehicles) [*]
A               Significant
B             Not significant
C             Not significant
AB              Significant
AC            Not significant
BC              Significant
ABC           Not significant
(*.)Conclusions drawn at 10% level of significance