A computer-based decision support system for truck dispatching.

Yang, Jiaqin ; Lee, Huei

INTRODUCTION

The trucking industry provides the essential service--transportation for all commodity shipments. It is estimated that in general over 50% businesses depend on trucking for delivery of their goods. Therefore, the trucking industry has been viewed as "the lifeblood of the economic structure and the linchpin of the industrial network". For example, it was reported that in 1991, 1.2 million tractors and 3.6 million full or semi trailers conveyed about 2.7 billion tons of goods between US cities at a cost of $167 billion and local truck deliveries cost another $110 billion (Transportation in America, 1993). For many states, the trucking companies offer one of largest state income revenues and more than 10% of employment opportunities (North Dakota Motor, 1995). Since switching between companies is quite easy for customers, intensified competition has squeezed the industry margins so tight that to remain profitable, the company must maintain as a low cost producer. With a continuing increase in operating costs (due to inflated diesel fuel taxes, multiple state registration fees and sales taxes in the last decade), trucking companies have been responding to low cost competition by cutting capital requirements, upgrading information management, and more important, improving driver productivity.

Truck dispatchers are the company's daily operations managers and the quality of their decisions is vital to the company's success. They are responsible for directing the production of the company's two major investments--its drivers and its trucks. The difficulty of dispatcher's job comes from industry unique problems such as unforeseen demand patterns, tight schedule time tables, unique drivers' requests and emergency situations. Advanced planning is difficult since many customers wait to place their orders, leaving little time to blend the customer into the delivery schedule mix. The growth of JIT (Just-In-Time) production by customers has led to even less time for planning and higher time pressure for trucking company's operations. Additionally, the time frames set by customers regularly overload drivers, as a result, affecting their capacity in the following days. A shortage of quality drivers creates other problems. Dissatisfied with their current company, drivers often quit by leaving their trucks on the side of the road to find employment with another company. Aware of their bargaining power, drivers use it extensively to request time-off, specific work loads, and selected destinations. All those industry unique problems demand high quality driver-to-load dispatching assignments to satisfy drivers' requests as often as possible while meeting customers' delivery requirements. As on-time delivery has become a key factor in differentiating competitors, driver-to-load dispatching is evidently critical for firm's on-time delivery performance.

In the trucking industry, dispatchers perform several important job functions. They are salespeople, operations specialists, trouble shooters, and driver supervisors. As a primary duty, the selling task requires the majority of a dispatcher's time. Whereas standing contracts are the responsibility of management and generally result in outbound loads, it is the dispatcher's responsibility to direct the trucks back to the terminal with a minimum deadhead (i.e., non-revenue travelling) miles. Finding inbound loads along the desired routes accomplishes this goal. These loads (hauling contracts or sales) come from (1) previous customers, (2) load brokers, (3) cold sales calls, and (4) call-in and walk-in customers. The first place to check is previous customers with whom the company has a quality working relationship. Next to be examined are load brokers, or clearing houses, whose purpose is finding transportation for loads. They often handle the arrangements for large volume shippers and receive a percentage of commission for their service. Cold sales calls are a last resort because of their low success ratio. The selection of appropriate drivers for loads requires that the dispatcher has cognitive ability. In assigning return loads, the dispatcher considers driver location, desired trip length, vehicle capacity and other factors like weather or the ability to find a new load at the next drop point. As the number of trucks supervised by a dispatcher increases, the complexity of managing truck delivery operations grows at an increasing rate, especially with the communication gaps between drivers and dispatchers. Communicating with drivers is the last primary duty of a dispatcher. Dispatchers take time-off requests and prepare driver schedules. They communicate load assignments to the drivers and monitor their progress. In addition, dispatchers provide a link between drivers and management to discuss any potential problems.

Advanced information technologies have been used in the trucking industry in recent years (Brown et al., 1987), such as using computer programs in evaluating truck loads, tracking customer orders through satellite, and paperless transaction processing with telecommunication techniques. Most recently, Bausch et al. (1995) describe a computer-assisted system that automatically consolidates and dispatches truck shipments of packaged and bulk lubricant products at Mobil Oil Corporation from 10 lubricant plants nationwide. With the help of this system, the dispatchers have been able to make minimal-cost truck schedules to reduce the company's transportation costs by about $1 million per year. Another example was reported by Sankaran and Ubgade (1994) in which a computer-based decision support system was developed to help a dairy company in constructing vehicle routes and scheduling delivery trucks to pick up milk from 70 milk collection centers within a 150 km distance. An $1 million annual transportation cost savings has been projected from such a system. Most reported computer-based vehicle dispatching systems, however, have been developed for specific non-trucking companies which have their own vehicle fleets and fixed routes and destinations in their unique transportation operations.

For a general trucking company, it has been suggested that a computer-based information system will offer dispatchers the advantage of automatic form completion, instant order tracking, direct communication with vehicles, and an on-line information inquiry. Based upon the information system, a computer-based Decision Support System (DSS) for truck dispatching can be developed to help dispatchers make improved driver-to-load assignments under given constraints with the objective of minimizing total deadhead miles. This is the primary motivation of this research. The proposed DSS will have more advantageous performance for large scaled problems, since such a DSS will be able to examine a much larger number of alternatives under time constraints for possible dispatching suggestions. The dispatchers then have the option to either accept or reject the computer "assignments" based on personal experiences and judgements.

The development of computer-based Decision Support Systems (DSS) for complex decision-making problems has been the focus of both academics and practitioners in last two decades (Alter, 1980; Bodily, 1985; Carter, et al., 1992). The continuing progress in the field of computer simulation and artificial intelligent (AI) further promotes the research of knowledge-based Expert Systems (ES) and Executive Support Systems or Expert Support Systems (ESS) (El-Najdawi & Stylianou, 1993; Rockart & Delong, 1988; Sprague & Watson, 1989; Turban & Watkins, 1986). The detailed discussion on the system framework, interface structure, solution techniques and procedures, and other design issues in the development of DSS can be seen in Badiru, et al. (1993), Courtney, et al. (1987), Sankar, et al. (1995), and Turban (1995).

A DSS FOR TRUCK DISPATCHING

<TransDispatch Lite> is a Windows based system developed with the popular Visual Basic. <TransDispatch Lite> has several basic working screens dedicated to its database and decision support functions. The mouse navigates the dispatcher through a graphically driven interface. Windows provides easy to use and esthetically pleasing screens. The system consists of two basic working units--Database Module and Decision Support Unit--both are briefly described below.

Database Module

The database module provides near instant access to information using a variety of search criteria. <TransDispatch Lite> is automatically copying information to all applicable areas so as eliminating duplicate data entry. The module manages the information through three databases: Geographic Data, Customer Data, and Driver Data. Upon receiving hauling contracts, the dispatcher enters all applicable load information including addresses, rates, dates, billing and cargo information. Time-off requests and current locations complete driver information as the dispatcher receives them. The program allows editing of both driver and customer data at any time, often from different screens. The geographic database contains latitude and longitude data along with postal codes for all U.S. towns and cities. The five basic working screens for the database module are described below.

Orders Screen--Upon taking an order from a customer, the dispatcher enters the information on the Orders Screen. The three data frames that comprise the Orders Screen follow the logical progression of a sales call. The procedure begins with the information concerning the load's source including the company, street address, zip code, contact person or department, and telephone number. Input of the zip code triggers the program to complete the city and state blanks with data retrieved from the geographic database. At the same time, the program loads the source latitude and longitude into memory for later use. Next, the dispatcher enters the destination data that call a routine to calculate the length of the trip in miles.

After the check for a source zip code, the program starts its search for zip code data, retrieving four items from the geographic database: city, state, longitude, and latitude. Although extensive at over 36,000 entries, the current geographic database is not complete and if any of the four items is missing, the program prompts the dispatcher to provide the zip code of a neighboring town. The next step converts latitude and longitude from a minutes/degrees/seconds format to a decimal format so that the Pythagorean Theorem can then be used to calculate the distance between points. Preparing a customer quotation at a later time will use this information. <TransDispatch Lite> enters the load mileage and prepares a quotation based on rates and premiums or discounts set by the dispatcher. If the customer agrees to the quotation, copying the source address, or destination address to the billing frame or entering a new address completes this frame. Load information is the next frame including dates, weights, times, and cargo. The noteworthy feature of this frame is its ability to store more than one pick-up or drop date for a load. Separate databases for pick-up and drop dates store the date selections made from a three-month list. Opening the load information frame runs a routine to construct the pick-up date and drop date lists. It is possible to select any number of dates, but at least one is necessary for the system to consider this load.

Schedule Screen--Truck driving is a job of varying hours with a workweek as unpredictable as the wind. Because of the dynamic scheduling environment, the system provides an interface dedicated to organize driver scheduling. This screen (also titled as Driver Availability Screen) uses lists to give the dispatcher point and click access to drivers and dates. Opening this screen automatically populates the driver list. Selecting a driver makes the program in search of driver's time-off requests, displaying the results by highlighting dates in the date list. For larger companies which may have a very long list of driver's names, the system provides a handy text searching option.

Assign Screen--After setting the drivers' schedules and entering the available loads into the database, the dispatcher now may choose the option to make manual driver-to-load assignments. The Assign Screen provides side-by-side access to both schedule and load information so as to make the process faster and easier. In addition, this screen also reports the driver's current position and a list of loads assigned to the driver. With the mouse, the dispatcher scrolls through unassigned loads selecting those requiring more information. After viewing the available information, the dispatcher can assign a load to a driver by double clicking its table entry. The table then removes this load and places it in a list showing all the assigned loads for that driver.

Reports Screen--This screen is an interface used to aggregate and display information of various types. The screen displays assignments by drivers, unassigned loads, and tentative deadhead miles. The Deadhead report is a useful piece of information that the dispatcher can use to fill gaps in a driver's route. For example, if a route has a driver unload in city A and reload in city B, the trip from A to B produces no revenue. The Deadhead report alerts the dispatcher to this who can then take steps to find an A-to-B load to eliminate, or at least, reduce the non-revenue miles traveled. In the report, the number of deadhead miles provides a flag so the dispatcher can easily identify which gaps have priority consideration in filling. In addition, identifying these deadhead miles earlier makes it more likely that the dispatcher will be able to find a load to replace the non-revenue miles. To construct the Deadhead report, the system finds all loads assigned to a driver and sorts them by their pick-up dates through retrieving all of a driver's loads from the database and placing them into a sorting list box. The list box then sorts the list items automatically by placing the load with the earliest pick-up date as the first list item, and the next earliest date the second list item. The distances between loads are then calculated using the information of the destinations and sources read from the sorted list box. After the system formats deadhead miles, dates and times, and locations, the report is ready for use by the dispatcher.

Forms Screen--This screen is the last working screen of the database module, and is designed as the interface that prints company documents. The document's layout can be customized according to the needs of each customer.

Decision Support Unit

Various route scheduling and vehicle dispatching heuristics have long been reported in the literature, such as; Gillett and Miller (1974), Mole and Jameson (1976), Golden et al. (1977), and Bodin et al. (1983). Most of these heuristics have been, however, developed for non-trucking companies which have their own vehicle fleets and fixed routes and destinations in their unique transportation operations. That is, these heuristics have a limited applicability in the truck dispatching for a commercial trucking company which has dynamic and complex vehicle routings and destinations.

The Decision Support Unit of the proposed DSS is designed to aid the dispatcher in making driver-to-load assignments. Using available heuristics, the system makes suggestions according to the given constraints.

Selecting a driver and a load date starts the solution process. First, the system examines the driver's work schedule to determine the number of days available for the trip. Subtracting the current date from the next requested time-off accomplishes this step. Next, the program reads the driver's current position and places it into memory. With this as a reference, the procedure searches all available loads for those with pick-up dates matching the current date. The load with the closest pick-up point becomes the load of choice. Before assigning this load to the driver, it must satisfy three rules:

Rule 1: Is the length of the trip (in days) shorter than the driver's available time?

Rule 2: From the driver's home, is the trip's destination within 500 miles times the number of days remaining in the trip?

Rule 3: Is the pick-up point within 150 miles of the driver's current position?

If any of the three rules is unsatisfied, the system does not assign the load. Violating Rule 1 prohibits assignment since the load's time requirement is greater than the available time. Not meeting Rule 2 makes getting the driver home for next day off too difficult. Finally by Rule 3, with the pick-up point greater than 150 miles away, it is economical to let the truck sit for a day and check the next day's loads for a better match. If the next day does not provide a load within 50 miles, Rule 3 is relaxed and the load may be assigned.

Violating Rule 1 or Rule 2 makes a match impossible. In search of a match, the system checks loads with progressively farther pick-up points. Without finding a match, the process is terminated and the dispatcher needs to manually find an appropriate load. Assigning a load reduces the driver's available trip time by the time length of the assigned load. If time remains in the driver's trip, the current date becomes the assigned load's drop date and the process repeats. The solution process flowchart is depicted in Figure 1. The explanation for the Decision Support Unit working screen--the Auto Screen, is discussed below.

Auto Screen--In this screen, different solution heuristics are first incorporated and evaluated by a predetermined set of criteria, and then adopted and selected to make driver-to-load assignments under the objective of minimizing total deadhead (i.e. non-revenue) miles. The solution process begins by selecting a date for the initial assignment. This date tells the system which loads to use in making an initial assignment and with only loads whose pick-up date matches the selected date being considered. The dispatcher then picks a driver for load assignment. Calculating the driver's available trip time is followed. The system finds the driver's record in the driver availability database and subtracts today's date from the driver's next requested vacation day. This results in a trip length in days that controls the number of loads assigned to a driver.

Each load assigned to a driver reduces the trip time by the time length of the load. The search terminates when assigned loads consume all of the driver's trip time or when no appropriate load is available. Subroutine programs are coded based on the corresponding solution heuristics to find loads suitable for assignment. In the heuristics, the starting reference is the driver's current position. Subsequent search steps use the destination of the previously assigned load as the starting reference. If the load proposed by the heuristic is greater than 150 miles away, the system will search the next day. Finding an alternative load that is at least 100 miles closer replaces the previous load and then making the alternative load as the current load. Assigning the current load then will reduce the driver's remaining trip time by the load's time requirement. The process will repeat until load assignments consume all of the driver's trip time or no appropriate load is available. Otherwise the search terminates and the selected driver's assignment process is ended.

[FIGURE 1 OMITTED]

With the driver's current position or the position of the driver's last drop point as a starting reference, the solution heuristic will search for the load with the closest pick-up location. To select a current load, the heuristic will search through the available loads to find the best match. The first step is to check if a match exists between the load's pick-up date and the current date for assignment. If the load is already assigned or if the dates do not match, then advances to the next load and repeats the process. When a match is made, the system reads the load's source location and calculates its distance from the driver's current position. The first iteration forces the selection of a current load if its distance is less than a preset bookmark-distance initialization. If a load's distance is less than the bookmark-distance, the current load lowers the benchmark by setting bookmark-distance equal to the current load. Two subroutines are designed to find the time required to pick-up and deliver a load and to determine the distance from the destination of the proposed load to the location designated as home.

As a driver's trip time expires, load assignments should bring the driver closer to home. The solution heuristics are thus designed to never assign a load with a destination farther than 500 miles per remaining trip day away from home. In addition, before adding a load, the heuristic will check to see if the driver can arrive at the source location on time. If the proposed load's pick-up date is the same as the previous load's drop date, a routine runs to examine the time difference between the two. If reaching a source on time by traveling an average of 45 miles per hour is not possible, load assignment does not take place. Satisfying the distance and time requirements makes the current record the new benchmark. Setting pointers to the current load and giving the new record a true value change the benchmark and the current record. The last two bookmarks return the record pointer to the benchmark record, or the record of first choice. The system then returns this record for possible assignment.

TESTING RESULTS

Example problems are used to test the efficiency and effectiveness of the proposed DSS for truck dispatching. For testing purposes, the three primary database--Geographic Database, Customer Database, and Driver Database, are first developed with over 36,000 entries of major U.S. cities and towns in the Geographic Database, 300 customer load requirements in the Customer Database, and 200 drivers' information in the Driver Database. Two experiments are conducted with 128 and 200 customer loads respectively. All example problems are solved by both the proposed DSS and manual procedures. For comparison purposes, two different search heuristics are used to generate solutions for the proposed DSS, and several experienced truck dispatchers from a local trucking company were asked to participated in the manual search procedures--to ensure that the solutions from manual search procedures are the best possible manual solutions. Table 1 summarizes the comparison results. (Note: Detailed lists of 200 customer load examples and their dispatching solutions from the proposed DSS and manual procedure are available upon request.)

As shown in Table 1, the proposed DSS has performed expectedly superior compared to traditional manual solutions. Measured by the Average Distance-To-First-Load, the DSS solutions are only about 25% of manual solutions or less in miles. In terms of the Total Non-Revenue-Miles-Traveled, the proposed DSS solutions are 60% below the manual solutions. Such percentage reductions in average distance to first load assigned and in total non-revenue traveled miles will have significant implications in practice for trucking operations cost reductions. Additionally, the proposed DSS on average only needs about 5% (9:180 or 21:360) of manual solution times to produce much better solutions.

The heuristic of initial load assignment used in the proposed DSS, however, was found not to work well under some specific conditions. Since that heuristic assigns the loads based on a list of available drivers, it can make some potential "bad" initial load assignments. In a case where there are two drivers, A and B, and one work load, Load-1, the heuristic will automatically consider Driver A first, and assign Load-1 to Driver A as an initial assignment because Load-1 is the closest available load to Driver A at the time. When it is time to consider Driver B, Load-1 has been already assigned to Driver A, no longer under the consideration as a unassigned load. It can be a "bad" initial load assignment if the load would have been better carried by Driver B.

Some modifications have been suggested for better and more consistent initial load assignments. One is to use two initial load assignment heuristics, the first will assign customer loads based on the list of available drivers, while the second will assign drivers based on the list of accumulated customer orders over a specified time period. The two assignment lists will be both holding for a while to compare their performance (such as the Average Distance-To-First-Load or Total Non-Revenue-Miles) for the final assignment. Another improvement technique is to add an algorithm similar to the famous multiple traveling salesperson problem. That is, for every two drivers, a multiple traveling salesperson solution routine will examine their assigned routes and make load exchanges between them (a pairwise exchange) if an improvement in performance (such as a reduction in Average Distance-To-First-Load or in Total Non-Revenue-Miles) can be realized. Similarly, a more complex T-interchange algorithm can also be added into the initial load assignment procedure, in which, all initial load assignments will be held by the dispatcher periodically and examined by the T-Interchange algorithm (Yang and Deane, 1993). The T-interchange algorithm will investigate all possible two-way (pairwise), three-way, four-way, or-nway load exchanges among the drivers to identify any potential performance improvements before the final load assignments are made.

SUMMARY AND SUGGESTIONS

Trucking transportation is a cut throat industry today where the competition is intensified and focused on cost reductions. In addition to other cost reduction measures, improving the efficiency and effectiveness of truck dispatching has attracted the attention of industrial practitioners in recent years. New technology advancement in computer science and management science has helped the trucking industry to replace their traditional paper-based transaction processing systems with advanced computer-based management information systems for fast paperless transaction processing, on-line instant information inquiry, and direct information sharing and communications between drivers and dispatchers. This paper presents a truck dispatching decision support system which further incorporates a database module (e.g., an MIS unit) with a decision support unit to help the dispatcher to make better (if not "optimal" in a mathematical sense) driver-to-load assignments under given constraints with the objective of minimizing total deadhead (i.e., non-revenue) miles while satisfying drivers' specific requests. It is believed that such a DSS will assist the trucking company to reduce its operating cost considerably in practice.

The testing results from the example data in this research have demonstrated that significant improvements in solution efficiency and effectiveness could be achieved by the proposed DSS for driver-to-load dispatching assignments. The Windows based system is also shown that it is easy to use, esthetically pleasing, and flexible to allow it for future expansion as the user's needs grow.

There are several suggestions to improve the performance of the <TransDispatch Lite> system. One is to improve the quality of initial load assignments by adding new assigning heuristics, such as: a multiple traveling salesperson solution routine, or a pairwise exchange algorithm procedure. Another is to provide a graphical interface for the dispatcher to display a map that highlights the related times, routes, and current locations of drivers and loads. The dispatchers will thus have a visual reference to assist them in making necessary adjustments.

Before the <TransDispatch Lite> system becomes a commercial quality program, some modifications and improvements will be made accordingly. As the current focus of academic research for trucking industry is on fixed route scheduling, the development of computer-based DSS to deal with more practical but also more complex and dynamic driver-to-load dispatching problems definitely represents a significant opportunity for future research.

REFERENCES

Alter, S.L. (1980). Decision Support System, Current Practice and Continuing Challenges. Readings, Mass.: Addison-Wesley Publishing.

Badiru, A.B., Pulat, P.S., and Kang, M. (1993). Decision Support System for Hierarchical Dynamic Decision Making. Decision Support Systems, 10(1), pp. 1-18.

Bausch, D.O., Brown, G.G., and Ronen, D. (1995). Consolidating and Dispatching Truck Shipments of Mobil Heavy Petroleum Products. Interfaces, 25(2), pp. 1-17.

Bodily, S.E. (1985). Modern Decision Making: A Guide to Modeling with Decision Support Systems. New York: McGraw-Hill.

Bodin, L., Golden, B., Assad, A., and Ball, M. (1983). Routing and Scheduling of Vehicles and Crews--The State of the Art. Computers and Operations Research, 10(2), pp. 63-212.

Brown, G.G., Ellis, C.J., Graves, G.W., and Ronen, D. (1987). Real-Time, Wide Area Dispatch Mobil Tank Trucks. Interfaces, 17(1), pp. 107-120.

Courtney, J.F., Paradice, D.B., and Mohammed, N.H. (1987). A Knowledge-Based DSS for Managerial Problem Diagnosis. Decision Sciences, 18(3), pp. 373-399.

Carter, C.M., and et al. (1992). Building Organizational Decision Support Systems. Boston: Academic Press.

El-Najdawi, M.K., and Stylianou, A.C. (1993). Expert Support Systems: An Integration of Decision Support Systems, Expert Systems, and Other AI Technologies. Communications of the ACM, 36(12), pp. 55-65.

Gillett, B.E., and Miller, L.R. (1974). A Heuristic Algorithm for the Vehicle-Dispatch Problem. Operations Research, 22(2), pp. 340-349.

Golden, B., Magnanti, T.L., and Nguyen, H. (1977). Implementing Vehicle Routing Algorithms. Networks, 7(2), pp. 113-148.

Mole, R.H., and Jameson, S.H. (1976). A Sequential Route Building Algorithm Employing A Generalised Savings Criterion. Operational Research Quarterly, 27(2), pp. 503-511.

North Dakota Motor Carriers Association & Western Highway Institute (1995). Joint Annual Report. Bismarck, North Dakota.

Rockart, J.F., and Delong, D.W. (1988). Executive Support Systems. Homewood, Ill.: Dow Jones-Irwin.

Sankar, C.S., Ford, F.N., and Bauer, M. (1995). A DSS User Interface Model to Provide Consistency and Adaptability. Decision Support Systems, 13(1), pp. 93-104.

Sankaran, J.K., and Ubgade, R.R. (1994). Routing Tankers for Dairy Milk Pickup. Interfaces, 24(5), pp. 59-66.

Sprague, R.H., and Watson, H.J. eds. (1989). Decision Support System: Putting Theory into Practice, 2nd ed., Englewood Cliffs, N.J.: Prentice-Hall.

Transportation in America (1993). Eno Transportation Foundation, Landsdowne, Virginia.

Turban, E., and Watkins, P.R. (1986). Integrating Expert Systems and Decision Support Systems. MIS Quarterly, June, pp. 121-136.

Turban, E. (1995). Decision Support and Expert Systems, 4th ed., Englewood Cliffs, N.J.: Prentice-Hall.

Yang, J., and Deane, R.H. (1993). An Appellate Court Case Assignment Algorithm. Decision Sciences, 24(3), pp. 509-528.

Jiaqin Yang, Georgia College & State University

Huei Lee, Eastern Michigan University

Table 1
Comparison between DSS and Manual Solutions

Problem Set Performance Criteria DSS Manual
 Solutions Solutions

128 Load Set Average Distance-To-First-Load 70 280
 (miles)
 Total Non-Revenue-Miles-Traveled 3,800 10,200
 (miles)
 Total Solution Time (minutes) 9 180

200 Load Set Average Distance-To-First-Load 63 284
 (miles)
 Total Non-Revenue-Miles-Traveled 5,700 15,000
 (miles)
 Total Solution Time (minutes) 21 360