|
...requests various shippers whose shipment loads are generally smaller than a truck's capacity. The trucking company needs to make decisions on when to close (dispatch) a truck. Closing a truck early reduces both the holding costs of customers and the revenue from customers. In conducting the business, the company needs to reject some requests of low profit margins, since such requests consume the capacity of a truck and generate waiting costs. Similar cases occur in settings such as the freight service of a forwarder and the long-distance bus service or postal service.
We would like to understand the admission of customers and the dispatching of vehicles in a general transportation system. To be realistic, we work on a tractable framework with manageable complexity. The result from this system will shed light on the operations of more complex systems.
We work with a two-terminal system such that customers (passengers, transportation requests) arrive at terminal [delta] requesting transportation services to terminal 1 - [delta] according to a Poisson process of rate [[lambda].sub.[delta]], [delta] = 0, 1. The transport services are satisfied by a vehicle of capacity Q (Q [less than or equal to] [infinity]) that runs back and forth between the two terminals. The inter-terminal travel times follow an Erlang distribution. All the random quantities, the travel times and the arrival processes, are independent of each other. Each customer brings in a random reward (revenue) that is observable on arrival. A central system administrator decides whether to accept or to reject a customer at the customer's arrival based on the brought-in reward and the status of the system. If a customer is accepted, the administrator receives the reward (immediately); otherwise, the administrator pays a compensation to the rejected customer. In addition to the customer admission decision, the administrator also considers the vehicle dispatching decision, with cost factors such as the holding cost of customers and the dispatching cost of the vehicle. The aim is to maximize the expected total long-run discounted profit.
There exist various models that consider the admission and dispatching decisions. The control of the bulk service queues to balance the waiting cost and the operating cost is very similar to the dispatching decision at one terminal. Such a bulk server fed by Poisson arrivals is studied by Bailey (1954), Neuts (1967), Deb and Serfozo (1973), and Weiss (1979), among others. A general result from Deb and Serfozo (1973) is that when the waiting cost is increasing in the number of customers waiting in the queue, and the service cost is linear in the number of customers in a batch, the optimal control policy is of the threshold type, i.e., to dispatch (to serve a batch) if and only if the number of customers waiting reaches or exceeds a certain level. For a bulk sever that can be switched on and off with a switching cost (Deb, 1976), or fed by a compound Poisson process (Deb, 1984; Aalto, 1998, 2000), the optimal dispatching policies are also of the threshold type.
The dispatching control of two-terminal systems has also been studied. Ignall and Kolesar (1974), Weiss (1981), and Lee and Kim (1994) consider the case that the vehicle can be held at only one terminal. They demonstrate that, for both Poisson (Ignall and Kolesar, 1974) and compound Poisson (Lee and Kim, 1994) arrival processes, it is optimal to dispatch the vehicle if and only if the total number of customers waiting at both terminals reaches (or exceeds) some threshold levels. Weiss (1981) presents a method to compute the optimal threshold levels. The problem that the vehicle can be held at both terminals is investigated by Deb (1978), Deb and Schmidt (1987), and Lee and Srinivasan (1990). The first two papers show that, for systems of Poisson arrivals, with complete information of the system, the optimal dispatching policies that minimize either the total discounted cost or the average cost are of the threshold type, and the threshold levels at one terminal are non-increasing functions of the number of customers waiting at the other terminal. Lee and Srinivasan (1990) study the problem with compound Poisson arrivals, where the number of customers waiting at a terminal is known only when a vehicle arrives there. They evaluate some threshold-based heuristics for this situation. Van Oyen and Teneketzis (1992) consider a discrete-time two-terminal system such that when making dispatching decisions at a terminal, the vehicle controller does not have the latest status of the other terminal. They show that there exists an optimal threshold type policy under such delayed information.
The papers cited so far consider cost minimization in which all arrivals are accepted. However, in many real-life applications, admission fees are collected from customers to maximize profit. In such cases, rejecting customers of low profit margins is clearly desirable, even when there is a penalty cost associated with such a rejection. The Dynamic and Stochastic Knapsack Problem (DSKP), a problem similar to the one-terminal version of our problem with only one-time vehicle dispatching, considers both the admission and the dispatching decisions. A new arrival is either accepted or rejected, depending on the remaining capacity of the knapsack, the time to a deadline, and the reward of the arrival. The system administrator also decides when to close the knapsack (dispatch the vehicle). Generally, the optimal admission policy is of the threshold type, and the optimal dispatching policy may bear certain monotone or convex properties even if it is not of the threshold type. See Kleywegt (1996), Papastavrou et al. (1996), Kleywegt and Papastavrou (1998a, 2001) for further details.
Kleywegh and Papastavrou (1998b) consider a comprehensive admission and dispatching control problem: the Dynamic and Stochastic Distribution Problem (DSDP) with multiple terminals, and multiple vehicles. With independent Poisson arrivals and exponential inter-terminal travel times, they partially characterize the optimal admission and dispatching policies, the former being of the threshold type. Because the number of states grows exponentially, they propose heuristics to solve problems of moderate size. Generally, the heuristics are based on the decomposition solving subproblems terminal by terminal.
From the literature, we observe that the admission decision is ignored in early papers or often in papers that focus on multiple terminals. When the admission decision is considered in a multi-terminal system, either the interaction of terminals is weakened by assumptions (e.g., it is possible to hold the vehicle only at one terminal), or the system may have a sufficient number of vehicles so that the terminal interaction is weak and reasonably good decisions can be made based on the local information of a terminal. In this paper we would like to pinpoint the interaction among customers, terminals, and vehicles. We work with a single-vehicle, two-terminal system in which customers can be rejected and the vehicle can be held at any terminal. To make it realistic, the admission decision also depends on the location of the vehicle, a feature also missed in the literature. For this problem, we fully characterize the optimal admission and dispatching policy that maximizes the total discounted profit of the whole system. We show that the optimal policy is of the threshold type, and we relate the optimal decision at one terminal with the status of the other terminal and with the location of the vehicle. Such results would provide us insights for more complex systems, such as one-hub-multi-spoke systems, where terminals significantly interact with each other.
The rest of this paper is organized as follows. We formulate the problem as a Markov decision process in Section 2. To find the structural property of the optimal policy, we define a finite horizon problem in Section 3. We show that both the admission and the dispatching control policies are...
NOTE: All illustrations and photos
have been removed from this article.
More articles from IIE Transactions
A synthesis of tactical fleet planning models for the car rental indus..., September 01, 2003
Generalized Linear Models With Applications in Engineering and the Sci..., September 01, 2003
Building and Solving Mathematical Programming Models in Engineering an..., September 01, 2003
Operations Research Models and Methods.(Book Review), September 01, 2003
Looking for additional articles?
Search our database of over 3 million articles.
Looking for more in-depth information on this industry?
Search our complete database of Industry & Market reports by text, subject, publication
name or publication date.
About Goliath
Whether you're looking for sales prospects, competitive information, company
analysis or best practices in managing your organization,
Goliath can help you meet your business needs.
Our extensive business information databases empower business
professionals with both the breadth and depth of credible,
authoritative information they need to support their business
goals. Whether it be strategic planning, sales prospecting,
company research or defining management best practices -
Goliath is your leading source for accurate information.
|
