Bulk Plan Multi-stop Shipment Clustering Merge Algorithm

The clustering merge algorithm is selected by setting the multi-stop logic configuration parameter, MULTISTOP CONSOLIDATION ALGORITHM TYPE, to Clustering Merge.

While most of the OTM multistop algorithms merge only two shipments at a time (so that combining N shipments into one shipment would take N-1 merge operations), this algorithm has the capability to combine any number of shipments in a single merge operation. This helps achieve significant performance improvement over all other algorithms, particularly in creating multistop shipments with a large number of stops.

OTM provides two clustering building algorithms: Legacy Cluster Building Algorithm and MIP Cluster Building Algorithm.

There are related Multistop Cluster Merge parameters in Logic Configuration - Multistop parameters.

There are related glog.business.consolidation.multistop.clusterMerge in glog.business Properties as well as the property glog.business.consolidation.multistop.doSavingsMergeAfterClusterMerge.

Legacy Cluster Building Algorithm

The legacy cluster building algorithm is where OTM implements the Sweep algorithm.

The Sweep algorithm is appropriate for multistop scenarios in which shipments will have one pickup stop and many delivery stops, or many pickup stops and one delivery stop. Under certain simplifying assumptions, this algorithm may perform better than other algorithms. The assumptions include that order time windows and compatibilities do not determine how orders are consolidated onto shipments.

 

For example, in the single pickup and multiple delivery scenario, this algorithm first forms clusters of delivery stops, and then merges the delivery stops into a single shipment for each cluster.  Note that these clusters are chosen such that all the delivery stops in a cluster would combine to form one shipment.

The clusters are formed using a Sweep algorithm, which sweeps clockwise from the single pickup location, and accounts for equipment capacity in terms of weight, volume, and Equipment Reference Unit.

MIP Cluster Building Algorithm

The MIP Cluster Building Algorithm is a more sophisticated cluster forming algorithm in the sense that it considers all the compatibilities among direct shipments and supports more general multiple pick-up multiple drop off scenario. More importantly, it provides much more flexibility on how the cluster is formed by using the concept of similarity.

Similarity between two shipments

The similarity between two shipments is determined by the linear combination of the certain weighted criteria. OTM takes distance saving, time window, rate, equipment and priority into consideration. These are defined by Multistop Logic Configuration parameters. You should not enable all the criteria (i.e., should not set a positive value for the weights): the weights should be set based on business scenarios. The parameters are

• MULTISTOP DISTANCE METRIC WEIGHT
• MULTISTOP EQUIPMENT METRIC WEIGHT
• MULTISTOP PRIORITY METRIC WEIGHT
• MULTISTOP RATE METRIC WEIGHT
• MULTISTOP TIME WINDOW METRIC WEIGHT

The following examples provide insight into the use of these criteria.

Scenario 1: Cluster based on Time

The user has three types of orders: must-go (late delivery date is the same as the early pick-up date), should-go (late delivery date is one or two days after early pick-up date) and can-go (late delivery date is four or five days after early pick-up date). The business requirement is to put must-go orders into one shipment, and, if there is equipment capacity remaining, put some should-go or can-go orders into the shipment as well.

OTM could realize the requirement by setting MULTISTOP TIME METRIC WEIGHT to be 1 and MULTISTOP DISTANCE METRIC WEIGHT to be 0.2. Thus, two direct shipments with more similar pick-up time windows would be considered more similar than two direct shipment with more different time windows, in spite of greater geographic closeness of the delivery stops. However, among shipments with the same time window, the geographically closer shipments should still be considered as more similar.

Scenario 2: Cluster based on Compatible Equipment

The user needs to send goods from one depot to multiple destination in one region, and has two types of trucks, big trucks and small trucks, across that region. The challenge here is that certain locations can only handle small trucks due to facility constraints. The business requirement is to build multi-stop shipments based on the destination location equipment constraint, i.e. build small truck multi-stop shipments to send goods for all small truck locations, and build large truck multi-stop shipments for the remaining.

OTM could realize the requirement by setting MULTISTOP EQUIPMENT METRIC WEIGHT to be 1 and MULTISTOP DISTANCE METRIC WEIGHT to be 0.2. Thus, two small truck shipment would be considered as more similar than one small truck shipment and one large truck shipment. Distance metric is still considered for building multi-stop shipment with good distance savings.

Scenario 3: Cluster based on Compatible Rate

The user has two nearby regions, and has one carrier for each region. Though the rate of the multi-stop shipment is determined by the source and destination locations, you still do not want to build shipments that go back and fourth between two regions.

OTM could realize the requirement by setting MULTISTOP EQUIPMENT RATE WEIGHT to be 1 and MULTISTOP DISTANCE METRIC WEIGHT to be 0.2. Thus, two shipments that are within one region is more similar than two shipments across two regions. Again, distance metric is still considered for building multi-stop shipment with good distance savings. Note that, in theory, the MIP Cluster Algorithm can handle up to one thousand direct shipment at the same time.

Multistop Cluster Merge Strategy

The cluster merge algorithm can be divided into two major steps: forming clusters and building multi-stop shipments for those clusters. In the multi-stop shipment building process for a cluster, there could be cases where direct shipments fail to get merged onto the multi-stop shipment for that cluster. The parameter MULTISTOP CLUSTER MERGE STRATEGY is used to configure how OTM handles those failed-to-merge direct shipments.

Cluster Merge Parameters Tuning

The cluster merge algorithm would significantly reduce the run time. However, in order to make sure it also produce high quality solutions, cluster merge parameter tuning is required.

The multi-stop shipment building process can be divided into two parts: the cluster merge process and the savings merge process. The cluster merge mimics the nature of clustering problem that occur during the assignment decision based on similarity between a single shipment node and the shipment which serves as the cluster center candidate. Thus, OTM cannot do sequence related feasibility check during the assignment process. Even if the shipment building process could separate those infeasible shipment nodes, the general solution quality would not be satisfying. This section provides suggestions about how to tune cluster merge parameters.

The system suggests to set the parameter MULTISTOP USE SAVINGS MERGE AFTER CLUSTER MERGE to be "3. Use concurrent saving after cluster merge" to make the multi-stop shipment building process robust. In order to observe the intermediate result of clustering merge you need to set the parameter MULTISTOP USE SAVINGS MERGE AFTER CLUSTER MERGE to be "1.Parameter tuning". Then, you can focus on the other parameters MULTISTOP DISTANCE METRIC THRESHOLD, MULTISTOP CLUSTER MERGE MIP GENERAL PENALTY, and similarity metric weights.

Let's look at two scenarios to understand cluster merge parameter tuning:

Scenario 1: A complex multi-stop shipment

The business requirement is when a shipment or locations has strict time window constraints; there are multiple pick-up and multiple drop-off locations or when a multi-segment multi-stop shipment is desired, the strategy is to use cluster merge to build multiple small clusters, then use savings merge to assemble them into a long multi-stop shipments.

OTM could realize the requirement by setting the value of parameters MULTISTOP DISTANCE METRIC THRESHOLD and MULTISTOP CLUSTER MERGE MIP GENERAL PENALTY to a relatively low value, i.e. MULTISTOP DISTANCE METRIC THRESHOLD to be 0.3 and MULTISTOP CLUSTER MERGE MIP GENERAL PENALTY to be 0.5.

Scenario 2:  A simple multi-stop shipment

The business requirement is when there is a single pick-up and multiple drop-off or single drop-off and multiple pick-up scenario and a shipment time window is open, the strategy is to use cluster merge to build big clusters and then use savings merge to insert the remaining left over direct shipments into those big multi-stop shipments.

OTM could realize the requirement by setting the value of parameters MULTISTOP DISTANCE METRIC THRESHOLD and MULTISTOP CLUSTER MERGE MIP GENERAL PENALTY to a relatively high value, i.e. MULTISTOP DISTANCE METRIC THRESHOLD to be 0.5 and MULTISTOP CLUSTER MERGE MIP GENERAL PENALTY to be 10.