Transcription

This article was downloaded by: [139.179.113.115] On: 04 March 2020, At: 11:38Publisher: Institute for Operations Research and the Management Sciences (INFORMS)INFORMS is located in Maryland, USAINFORMS Journal on Applied AnalyticsPublication details, including instructions for authors and subscription g Transportation by Inventory Routing andWorkload Balancing: Optimizing Daily Dray OperationsAcross an Intermodal Freight NetworkXiaoqing Sun, Manish Garg, Zahir Balaporia, Kendall Bailey, Ted GiffordTo cite this article:Xiaoqing Sun, Manish Garg, Zahir Balaporia, Kendall Bailey, Ted Gifford (2014) Optimizing Transportation by Inventory Routingand Workload Balancing: Optimizing Daily Dray Operations Across an Intermodal Freight Network. INFORMS Journal on AppliedAnalytics 44(6):579-590. https://doi.org/10.1287/inte.2014.0746Full terms and conditions of use: ians-Portal/PubsOnLine-Terms-andConditionsThis article may be used only for the purposes of research, teaching, and/or private study. Commercial useor systematic downloading (by robots or other automatic processes) is prohibited without explicit Publisherapproval, unless otherwise noted. For more information, contact [email protected] Publisher does not warrant or guarantee the article’s accuracy, completeness, merchantability, fitnessfor a particular purpose, or non-infringement. Descriptions of, or references to, products or publications, orinclusion of an advertisement in this article, neither constitutes nor implies a guarantee, endorsement, orsupport of claims made of that product, publication, or service.Copyright 2014, INFORMSPlease scroll down for article—it is on subsequent pagesWith 12,500 members from nearly 90 countries, INFORMS is the largest international association of operations research (O.R.)and analytics professionals and students. INFORMS provides unique networking and learning opportunities for individualprofessionals, and organizations of all types and sizes, to better understand and use O.R. and analytics tools and methods totransform strategic visions and achieve better outcomes.For more information on INFORMS, its publications, membership, or meetings visit http://www.informs.org

Vol. 44, No. 6, November–December 2014, pp. 579–590ISSN 0092-2102 (print) ISSN 1526-551X (online)http://dx.doi.org/10.1287/inte.2014.0746 2014 INFORMSOptimizing Transportation by Inventory Routing andWorkload Balancing: Optimizing Daily Dray OperationsAcross an Intermodal Freight NetworkXiaoqing Sun, Manish Garg, Zahir Balaporia, Kendall Bailey, Ted GiffordSchneider National Inc., Green Bay, Wisconsin 54306 {[email protected], [email protected],[email protected], [email protected], [email protected]}In rail-based intermodal freight operations, full containers are moved by truck from shipper locations to rail ramps,transported via train to destination ramps, and then moved again by truck to consignee locations. We commonlyrefer to the roadway portions of this activity as dray operations. In a large metropolitan hub area, such as Chicagoor Los Angeles, this drayage activity may involve several hundred drivers and up to 500 daily container moves toor from several distinct rail ramps. Both cost and environmental considerations drive the need to maximize driverproductivity and minimize the time and miles not directly associated with moving loaded containers to orfrom rail ramps. In this paper, we describe a solution to this problem using a set-partitioning formulation andcolumn-generation heuristic and report on a large-scale implementation. We focus on real-world implementationdetails that include (1) fast solve times to support near-real-time re-solving in the face of constantly changing data,(2) adjustments to account for traffic congestion and other operational considerations, and (3) integration with acommercial transportation management system to provide real-time data to the optimizer and to send solutionrecommendations to a driver-assignment process.Keywords: computer science; transportation/shipping; tree algorithms; networks/graphs; deterministic sequencing;production/scheduling; Benders decomposition; algorithms; integer programming; column generation.History: This paper was refereed. Published online in Articles in Advance June 30, 2014.Increasing fuel prices and the geographic expansion of distribution networks have made intermodalfreight transport systems an increasingly competitive alternative to single-mode transportation services.The use of multiple transport modes leverages tradeoffs between cost and efficiency on high-volume modesand access and flexibility on low-volume ones. The termintermodal, as distinct from multimodal, is normallyreserved for the sequential movement of a containeror full-truckload shipment across several modes oftransportation. Multimodal is a more general termthat includes less-than-truckload and small-packagedelivery, and often involves consolidation and deconsolidation of individual freight units as they movethrough a defined transportation network.The two prevalent forms of intermodal transport areroad-rail-road for continental shipping and road-searoad for intercontinental shipments. To facilitate modechanges, freight is normally loaded into containers, withcapacities ranging from 1,000 to 4,000 cubic feet thatcan be easily transferred between modes. The middleleg of the freight transport, train, or sea-going vesselrealizes low per-unit cost and high efficiency by movingmany containers at a time. The largest cargo vesselsnow in service carry 15,000 twenty-foot equivalent unitsand the longest trains carry as many as 500 doublestacked 53-foot containers. The end legs of transport,termed drayage, are characterized by much shortertransit distances and the movement of individual containers to or from time-constrained customer locations.The simultaneous arrival or departure of a large numberof containers at a port or rail hub creates a challengefor dray transportation resources. Although this activity is often outsourced to third-party draymen, whichwe refer to as foreign carriers in this discussion, costand environmental impact considerations can makeit attractive to employ a dedicated fleet of tractorsand drivers and use route and schedule optimizationsoftware systems to maximize the utilization of thefleet.579

580Sun et al.: Optimizing Daily Dray Operations Across an Intermodal Freight NetworkFigure 1: This map depicts railroad routes for the intermodal freight network.Schneider National, Inc. operates a large intermodalfreight transportation network, which encompassesthe continental United States with significant coverage in Canada and Mexico. This network has 24 railhubs, served by a fleet of more than 1,300 trucks and14,000 containers, and moves more than 4,000 drayshipments per day, including pickup, delivery, andcrosstown transfers between railroads, and repositioning moves (see Figure 1). Dray shipment distancesrange from several miles to several hundred miles.Drivers transporting the longer-distance loads may beaway from home overnight, but most drivers returnhome at the end of each daily shift.In addition to company-employed and independentcontractor (IC) drivers, whose schedules are manageddirectly by the company, dray freight is also movedby foreign carriers who provide flexible capacity tosupport seasonal shifts in volume and shorter-termdemand fluctuations.Specific freight characteristics must also be considered. Examples include shipments or locations thatrequire specific driver certifications and weight limitsthat necessitate the use of lighter day cabs (a tractorthat does not have a sleeper berth). Actual pickup anddelivery times also vary, depending on whether thedriver must wait for the container to be loaded orunloaded or can quickly drop (and depart) or pick upa preloaded container.In this paper, we describe the implementation of acomputer-based solution to address the recurring dailyInterfaces 44(6), pp. 579–590, 2014 INFORMSproblem of assigning drivers to transport drayage toboth maximize driver productivity and minimize thetotal operations cost. This project consists of (1) thedevelopment of a mathematical programming optimization model, (2) the implementation of the modelinto an operational decision support system, (3) theintegration via near real-time data flows into a suite ofcommercial software systems, and (4) the developmentof corresponding business processes to realize significant tangible benefits. We begin with a discussionof the business processes, follow with a review ofrelevant prior work, and describe the implementationand a number of modeling details. We then review thefinancial benefits and discuss model extensions andenhancements now in development. Appendix A coversalgorithmic details and the mathematical formulation.Business Process forIntermodal OperationsThe flow of information, with corresponding processingand decision steps, is shared across a set of softwaremodules (see Figure 2).Intermodal freight orders are initially captured in theorder entry system via either electronic transfer from acustomer or direct entry with information received byfax or telephone (step 1). Order information includesorigin pickup location, destination delivery location,and associated time constraints. Some orders mayOrder entryand management(5) Accepted ordersShipmentplanning andexecution(8) Dispatch(1) Order data(4) Acceptancerecommendations(2) Order data(3) ScheduleoptionsRevenuemanagementengine(6) Shipmentand driver data(7) SolutionShort hauloptimizerDriverFigure 2: This diagram illustrates the process flow for intermodal freightorders. The numbers in parentheses represent steps in the process flow.

Sun et al.: Optimizing Daily Dray Operations Across an Intermodal Freight NetworkInterfaces 44(6), pp. 579–590, 2014 INFORMSrequire more than one pickup (delivery) stop to complete the loading (unloading) of the container. As partof the order acceptance process, the order is validatedfor geographic and transit feasibility, train optionsare determined, and preliminary profitability analysisis carried out (steps 2, 3, and 4, respectively). If theorder is confirmed, it is passed to the transportationmanagement system (TMS) for splitting into componentshipments (step 5). For example, an order from Chino,California to Woburn, Massachusetts would plan intofive shipments:1. Origin dray from shipper in Chino to railroadramp in Los Angeles, California;2. Rail shipment from Los Angeles to Chicago,Illinois on western U.S. rail service provider;3. Crosstown dray in Chicago from western U.S. toeastern U.S. rail service provider;4. Rail shipment from Chicago to Worcester,Massachusetts on eastern U.S. rail service provider;5. Destination dray from Worcester ramp to consignee in Woburn.The number of component shipments for an ordervaries from three (for the simple single-rail-leg case)to as many as 10 when several railroads and international (e.g., Canada-U.S.-Mexico) border crossings arerequired.The rail shipment components of each order areplanned first using train schedule information andrelevant feasibility and cost information. When thisstep is complete, the corresponding dray shipments(origin, destination, and crosstown) are grouped intosubsets according to the rail hub regions and timeframes that apply. As we describe in the ImplementationDetails sections, the data integration process managesthese shipment subsets and presents them, togetherwith current information on the appropriate driversand relevant cost and feasibility data, to instances ofthe short haul optimizer (SHO) (step 6).The SHO provides a user interface that displaysshipments and drivers for a dispatching region. Separate tabs for pickups, deliveries, and crosstown movesdisplay key information and allow users to quicklyfilter and sort the data to facilitate dispatch-relatedtasks. The assignment optimization process runs ona schedule for each dispatching region, typically at10-minute intervals. The user interface displays a summary of the solution from the last optimization run581and provides detailed assignment information. It alsoprovides information about infeasible shipments andpotential excessive use of foreign carriers. This enablesthe user to identify potential problems to be addressedon an exception basis. The user is then able to acceptSHO recommendations, and driver-shipment assignments are communicated back to the TMS for dispatchto the driver (steps 7 and 8, respectively).Figure 3 illustrates a tour for a single driver. In thisexample, the first leg is a loaded move, 37 miles fromthe BNSF ramp at Haslett, Texas (near stop 7 on themap in Figure 3) to a customer location in Lewisville,Texas (stop 3). The driver then moves empty 37 milesto the KCS ramp in Dallas, Texas (stop 4) to pick up aloaded container and deliver it to a customer locationin Grand Prairie, Texas (stop 5)—a distance of 29 miles.The driver next moves two miles to location (stop 6)and picks up a loaded container for delivery to theBNSF back in Haslett (stop 7).Literature Review and SolutionMethodology DescriptionA considerable body of literature pertaining to vehiclerouting in general and intermodal freight transportation specifically is available. Caris et al. (2008) discussvarious planning problems in intermodal freight transport and provide an overview of research in this area.Because our discussion focuses on the daily drayageplanning problem of determining driver tours, previouswork on vehicle routing is generally more relevant.Erera and Smilowitz (2008) provide a good overview ofdray planning problems; in particular, they note that theproblem is NP-hard. They describe a column-generationapproach for solving these problems; however, themodeling constructs are different. Both Desrocherset al. (1992) and Savelsbergh and Sol (1998) providerelevant examples of applying column generation tosuccessfully solve vehicle routing problems. Baldacciet al. (2011) give an exact solution technique for solvingpickup and delivery problems with time windowsbased on a branch-and-cut-and-price algorithm; however, exponential time complexity makes this approachimpractical for our problem size and response-timerequirements.Our approach combines a mixed-integer programming (MIP) master problem with subproblems that

582Sun et al.: Optimizing Daily Dray Operations Across an Intermodal Freight NetworkInterfaces 44(6), pp. 579–590, 2014 INFORMSFigure 3: This map illustrates a representative driver tour. The numbers represent stops along the tour.solve resource-constrained shortest-path problemsusing a labeling heuristic. Namboothiri and Erera (2008)propose a similar approach for managing drayageservices in port operations. Their approach, referredto as a layered shortest-path heuristic, uses dynamicprogramming to find new tours that will be time feasible. As Erera and Smilowitz (2008) note, this heuristicappears to perform well, relative to exact methods, forloosely constrained problems. Our case can includea large percentage of narrow appointment windowsand significant variation in shipment transit duration;therefore, we would not expect this approach to workparticularly well. As such, we account explicitly forboth the elapsed time and the accumulated reduced costalong partially generated tours and use this informationto determine those to extend and include in the nextMIP iteration. Our work extends and refines the workof Ileri et al. (2006), particularly with respect to detailsand implementation of the tour generation process. Ileriet al. (2006) generate tours for groups of drivers thatshare similar attributes and insert empty-equipmentmovements required to pick up a shipment during thecolumn generation. Because grouping drivers is practical only for a start-of-day solution, we generate routesfor individual drivers to support our iterative re-solveapproach described in the Implementation Details section.At the beginning, we precompute the set of feasibleassignments of drivers to shipments and transitionsbetween shipments. The column-generation process canthen follow these transitions and correspond to feasibletours that string together the sequential execution ofone or more shipments for a single driver. We generatetwo types of tours—those assigned to foreign carriersand those assigned to the company-managed fleet.The cost and operating characteristics of the formerallow us to precompute the relatively small number oftours that are reasonable for them. For the companyfleet, the number of possible tours is exponentiallylarge. We provide a detailed explanation of how wegenerate these tours in Appendix A.Implementation DetailsIntegration: Data Sources and theTransportation Management SystemThe dray optimization software module (i.e., SHO) sitswithin an integrated software suite that includes ordermanagement, shipment planning and execution, drivermanagement, and financial components. The SHO integrates closely with the TMS, which maintains currentdetails and status information related to shipments anddrivers. To meet the requirement for timely data while

Sun et al.: Optimizing Daily Dray Operations Across an Intermodal Freight NetworkInterfaces 44(6), pp. 579–590, 2014 INFORMSminimizing the performance impact on the TMS, wemaintain data hubs that are refreshed with new information every few minutes to supply current shipmentand driver data to the SHO. The SHO then computesany necessary changes in model data, and accordinglyupdates the tour-generation graphs and mathematicalprogram, removing shipments that no longer requireplanning and tours that are no longer feasible or in play.The SHO is then run with a warm start to produce anew solution.When the user accepts the SHO solution, the corresponding shipment-to-driver assignments are postedback to the TMS, where they are reviewed and communicated to the drivers via integration from the TMS tothe drivers’ in-cab communication system.Objective Function and Cost FactorsThe objective function combines the cost of serving thetours to be executed with penalties for leaving certainshipments unassigned. If a shipment’s time windowsfall completely within the specified time horizon, thepenalty cost is set high to ensure execution. In othercases, a modest penalty is imposed to encourage theachievement of various operational objectives.The cost of executing a tour for company driversincludes driver pay, fuel costs, driver delays, stop-off(extra-stop) charges, and equipment depreciation. Foreign carrier costs are based on contractual agreementsthat include these various costs in the contracted rates.Other factors, including tour robustness, chassis rentalcost, ramp storage cost, and equipment utilization, arealso considered.In the Extensions section, we briefly discuss fleetsize optimization. In the present operations, foreigncarrier coverage varies from 5 to 15 percent on a dailybasis, with the per-shipment cost premium averagingabout 60 percent. Although this cost differential wouldseem to create a strong incentive to increase the sizeof the company fleet, an oversized fleet can quicklydegrade productivity because of demand variation andgeographic imbalance.Driver Groups and Work SchedulesSeveral groups of drivers work within typical drayoperations. Company drivers are company employeesand have pay packages that include fixed and variablecompensation components. ICs are similar to company583drivers; however, they are responsible for their owntractors and have pay agreements that reflect this. Bothcompany and IC drivers are part of either a local orregional fleet. Local drivers transport shipments up to amaximum distance (typically 150 miles, but it can varyby hub region) and return home each day. Regionaldrivers transport shipments subject to a minimumdistance (typically 100 miles, but it can vary by hubregion) and are sometimes away from home for one ortwo nights. These drivers are subject to standard U.S.Department of Transportation hours-of-service rulesand must take a 10-hour sleep break after no morethan 11 driving hours or 14 total work hours.Generally, when a foreign carrier is selected to movea shipment, we incur the full round-trip cost, but mayaccept a two-shipment tour if it can be executed withina specified transit constraint. Therefore, the number ofpotential carrier tours is small enough to enumerate inadvance.Container ManagementA critical requirement of intermodal freight transportis ensuring that adequate numbers of containers areavailable where and when they are needed. This issuehas two important components, as we discuss next.(1) Addressing imbalance in freight flows acrossthe rail network. As freight flows across our 24-hubrail network, containers accumulate in regions withnet inbound flow and become depleted in those withnet outbound flow. This necessitates repositioningempty containers among the hub regions on a regularbasis. The problem of determining the appropriateempty-repositioning moves to achieve the desired hubinventory levels is handled by a reasonably straightforward model and corresponding subsystem that areoutside the scope of this discussion. To facilitate thisrail-based repositioning at the local level, we need tomove empty containers between rail ramps and customer locations or container storage yards. We currentlyplan these moves outside the SHO process; however,we plan to incorporate them into the optimizationprocess.(2) Meeting specific requirements at individual customer locations. In addition to executing empty shipments, drivers must frequently make intermediatestops to acquire or dispose of containers to arrive at thenext location with (without) empty containers, based on

584Sun et al.: Optimizing Daily Dray Operations Across an Intermodal Freight Networkcustomer requirements. As currently implemented, thesystem does not explicitly evaluate and plan these stops;instead, it introduces a penalty cost and time delay intothe tour to estimate the impact of any required detour.Although we have designed model enhancements toexplicitly address container repositioning, we have notyet implemented the required data integration into theTMS. We are evaluating whether the resultant solution quality improvement would justify the additionalproblem complexity and solve-time impact.Time Horizon and Re-Solve FrequencyThe drayage optimization problem is formulated andsolved independently for each rail hub region. Problemsare formulated with a finite time horizon, currentlyset for 36 hours, to allow us to look ahead throughthe following day. New information about cancellations, additions, changes to shipments, and updatesto driver locations and availability arrives continuously. To account for this information flow, we updatethe problem and re-solve it frequently. The re-solveinterval is scheduled by region and controlled by theuser, with 10 minutes as a typical value. Successivere-solves are run from a warm start, preserving feasible columns from the previous solution and reusingthe tour-generation graphs with suitable adjustments.A cold start is required very rarely, usually only whena new rail hub region is instantiated. In this case, weconstruct the initial problem by enumerating the set offeasible single-shipment tours.Additional Model AttributesTo obtain solutions that are both implementable androbust in the face of operational variability and specificcircumstances, we capture and apply a number ofadditional modeling attributes. These conditions areembodied in a collection of business rules, data filters,conditional time adjustments, and penalty and (or)bonus cost factors. To effectively implement these, wehave developed several ancillary tools, including (1) adatabase that supports clauses, parameters, and factorsto capture these attributes, (2) a preprocessor to convertthese database representations into efficient in-memorystructures, and (3) a functional operator that appliesthis information, as appropriate, during the graphconstruction and tour-generation processor. Althoughthe details of these components are beyond the scopeInterfaces 44(6), pp. 579–590, 2014 INFORMSof this paper, we will briefly note a few of them, asfollows:Tractor ruleMaintains tractor-location feasibilityconditions relative to tractor types.Drop pickEnforces location-specific sequencing.HazmatEnforces hazmat-certificationfeasibility.Location delay Specifies time delays for certainlocation combinations.OutgateIncreases outgate time for certainshipments.Last loadAllows for shipment carryover to nextshift.Priority apptPads times for priority shipment stopsto decrease fail probability.Priority stopApplies stop-time penalty toencourage earliest delivery.Time WindowsRailroad train schedules dictate a portion of the timeconstraints associated with a dray shipment. For eachtrain, the railroad specifies a cutoff time, which can varyfrom two to 24 hours before train departure, by whichoutbound containers must arrive at the rail ramp fortransfer from chassis to railcar. For the correspondingdestination ramp, the railroad announces a groundingtime that indicates when containers from a specifiedtrain are available for pickup at the ramp. Cutoff timesare usually stable; however, grounding times are subjectto periodic revision during transit because a train maybe subject to various delays.Conversely, the time constraint for the customerside of dray shipments varies according to customerand (or) location requirements. Some shipments mayspecify prearranged appointment times with little orno tolerance; others may specify an interval window;and some are open-ended with only no-sooner-than orno-later-than directives.Rush-Hour Transit Time AdjustmentsThe geographic areas covered by our dray operationsoverlap urban areas and are subject to considerabletraffic congestion variation during the day. To producesolutions that are both implementable and efficient,transit times used in the optimization process mustaccount for time-of-day variations. Arcs and nodesare repeatedly explored during the column-generation

Sun et al.: Optimizing Daily Dray Operations Across an Intermodal Freight Network585Interfaces 44(6), pp. 579–590, 2014 INFORMS1.0Speed factor0.90.80.70.60.504812162024ShipmentsTotalMust move todayFrom customer to rampFrom ramp to customerOther (repositioning)Average distanceDriversRegionalLocalRail rampsCustomer locations407207180 (44%)225 (55%)2117 miles145906192Time of dayTable 1: This table shows details for a typical problem instance.Figure 4: This graph shows a typical speed-reduction factor for urban areasby time of day.To illustrate the computation details of the SHO, weshow problem-size data for a large representative drayscheduling problem in Table 1, and then summarize thecorresponding solution and performance characteristics.For reference, we provide hardware and softwareplatform details in Appendix 678Columns generated (00s)Results and Computational Performance50454035302520151050370Objective cost (000s)phase and each exploration may induce a differentstart time. Consequently, the speed of the transit timecalculation or retrieval plays a significant role in overallcomputational performance. To achieve a good tradeoff between performance and accuracy, we precomputeand cache data that are used to quickly estimate transittimes. We begin by segmenting each dray operationsregion into a rush-hour sensitive urban and a rushhour indifferent rural area. Using historical data andnonparametric regression, we can generate a rushhour profile for each urban area; in the example inFigure 4, the x-axis specifies a start time and the y-axisa speed-discount factor.For each arc (i.e., route between locations), we identify the set of segments determined by intersecting theroute with the urban and rural areas and then maintain a list of tuples, 84t1 1 p1 54t2 1 p2 51 0 0 0}, where ti is therush-hour-free transit time and pi is the profile numberassociated with the segment or 0, if the segment lieswithin a rural area. During the search process, wequickly calculate transit times for segments by applyingthe discount (to standard speed) corresponding to the(simulated) start time of the segment.The total processing time for the solution was 119 seconds. Initial graph construction consumed 2.68 seconds,optimization processing time was 88.5 seconds, andthe remaining time was associated with data movement and other overhead. During graph construction,roughly 100,000 arcs were generated to capture feasibility and precedence relationships between shipments orshipments and drivers.Figure 5 shows the reduction in the linear programming (LP) objective value and the number of newcolumns generated at each successive iteration. Iteration final (9) represents the integer programming (IP)solution of the last master problem (Iteration 8).Figure 6 shows the time spent in the columngeneration phase and LP-IP solver phase for eachiteration.We also observed SHO performance across a widerange of problems. In Figure 7, we plot optimizer processing time as a function of the number of shipmentsfor 6,889 problem instances across 29 distinct problemFinalIterationFigure 5: This chart shows the objective value and columns generated periteration.

Sun et al.: Optimizing Daily Dray Operations Across an Intermodal Freight NetworkTime (seconds)586Interfaces 44(6), pp. 579–590, 2014 INFORMS181614121086420Col genLP/IP123456789IterationFigure 6: This chart shows the processing time for the LP-IP and columngeneration phases at successive iterations.settings. Note that the vertical processing-time axis isdisplayed in logarithmic scale. As we would expect,the fit line, given by y 105e0001x with R2 00915, showsa strong exponential correlation of processing time tothe number of shipments.Bus

Intermodal Operations The flow of information, with corresponding processing and decision steps, is shared across a set of software modules (see Figure 2). Intermodal freight orders are initially captured in the order entry system via either electronic transfer from a customer or direct entr