MBTC 2004 Final Report:
Efficient Dispatching in a
PI: Erhan
Kutanoglu,
Co-PI: G. Don
Taylor,
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
It is difficult to recruit and retain drivers in
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
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) |
(B) Louisville, KY |
72 |
436 |
(F) |
(E) |
62 |
470 |
|
(A) |
(E) |
59 |
862 |
(F) |
(J) |
1082 |
341 |
|
(A) |
(F) |
307 |
538 |
(F) |
(K) |
417 |
481 |
|
(A) |
(I) |
47 |
869 |
(G) |
(K) |
34 |
575 |
|
(A) |
(J) |
249 |
804 |
(H) |
(D) |
148 |
610 |
|
(K) |
89 |
814 |
(H) |
(E) |
151 |
289 |
|
|
(B) Louisville, KY |
(A) |
109 |
436 |
(H) |
(J) |
142 |
328 |
|
(B) Louisville, KY |
(C) Detroit, MI |
218 |
355 |
(I) |
(A) |
61 |
869 |
|
(B) Louisville, KY |
(D) |
212 |
324 |
(I) |
(J) |
40 |
233 |
|
(B) Louisville, KY |
(F) |
23 |
513 |
(I) |
(K) |
62 |
476 |
|
(C) Detroit, MI |
(B) Louisville, KY |
220 |
355 |
(J) |
(A) |
341 |
804 |
|
(C) Detroit, MI |
(D) |
260 |
265 |
(J) |
(D) |
74 |
899 |
|
(D) |
(B) Louisville, KY |
248 |
324 |
(F) |
1127 |
341 |
|
|
(D) |
(C) Detroit, MI |
262 |
265 |
(J) |
(H) |
278 |
328 |
|
(D) |
(H) |
90 |
610 |
(J) |
(I) |
93 |
233 |
|
(D) |
(J) |
94 |
899 |
(J) |
(K) |
396 |
258 |
|
(E) |
(A) |
59 |
862 |
(A) |
132 |
814 |
|
|
(E) |
(F) |
140 |
470 |
(K) |
(F) |
107 |
481 |
|
(E) |
(H) |
73 |
289 |
(K) |
(G) |
34 |
575 |
|
(F) |
(A) |
121 |
538 |
(K) |
(I) |
23 |
476 |
|
(F) |
(B) Louisville, KY |
22 |
513 |
(K) |
(J) |
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 (Zm) (1)
Subject to:
Lm 
A
m 
,m
(2)
Lm - 
Lm = 0 (3)
Lm = Integer ,m (4)
Where:
L
m = Number
of loads to move from cityto city m.
Z m = Miles
(or revenue-costs) from city to city m.
Am = Maximum
allowable moves from city to city m (from the 'volume' column in Table 1.
The objective function in equation 1 seeks to make use of the maximum
number of loaded miles. The objective is
constrained by load availability for all freight lanes (,m in equation 2), and by the need to balance freight flow at
each node (equation 3) at an aggregate level, i.e., the number of moves out of
each node must equal the number of moves into each node. Note in equation (3) that Lm represents
loads from to m and that Lm represents loads from m to . Equation (3) is
repeated for all values of . Equation 4 ensures
the integrality of Lm values.
The examination of alternative tour length and dispatching rules require minor changes to the source code, but in well-defined modular locations with pre-defined information transfer protocols to ensure that alternative methods are easily tested. The dispatching systems used can range from very sophisticated to very simple or even random.
After the simulated completion of a dispatch, the simulation entity representing the driver and his or her truck is sent back to the dispatcher for the next driving assignment. Each dispatching assignment is made based on node specific discrete probability density functions driven by historical freight availability. Upon return to the individual driver domicile, tour statistics are collected. After completion of the final tour, network statistics are collected and the simulation is stopped. Using simulation iterations featuring varied tour start profiles, it is a simple matter to quickly converge to near-optimal solutions to the driver domicile problem.
Simulation outputs include driver tour lengths by domicile and the overall weighted driver tour length for all drivers and all domiciles. It also calculates a final value for the number of drivers required (by domicile) and provides an overall number of required drivers in the total network (for network drivers only). Because some dispatching systems being simulated (i.e. random dispatching) would not necessarily require node balance or full compliance with load requirement profiles, additional system level metrics are collected to determine node balance and lane coverage in comparison with load requirements. Node balance is achieved when the observed departures from a node (terminal city) are equal to the desired departures from the node. Desired departures are an input to the simulation while observed values are simulation output. A positive node balance indicates that observed departures exceed actual requirements. A negative node balance indicates that actual requirements exceed observed departures. Similarly, lane balance is achieved when the observed lane volume is equal to the desired lane volume, where a lane is defined as a node-to-node (terminal city to terminal city) driving route.
In summary, the simulation requires initial estimates of driver tour starts by domicile and outputs performance information in terms of driver requirements and tour lengths in both summary and detailed formats for a given dispatching method. It also provides node balance and lane coverage information for various dispatching rules. The simulationist can iterate with the tool by varying tour start profiles to find near-optimal solutions for driver fleet size and domicile determination problems.
3.2 Case studies and model validation
In this section, the authors demonstrate the efficacy of use of the simulation model using the case study information supplied by JBHT and described in section 2.0 above. Additional validation for both the simulation and optimization approaches is offered in section 5.0 via comparison with solutions from state-of-the-art proprietary tools at JBHT.
The case study involves a network composed of 11 cities within the JBHT terminal-city network. The city nodes are not fully connected to all other city nodes via direct arcs (see figure 1) and no pre-conceived notions exist regarding the number of drivers to domicile at each city in support of the inter-city moves. First, the use of the model for domicile determination will be demonstrated. Subsequently, the use of the model to examine alternative dispatching methodologies will be presented.
The use of the simulation model as a means of determining driver fleet size and driver domiciles is demonstrated using a totally random dispatching method. Upon arrival at a system node, drivers are routed to a next city location totally randomly with the exceptions that only connected nodes can be used and that the probability of moving along a specific arc is driven by the long-term freight density profiles provided in table 1.
Initially, the simulation is used to iterate to a driver tour start
profile that balances system nodes and covers the required inter-city moves for
a one-quarter year planning period. This
tour start profile is presented in table 2 under the heading of ‘driver
scenario 1’. Note that 1200 tour starts
are permitted. The tour starts are
limited to 5 domiciles in scenario 1.
This scenario recommends 81.01 drivers on duty at any given time to
support inter-city deliveries. The
drivers have an average tour length of 6.08 days with a maximum tour length of
12.35 days for drivers domiciled at
Table 2. Sample Simulation Output for Domicile Planning
|
|
City |
Driver Scenario 1 |
Driver Scenario 2 |
|
Allowable |
Atlanta |
230 |
220 |
|
Tour |
Louisville |
0 |
10 |
|
Starts |
|
0 |
10 |
|
By |
|
150 |
140 |
|
City |
|
0 |
10 |
|
|
|
290 |
280 |
|
|
|
0 |
10 |
|
|
|
0 |
10 |
|
|
|
0 |
10 |
|
|
|
400 |
380 |
|
|
|
130 |
120 |
|
Total Tour Starts |
1200 |
1200 |
|
|
Avg. Tour Length (Days) |
6.08 days |
8.35 days |
|
|
Max Tour Length |
12.35 days at |
227.38 days at |
|
|
Total Drivers Required |
81.01 |
111.34 |
|
|
Weighted Node Balance |
7.09 |
293.18 |
|
|
Weighted Lane Balance |
0.64 |
26.65 |
|
Driver scenario 2 in table 2 indicates a slightly different driver
domicile plan with permissible tour starts in all 11 terminal cities involved
in the study. Note that the overall
number of tour starts remains the same at 1200, and that the dispersion of tour
starts has changed only slightly. This
scenario demonstrates the efficacy of the simulation system in determining the
effects of seemingly small changes to domicile planning. Again assuming random dispatching upon
arrival at a city, the drivers now take an average of 8.35 days to return to
their point of origin (their domicile).
At worst case (
In both cases, the simulation is replicated 10 times and generally results in tight confidence intervals. The results of driver scenario 1 are therefore statistically significantly different from driver scenario 2 for all metrics.
The model can also be used to evaluate the effects of various dispatching methods. Table 3 summarizes the results of using three different dispatching methodologies, ranging from totally random to very restrictive dispatching rules. The first dispatching method is the random dispatch described above. The second makes use of random dispatching also, but with forced returns based on certain conditions. The conditions for these simulation runs are that a maximum of four dispatches or 2,500 miles per tour is allowed. After three dispatches or 2,000 miles, the driver must return to his or her domicile even if the resulting dispatch leads to an empty move. This type of forced return system would be essential in practical use even though the forced returns leads to significant increases in the required number of on duty drivers. The third dispatching system is even more restrictive. It permits drivers to travel only one city (one dispatch) from their domicile with forced returns to the domicile on the very next dispatch.
Table 3. Simulation Output for Various Dispatching Methods
|
|
City Number |
Random Dispatch |
Forced Returns |
One-City Dispatch |
|
Allowable |
|
230 |
531 |
412 |
|
Tour |
Louisville |
0 |
0 |
281 |
|
Starts |
|
0 |
0 |
240 |
|
By |
|
150 |
347 |
347 |
|
City |
|
0 |
0 |
136 |
|
|
|
290 |
670 |
852 |
|
|
|
0 |
0 |
16 |
|
|
|
0 |
0 |
221 |
|
|
|
0 |
0 |
82 |
|
|
|
400 |
924 |
1155 |
|
|
|
130 |
300 |
499 |
|
Total Tour Starts |
1200 |
2772 |
4241 |
|
|
Avg. Tour Length (Days) |
6.08 days |
2.89 days |
1.69 days |
|
|
Max Tour Length |
12.35 days at |
3.97 days at |
2.70 days at |
|
|
Total Drivers Required |
81.01 |
88.96 |
79.83 |
|
|
Weighted Node Balance |
7.09 |
17.36 |
0.18 |
|
|
Weighted Lane Balance |
0.64 |
1.58 |
0.02 |
|
The domicile plans for the three dispatching methods are different as well. The domiciles for the forced returns dispatching method differ from random dispatching domiciles primarily in scale. The forced returns create the need for more tour starts at each domicile. A total of 2,772 tour starts are required in the forced returns model compared to only 1,200 for the random dispatching model. The one-city dispatching rules, on the other hand, lead to the need for driver domiciles at each city in the network instead of only at five cities. The one-city dispatching method requires a total of 4,241 tour starts.
It should be noted that the only stochastic element in the simulation is the use of multiple replications of repeated sampling from discrete probability density functions for dispatching purposes. Therefore, the simulation model could also be implemented using dispatching heuristics with almost any general purpose software.
4.0 Optimization methods
As discussed in the literature review, a number of optimization approaches exist for a broad array of problem formulations in truckload trucking and dispatching. In this section, the authors formulate an integer programming (IP) model to optimize material movements between the various supply chain locations in limited networks. The IP model presented in this section produces optimal results for the dispatching problem relative to the stated objective function, but the computational complexity is increased and the operational efficacy is decreased relative to the simple rule based dispatching systems used in the simulation models. This section introduces the IP formulation used, demonstrates its feasibility for solving realistically sized planning and operations problems using the JBHT case data, and briefly discusses problem complexity and constraint management issues. In addition to the notation presented earlier to describe equations 1-4, the following notation is used to describe the IP model:
X j km = The
number of times during the planning horizon that some driver domiciled at city
j makes their kth move from city to city m in a loaded
status.
Y j km = The
number of times during the planning horizon that some driver domiciled at city
j makes his or her kth move from city to city m in an unloaded status.
Tmax = Maximum allowable tour length (or distance).
4.1 Model formulation
The IP model supports driver tour development in a seemingly random dispatch environment within a limited delivery network. It is suitable for building tours for a dedicated trucking fleet within a supply chain for a large company or companies, or for a truckload carrier operating within some limited network (i.e. between cities with existing terminals or between large customers and intermodal ramps, etc.). The formulation follows below:
Maximize: 
X j k m (Zm) - Y j k m (Zm) (5)
Subject to:
X j k m Am ,m (6)
X j k m + Yj k m = 0 j,k=1 (7)
X j k m + Y j k m - X j (k+1) m
-Y j (k+1) m =0 j,k<K,mj (8)
X j k m + Yj k m = 0 j,k=K (9)
X j k m (Zm) + 
Y j k m (Zm) Tmax j (10)
X j k m =
Integer j,k, ,m (11)
Y j k m =
Integer j,k, ,m (12)
The objective function in equation (5) maximizes the loaded miles minus
empty miles, which is directly proportional to profit (carriers are normally
not paid for empty repositioning moves).
Actually Zm values can take on profit (revenue minus cost)
values for a slightly different objective function that would penalize empty
moves more heavily. In this report, we
assume that Zm holds mileage values for city-to-city pairs to
facilitate direct comparison with other tools that attempt to maximize the
miles used in 'regular' tours. This
comparison appears subsequently in this report. The first constraint (equation 6) is an
expression that restricts network flow to known or assumed lane capacity based
on the total number of shipments available during the time period under
consideration. In other words, the
carrier cannot move freight that does not exist but can use empty repositioning
moves once freight on a particular lane is exhausted. Equation 7 ensures that all drivers begin
their tours at their domicile by requiring that the sum of all empty or loaded
moves for the first dispatch is zero when the dispatch is not from the driver
domicile. Equation 8 ensures that all
transshipment nodes (excluding the domicile) in each driver tour maintain a
balance of capacity. Each driver that
enters a node that is not his or her domicile must leave that node on the next
dispatch. Drivers reaching their
domicile prior to the kth dispatch are not required to leave on the
next dispatch but can stay at home. The
next constraint (equation 9) ensures that each driver must return to his or her
domicile prior to the end of the planning period. Actually, the constraint requires that the
sum of moves during the last dispatch is zero at every node except the driver
domicile. Equation 10 is an optional
constraint that ensures that some maximum number of miles restricts driver tour
lengths. This helps to ensure that
drivers return to their domicile according to carrier goals. An alternative means of achieving this goal
is by controlling the number of allowed dispatches per tour through
specification of the upper bound, K, on the driver subscript, k, representing
the dispatch number. Finally, equations
11 and 12 specify that X j k 
m and Y j k m are positive integers.
4.2 Numerical example
To illustrate the optimization model and to demonstrate its efficacy of
use, the same national scale case study used to illustrate the simulation methods
will be used. It should be noted at this
point that the IP model (and the simulation models) can be used in two
distinctly different ways. It can be
used for aggregate planning or for detailed operational dispatching. In this section, the results of an aggregate
planning case example are presented. The
differences between the two applications will be more clearly presented in
section 4.3. For convenience in making
comparisons between the simulation and optimization methods, we have assumed
that we will use the same five driver domiciles that resulted in near-optimal
performance in the random OTR simulation model (
The example problem has been
formulated and solved using the LINDO solver (Schrage 1986) which required less
than 2 seconds on a 750 MHz Pentium PC.
The solution output is shown in table 4.
To aid in understanding the table, consider the first row. Tour A-1 indicates that this is the first
tour in domicile A (
Table 4. Tour Summary From Optimization Solution
|
Domicile |
Tour Number |
Tour Description |
Tour Quantity |
Tour Miles |
Tour Days |
Required
Drivers |
|
(A) |
A-1 |
A-F-K-J-A |
302 |
2081 |
4.16 |
13.97 |
|
|
A-2
|
A-B-A |
72 |
872 |
1.74 |
1.40 |
|
|
A-3 |
A-K-J-I-A |
61 |
2174 |
4.35 |
2.95 |
|
|
A-4 |
A-E-F-A |
59 |
1870 |
3.74 |
2.45 |
|
|
A-5 |
A-J-F-E-A |
57 |
2477 |
4.95 |
3.14 |
|
|
A-6 |
A-I-K-J-A |
39 |
2407 |
4.81 |
2.09 |
|
|
A-7 |
A-J-F-A |
29 |
1683 |
3.37 |
1.09 |
|
|
A-8 |
A-K-J-F-A |
28 |
1951 |
3.90 |
1.21 |
|
|
A-9 |
A-J-F-B-A |
14 |
2094 |
4.19 |
0.65 |
|
|
A-10 |
A-F-E-F-A |
5 |
2016 |
4.03 |
0.22 |
|
(D) |
D-1 |
D-C-D |
224 |
530 |
1.06 |
2.64 |
|
|
D-2 |
D-B-C-B-D |
210 |
1358 |
2.72 |
6.34 |
|
|
D-3 |
D-H-E-H-D |
73 |
1798 |
3.60 |
2.92 |
|
|
D-4 |
D-B-A-J-D |
23 |
2463 |
4.93 |
1.26 |
|
|
D-5 |
D-H-J-H-D |
17 |
1876 |
3.75 |
0.71 |
|
|
D-6 |
D-B-F-J-D |
15 |
2077 |
4.15 |
0.69 |
|
|
D-7 |
D-C-B-D |
2 |
944 |
1.89 |
0.04 |
|
(F) |
F-1 |
F-J-F |
758 |
682 |
1.36 |
11.49 |
|
|
F-2 |
F-J-H-J-F |
125 |
1338 |
2.68 |
3.72 |
|
|
F-3 |
F-J-K-J-F |
108 |
1198 |
2.40 |
2.88 |
|
|
F-4 |
F-J-H-E-F |
76 |
1428 |
2.86 |
2.41 |
|
|
F-5 |
F-K-A-J-F |
8 |
2440 |
4.88 |
0.43 |
|
|
F-6 |
F-B-C-B-F |
8 |
1736 |
3.47 |
0.31 |
|
(J) |
J-1 |
J-K-A-J |
116 |
1876 |
3.75 |
4.84 |
|
|
J-2 |
J-K-F-K-J |
107 |
1478 |
2.96 |
3.51 |
|
|
J-3 |
J-H-D-J |
58 |
1837 |
3.67 |
2.37 |
|
|
J-4 |
J-D-C-D-J |
36 |
2328 |
4.66 |
1.86 |
|
|
J-5 |
J-K-G-K-J |
34 |
1666 |
3.33 |
1.26 |
|
|
J-6 |
J-I-J |
32 |
466 |
0.93 |
0.33 |
|
|
J-7 |
J-K-I-K-J |
23 |
1468 |
2.94 |
0.75 |
|
|
J-8 |
J-K-A-I-J |
8 |
2174 |
4.35 |
0.39 |
|
|
J-9 |
J-H-E-A-J |
2 |
2283 |
4.57 |
0.10 |
|
(K) |
K-0 |
No tours specified |
0 |
0 |
0 |
0 |
covers approximately 500 miles per day), and collectively would occupy the full-time activities of 13.97 drivers to satisfy the freight demand on the network tour arcs.
All loads contributing to the objective of increasing loaded miles (or revenue) are included in the solution. Note that each driver starts his or her tour at the appropriate driver domicile, and that no load availability constraints are exceeded. Similarly, note that each driver returns to his or her domicile at the end of each tour. In this example, it is assumed that a maximum of K = 4 dispatches are permitted. This example makes use of 100% of the allowed maximum freight in all lanes and the naturally integer solution is equal to the linear programming (LP) maximum. No additional random OTR drivers are needed to handle excess network freight and there is no need for subcontract drivers.
4.3 Driver-based
aggregate planning problem
In addition to the above aggregate planning
problem, we developed a formulation for a driver-based aggregate problem. The
problem is inherently the same with the pure aggregate problem; the only
difference is that the solutions of this problem are able to identify the
drivers that are needed from each domicile. This is done by defining an
additional set I of drivers domiciled at any domicile, indexed by i=1, …, nj
where nj is the number of drivers at domicile j. While in this
driver-based aggregate model we still treat the decision variables Xijkm and Yijkm to be general
integers, we will later discuss a model for a more detailed driver-based
operational problem where X ijkm and Yijkm will be binary integers.
The mathematical model
for this driver based aggregate planning is very similar with the aggregate
based planning model outlined in section 4.1. In the driver based aggregate
planning model, we add an index i as set of drivers and one additional
constraint which enforces the tour to have the domicile be initiated at the
first move and be ended at the last move.
Alternatively
we can do this constraint by assigning each variable in the equality to be
zero, i.e., Xijkm = 0 and Yijkm = 0 ;
, ą j and m ą .
4.3.1 A Numerical Example
We provide examples of the driver-based aggregate model by analyzing a
small-scale problem (See Table 5 for the data of the example). We have only two
domiciles,
Table 5. Data for the small scale problem
|
From City |
To City
|
Volume |
Miles |
|
|
Louisville |
72 |
436 |
|
Atlanta |
Detroit |
297 |
265 |
|
Louisville |
Atlanta |
109 |
436 |
|
Louisville |
Detroit |
218 |
355 |
|
Detroit |
Louisville |
220 |
355 |
|
Detroit |
|
260 |
265 |
Table 6.
Solution of small scale problem
|
Tour |
Driver |
Domicile |
Tour Description |
Tour Quantity |
Tour Miles |
|
1 |
1 |
Detroit |
Det-Atl-Det |
1 |
530 |
|
2 |
1 |
Detroit |
Det-Lou-Det |
62 |
710 |
|
3 |
2 |
Detroit |
Det-Lou-Det |
3 |
710 |
|
4 |
3 |
Detroit |
Det-Atl-Det |
2 |
530 |
|
5 |
3 |
Detroit |
Det-Atl-Lou-Det |
34 |
1056 |
|
6 |
3 |
Detroit |
Det-Lou-Det |
1 |
710 |
|
7 |
3 |
Detroit |
Det-Lou-Atl-Det |
6 |
1056 |
|
8 |
4 |
Detroit |
Det-Lou-Det |
63 |
710 |
|
9 |
5 |
Detroit |
Det-Lou-Det |
2 |
710 |
|
10 |
5 |
Detroit |
Det-Lou-Atl-Det |
41 |
1056 |
|
|
|
|
|
|
|
|
11 |
1 |
Atlanta |
Atl-Det-Atl |
83 |
530 |
|
12 |
1 |
Atlanta |
Atl-Lou-Atl |
1 |
872 |
|
13 |
2 |
Atlanta |
Atl-Det-ATl |
31 |
530 |
|
14 |
2 |
Atlanta |
Atl-Det-Lou(Y)-Atl |
1 |
1056 |
|
15 |
3 |
Atlanta |
Atl-Det-ATl |
8 |
530 |
|
16 |
3 |
Atlanta |
Atl-Lou_Atl |
17 |
872 |
|
17 |
3 |
Atlanta |
Atl-Lou-Det-Atl |
18 |
1056 |
|
18 |
4 |
Atlanta |
Atl-Det-Lou-Atl |
42 |
1056 |
|
19 |
5 |
Atlanta |
Atl-Det-Atl |
82 |
530 |
|
20 |
5 |
Atlanta |
Atl-Lou-Atl |
1 |
872 |
The solution presented in Table 6 has additional information about who
is responsible for a particular tour. The solution produces the objective
function value, which is the loaded mileage of 365,895 and 20 tours (not
necessarily different). For example, there are two drivers (driver 3 and driver
5) responsible for tour Detroit-Louisville-Atlanta-Detroit (tours 7 and 10).
Driver 3 would drive the tour (tour 7) for 6 times, driver 5 would drive the
tour (tour 10) for 41 times. In addition to this tour, driver 5 is also
responsible for another tour Detroit-Louisville-Detroit (tour 9) for two times,
driver 3 also has three other tours (tours 4, 5, and 6). We should note that a
quick analysis of the solution might improve the assignment of tours to driver.
For example, driver 3 domiciled at Detroit drives tour
Detroit-Louisville-Detroit (tour 6) just once. An improvement to the solution
would be to assign tour 6 to driver 1 since s/he already drives the same tour
62 times. In this way, we can relieve driver 3 from driving tour 6. We can
think of this as a consolidation of the tours so that at least some
regularization of “tour types” is realized. We can achieve this by introducing
a lower bound on the number of tours a driver can be assigned, which is left
for future research.
To see how factors such as the number of drivers and the number of
moves affect the solution and its associated total mileage, we conducted
additional experiments. Table 7 shows the results for different number of
drivers (5,6,7,8, and 9 per domicile) and different number of moves allowed
(2,3, and 4).
Table 7.
Objective Function Value for Different Scenarios
|
Set
I (# of drivers) per domicile |
Set
K (# of moves) |
Objective Function
(in
loaded miles) |
|
5 |
2 |
355364 |
|
6 |
2 |
355364 |
|
7 |
2 |
355364 |
|
5 |
3 |
369586 |
|
6 |
3 |
369586 |
|
7 |
3 |
369586 |
|
8 |
3 |
369586 |
|
9 |
3 |
369586 |
|
5 |
4 |
369586 |
|
6 |
4 |
369586 |
The results show that using the same number
of moves (|K| =3 or |K| = 4) the objective function value would be the same
regardless of the number of drivers available. However, if we reduce the number
of moves allowed, then the objective function value decreases, which shows the
need for determining the number of moves carefully.
In addition
to the above model, we also modify the model slightly by changing the objective
function. This objective function is to minimize the total number of drivers
needed to cover the demanded loads; 
, where Oij is a binary decision variable which is
1 if driver i from domicile j is actively utilized (used in the solution), zero
otherwise. We need to add a set of constraints to the existing constraints
above to satisfy the logical relationship between Oij and Xijkm. This constraint set is as follows:
The new constraints make sure that
if Oij is zero then Xij km is also zero and if Oij is one then some X ij k m can be greater than zero. In other words, if driver i from domicile j is
not used (Oij is zero) then the number of tours by driver i from any
origin cities to any destination cities in any move has to be zero. We left the
further exploration of this more detailed and complex formulation as a future
research. In the next section, we discuss another driver-based model, which is
called operational dispatching model where driver-load assignment decisions are
made for shorter term planning horizon.
4.4 Constraint management, model use, and
problem relaxations
The IP models presented above can be
used for detailed operational dispatching as well as aggregate planning, and
driver based aggregate planning as discussed previously. Aggregate planning
provides the tour overview information provided in table 4. This is very useful information for hiring
and asset planning. When used for
aggregate planning or driver based aggregate planning, equations 11 and 12
indicate that Xjkm and Yjkm are general integers. Normally, this would lead to solution
difficulty. However, when used for
aggregate planning, the model is naturally integer and solution times are
trivial, even for relatively large problems.
Detailed operational planning creates a more challenging environment for the IP model. When used for detailed dispatching, the model provides information about which particular driver will need to pick up which particular load during each dispatch cycle. The variables
X j km and Y
j km now
need an additional subscript for each driver i:
X i j km = 1
if driver i from domicile j makes his or her kth move from city to city m in
a loaded status, 0 otherwise.
Y i j km = 1
if driver i from domicile j makes his or her kth move from city to city m in
am unloaded status, 0 otherwise.
Similarly, the formulation must recognize the
additional subscript needs. X i j km and
Y i j km values
in equations (5) and (6) must be summed over all i and equations (7-10) must be
repeated for all i. Equations 11 and 12
now specify that Xi j km and Yi
j km values are binary (0,1) integers, because a
particular driver can pick up only one load at a time.
The optimization model, whether used for aggregate planning or for operational dispatching, provides a means of developing optimal tours for problems of national scale. Even so, as pointed out in Crainic and LaPorte (1997), vehicle routing problems can quickly become cumbersome in terms of the number of integer variables required. The current formulation is much more cumbersome computationally when used as an operational dispatching tool. Consider the computational complexity information for the operational problem formulation presented in table 8. The table reveals that when four dispatches per tour are permitted (a reasonable number of dispatches given the goal to reduce tour length), this problem remains quite reasonable in terms of the number of constraints but that the number of variables quickly grows as a function of problem size. The optional mileage constraint (equation 10) that caps Tmax (maximum tour length in miles) adds very little computational burden in terms of added constraints.
In general, recognizing that each
driver has only one domicile, we let I’ = the unique driver/domicile
combinations (I’ = I). Similarly, we let
’ = the unique combinations of and m where m (m-m). In the worst
case, the model results in {2(I’)(k)( ’)} variables but only {I’[3+(k-1)(m-1)]+ ’} constraints. Only
{I’[2+(k-1)(m-1)]+ ’} constraints are required when the optional constraints (
equation 10) indicating Tmax are omitted.
Table 8. Worst
Case Computational Complexity When K=4
|
Drivers |
Nodes |
Variables |
Constraints With Tmax |
Constraints Without Tmax |
|
3 |
3 |
144 |
33 |
30 |
|
3 |
5 |
480 |
65 |
62 |
|
3 |
10 |
2160 |
180 |
177 |
|
3 |
20 |
9120 |
560 |
557 |
|
|
|
|
|
|
|
5 |
3 |
240 |
51 |
46 |
|
5 |
5 |
800 |
95 |
90 |
|
5 |
10 |
3600 |
240 |
235 |
|
5 |
20 |
15200 |
680 |
675 |
|
|
|
|
|
|
|
10 |
3 |
480 |
96 |
86 |
|
10 |
5 |
1600 |
170 |
160 |
|
10 |
10 |
7200 |
390 |
380 |
|
10 |
20 |
30400 |