Bulk Plan Tuning Multi-Stop Shipment Logic

Oracle Transportation Management provides several algorithms for multi-stop shipment creation. In order to tune multi-stop shipment creation for solution quality or performance, it is important to understand various multi-stop algorithms in Oracle Transportation Management and their internal workings at a high level.

Oracle Transportation Management offers these major algorithms for building multi-stop shipments:

• Clustering Merge Algorithm: Forms clusters of input shipments and merges together the shipments in each cluster.
• Conopt Merge Algorithm: Splits input shipments and repacks their contents to form tightly-packed multi-stop shipments.
• Savings Algorithm: Constructs shipments by merging two shipments at a time.
  • Concurrent Savings: Several shipments are formed simultaneously.
  • Look-Ahead Savings: Same as Concurrent Savings, but with a modified policy for choosing the next best pair to combine.
  • Sequential Savings: Constructs one shipment at a time until that shipment is completely formed.
  • Iterative Savings: Runs multiple iterations of Concurrent Savings algorithm to provide higher-quality multistep solutions.
• Column Generation Algorithm: Using repetitive savings algorithm solves, this scheme generates several shipments, and the best set of shipments is obtained through a Mixed Integer programming Solver.
• Complete Enumeration Algorithm: Creates all combinations of input shipments and selects the best set of shipments using a Mixed Integer Programming Solver.

The input to these algorithms is a set of direct shipments. The goal of the multi-stop logic is to consolidate these shipments into multi-stop shipments.

Shipment Pairing

For all of the multi-stop shipment algorithms, a shipment pairing logic is used to consolidate two shipments into one. The shipment pairing is used both for evaluating the savings, as well as, committing a particular pair and combining the shipments in the pair. The flow chart below highlights various steps in the pairing process: The shipments are paired to construct a paired shipment. Then stop sequences are generated using algorithms. Next the best cost sequence is selected after evaluating equipment, cost and drive feasibility to create a paired shipment.

Constructing Paired Shipment

This step takes two shipments and constructs a paired shipment. Stops from the individual shipments are added to the paired shipment. Stops having the same location are merged together into one. There are times when two stops at the same location must be kept separate. For example, when you drop off and pickup at the same location, you may wish to have two separate stops, one for drop off and one for pickup.

Prior to pairing the two shipments, there are several constraints that are checked to ensure that the two shipments can be paired together:

• Can the combined shipment’s weight and volume fit the equipment’s weight and volume capacities?
• Are the orders that are being placed into the equipment compatible with each other?

In addition to the constraints, there are also several quick checks to eliminate certain less than optimal combinations in order to reduce the overall run time. The distance-based and time-based tuning parameters described below help in reducing the number of shipment pairs to evaluate.

Distance-Based Parameters

There are several multi-stop logic configuration parameters that can be used to limit the number of shipment pair computations that the algorithm performs. By eliminating the number of shipment pairs to evaluate, the run times can be drastically reduced. While mainly used for improving performance, these parameters also help solution quality by clustering the stops close to each other. For example, setting the MULTISTOP MAX RADIUS FOR DELIVERIES to 50 miles will cluster all the delivery stops to within a 50 mile radius of the farthest delivery point.

• MULTISTOP MAX DISTANCE BETWEEN DELIVERIES = 50
• MULTISTOP MAX DISTANCE BETWEEN PICKUPS = 50
• MULTISTOP MAX RADIUS FOR DELIVERIES = 50
• MULTISTOP MAX RADIUS FOR PICKUPS = 50
• MULTISTOP MAX RADIUS PERCENTAGE FOR DELIVERIES = 25
• MULTISTOP MAX RADIUS PERCENTAGE FOR PICKUPS = 25

The MULTISTOP MAX RADIUS PERCENTAGE FOR PICKUPS and MULTISTOP MAX RADIUS PERCENTAGE FOR DELIVERIES parameters work well for situations when you have long stem miles and several pickups or deliveries clustered together. For example, consider a pickup at a distribution center and traveling over 500 miles and delivering to 3 or 4 locations. Setting the MULTISTOP MAX RADIUS PERCENTAGE FOR DELIVERIES to 10% in this case, ensures that all the deliveries are within 50 miles of each other.

Note: These parameters also exist on itineraries. However, since the multi-stop logic in certain points in the algorithm does not have access to an itinerary, the parameters defined on the multi-stop logic configuration are used. If the itinerary is available, the parameters from the itinerary are used instead. As a result, it is recommended that you set these parameters on the itinerary, as well as, on the multi-stop logic configuration.

The parameter IGNORE PROXIMITY CHECKS FOR RETURN TO SOURCE allows the distance or time from the source location to the service area to be longer than any specified limit. When this parameter is set to true, while departing or returning to the shipment source location, OTM will not perform checks for maximum distance or time between pickups or deliveries.  

The parameter MULTISTOP MAX DISTANCE BETWEEN STOPS specifies the maximum distance limit between certain pair of consecutive stops in a multi-stop shipment. This parameter will work only if IGNORE PROXIMITY CHECKS FOR RETURN TO SOURCE is set to true.

 

The parameter MULTISTOP MAX DISTANCE BETWEEN CO-LOCATED STOPS specifies the maximum distance within which two locations can be considered co-located. The default is 0, so the co-located multistop logic is not used in this case.

Time-Based Parameters

The time-based multi-stop logic configuration parameters also help reduce the computations by looking at the times on the shipments. In addition, the parameters will cluster the orders together that are close to each other in time.  

• MULTISTOP MAX TIME BETWEEN DELIVERIES = 60 Minutes
• MULTISTOP MAX TIME BETWEEN PICKUPS = 60 Minutes

Generating Stop Sequences

Once the consolidated shipment is formed, the stops must be sequenced so that the total distance (or total cost) is minimized. Oracle Transportation Management provides several multi-stop sequencing algorithms for you to choose from. The available sequencing algorithms are, from fastest to the highest quality results:

• 2-Opt: Iteratively generates new sequences by swapping two links.
• 3-Opt: Iteratively generates new sequences by swapping three links.
• Insertion: Inserts the stops of one shipment into the other shipment without distorting the original sequence of either shipment.
• MIP: Provides solutions to the sequencing problem by solving its MIP formulation.
• Time Window MIP: Provides solutions to the sequencing MIP formulation by considering additional time constraints involving time windows, location calendars, etc.
• Enumeration: Generates sequences by creating all permutations of the stops.

2-Opt and 3-Opt

The 2-opt and 3-opt algorithms run fast by considering only a subset of all the sequences. With these algorithms, it is possible that some good stop sequences are not generated.

Insertion

Insertion retains the original stop sequences of the first and second shipment.

Enumeration

If a shipment has a small number of stops, say 3 or 4 stops, then the enumeration algorithm works well and produces highest quality sequences. However, the enumeration algorithm does not scale well for shipments with a large number of stops (greater than 8 stops).

MIP

In the MIP Sequencer algorithm, OTM solves a mixed integer programming (MIP) formulation of the stop-sequencing problem (which is essentially a travelling salesman problem). This algorithm provides high quality sequences (as good as Complete Enumeration), and it also runs much faster than the Enumeration algorithm for a high number of stops.

Time Window MIP

In the time window MIP algorithm, OTM takes time constraints into consideration (location calendar, order pick-up & delivery date). This algorithm can provide the optimal solution, but also can be time consuming for high number of stops.

Oracle Transportation Management provides the ability to choose different algorithms based on the number of shipments. The following multi-stop logic configuration parameters control the sequencing algorithms with default values. With the default settings, the 2-Opt algorithm will be used for shipments with 8 or more stops and the Enumeration algorithm for shipments with 4 or fewer stops. For anything in between, the 3-Opt algorithm will be used.

• MULTISTOP SEQUENCING HIGH STOPS MINIMUM = 8
• MULTISTOP SEQUENCING LOW STOPS MAXIMUM = 4
• MULTISTOP SEQUENCING ALGORITHM = 3-Opt
• MULTISTOP SEQUENCING ALGORITHM FOR HIGH STOPS = 2-Opt
• MULTISTOP SEQUENCING ALGORITHM FOR LOW STOPS = Enumeration

Other Sequencing Related Parameters

There also several other sequencing related multi-stop logic configuration parameters that control how the shipment sequences are formed.

MULTISTOP QUICK HOS CHECK IN SEQUENCING: This multi-stop logic configuration parameter provides the option of doing quick HOS check while generating multistop sequences. Generated sequences can be infeasible due to various time-constraining factors such as HOS Rules. OTM can improve performance and solution quality by throwing out time-infeasible sequences during the sequence generation step itself by running a quick time-feasibility check on HOS. This parameter is helpful if there is a maximum duration for the shipment.

MULTISTOP SEQUENCE COST FOR DISTANCE: This multi-stop logic configuration parameter specifies the distance based cost to be considered during sequence generation.

MULTISTOP SEQUENCE COST FOR TIME: This multi-stop logic configuration parameter specifies the time based cost to be considered during sequence generation.

Following are a few examples using the two cost parameters above in multistop sequencing:

1. Consider only distance: MULTISTOP SEQUENCE COST FOR DISTANCE = 1.0, MULTISTOP SEQUENCE COST FOR TIME = 0.0
2. Consider only time: MULTISTOP SEQUENCE COST FOR DISTANCE = 0.0, MULTISTOP SEQUENCE COST FOR TIME = 1.0
3. Consider distance and time costs (e.g. distance cost = 5 per unit distance and time cost = 100 per hour): MULTISTOP SEQUENCE COST FOR DISTANCE = 5.0, MULTISTOP SEQUENCE COST FOR TIME = 100.0

MULTISTOP SEQUENCING ALLOW PICKUP REVISIT and MULTISTOP SEQUENCING ALLOW DROPOFF REVISIT: These multi-stop logic configuration parameters allow a pickup or drop off location to be revisited more than once. This is very useful in situations where a particular distribution center (DC) has more than one truckload worth of orders and these orders are shipped by having the driver perform multiple trips on the same shipment.

MULTISTOP START OR END AT DEPOT REWARD: This multi-stop logic configuration parameter encourages shipments to start (or end) at a pickup (or drop off) location that is also a depot. In the figure below, the DC is marked as both pickup and delivery depot.

When a shipment is formed by consolidating orders A and B, the logic does not take into account depot locations. So, the following two sequences are evaluated and the second one will be selected as it covers less distance.

• DC – A – B – DC
• B – DC – A

Later, the logic adds the depot locations to the selected sequence and the second sequence now looks like this: Depot (DC) – B – DC – A – Depot (DC), which incurs the two extra empty moves. By encouraging the depot pickups and drop offs as the first and/or last locations, the first option is selected as it contains the first stop and last stop at the depot location.

MULTISTOP USE RETURN MILES IN SEQUENCING: This multi-stop logic configuration parameter considers the return miles to the first stop when finding the least distance sequence. This is useful if you know that the driver will return to the start location.

Multistop Use Unmerged Stops in Sequencing Logic

The multi-stop logic will always combine two stops if they are at the same location. In some instances, it may be useful to keep the stops separate, as in multi-segment shipments or when dealing with situations requiring revisits to the same stop. Even though the sequencing logic keeps the stops separate, the stops get merged together into one if two stops of the same type (pickup or delivery) and at the same location are next to each other in the final sequence. Keeping the stops separate is controlled via the multi-stop logic configuration parameter MULTISTOP USE UNMERGED STOPS IN SEQUENCING LOGIC.

Last in First out (LIFO)

LIFO means that the last order loaded into the equipment must be the first one to be removed from the equipment. LIFO influences the stop sequences in that it eliminates the non-LIFO sequences being considered for evaluation. The multi-stop logic configuration parameter MULTISTOP USES LIFO PICKUP DROPFF is used to control this behavior. With LIFO on, you can still get shipments with multiple pickup and multiple drop off stops.

Multistop Sequencing in Multi-Segment Shipments

A multi-segment shipment is a multistop shipment where the equipment is emptied at least once before the final delivery. Each segment in a multi-segment shipment is a continuous part in the journey of the shipment where the equipment is non-empty.

The following figure shows a 2-segment shipment that picks up 3 orders at a distribution center (DC) and delivers these orders at different drop-off locations. Then the shipment equipment remains empty until it picks up the first of the 2 back-haul orders to be delivered back to the DC.

The multistop logic in OTM has the capability to create multi-segment shipments. To be able to create multi-segment shipments in OTM, you should set the value of the parameter MULTISTOP MAXIMUM SEGMENTS PER SHIPMENT to a value greater than 1. The rate offering to be used should also have “Max Num of Shipment Segments” set to a value greater than 1.  

Additionally, it is usually very helpful to have the following multistop settings for multi-segment shipments.

MULTISTOP USE UNMERGED STOPS IN SEQUENCING LOGIC = true

MULTISTOP SEQUENCING ALLOW PICKUP REVISIT = true

MULTISTOP SEQUENCING ALLOW DROPOFF REVISIT = true

The following figure shows an example of a multi-segment shipment that is shaped by equipment capacity and Hours of Service (HOS) constraints and is also LIFO (last-in-first-out) compatible. The shipment makes multiple round trips from a common distribution center (DC) location, making deliveries and pickups in a LIFO manner on each trip. Note that the length of every individual trip is limited by equipment capacity though HOS limit could allow the shipment to cover all stops in one single trip.

In shipment planning scenarios like this, it is typically very challenging to create multi-segment shipments involving a high number of stops and segments (for example more than 15 stops is high). That is because, in the multi-segment case, it is not easy to find feasible stop sequences satisfying various constraints such as equipment capacity, Hours of Service (HOS), LIFO stop sequencing etc. In this case, using the following options can be helpful.

Quick Checks in Sequencing

Multistop logic provides the options for performing various quick checks in sequencing so that sequences failing in these checks can be identified and rejected during sequence generation. Some of these important quick checks can be turned on through the following parameters.

CHECK EQUIPMENT CAPACITY IN SEQUENCING

CHECK ITEM COMPATIBILITY IN SEQUENCING

CHECK LIFO IN SEQUENCING

MULTISTOP QUICK HOS CHECK IN SEQUENCING

Note that these additional checks aim to improve multistop shipment quality, but that improvement may come at the expense of additional run time in the multistop logic.

DC Based Multi-segment Sequencing

This DC based multi-segment sequencing logic is suitable for planning scenarios such as the above example. This logic can be turned on by setting the parameter INSERT DC STOPS AFTER SEQUENCE GENERATION to true.  

This logic only works for the case where there is only one source DC and one destination DC (both the source and destination DCs can also be the same location). The logic internally identifies a location pair as source DC and destination DC only if all the orders either start from the source DC or end with the destination DC.

This logic tries to reduce workload for sequencing logic by identifying and eliminating the frequently occurring DC stops in the beginning and later inserting them appropriately into the generated stop sequences. Further, while inserting the DC stops back into a stop sequence, feasibility quick checks can be performed if specified.

Guiding Multi-Stop Consolidation

OTM users may want to encourage certain orders to end up on the same multi-stop shipments for business reasons rather than cost.  As discussed elsewhere, Ship With Group functionality is used to encourage orders with the same Ship With Group value to consolidate onto the same multi-stop shipments. Multi-stop logic has a couple of other options for guiding order consolidation that happen before the regular multi-stop logic.

Combining Inbound and Outbound Shipments

The logic parameter MULTISTOP COMBINE INBOUND AND OUTBOUND SHIPMENTS enables logic that identifies orders going from a hub to a delivery location and corresponding orders coming back from the delivery location to the hub, and combines them onto the same shipment. This logic is encouraged to combine these orders onto the same shipment regardless of cost.

Using this logic makes it easier to ensure that these outbound-inbound opportunities are identified, instead of relying simply upon cost savings calculations to discover them in regular multi-stop consolidation.

Identifying Co-Located Stops

The logic parameter MULTISTOP MAX DISTANCE BETWEEN CO-LOCATED STOPS enables logic that encourages orders with co-located stops to be combined onto the same shipment. Co-located stops are locations that are different OTM locations but are very close together, for example, different locations defined for the same large facility, or different locations along the same stretch of road.

The parameter indicates which locations should be considered co-located, and the logic encourages orders picked up at or delivered to co-located stops to be combined onto the same multi-stop shipment. The logic also encourages the sequencing logic to sequence these co-located pickups and deliveries next to each other.

Topping off Multi-stop Shipments

OTM can use top-off orders to fill under-utilized shipments. Top-off orders are not consolidated with core orders (i.e. orders that are not top-off) while building direct shipments. However towards the end of multi-stop processing, in the multi-stop top-off pass, top-off shipments (i.e. shipments containing only top-off orders) are brought in for consolidation with the consolidated core shipments.

The multi-stop logic configuration parameter USE CONOPT MERGE IN TOP-OFF PASS provides an option to use the Conopt Merge algorithm for shipment consolidation in the top-off pass. Note that the main objective in the top-off pass is to move contents of the top-off shipments to the consolidated core shipments to utilize their equipment as much as possible. You have the option of using the Conopt Merge algorithm in this step (which does a better job than the Savings based algorithms) to achieve high equipment utilization. See current limitations of Conopt Merge algorithm.

The multi-stop logic configuration parameter IGNORE CAPACITY OVERRIDES IN TOP-OFF PASS provides an option to ignore capacity overrides on the itinerary legs during shipment consolidation in the top-off pass. It makes sense to use this option only when the enforced capacity overrides are required, only until the top-off stop which should also be the last pick-up stop.

Top-off Scenario Example 1

Consider the planning scenario on a 2-leg itinerary as shown in the figure below. There are 4 core orders of 20,000 LB each, with 4 different source locations in a city region and a common destination at a port of discharge (POD). Only one type of equipment is available with a load capacity of 50,000 LB.

In this situation, multi-stop shipments will arrive at the port of loading (POL) location and continue on the ocean leg with under utilized equipment (10,000 LB capacity still available). To avoid this waste of equipment capacity, first leg shipments with unused capacity are brought to a top-off location (T in the above figure) where a top-off order of 20,000 is available for pick-up. In this case, as shown in the following figure, planning with the setting “USE CONOPT MERGE IN TOP-OFF PASS = true” will result in the 2 fully-utilized shipments on the first leg.

Top-off Scenario Example 2

The planning scenario in this example is shown in the following figure and is similar to Example 1. The main difference in this case is that a street legal load limit of 40,000 LB is imposed in the city region. This is defined as an equipment capacity override on the first leg. However, the full equipment capacity of 50,000 LB is allowed between the top-off location T and POL as T is strategically located very close to POL.

Suppose there are 2 "core” orders of 60,000 LB each, with 2 different source locations in the city region and a common destination at a port of discharge (POD). In this situation, multi-stop shipments will arrive at the POL location and continue on the ocean leg with underutilized pieces of equipment (with at least 10,000 LB capacity still available). To avoid this waste of equipment capacity, a top-off order of 30,000 LB is available for pick-up at T. In this case, as shown in the following figure, planning with the setting “USE CONOPT MERGE IN TOP-OFF PASS = true” and “IGNORE CAPACITY OVERRIDES IN TOP-OFF PASS = true” will result in 3 fully-utilized shipments on the first leg.

Note: Typically, top-off orders would be used to fill under-utilized shipment with core orders, rather than to create top-off-only shipments.  However, for a scenario in which top-off-only shipments are allowed, turning on the multi-stop logic configuration parameter TOP-OFF DISABLE SAME OD PAIRING may allow better utilization on top-off-only shipments. This parameter should not be turned on if top-off-only shipments are not desired.