W e consider the problem of scheduling trains and containers (or trucks and pallets) between a depot and a destination. Goods arrive at the depot dynamically over time and have distinct due dates at the destination. There is a fixed-charge transportation cost for each vehicle, and each vehicle has the same capacity. The cost of holding goods may differ between the depot and the destination. The goal is to minimize the sum of transportation and holding costs. For the case in which all goods have the same holding costs, we consider two variations: one in which the holding cost at the destination is less than that at the origin, and one in which the relationship is reversed. For the first variation, we derive properties of the optimal solution which provide the basis for an O T 2 solution procedure. For the second variation, we introduce a new definition of a regeneration state, derive strong characterizations of the shipment schedule within a regeneration interval, and develop an O T 4 procedure. We also analyze two multi-item scenarios. In the first, for each item, the holding cost at the origin is less than that at the destination; in the second, the relationship is reversed for all items. We generalize several of the structural results for the single-item problem to the corresponding multi-item case. We also show that the optimal vehicle schedule can be obtained by solving a related single-item problem in which the item demands are aggregated in a particular way. The optimal assignment of customer orders to vehicles can then be found by solving a linear program. Our work is motivated by the problem of scheduling trains or trucks outbound from a single depot and assigning goods to these vehicles, with the objective of achieving on-time delivery at minimum cost. We consider a finite time horizon during which customer orders dynamically become available at the origin, and have different due dates at their destinations. We assume that the demand, distinguished by origin, arrival date at the origin, destination, and due date at the destination, is known in advance, or can be forecasted accurately enough over the time horizon for planning purposes. We consider direct shipments between a depot and each of the various destinations. Assuming there is no dependence among the destinations, we can decompose the problem by destination. Although our initial motivation was derived from train scheduling applications, a similar situation also arises when finished goods must be transported by truck from a factory to distant markets or break-bulk warehouses. Customer orders with distinct due dates and destined for a particular market are produced at the factory and become available for shipment over time. The manufacturer faces the decision of when to dispatch trucks and which customer orders to assign to each truck. Of course, this problem would be simplified if goods destined for a particular market were manufactured close together in time. However, there are often competing and/or overriding considerations in establishing the production schedule, thus necessitating the solution of the transportation scheduling problem. As is typical in rail, trucking, and sea transport operations, there is a (nearly) fixed charge associated with the direct movement of the vehicle or vessel from the origin to the destination which includes the cost of labor for the movement of the vehicle and any other costs that are not volume dependent, including the portion of fuel and maintenance costs that do not depend on the volume of goods in the vehicle. Furthermore, the capacity of the transport vehicle is known. Because we are addressing a short-horizon problem, we assume that the fixed cost of transportation per vehicle is constant over time and independent of the number of vehicles sent. In the vast majority of situations, total volumedependent costs will differ only slightly, if at all, as the shipping schedule changes. For example, the incremental cost for fuel associated with carrying a given weight or volume of goods via truck from origin to destination, above and beyond that required to operate the truck(s) empty, would be roughly the same irrespective of the allocation of goods among trucks. It would be more efficient, of course, to ship all of the goods on as few trucks as possible, provided their capacity is not exceeded, and this aspect is captured by the fixed-charge transportation cost. We assume that total volume-dependent costs are insensitive to the details of the shipping schedule. Similarly, in many settings the cost of holding the goods at the origin differs little from the cost at the destination, but they may differ widely in other settings. For this reason, we also analyze situations in which the holding costs differ among items and between locations. Because penalties for tardy delivery may be substantial, our primary goal is to minimize the sum of fixed-charge transportation costs while delivering the goods on time. We will, however, consider the more general problem in which the holding costs may differ between the origin and destination to reflect the relative cost of storage space, as well as the extent to which the customer is willing to accept early shipments. In some instances, the customer may wish to receive the shipment as early as possible, while in other instances a just-in-time shipping schedule may be preferable. The former situation can be modeled by imposing a higher holding cost at the origin than at the destination, while the latter scenario is represented by the reverse relationship. We note that any opportunity costs of capital associated with holding the goods in transit are usually borne by the shipper or consignee, and not by the transporter. The transporter does, however, bear the opportunity cost of having equipment, such as trailers and containers, unavailable for use. We analyze the case in which goods have homogeneous holding costs, where the holding cost is more expensive at the destination than at the origin. The opposite holding cost relationship can be addressed by the same approach using an appropriate transformation of the problem. We also model versions of the problem with item-dependent holding costs. We present results for the case in which, for each item, the holding cost at the destination is higher than that at the origin. If the reverse relationship holds for all items, a transformation similar to that mentioned above can be used to solve the problem. We do not consider the most general case in which it is less expensive to hold some items at the origin than at the destination, and the reverse holds for the other items. The latter situation may arise, for example, if the freight has different temperature requirements; storage costs will depend upon the ambient weather. Our problem is similar to other capacitated fixedcharge network flow problems but contains three important complicating features: (i) not all goods are available at the beginning of the horizon, i.e., goods arrive dynamically, (ii) it may be necessary and/or optimal to send more than one vehicle in a given period, i.e., to incur "multiple setups," and (iii) goods are not homogeneous and have distinct due dates at the destination, and thus must be treated as distinct customer orders. We assume, however, that the goods are homogeneous in their use of transport capacity. Although there is a large body of literature on lotsizing problems with a fixed-charge structure, little work has been done on problems in which there is a Iwaniec (1979) stochastic, dynamic one no yes Lee (1989) deterministic, dynamic one no yes Ben- Kheder (1990) deterministic, dynamic multiple no yes Our paper deterministic, dynamic one or more yes yes capacity associated with each fixed charge incurred. Florian and Klein (1971) consider a single-item capacitated lot-sizing problem where all materials are available for processing (or, alternately, for shipment) at the beginning of the horizon, and there is a fixed charge for each production run with fixed capacity. At most, one production run is allowed in each period. They show that when capacity is constant over time, the optimal solution has a production level equal either to zero or to the capacity in all periods except at most one between two consecutive regeneration points. (For Florian and Klein's problem, a regeneration point is defined as a point in time with no onhand inventory.) This result provides the basis for an efficient solution procedure based on an underlying shortest path problem. Lippman (1969) addresses the single-product problem with static arrivals and multiple setups. He derives several properties of the optimal solution and develops an O T 3 algorithm for the problem. We relate his characterization of the optimal solution to our structural results as our discussion proceeds. In a later paper, Lippman (1971) treats a continuous-time, constant-demand version of the problem. Iwaniec (1979) studies a base stock policy, rounded up to the next full vehicle, in the context of a discrete-time version of the problem with stochastic demand. Lee (1989) addresses the multiple setup problem where all materials are available for shipment at the beginning of the horizon and there is a separate setup cost per order. He presents an O T 4 procedure for the problem. All of the aforementioned articles consider only a single product. The only research of which we are aware that treats the multi-item case (where the items have different holding costs) in Ben-Kheder (1990) . He studies the case with dynamic demands under the assumption that the holding cost at the destination is higher than at the origin. He presents a solution procedure with an underlying shortest path network, where the path costs are computed using a branchand-bound algorithm. Table 1 contrasts our models with others in the literature. Note that none of the models in the literature allows for dynamic arrivals of goods. The remainder of the paper is organized as follows. In §1, we present a dynamic programming formulation of the problem. In §2, we characterize the optimal solution and present an optimal O T 4 algorithm for the case in which all goods have the same holding costs, and the holding cost is larger at the destination than at the origin. We also explain how the reverse holding cost relationship can be handled by an appropriate transformation of the network. In §3, we extend these results to allow for items with different holding cost rates. Section 4 concludes the paper with a discussion of the relationship between our results and those for related models with static arrivals.
Yano and Newman REF proposed a model where train schedules are to be established based on a dynamic arrival of freight at origins.
Scheduling Trains and Containers with Due Dates and Dynamic Arrivals
Transportation Science
Transportation Science
Mathematics Computer Science