Abstract | ||
---|---|---|
Balanced order batching problem (BOBP) arises from the process of warehouse picking in Cainiao, the largest logistics platform in China. Batching orders together in the picking process to form a single picking route, reduces travel distance. The reason for its importance is that order picking is a labor intensive process and, by using good batching methods, substantial savings can be obtained. The BOBP is a NP-hard combinational optimization problem and designing a good problem-specific heuristic under the quasi-real-time system response requirement is non-trivial. In this paper, rather than designing heuristics, we propose an end-to-end learning and optimization framework named Balanced Task-orientated Graph Clustering Network (BTOGCN) to solve the BOBP by reducing it to balanced graph clustering optimization problem. In BTOGCN, a task-oriented estimator network is introduced to guide the type-aware heterogeneous graph clustering networks to find a better clustering result related to the BOBP objective. Through comprehensive experiments on single-graph and multi-graphs, we show: 1) our balanced task-oriented graph clustering network can directly utilize the guidance of target signal and outperforms the two-stage deep embedding and deep clustering method; 2) our method obtains an average 4.57m and 0.13m picking distance reduction than the expert-designed algorithm on single and multi-graph set and has a good generalization ability to apply in practical scenario.
|
Year | DOI | Venue |
---|---|---|
2020 | 10.1145/3394486.3403355 | KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
Virtual Event
CA
USA
July, 2020 |
DocType | ISBN | Citations |
Conference | 978-1-4503-7998-4 | 0 |
PageRank | References | Authors |
0.34 | 0 | 7 |
Name | Order | Citations | PageRank |
---|---|---|---|
Lu Duan | 1 | 13 | 2.80 |
Haoyuan Hu | 2 | 5 | 1.77 |
Zili Wu | 3 | 0 | 1.35 |
Guo-Zheng Li | 4 | 368 | 42.62 |
Xinhang Zhang | 5 | 0 | 0.68 |
Yu Gong | 6 | 132 | 8.35 |
Yinghui Xu | 7 | 172 | 20.23 |