Walmart Inc.
AUTOMATICALLY PLANNING DELIVERY ROUTES USING CLUSTERING

Abstract:

A method including planning delivery routes using clustering. The method can include extracting (a) location information of nodes from order data, (b) time window information of the nodes from the order data, and (c) load capacity information of delivery vehicles. The method further can include generating, in real-time, one or more clusters for the nodes based, at least in part, on (a) the location information of the nodes and (b) the load capacity information. Each of the one or more clusters can be associated with a respective vehicle of one or more dispatched vehicles of the delivery vehicles. The method also can include determining, in real-time, a respective centroid for each of the one or more clusters based on location information of cluster nodes of the nodes for each of the one or more clusters. Further, the method can include computing, in real-time, a node-cluster distance matrix. The node-cluster distance matrix can comprise a respective node-cluster distance between each of the nodes and each of the one or more clusters based, at least in part, on a respective distance between each of the nodes and the respective centroid for each of the one or more clusters. Additionally, the method can include reassigning, in real-time, the nodes to the one or more clusters based, at least in part, on: (a) the node-cluster distance matrix; (b) load capacity information of the one or more dispatched vehicles; and (c) a predetermined average load threshold of the one or more dispatched vehicles. Moreover, the method can include further reassigning, in real-time in at least 2 passes, the nodes to the one or more clusters based, at least in part, on the time window information of the nodes. Other embodiments are disclosed.