MBTC 2004 Final Report:

Efficient Dispatching in a Terminal City Network

PI: Erhan Kutanoglu, University of Arkansas

Co-PI: G. Don Taylor, University of Louisville

RA: Darsono Tjokroamidjojo

Abstract:

In this project report, we describe new optimization and simulation tools to address several problems in transportation, specifically driver dispatching and tour formation in full truckload trucking. In this segment of transportation industry, one of the problems is low driver retention mainly due to the long routes that keep drivers away from home for long time. We address this issue first by extracting a network of high volume cities (called terminal city network) from the existing transportation network. Then, we regularize the tours for the drivers in the terminal network as much as possible using simulation and optimization. Specifically, we develop integer programming models and discrete-event system simulation tools to design and evaluate optimal or near-optimal delivery plans for truckload shipments between terminal cities in a truckload-trucking environment. We examine the problem primarily from a freight carrier’s perspective, with a goal of providing driver tour pattern and domicile information to maximize carrier revenue while meeting shipment demands and driver needs. We provide multiple models which span from long-term aggregate planning problems to short-term driver-specific operational models and show how they can be used in different settings. We also provide realistically sized case studies to demonstrate the efficacy of the approaches using data supplied by J.B. Hunt Transport, Inc.

Keywords: Simulation, Optimization, Truckload Trucking, Distribution

1.0 Introduction

One of the most difficult tasks associated with agile and distributed manufacturing is that of logistics management for material movement activities between various sites. In fact, popular manufacturing strategies such as just-in-time manufacturing and agile manufacturing have driven logistics solutions to being more important and less tolerant of deviation from dispatch and delivery plans. This is especially true in situations where the geographical distances between design sites, raw material and component supply sites, manufacturing sites, distribution centers, and customer locations are of a national or even global scale. Efficient material movement between these sites is key to success and well designed supply chains are likely to play an even larger role in the future success of business entities.

In this report, the authors focus on the development of simulation and optimization methods to examine inter-site distribution alternatives in a dedicated truckload trucking environment, assuming a North American business platform. Solution methods, regardless of the techniques used, must consider two viewpoints. From a customer or shipper perspective, the primary areas of concern are price, delivery (on-time) performance, and service quality (lack of damage). These service needs are intensifying as manufacturing evolves into increasingly global systems and as it evolves into systems that are decreasingly dependent on buffer stock supplies. From a carrier perspective, the key issues are equipment utilization and driver tour length reduction. The highly competitive nature of North American truckload trucking, with its low capital requirements to become an industry participant, requires high equipment utilization, especially following US deregulation legislation in 1980. The improvements to carrier profitability brought about by driver tour length reduction are perhaps the most difficult to explain to persons outside the industry, but it is this key area of concern that motivates the development of the tools described in this paper.

It is difficult to recruit and retain drivers in North America. Schwartz (1992) discusses driver retention and recruiting as a key business strategy for truckload carriers. Carriers that are successful in recruiting and keeping drivers will likely emerge as industry leaders. The excessive tour lengths inherent to traditional truckload dispatching methodologies are a primary reason for losing drivers. Mele (1989a, b) provides statistics that support this premise. He states that annual turnover rates among truckload carriers can range from 85% to 110%, while less-than-truckload (LTL) carriers with more regular routes often experience turnover rates on the order of 4.5% for city drivers and 10% for linehaul drivers. If carriers can find ways to regularize and reduce driving routes, they have a better chance to retain drivers than their competitors. In this context, the term ‘regularize’ means to find patterns in seemingly random freight that would enable drivers to repeatedly drive the same short tour day after day or week after week, returning to their domicile (home city) at the end of each tour dispatch. Regularized tours enable the drivers to return home more frequently and with greater certainty, thus contributing to driver satisfaction and retention. Concurrently, regularized tour drivers are able to increase safety on the road because of familiarity with the roads they travel.

There are many ways to regularize driving routes. Several of these alternatives, including the development of hub & spoke networks, the development of regularly scheduled lanes similar to those used in intermodal transit with rail, and the development of regional zones are discussed in Taylor et al. (1999). The remainder of this report examines a new means of driver route regularization that is not represented in the current literature. The techniques used herein represent a compromise between random dispatching and strict regularization. This report examines the use of driver partitions into two sets of drivers; those that operate only within a limited network of high freight density delivery nodes (network drivers), and those that carry remaining freight in a random fashion (random drivers). Network drivers may drive highly regular routes or seemingly random routes, but only within the selected high freight density network. Network drivers, even if traveling randomly within the selected network, would experience reduced tour length based on the limited number of allowable network destinations. Random over-the-road (OTR) drivers would carry remaining non-network freight using traditional dispatching methods and may include sub-contract drivers. This strategy is wholly compatible with the use of dedicated fleets for large shippers, but is also a reasonable strategy for larger carriers who desire to partition their driver capacity into regular and random jobs.

The following sections describe two tools for examining the efficacy of limited network designs as a tour length reduction strategy. The first is simulation based and the other is optimization based. The literature is rich with examples of both types of tools in distribution problems, but no literature has been found directly addressing the problems presented herein. Many authors have addressed the use of optimization in trucking. Crainic and LaPorte (1997) provide an excellent overview of planning models in freight transportation at the strategic, tactical, and operational level. At the strategic level, they discuss location models, network design models, and regional multi-modal planning models. At the tactical level, they discuss service network design and vehicle routing problems. At the operational level, they discuss dynamic modeling to support carrier operations and capacitated routing with uncertainties. Powell (1991) also reviews a fairly wide range of optimization tools developed for trucking with an emphasis on real-time optimization in truckload trucking. Hall and Racer (1995) present methodologies that are somewhat similar to those presented herein in that they examine the use of private fleets. In some cases, their approach considers both transportation and inventory costs. Other authors also develop optimization models that minimize transportation and inventory costs using economic order quantity models and other tools, but no literature has been found dealing with multiple concurrent links of logistics networks. Frantzeskakis and Powell (1990) and Kleywegt and Papastavrou (1998) develop heuristic algorithms based on the formulation of dispatching problems as stochastic programming problems. Other papers of interest include Ronen (1992) who examines dispatching of mixed fleets from a single terminal, Equi et al. (1997) who examine, via Lagrangean decomposition, dispatching from several origins to several destinations within a single work day, and a multitude of papers in LTL trucking including an interesting paper by Crainic and Roy (1992) which addresses regular route building. Another paper of interest is presented by Powell and Carvalho (1997) in which the authors discuss a dynamic multicommodity network flow problem that can be used to solve large problems that are difficult to solve using integer programming. Simulation is also useful in solving large problems. Although the literature is less abundant in presenting simulation solutions in the trucking industry, some strong examples exist, including the previous work of the author of this paper. Much of this is reviewed in detail in Taylor et al. (1999).

Another related area from the literature is that of airline crew scheduling. The crew scheduling problem basically builds minimal cost pairings of flight crews and flights to satisfy constraints associated with labor rules and regulations. To some degree, most published solutions deal with schedule perturbations including weather, traffic, crew and equipment delays. As pointed out by Hoffman and Padberg (1993), the problem is very significant and has consequently been studied almost continually for the past 40 years. They also state that crew costs are exceeded only by fuel costs in the airline industry. As stated in Vance et al. (1997), the problem has traditionally been modeled as a set partitioning problem. Even so, many solution alternatives exist in the published literature involving both traditional and non-traditional approaches. For interesting examples of the state-of-the-art featuring more or less traditional solution methods, the reader is referred to Graves et al. (1993) and Stojkovic et al. (1998). Graves et al. (1993) present an applications based solution working with United Airlines. Stojkovic et al. (1998) focus on the operational aspects of the crew scheduling problem. Non-traditional approaches to solving the problem include a preferential bidding system by Gamache et al (1998), simulated annealing by Lucic and Teodorovic (1999), and even a decision support system developed by Mathaisel (1996). Effective crew scheduling systems can lead to huge savings, as documented by several authors. Graves et al. (1993) state that their system has led to annual savings of more than $16 million dollars at United Airlines. Similarly, Rushmeier and Kontogiorgis (1997) discuss annual savings of more than $15 million at USAir.

While the airline crew scheduling problem has many similarities to the truckload trucking problem presented herein, there are several key differences. Most notable are differences in freight characteristics. Airlines travel between well defined air hubs. Truckload trucking carriers can be asked to travel from anywhere to anywhere. Airlines can establish specific departure and arrival schedules that are known months in advance. In truckload trucking, load information is often not known until 8 hours or less prior to pick-up. At best, the truckload trucking industry can use aggregate past information for rough stochastic scheduling. Consequently, it is impossible to know with certainty where trucks and drivers will be at a future point. Another difference is that it is possible to make use of small empty asset repositioning moves in trucking that would be cost prohibitive in airline scheduling. Finally, truckload trucking, unlike the airline industry or LTL trucking, cannot partially fill an asset via customer or order aggregation. Therefore, making use of yield management strategies to maximize revenue while adhering to a regular schedule is very difficult in the industry.

The remainder of this report focuses on the development of simulation and optimization approaches for the dispatching problem within a limited network design. Several techniques for regularizing the driving job for network drivers are presented and test results verify the efficacy of the various approaches. J.B. Hunt Transport, Inc. (JBHT) has served as a project sponsor for the tool development activities presented herein and has provided valuable data and information to support the work, especially in the development of the simulation-based tools. As North America’s largest publicly held trucking company (J.B. Hunt 1999), their participation serves to validate the topics as viable and necessary tools for the truckload trucking industry.

2.0 Case Study Setting

All solution approaches in this report will be presented in a case study setting to demonstrate the efficacy and practical use of the tools in solving pertinent problems of continental scale. The case study setting involves North American freight movements for JBHT during a one-quarter year time period in 1998. Although the freight density data supplied by JBHT is historical, the data provide the best indicator available in predicting future aggregate freight density in a particular lane, where a lane is defined as a city-to-city pairing.

The driver partitioning system takes advantage of a partial delivery network composed of 11 high freight density terminal cities within the JBHT terminal city network. Network drivers are partitioned to include terminal city drivers with domiciles in these 11 network cities and with permissible freight origins and destinations only in these network cities. The remaining drivers handle random OTR freight outside the terminal city network. The focus of this report is on the network drivers only.

The terminal city network and freight lanes used in the study are indicated in figure 1. Table 1 provides aggregate freight information in the form of expected freight volume and lane mileage for each lane.

Table 1. Lane Data for Case Study

From City	To City	Volume	Miles	From City	To City	Volume	Miles
(A) Atlanta, GA	(B) Louisville, KY	72	436	(F) Little Rock, AR	(E) Kan. City, MO	62	470
(A) Atlanta, GA	(E) Kan. City, MO	59	862	(F) Little Rock, AR	(J) Dallas, TX	1082	341
(A) Atlanta, GA	(F) Little Rock, AR	307	538	(F) Little Rock, AR	(K) Houston, TX	417	481
(A) Atlanta, GA	(I) Okla. City, OK	47	869	(G) Memphis, TN	(K) Houston, TX	34	575
(A) Atlanta, GA	(J) Dallas, TX	249	804	(H) Lowell, AR	(D) Chicago, IL	148	610
(A) Atlanta, GA	(K) Houston, TX	89	814	(H) Lowell, AR	(E) Kan. City, MO	151	289
(B) Louisville, KY	(A) Atlanta, GA	109	436	(H) Lowell, AR	(J) Dallas, TX	142	328
(B) Louisville, KY	(C) Detroit, MI	218	355	(I) Okla. City, OK	(A) Atlanta, GA	61	869
(B) Louisville, KY	(D) Chicago, IL	212	324	(I) Okla. City, OK	(J) Dallas, TX	40	233
(B) Louisville, KY	(F) Little Rock, AR	23	513	(I) Okla. City, OK	(K) Houston, TX	62	476
(C) Detroit, MI	(B) Louisville, KY	220	355	(J) Dallas, TX	(A) Atlanta, GA	341	804
(C) Detroit, MI	(D) Chicago, IL	260	265	(J) Dallas, TX	(D) Chicago, IL	74	899
(D) Chicago, IL	(B) Louisville, KY	248	324	(J) Dallas, TX	(F) Little Rock, AR	1127	341
(D) Chicago, IL	(C) Detroit, MI	262	265	(J) Dallas, TX	(H) Lowell, AR	278	328
(D) Chicago, IL	(H) Lowell, AR	90	610	(J) Dallas, TX	(I) Okla. City, OK	93	233
(D) Chicago, IL	(J) Dallas, TX	94	899	(J) Dallas, TX	(K) Houston, TX	396	258
(E) Kan. City, MO	(A) Atlanta, GA	59	862	(K) Houston, TX	(A) Atlanta, GA	132	814
(E) Kan. City, MO	(F) Little Rock, AR	140	470	(K) Houston, TX	(F) Little Rock, AR	107	481
(E) Kan. City, MO	(H) Lowell, AR	73	289	(K) Houston, TX	(G) Memphis, TN	34	575
(F) Little Rock, AR	(A) Atlanta, GA	121	538	(K) Houston, TX	(I) Okla. City, OK	23	476
(F) Little Rock, AR	(B) Louisville, KY	22	513	(K) Houston, TX	(J) Dallas, TX	702	258

Figure 1. Case Study Network

3.0 Simulation tools

Simulation methods are non-optimizing by nature, but often provide excellent results for problems of practical size. Although the optimization methods presented below are appropriate for use in relatively large problems, they are somewhat restricted by the assumptions that make the problem tractable. For example, some of the data requirements for optimization include inputs that could arguably be reasonable model outputs. Specifically, the optimization formulation (for some applications) requires that we know the number of drivers and their domiciles. The simulation methods presented in this section are not restricted in this way. They are designed to assist in the determination of the number of required drivers and their domiciles for various dispatching methodologies. Using the simulation model, the user is able to quickly iterate to a good (but not optimal) solution to the driver fleet size and domicile determination problems.

3.1 Simulation model development

The simulation model is written in the SIMNET II simulation language (Taha 1988) and has been developed in a highly modular fashion that should be easily transportable into other languages. Consider the flowchart in figure 2. Model input includes the load availability table, tour length rules, network configuration and mileage tables, and dispatching rules. Also, the model requires initial inputs regarding the maximum number of allowable tour starts permitted during the planning horizon (one-quarter year in this report) from each domicile. Tour start inputs are the primary user input to the model. The simulation uses the allowable tour start inputs to source entities into the model at each proposed domicile. The entities represent drivers

Figure 2. Simulation Flowchart

(with their trucks) starting new tours. These entities are immediately sent to a modular section of code to dispatch the driver entities to network destinations.

It is the dispatching code that makes the simulation truly modular. The model architecture permits easy ‘what-if’ analysis. All network configuration and mileage information supporting the dispatch function is table-driven, so that network configuration issues can be addressed without modifying source code. Similarly, load availability information is table-driven. Load availability information can be input for all available loads or for all ‘balanced’ available loads, where 'balance' is defined as a network in which the total loads into each node is equal to the total loads out of each node. Beginning with a balanced network increases the probability of being able to create regular driving routes for drivers that begin and end at the driver's domicile, without the need to return empty to the domicile at the end of a tour. A balanced network is found by using the following simple node balance formulation:

Maximize: L_m (Z_m) (1)

Subject to:

L_m A_m ,m (2)

L_m - L_m = 0 (3