Research
My research interests include mathematical programming, polyhedral combinatorics,
combinatorial optimization, supply chain management and transportation.
Active Research Projects
- Multiobjective Mixed Integer Programming
- Dynamic Handling of Partially Time-Expanded Networks
- Advances in Dynamic Ridesharing
- Innovations in Last Mile Delivery
Some Past Research Projects
Per-Seat On-Demand Air Transportation
According to the United States Department of Transportation (DOT), Americans make more than 405 million business trips of more than 50 miles each year. Of these trips, 84 percent do not cross regional boundaries and close to 20 percent involve travel of 250 to 1000 miles.
Despite the length of the trips in the latter category, most of these trips are done by automobile. This phenomenon can be explained by examining the air travel alternative. To get from one regional airport to another, travelers typically have to connect through heavily congested ``hub'' airports, often located many miles from their origins and destinations. Missed connections and flight delays are not uncommon. Furthermore, travelers often have to drive many miles to get to or from an airport serviced by a
schedule-operated airline. In fact, commercial flight service exists in only about 550 of the nation's 5,000 public-use airports, with a mere 67 of these airports accounting for 90 percent of domestic traffic. Add to this the fact that airlines offer limited schedules at regional airports, and the air travel alternative does not look very appealing.
What is more, the DOT reports, the trend seems to be that more and more travelers prefer driving rather than flying for trips between 200 and 500 miles. This is in part due to the changes taking place in the commercial airline industry. Increased security at airports
has resulted in longer waiting times, with the associated frustrations, and thus longer travel times. Furthermore, due to the huge losses suffered by the airlines in recent years (airlines worldwide have lost $25 billion dollars and more than 400,000 jobs in 2002 and 2003), airlines have cut back and are operating with a reduced schedule, affecting the flexibility of the business traveler, especially when it concerns smaller regional airports.
Can this trend be reversed? Can an air travel alternative be developed that appeals to the regional business traveler? Some people believe so.
New developments in avionics and airplane manufacturing have brought about a new technology: the very light jet (VLJ), also called the microjet. Weighing less than 10,000 pounds, these aircraft can carry 4-5 passengers, fly distances of over a 1,000 miles, reach altitudes of 19,000-30,000 feet, and travel at speeds between 350-390 nautical miles per hour (almost twice the altitude and speed of current turbo-prop airplanes). Priced at approximately 1 million US dollars, these jets cost about one fourth of the price of the cheapest business jets sold today. Additionally, these jets can be operated by a single pilot, which means low operational costs. Several manufacturers are taking orders for VLJs with Eclipse Aviation being the first with planned deliveries in March of 2006.
The availability of relatively cheap small jet aircrafts suggests a new air transportation business: the air taxi, an on-demand service in which travelers call one day or a few days in advance to schedule transportation. The advantages of such a system are obvious. An air-taxi service gives regional travelers the option of hopping aboard small jets that fly to and from less congested outlying airports, without packed parking lots, long lines at security checkpoints, flight delays, and lost luggage, that are closer to where they live and where they want to go. In fact, VLJs could land at any of 14,000 private and public landing strips in the United States.
By charging a discount fare for sharing cabin space with other passengers, aggregation can greatly reduce costs while still ensuring a very convenient service.
The idea of an air-taxi service to satisfy regional demand is rapidly becoming a reality. In fact, even though VLJs are not yet available, air taxi services already exist today. Since April 2002, SkyTaxi Inc. has been providing on-demand air transportation in the northwestern United States. Likewise, SATSair provides such a service in the northeast. And recently, DayJet Corporation has announced that they will be providing air-taxi services in the southeast starting in mid-2006. All of them plan to expand their services to the entire United States.
The air-taxi alternative has generated a lot of interest. Recent media coverage includes The New York Times, The Wall Street Journal, USA Today, Business Week, Newsweek, CNN, BBC, and much, much, more.
Will this business model be successful? Ed Iacobucci, founder and CEO of DayJet Corporation, believes that it is not only possible to successfully run an air taxi service business, but it is possible to do so charging an amount only slightly above non-discount, or last minute, coach fares of commercial airlines. In order for the business to be profitable at these rates, each flight segment should average a load of 1.7 paying passengers. And, Iacobucci says, the key to attaining such load factors is optimization-based scheduling systems.
To effectively manage day-to-day operations at an air taxi service, several optimization-based scheduling components need to be employed: (1) an online scheduling system to quickly inform passengers if their air transportation requests can be serviced and at what price, (2) an off-line scheduling system to construct minimum cost pilot and jet itineraries for the next day once the reservation deadline has passed, (3), a maintenance scheduling system to ensure that the aircraft regularly visit maintenance facilities to undergo the FAA and manufacturer mandated maintenance, and (4) a disruption management system to re-route jets in case of failures, bad weather, or other unpredictable events.
In collaboration with the optimization group at DayJet, we have developed various scheduling engines based on integer multi-commodity network flow models and innovative local search procedures. The technology has been implemented to run on a distributed computing platform. Extensive simulation studies have demonstrated the effectiveness of the technology.
Robust Optimization for Empty Repositioning Problems
Consider a problem faced by most large freight transportation
service providers: the management of empty resources over time.
Almost all freight transporters serve a set of load requests that
is imbalanced in both time and space. Thus, when a resource such
as a container or truck driver arrives at the destination location
of a loaded move, there may not be an opportunity to match that
resource in a timely way with a new loaded move outbound from that
location. To correct imbalance, transporters move resources empty
between locations and minimizing the costs of such empty moves is
a primary challenge.
Currently, most transporters address this problem using simple
deterministic flow optimization models over time-expanded
networks. Network nodes are defined at relevant decision points,
and connect forward in time with other nodes via arcs that
represent management decisions (and their costs) such as holding
inventory of empty resources, or repositioning such resources
between locations. Next, point forecasts are developed for the net
expected supply for resources at some or all of the time-space
network nodes, and initial and final resource states are
specified. A feasible flow on such a network represents a set of
feasible empty management decisions, and network optimization
algorithms can be used to find an optimal flow. For problems that
can be decomposed by resource, the resulting problems are often
single-commodity minimum cost network flow problems, which can be
solved very efficiently. In practice, these models are used in a
rolling horizon implementation where a solution is obtained for a
long planning horizon, but only the decisions in an initial set of
time periods are implemented.
One major deficiency of this traditional approach is that there
may be significant uncertainty in the forecasts of resource net
supply at each time-space node, especially when the planning
horizon grows large. When realized demands differ from forecasts,
the implemented empty allocation plan may be far from optimal.
Stochastic models for these problems typically replace point
forecasts of expected net supply with distribution forecasts, and
attempt to find solutions that minimize total expected cost over
the planning horizon; in this case, difficult-to-solve stochastic
dynamic programming or stochastic integer programming problems
result.
In contrast to existing stochastic approaches that focus on
expected cost minimization, this research develops a robust
optimization approach for repositioning problems. To do so, we
extend the standard single-commodity minimum cost network flow
problem on time-expanded networks. To avoid requiring estimates of
probability distributions, we model forecast uncertainty using
intervals about a nominal expected net supply at each time-space
node. The robust approach seeks to find minimum cost solutions
that satisfy special feasibility conditions for any demand
realization in which (1) each time-space point demand lies within
its forecast interval, and (2) the total absolute deviation of the
realized demand from the nominal expected demand across all
time-space points is bounded by a control parameter k. Parameter
k determines the conservatism of the solution: when k equals 0, the
problem reduces to the deterministic problem, and when k equals infinity,
solutions must satisfy the special feasibility conditions for all
realizations.
The special feasibility conditions for the developed approach
require that a robust repositioning plan (1) satisfies flow
balance equalities and flow bounds with respect to the nominal
expected net supply values, and (2) is recoverable, that
is, it can be converted into a plan that satisfies flow balance
equalities and flow bounds for every demand realization using some
predefined subset of the original allowed decisions, known as the
recovery actions. (Note that any solution feasible for a specific
realization of net supplies is necessarily infeasible for every
other realization.) The recovery actions are similar to recourse
actions in two-stage stochastic programming models. The simplest
recovery action considered allows flow changes only on inventory
arcs between the same space point in consecutive time periods;
this scenario, therefore, models the case where each spatial
location must hedge independently against uncertain future
outcomes. We also consider recovery actions that allow limited
reactive repositioning between locations.
The robust repositioning problem that allows only inventory
recovery actions is shown to be polynomially-solvable. For the
robust repositioning problems that allow reactive repositioning,
we develop sets of feasibility conditions whose sizes, while not
polynomial, do not grow with the size of the uncertain outcome
space. We illustrate the robust repositioning ideas developed
with a numerical example. The example provides some insight into
how different levels of conservatism, measured by k, and
different degrees of flexibility for performing recovery actions
affect the cost of a robust repositioning plan, and therefore the
price of robustness.
The main contributions of our research can be summarized as follows.
- We introduce a robust optimization framework in
which uncertain parameters are assumed to fall within an interval
around a nominal value and where the conservatism of a solution is
controlled by limiting the total absolute deviation from the
nominal values. In addition, the framework explicitly incorporates
the notion of recovery actions to dynamically handle realizations
of the uncertain parameters.
- We show the implementation and value of the
proposed robust optimization framework in the context of empty
repositioning problems faced by many freight transportation
service providers for three sets of recovery actions.
- We show that for each of the three sets of recovery
actions considered for the empty repositing problem, the size of
the resulting optimization problem does not depend on the size of
the uncertain outcome space, and that for the simplest set of
recovery actions the resulting optimization problem can be solved
in polynomial time.
Decision Support for Consumer Direct Grocery Initiatives
In recent years, many new and existing businesses have adopted a consumer direct (CD) service model that allows customers to purchase goods online and have them delivered directly to their front door. Crossing this ``last mile" provides a huge increase in service for customers, but also creates a huge logistics challenge for companies, even with the advantages e-commerce provides. For example, we have seen the rise and subsequent fall of many e-grocers, including Webvan and Shoplink, who have run out of money in the process of finding a distribution model that enables them to stay competitive with
local grocery stores and stay in business. E-grocers that have survived have changed distribution plans and focus, as demonstrated by the closing of the San Francisco-based operations for Peapod and many continue to enter the arena with their own ideas on how to succeed. With annual revenue from all goods sold online predicted to be $195 billion by 2006 consumer direct is quickly becoming one of the most important business models, but there are still many open questions about how to run such businesses efficiently and effectively.
There are several issues in developing a successful direct delivery strategy. The fulfillment process for most consumer direct businesses can be divided into three phases: (1) order capture and promise, (2) order sourcing and assembly, and (3) order delivery. Our research effort focuses on the interactions between order promise (deciding on a delivery time) and order delivery (devising efficient delivery schedules). Better integration of these decisions has the potential to substantially improve profitability, especially for those consumer direct businesses offering “attended” deliveries. Attended deliveries are those where the consumers must be present and may be necessary for security reasons (e.g. expensive computer equipment), because goods are perishable (e.g. milk, flowers), or because goods are being picked up or exchanged (e.g. dry cleaning), and are a vital feature of many consumer direct service models. To provide a high service level and to avoid delivery failures as much as possible, it is customary in attended home delivery services for the company and customer to mutually agree on a narrow delivery window, or time slot.
We have studied and developed methodologies for order acceptance decisions so as to maximize overall profit. The key idea underlying these methodologies is to exploit information about potential future orders to evaluate whether it is better to accept a customer's order or to reserve capacity for potential future orders. As each order arrives, we compare the value of accepting that particular order versus accepting potential future orders that are properly discounted based on their probability of being realized. Computational results indicate that these order acceptance strategies can significantly increase profits.
In practice, it is typically the case, particularly in a struggling industry such as e-groceries where high customer retention is of utmost importance, that a vendor accepts an order unless it is truly impossible to satisfy the request. In such a scenario, we can potentially make significant improvements in routing costs through influencing customers' choices of delivery time slot. If better time slots are selected, not only will total distance be less, but a more efficient use of resources may increase the number of orders that can be accepted and thus create higher revenues. We have focused on offering discounts, or incentives, to customers to influence their time slot selection. Our computational experiments have shown that incentives schemes can significantly increase the profitability of companies providing home delivery. Our computational studies have offered greater insight and better understanding of when incentives will be successful and what type of incentives will perform best.
Driver Management Technology for Less-than-Truckload Carriers
The trucking industry is vitally important to the U.S. economy and
provides an essential service by transporting goods from business
to business (BtoB) and from business to consumer (BtoC). The
less--than--truckload (LTL) industry is an important segment of
the trucking industry, serving businesses that ship quantities
ranging from 150 lbs to 10,000 lbs, i.e., less--than--truckload
quantities. To be economically viable, LTL carriers have to
consolidate shipments into truckloads. Therefore, LTL carriers
pick up shipments from various shippers in a relatively small
geographical area, say a city, and bring them to a terminal
serving the area, referred to as a satellite or end-of-line
terminal. These satellite terminals serve as sorting centers and
loading facilities for outbound freight. As there usually is not
enough freight at a satellite terminal to build full truckloads to
satellite terminals serving other areas, another level of
consolidation is introduced in the system. Outbound freight from a
satellite is sent to a terminal that consolidates freight from
different satellite terminals, referred to as a breakbulk
terminal. Breakbulk terminals do handle enough freight to build
and dispatch cost efficient loads, i.e., loads that completely or
almost completely fill up two trailers. So typically a shipment
travels from an origin satellite to an origin breakbulk, then to a
destination breakbulk and finally to a destination satellite. This
hub--and--spoke network is referred to as the (main) linehaul
network. When the distance between the origin and destination
breakbulk of a load is too long for a single driver to cover in
the driving hours allowed by Department of Transportation
regulations, a sequence of intermediate stops is introduced at
so--called relay terminals. Usually, relay terminals are
breakbulk terminals on the path from the origin breakbulk to the
destination breakbulk. At a relay terminal, the load is taken over
by another driver to ensure high service levels. Since shipments
are not unloaded and loaded at the relay terminals, the path of a
shipment is identified by the sequence of terminals where the
shipment is handled, which are the origin end of line, the
destination end of line, the origin breakbulk and the destination
breakbulk. The routing of a shipment over this network is called
the load plan.
If enough freight is available, it may be possible at an outbound
breakbulk to build a load for a satellite terminal and bypass the
inbound breakbulk. Loads dispatched from an outbound breakbulk to
a satellite terminal are called direct loads, because they
do not need to be handled at an inbound breakbulk. LTL carriers
prefer that loads from breakbulks are dispatched directly to
destination satellites, because it reduces handling costs.
Usually, a direct load follows the same path as a regular load, so
as to allow driver changes at relay terminals, but it is not
handled until it reaches the destination satellite. Hence, direct
loads may not decrease transportation costs. Another important
advantage of direct loads is that it typically reduces the time
freight spends in the linehaul system (because it is handled
less), which improves service. As freight patterns observed by
LTL carriers are fairly regular, LTL carriers usually identify and
operate direct loads on certain origin--destination pairs. Direct
loads from an origin satellite to a destination breakbulk are
possible, but happen less frequently. Furthermore, if trailers
are used for pickup and delivery of freight, then it may be
possible to build loads for the outbound breakbulk without
unloading and loading at satellite terminals. This practice,
which reduces handling cost and may improve service, is another
reason why breakbulk--satellite direct loads are more likely to
occur than satellite--breakbulk direct loads.
LTL carriers use 28-foot trailers (or pups) or 48-foot vans.
Typically, a single driver will pull a single 48-foot van or two
28-foot trailers. One advantage of the use of 28-foot trailers is
that they allow a single driver to pull 56 feet of trailers.
However, the use of 28-foot trailers also improves service and
reduces handling costs. It is easier to fill a 28-foot trailer
than a 48-foot trailer. By combining trailers with different final
destinations, it is possible to build loads that can be dispatched
earlier. Furthermore, filling an entire 28-foot trailer with
shipments with a common final destination (which is more likely to
happen with a 28-foot trailer than a 48-foot van) allows simple
drop-and-hook operations at the next terminal as opposed to
loading and unloading. Effectively exploiting the advantages of
the use of 28-foot trailers requires proper pup matching,
i.e., deciding which 28-foot trailers to combine into a loads.
Due to imbalances in freight flows, it is unavoidable to have to
reposition trailers in an LTL operation, i.e., move trailers
empty. Repositioning, to a certain degree, happens naturally when
drivers are required to always pull a van or two trailers. Since
drivers have to return to their domicile regularly, trailer
balance will be achieved automatically. Unfortunately, sometimes
it is necessary for drivers to bobtail, i.e., move the
tractor without a trailer, and specific actions are required to
restore trailer balance. Bobtailing may happen, for example,
between a terminal and a rail head to accommodate freight
movements by rail. Most national carriers rely on rail to move
freight across long distances.
As indicated above, a load plan provides for each terminal a
lookup table that specifies for each shipment given its final
destination, its next destination. However, knowing how shipments
flow through the linehaul network is not enough to establish an
effective operation. In fact, a crucial component, one that has a
significant impact on overall performance, is still missing:
scheduling drivers to actually move the freight through the
linehaul network. Effective driver management is one of the most
challenging aspects of an LTL operation as drivers have to abide
by a large number of rules that limit their use. The first source
of such rules is the U.S. Department of Transportation, which
limits driving hours and duty hours to ensure highway safety. The
second source of such rules are the labor unions. Most carriers
are unionized and the labor unions have negotiated rules that
restrict, sometimes severely, the use of drivers at terminals.
Even though driver management is of the utmost importance for
efficient and effective LTL operations, it has been virtually
ignored by the academic community. In part because of a tendency
in the operations research community to focus on planning
problems, as opposed to operational problems, and in part because
the challenges of driver management at national LTL carrier, at
first glance, seem to be almost insurmountable.
With the increase in computing power and the growing trend to
focus on dynamic real-time operational problems, the time seemed
right to see what can be done to assist the planners national LTL
carriers in terms of driver management technology. We have designed and
implemented driver scheduling technology for the largest U.S. LTL carrier.
The technology is capable of generating cost effective driver schedules
satisfying a variety of real-life constraints in a matter of minutes.
Global Intermodal Tank Container Management for the Chemical Industry
The chemical industry is growing steadily, especially in China,
where chemical consumption is growing at a rate of 8% annually
(China is projected to become the third largest consumer by 2010).
The value of global chemical production exceeded US$1.7 trillion
in 2003. World trade in chemicals continues to surge as well. In
2002, chemicals led all product groups in global trade growth at
over 10%, with total world export value reaching US$660 billion.
As a consequence, transport of chemicals represents a significant
portion of worldwide transport of goods.
Long-distance, international transportation of liquid chemicals is
conducted using one of five modes: pipeline, bulk tankers, parcel
tankers, tank containers, or drums. Pipeline and bulk tankers are
used primarily in the petrochemical industry for the transport of
large quantities of a single product. Parcel tankers are smaller
vessels with up to 42 tank compartments and are used to
simultaneously transport multiple cargoes. Tank containers, also
referred to as ISO tanks, intermodal tanks, or IMO portable tanks,
are designed for intermodal transportation by road, rail, and
ship. Tank containers have many advantages for the international
transport of liquid chemicals:
- They are environment-friendly, since they are less prone to
spillage during filling and unloading, as well as leakage during
transportation.
- They permit a higher payload when compared to drums stowed
in dry containers (43\% more volume).
- They can be handled mechanically, which results in cost
savings, but also ensures safety when handling hazardous
commodities.
- They provide secure door-to-door multi-modal transportation
(by road, rail, sea or inland waterways), and do not require
specialized port-side infrastructure.
- They are safe and durable, with a design life of 20-30
years.
- They can be cleaned and placed into alternate commodity
service with minimum downtime.
- They can be used as temporary storage for customers with
limited space or high-cost permanent storage.
A tank container operator manages a fleet of tanks to transport
liquid cargo for a variety of customers between essentially any
two points in the world. Typically, 60% to 70% of the fleet is
owned by the operator; the remaining tanks are leased, usually for
periods of 5 to 10 years. To serve a standard customer order, a
tank container operator would provide a tank (or multiple tanks)
at the customer's origin plant and arrange transportation for the
tank across multiple modes to the destination plant.
Transportation will usually include a truck leg at origin and
destination and a steamship leg between a port near the origin to
another port close to the destination. It may also include rail
or barge legs at each end. Operators use depots for temporary
storage, cleaning, and repair of empty containers.
We study the management problems faced by tank container operators.
Specifically, we are interested in the difficult task of
cost-effectively managing a fleet of tank
containers, given imbalanced global trade flows. Given the high
cost of tanks, high loaded container utilization is very important
in this industry.
Split Deliveries in Distribution Operations
In many distribution environments a fleet of capacitated vehicles
is has to serve a set of customers with known demand. Each
customer is required to be visited by exactly one vehicle and the
goal is to minimize the total delivery costs. We study the benefit
of allowing split deliveries, i.e., removing the restriction that
each customer has to be visited exactly once. The upside of
allowing split deliveries is a reduction in delivery costs. The
downside of allowing split deliveries is an increase in customer
inconvenience and more complex administration and accounting. To
allow companies to carefully evaluate these trade-offs, it
important to understand the benefits of allowing split deliveries.
Theoretically, it has been shown that the reduction in delivery
costs from allowing split deliveries will never be more than 50%.
Although of theoretical interest, this result has limited value
for practitioners. It does not provide any insight into the
relation between the characteristics of a specific distribution
environment, e.g., geographic distribution of customers and demand
distribution of customers, and the reduction in delivery costs
from allowing split deliveries. Here we remedy that situation. We
focus on estimating the benefits of allowing split deliveries
based on customer characteristics, e.g., customers' locations and
the customers' demand patterns.
A few minutes of thought reveal that
- when demands are large relative to the vehicle capacity, then
there is little advantage to splitting deliveries;
- when demands are small relative to the vehicle capacity, then
there is little advantage to splitting deliveries;
- when demands are a little over half the vehicle capacity, then
there may be substantial advantages to splitting deliveries.
To make these observations more precise and to generalize them, we
empirically study the ratio z(VRP)/z(SDVRP) as a function of
customers' locations and customers' demand, where z(VRP) and
z(SDVRP) denote the cost of an optimal VRP solution and an optimal
SDVRP solution, respectively.
Our computational study and subsequent analysis confirms that
allowing split deliveries can result in substantial benefits, but
also shows that substantial benefits only occur for customers'
demands with fairly specific characteristics. More specifically,
the following insights have been obtained:
- The delivery cost reductions obtained when allowing split
deliveries appear to be due primarily to the ability to reduce the
number of delivery routes. A reduction in the number of delivery
routes may have additional cost benefits, as a smaller vehicle
fleet is required.
- The largest benefits are obtained when the mean demand is
greater than half the vehicle capacity but less than three
quarters of the vehicle capacity and the demand variance is
relatively small.
- The benefits from allowing split deliveries mainly depends on
the relation between mean demand and vehicle capacity and on
demand variance; there does not appear to be a dependence on
customer locations.
Asset Repositioning in Truckload Transportation
The growing interest in collaborative logistics is fuelled by an ever increasing pressure on companies to operate more efficiently, the realization that suppliers, consumers, and even competitors, can be potential collaborative logistics partners, and the connectivity provided by the Internet.
In the trucking industry, shippers and carriers are continuously facing pressures to operate more efficiently. Traditionally shippers and carriers have focused their attention on controlling and reducing their own costs to increase profitability, i.e., improve those business processes that the organization controls independently. More recently, shippers and carriers have focused their attention on controlling and reducing system-wide costs and sharing these cost savings to increase everyone's profit. A system-wide focus, e.g., a collaborative focus, opens up cost saving opportunities that are impossible to achieve with an internal company focus. A good example is asset repositioning. To execute shipments from different shippers a carrier often has to reposition its assets, i.e., trucks. Shippers have no insight in how the interaction between their shipments affects a carrier's asset repositioning costs. However, shippers are implicitly charged for these repositioning costs. No single participant in the logistics system controls asset repositioning costs, so only through collaborative logistics initiatives can these costs be controlled and reduced.
Collaborative transportation networks, such as those managed by Nistevo (www.nistevo.com) and Transplace (www.transplace.com), are examples of collaborative logistics initiatives focused on bringing together shippers and carriers to increase asset utilization and reduce logistics costs. For example, analysts at Nistevo have been able to identify a repeatable dedicated 2,500-mile continuous move tour for two of the members of the Nistevo network visiting distribution centers, production facilities, and retail outlets. The tour has resulted in a 19% savings for both shippers (over the costs based on one-way rates) and the carrier is experiencing higher margins through better asset utilization and lower driver turnover through more regular driver schedules. Identifying tours minimizing asset repositioning costs in a collaborative logistics network is no simple task. When the number of members of the network, and thus the number of truckload movements to consider, grows, the number of potential tours to examine becomes prohibitively large. In that case, optimization technology is needed to assist the analysts.
We have developed optimization technology that can be used to assist in the identification of repeatable, dedicated truckload continuous move tours. This technology is of value for companies that regularly send truckload shipments, say several days of the week, and are looking for collaborative partners in similar situations to cross-utilize a dedicated fleet, or strengthen their negotiating position during transportation procurement. In situations where shippers regularly send truckload shipments, it is common to find contracts in which carriers dedicate a portion of their fleet to the shipper, but then transfer responsibility for all costs, including repositioning costs, to the shipper. Thus, it is in the interest of the shipper to find partners to most effectively use the dedicated fleet.
Timing considerations are critical to the practical viability of continuous move tours and are a key focus of our efforts. We have developed a highly effective and extremely efficient heuristic that incorporates, among others, fast routines for checking time-feasibility of a tour in the presence of dispatch time windows and for minimizing the duration of a tour by appropriately selecting a starting location and departure time. We have demonstrated the effectiveness of the algorithms developed on various randomly generated instances and on instances derived from data obtained from a strategic sourcing consortium for a $14 billion dollar sized US industry.
The basis for the proposed optimization technology is a heuristic for the time-constrained lane covering problem. The lane covering problem was introduced in Ergun et al. (2003) and represents the core optimization problem: covering a set of lanes, i.e., shipments, with a set of cycles, i.e., continuous move tours, of minimum cost. The time-constrained lane covering problem captures the additional complexities introduced when considering dispatch windows on the lanes.
The benefits of continuous move tours depend on the pricing model employed by a carrier. Different carriers have different schemes for incorporating repositioning costs in the price charged for a one-way move between two locations. The simplest scheme applies a markup factor to the cost of a one-way move, e.g., 20 percent, to cover anticipated repositioning costs. More sophisticated schemes may take the destination location into account, because the destination location is typically a good indicator of the expected repositioning costs. Our proposed methodology is flexible and can accommodate a variety of carrier pricing models. For convenience, we assume a simple pricing model for most of our presentation and discussion. However, for the computational study with real-life data from a strategic sourcing consortium, we have used a pricing model representative of those used in practice.
As mentioned above, we focus on optimization technology that can be used to assist in the identification of repeatable, dedicated truckload continuous move tours. However, the technology can be adapted straightforwardly to handle more dynamic situations, in which continuous move paths (as opposed to tours) are constructed, extended, and modified based on truckload shipments being revealed to a dispatcher over time.
|
