Jump to Content: Welcome to the virtual world of Georgia Tech

Jump to Footer Navigation: Accessibility | Contact Us | Legal & Privacy Information | Technology

School of Industrial and Systems Engineering at Georgia Tech

Assistance Navigation:

Campus Map Directories Site Map Site Help Site Search
Faculty Webpage

Martin Savelsbergh Website

crumb trail: GT >> College of Engineering >> School of Industrial and Systems Engineering >> ISyE Personal Web Site


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.

This site is available to any internet device, but really looks best in a modern graphical browser that supports web standards.

GT website ISyE website GT CoE website