Integrated optimization approach to multi-depot order splitting and heterogeneous vehicle routing with time windows

TANG Jianqiang, QI Chao, WANG Hongwei

Systems Engineering - Theory & Practice ›› 2023, Vol. 43 ›› Issue (5) : 1446-1464.

PDF(356 KB)
中国科学院数学与系统科学研究院期刊网
PDF(356 KB)
Systems Engineering - Theory & Practice ›› 2023, Vol. 43 ›› Issue (5) : 1446-1464. DOI: 10.12011/SETP2022-0501

Integrated optimization approach to multi-depot order splitting and heterogeneous vehicle routing with time windows

  • TANG Jianqiang1, QI Chao1, WANG Hongwei1,2
Author information +
History +

Abstract

With the rapid development of online retail, order splitting and time-limited distribution have become two key issues of the order fulfillment process in a multi-depot environment. Existing studies and operations in practice usually deal with these two issues separately, ignoring the coupling relationship between them. This paper studies the integrated optimization of multi-depot order splitting and heterogeneous vehicle routing problems in the online retail environment, especially considering finite inventory and time windows constraints. We construct a mixed integer programming model for this problem and design an integrated optimization algorithm with branch price and neighborhood search nested in each other to solve it. Based on the initial order splitting scheme, we solve the heterogeneous vehicle routing problem with time windows by branch price algorithm, and a bidirectional label-setting algorithm is proposed to accelerate the solution of the pricing subproblem. Then, the neighborhood search algorithm is used to find a feasible order splitting scheme under the current optimal vehicle route solution. Optimize the distribution route when adjusting the order splitting scheme by alternating the branch price algorithm and the neighborhood search algorithm for iterative solution. The experimental analysis verifies the effectiveness of the model and algorithm, showing that the algorithm can reduce the order splitting rate, optimize the distribution route, and reduce the total cost of distribution, thus effectively realizing the integrated optimization of order splitting and heterogeneous vehicle route.

Key words

vehicle routing problem / order splitting / time windows / heterogeneous vehicle / integrated optimization algorithm

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations
TANG Jianqiang , QI Chao , WANG Hongwei. Integrated optimization approach to multi-depot order splitting and heterogeneous vehicle routing with time windows. Systems Engineering - Theory & Practice, 2023, 43(5): 1446-1464 https://doi.org/10.12011/SETP2022-0501

References

[1] 商务部电子商务和信息化司. 中国电子商务报告(2021)[EB/OL]. [2022-11-21].http://images.mofcom.gov.cn/dzsws/202211/20221118180137127.pdf. Department of Electronic Commerce and Information Technology, Ministry of Commerce. China's e-commerce report (2021)[EB/OL]. [2022-11-21]. http://images.mofcom.gov.cn/dzsws/202211/20221118180137127.pdf.
[2] 张源凯, 胡祥培, 黄敏芳, 等. 网上超市拆分订单合并打包策略经济决策模型[J]. 管理科学学报, 2019, 22(10): 24-36. Zhang Y K, Hu X P, Huang M F, et al. Economic decision model for package consolidation in fulfilling split orders of online supermarkets[J]. Journal of Management Sciences in China, 2019, 22(10): 24-36.
[3] 李建斌, 孙哲, 陈威帆, 等. 面向最小化拆单率的基于订单分配顺序的库存优化研究[J]. 工业工程与管理, 2017, 22(6): 78-84. Li J B, Sun Z, Chen W F, et al. Research on inventory optimization for minimizing the rate of separating bills based on the sequence of order distribution[J]. Industrial Engineering and Management, 2017, 22(6): 78-84.
[4] 范厚明, 张轩, 任晓雪, 等. 多中心开放且需求可拆分的VRPSDP问题优化[J]. 系统工程理论与实践, 2021, 41(6): 1521-1534.Fan H M, Zhang X, Ren X X, et al. Optimization of multi-depot open split delivery vehicle routing problem with simultaneous delivery and pick-up[J]. Systems Engineering—Theory & Practice, 2021, 41(6): 1521-1534.
[5] 郭放, 黄志红, 黄卫来. 考虑前置仓选址与服务策略的同时取送货车辆路径问题研究[J]. 系统工程理论与实践, 2021, 41(4): 962-978.Guo F, Huang Z H, Huang W L. Integrated sustainable planning of fast-pick area network and vehicle routing with simultaneous delivery and pick-up[J]. Systems Engineering—Theory & Practice, 2021, 41(4): 962-978.
[6] 京东物流. 京东物流主页[EB/OL]. [2022-11-21]. https://www.jdl.cn/. JD Logistics. JingDong logistics homepage[EB/OL]. [2022-11-21]. https://www.jdl.cn/.
[7] Li X, Li J, Aneja Y P, Guo Z, et al. Integrated order allocation and order routing problem for e-order fulfillment[J]. IISE Transactions, 2019, 51(10): 1128-1150.
[8] Li S, Jia S. A Benders decomposition algorithm for the order fulfilment problem of an e-tailer with a self-owned logistics system[J]. Transportation Research Part E: Logistics and Transportation Review, 2019, 122(2): 463-480.
[9] Nasiri M M, Rahbari A, Werner F, et al. Incorporating supplier selection and order allocation into the vehicle routing and multi-cross-dock scheduling problem[J]. International Journal of Production Research, 2018, 56(19): 6527-6552.
[10] Dupont L, Bernard C, Hamdi F, et al. Supplier selection under risk of delivery failure: A decision-support model considering managers' risk sensitivity[J]. International Journal of Production Research, 2018, 56(3): 1054-1069.
[11] 晏鹏宇, 杨柳, 车阿大. 共享制造平台供需匹配与调度研究综述[J]. 系统工程理论与实践, 2022, 42(3): 811-832.Yan P Y, Yang L, Che A D. Review of supply-demand matching and scheduling in shared manufacturing[J]. Systems Engineering—Theory & Practice, 2022, 42(3): 811-832.
[12] Zhou X, Yu N, Tu Y, et al. Bi-level plant selection and production allocation model under type-2 fuzzy demand[J]. Expert Systems with Applications, 2017, 86: 87-98.
[13] Xu P J, Allgor R, Graves S C. Benefits of reevaluating real-time order fulfillment decisions[J]. Manufacturing & Service Operations Management, 2009, 11(2): 340-355.
[14] Jasin S, Sinha A. An LP-based correlated rounding scheme for multi-item ecommerce order fulfillment[J]. Operations Research, 2017, 63(6): 1336-1351.
[15] Acimovic J, Graves S C. Making better fulfillment decisions on the fly in an online retail environment[J]. Manufacturing & Service Operations Management, 2015, 17(1): 34-51.
[16] 李建斌, 李乐乐, 黄日环. 最小化拆单率的在线零售商多仓商品摆放优化策略研究[J]. 管理工程学报, 2017, 31(3): 167-173.Li J B, Li L L, Huang R H. Research on multi-warehouse product placement optimization strategy for online retailers with minimized dismansion rates[J]. Journal of Industrial Engineering and Engineering Management, 2017, 31(3): 167-173.
[17] Mahar S, Modi S, Salzarulo P A. Appreciating how your bread is buttered: Improving online order allocation for cross-channel retailers[J]. International Journal of Production Research, 2021, 60(15): 4845-4867.
[18] Baldacci R, Mingozzi A, Roberti R. Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints[J]. European Journal of Operational Research, 2012, 218(1): 1-6.
[19] Montoya-Torres J R, Franco J L, Isaza S N, et al. A literature review on the vehicle routing problem with multiple depots[J]. Computers & Industrial Engineering, 2015, 79: 115-129.
[20] Braekers K, Ramaekers K, Nieuwenhuyse I V. The vehicle routing problem: State of the art classification and review[J]. Computers & Industrial Engineering, 2016, 99: 300-313.
[21] Dondo R, Cerda J. A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows[J]. European Journal of Operational Research, 2007, 176(3): 1478-1507.
[22] Dondo R, Cerda J. A hybrid local improvement algorithm for large-scale multi-depot vehicle routing problems with time windows[J]. Computers & Chemical Engineering, 2009, 33(2): 513-530.
[23] Ceselli A, Righini G, Salani M. A column generation algorithm for a rich vehicle-routing problem[J]. Transportation Science, 2009, 43(1): 56-69.
[24] Adelzadeh M, Mahdavi Asl V, Koosha M. A mathematical model and a solving procedure for multi-depot vehicle routing problem with fuzzy time window and heterogeneous vehicle[J]. International Journal of Advanced Manufacturing Technology, 2014, 75(5-8): 793-802.
[25] Ruiz-Meza J, Montes I, Perez A, et al. VRP model with time window, multiproduct and multidepot[J]. Journal of Applied Science and Engineering, 2020, 23(2): 239-247.
[26] Hou D, Fan H, Ren X, et al. Time-dependent multi-depot heterogeneous vehicle routing problem considering temporal-spatial distance[J]. Sustainability, 2021, 13(9): 4674. doi: 10.3390/su13094674.
[27] Bettinelli A, Ceselli A, Righini G. A branch-and-cut-and-price algorithm for the multi-depot heterogeneous vehicle routing problem with time windows[J]. Transportation Research Part C: Emerging Technologies, 2011, 19(5): 723-740.
[28] 李政道, 周泓. 基于限时送达服务的订单分派与生产运送调度的集成优化[J]. 计算机集成制造系统, 2014, 20(7): 1643-1653.Li Z D, Zhou H. Integrated optimization of order distribution and production delivery scheduling based on time-limited delivery service[J]. Computer Integrated Manufacturing Systems, 2014, 20(7): 1643-1653.
[29] 张源凯, 黄敏芳, 胡祥培. 网上超市订单分配与物流配送联合优化方法[J]. 系统工程学报, 2015, 30(2): 251-258. Zhang Y K, Huang M F, Hu X P. Integrated optimization approach to order allocation and delivery problem of online supermarket[J]. Journal of Systems Engineering, 2015, 30(2): 251-258.
[30] 韩曙光, 章园园. 基于最小集合覆盖的电商订单拆分及配送方式[J]. 浙江理工大学学报(社会科学版), 2019, 42(6): 627-636.Han S G, Zhang Y Y. Order resolution and delivery method of e-commerce based on minimum set coverage[J]. Journal of Zhejiang Sci-Tech University (Social Science Edition), 2019, 42(6): 627-636.
[31] Kara I, Laporte G, Bektas T. A note on the lifted Miller-Tucker-Zemlin subtour elimination constraints for the capacitated vehicle routing problem[J]. European Journal of Operational Research, 2004, 158(3): 793-795.
[32] Mahvash B, Awasthi A, Chauhan S. A column generation-based heuristic for the three-dimensional bin packing problem with rotation[J]. Journal of the Operational Research Society, 2017, 69(1): 1-13.
[33] Dror M. Note on the complexity of the shortest path models for column generation in vrptw[J]. Operations Research, 1994, 42(5): 977-978.
[34] Feillet D, Dejax P, Gendreau M. An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems[J]. Networks, 2004, 44(3): 216-229.
[35] Righini G, Salani M. Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints[J]. Discrete Optimization, 2006, 3(3): 255-273.
[36] Yu Y, Wang S, Wang J, et al. A branch-and-price algorithm for the heterogeneous fleet green vehicle routing problem with time windows[J]. Transportation Research Part B: Methodological, 2019, 122: 511-527.
[37] Desaulniers G, Desrosiers J, Ioachim I, et al. A unified framework for deterministic time constrained vehicle routing and crew scheduling problems[M]. US: Springer, 1998.
[38] Wang J, Yuan L, Zhang Z, et al. Multiobjective multiple neighborhood search algorithms for multiobjective fleet size and mix location-routing problem with time windows[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2019, 51(4): 2284-2298.
[39] Hintsch T. Large multiple neighborhood search for the soft-clustered vehicle-routing problem[J]. Computers & Operations Research, 2021, 129: 105132.
[40] Cordeau J F, Laporte G, Mercier A. A unified tabu search heuristic for vehicle routing problems with time windows[J]. Journal of the Operational Research Society, 2001, 52(8): 928-936.
[41] Liu F H, Shen S Y. The fleet size and mix vehicle routing problem with time windows[J]. Journal of the Operational Research Society, 1999, 50(7): 721-732.

Funding

National Key R&D Program of China (2018YFC0807500); National Natural Science Foundation of China (71821001)
PDF(356 KB)

774

Accesses

0

Citation

Detail
Sections
Recommended

/

〈 〉