PREPROCESSING TECHNIQUE TO SPEED THE SOLVING TIME OF THE NETWORK DESIGN PROBLEMS (CYLINDER SUPPLY CHAIN LOGISTICS) BY AGGREGATING CUSTOMERS THROUGH A DENSITY-BASED METHOD
Publication Date: 2017-Aug-08
The IP.com Prior Art Database
PREPROCESSING TECHNIQUE TO SPEED THE SOLVING TIME OF THE NETWORK DESIGN
PROBLEMS (CYLINDER SUPPLY CHAIN LOGISTICS) BY AGGREGATING CUSTOMERS THROUGH A
The goal of this technique is to simplify the network transportation model by reducing the number of final customers into the model. This simplification considerably reduces the number of variables and therefore speeds the solution time.
In the original model of OPTIPLANT, to each customer are associated a number of variables equal to the number of potention locations. This could cause a reduction of the solving time in case of a high number of customers. Moreover, the customer aggregation is not easy to set up.
This technique enables a "zero parameters" customer aggregation and enables a more easy configuration of the solver. Moreover, this simplifcation reduces considerably the umber of variables and terefor speds the solution time.
Indeed, in the original model, to each customer are associated a number of variables equal to the number of potential location.
The main idea is to aggregate customers that are geographically near to a one or several “meta-customers” that have has cylinder demand the sum of the cylinder demand of the original.
First, we choose the minimum number of points that compose a “metacluster”. This parameter is named MinPoints. MinPoint is choosen depending on the number of total customers.
Then, for each customer c, we compute the set U(c) of the distance of the nearest Minpoints customers. Then, for each customers c, we takes the distance of the farest customers in U(c), that is named MinPoint_Dist(c).
Then we compute the distribution of the values of MinPoint_dist. In this distribution, we extract at regular intervals 20 values of MinPoints_dist. These 20 values are named MinPoints_dist*.
For each MinPoints_dist* value we apply a clustering technique known as DBSCAN (density-based spatial clustering of application with noise).
This technique is based on the concept of “density-reacheable” set, in relationship with a predefined distance DIST, named Q(DIST), defined as follow:
è By definition we consider as “Directly density-reachable” to a customer p, any customer that is distant from p less than the predefined distance DIST. We name this set as P.
è Then we compute all the customer that doesn’ belong to P that are “directly density-reacheable” to each customer in P, we name this set P’
è In the same way, we compute the set P’’ composed by the customers that are “directly density-reachable” to any customer in P’ and that doesn’t belong to P’.
è We repeat this procedure until there is no more directly connected customers.
è The union of the set P, P’, P’’,… are defined as “Density-reacheable” set of p with a distance DIST , and is named Q(DIST,p).
The procedure to find the meta cluster is the following. We take the first value of MinPoint_dist*, named mindist.
1. We ch...