B2C电子商务环境下订单拣选与配送联合调度优化

doi:10.16381/j.cnki.issn1003-207x.2016.07.012

摘要/Abstract

摘要： 如何在顾客下单后协调好拣选和配送环节，在最短的时间、以较低的成本将商品从货架上拣出、打包后配送到顾客手中，已成为B2C电子商务物流管理中亟待解决的问题。本文尝试以最小化订单履行时间为目标，构建非线性拣选与配送联合调度模型，以解决订单拣选顺序、拣选作业方式、车辆行驶线路等联合决策。为求解此NP难问题，设计了三阶段启发式算法：首先采用“聚类-路径优化”思想，依据顾客位置进行配送方案确认；然后采用基于相似度聚类的订单分批规则对每条配送线路的订单进行分批合并；最后调整拣选任务与配送线路顺序。通过数据实验对模型进行验证，并与传统拣选与配送分开优化的结果进行对比。结果表明，三阶段算法能够有效缩短订单完成时间、降低配送车辆等待时间、改善配送资源利用率。

关键词: 联合调度, 订单拣选, 路径优化, 三阶段算法, 遗传算法

Abstract: It is an important issue to integrate the order picking with delivery problem under shorter time and lower cost by picking the items from the shelves, packaging them and delivering to customers. A nonlinear mathematical model is proposed to minimize the time required to complete picking the orders, delivering to customer and returning to the distribution center, which solves the joint decision-making problem such as order picking sequence, picking process method and vehicle routing. For this NP-hard problem, a three-phase heuristic algorithm is designed. Firstly, the "clustering-vehicle routing" method is used to get delivery solutions. Secondly, the similarity-based order batching rules are used to optimize each route's orders. Thirdly, picking sequence is sorted based on the descending order of each route's delivery time. The experiments are proposed to test the efficiency of the model. The results are compared with the traditional optimization algorithm, which show that the three-phase algorithm can reduce the throughput time, decrease the vehicle's wait time and improve the delivery resource utilization. integrated scheduling; order picking; vehicle route; three-phase algorithm; genetic algorithmAbstract:
With the development and wide-spread use of mobile technology, customers can shop anytime and anywhere through a business-to-consumer (B2C) e-commerce shopping platform. However small lot-size and high frequency customer orders make order picking and delivery difficult to implement. In order to accelerate the whole order fulfillment process, orders should be picked and delivered to customers in a very short lead time. It is therefore critical to integrate scheduling order picking and distribution under B2C e-commerce. Research on order picking problems, however, seldom takes delivery constraints into consideration.
The integrated order picking and distribution scheduling (IOPDS) problem is studied to minimize the time required to complete picking the orders, delivering to customer and returning to the distribution center to meet the demand of a given set of customers. The picking processing method is order bathing optimization and distribution characteristic is batching delivery with vehicle routing problem. The problem is NP-hard in strong sense. A three-phase heuristic algorithm is proposed, analyze upper bounds and low bounds of the algorithm are analyzed. The first phase uses the "clustering-vehicle routing" method to get delivery solutions; the second phase uses the similarity-based order batching rules to optimize each route's orders; the third one sorts picking sequence based on the descending order of each route's delivery time. The traditional sequential approach is also proposed, which optimizes order picking and delivery processes separately.In order to verify the effectiveness of the proposed model and algorithms for IOPDS, several examples are tested. The locations for 300 customers are randomly generated in the 100*100 square, where the warehouse is in the center of the square. The three-phase algorithm's relative difference from the lower bounds is good. The results are also compared with the traditional algorithm, which show several enlightening findings:1) the throughput time of the three-phase algorithm is 17.11% shorter than the one of the traditional algorithm, which means it is significant to integrate order picking and distribution; 2) the average improvement of the three-phase algorithm is 13.03%, shows that it is helpful to improve the whole efficiency of the picking and distribution system; 3) it decreases the vehicle's wait time and improve the delivery resource utilization.Theoretically the IOPDS model and algorithm in the work expand the order picking optimization theory and improve the scheduling of production and distribution problem. Moreover, it is beneficial to the e-commerce shopping platform, which can promote the shipping efficiency, save vehicle resources and improve customer satisfaction.

Key words: integrated scheduling, order picking, vehicle route, three-phase algorithm, genetic algorithm

中图分类号:

F274

王旭坪, 张珺, 易彩玉. B2C电子商务环境下订单拣选与配送联合调度优化[J]. 中国管理科学, 2016, 24(7): 101-109.

WANG Xu-ping, ZHANG Jun, YI Cai-yu. Integrated Scheduling of Order Picking and Delivery Under B2C E-commerce[J]. Chinese Journal of Management Science, 2016, 24(7): 101-109.

参考文献

[1] Koster R, Tho L D,Roodbergen K J. Design and control of warehouse order picking:A literature review[J]. European Journal of Operational Research, 2007, 182(1):481-501.

[2] 王旭坪, 阮俊虎, 张凯, 等. 有模糊时间窗的车辆调度组合干扰管理研究[J]. 管理科学学报, 2011, 14(6):2-15.

[3] 黄敏芳, 张源凯, 胡祥培. 有机蔬菜B2C直销的配送方案智能生成方法[J]. 系统工程学报, 2013, 28(5):600-607.

[4] Chen Zhilong. Integrated production and outbound distribution scheduling:Review and extensions[J]. Operations Research, 2010, 58(1):130-148.

[5] Geismar H N, Laporte G, Lei Lei, Sriskandarajah C. The integrated production and transportation scheduling problem for a product with a short life span and non-instantaneous transportation time[J]. INFORMS Journal on Computing, 2008, 20(1):21-33.

[6] Low C Y, Li R K, Chang C M. Integrated scheduling of production and delivery with time windows[J]. International Journal of Production Research, 2013, 51(3):897-909.

[7] Low C Y, Chang C M, Li R K, et al. Coordination of production scheduling and delivery problems with heterogeneous fleet[J]. International Journal of Production Economics, 2014, 153(4):139-148.

[8] 李凯, 王明星, 杨平, 等. 单机多车情形生产与配送协同调度算法[J]. 计算机集成制造系统, 2014, 20(12):3011-3019.

[9] Chen Zhilong, Vairaktarakis G L. Integrated scheduling of production and distribution operations[J]. Management Science, 2005, 51(4):614-628.

[10] 裴军, 刘心报, 范雯娟, 等. 基于生产与运输的供应链调度优化问题[J]. 中国管理科学, 2012, 20(S1):586-593.

[11] 马士华, 吕飞. 基于Supply-Hub的生产与配送协同模式研究[J]. 中国管理科学, 2014, 22(6):50-60.

[12] 马士华, 王青青. 同步物流系统下准时化生产与配送调度问题研究[J]. 中国管理科学, 2012, 20(6):125-132.

[13] 冯鑫, 郑斐峰, 徐寅峰. 批加工生产配送二级供应链协同调度[J]. 系统管理学报, 2015, 24(2):275-279.

[14] Li Kai, Yang Shanlin, Ma Huawei. A simulated annealing approach to minimize the maximum lateness on uniform parallel machines[J]. Mathematical and Computer Modelling, 2011, 53(5-6):854-860.

[15] 李昆鹏, 马士华. ATO供应链中航空运输及并行机生产协调调度问题[J]. 系统工程理论与实践, 2007, 27(12):8-15.

[16] 王建华, 李南, 郭慧. 基于时间槽的敏捷供应链集成调度模型及优化[J]. 系统工程理论与实践, 2011, 31(2):283-290.

[17] Cheng Bayi, Li Kai, Hu Xiaozuan. Approximation algorithms for two-stage supply chain scheduling of production and distribution[J]. International Journal of Systems Science:Operations & Logistics, 2015,2(2):78-89.

[18] Gao Su, Qi Lian, Lei Lei. Integrated batch production and distribution scheduling with limited vehicle capacity[J]. International Journal of Production Economics, 2015,160:13-25.

[19] Amstrong R, Gao Su, Lei Lei. A zero-inventory production and distribution problem with a fixed customer sequence[J]. Annals of Operations Research, 2008, 159(1):395-414.

[20] Low C R, Chang C M, Li R K, et al.Coordination of production scheduling and delivery problems with heterogeneous fleet[J].International Journal of Production Economics, 2014,153:139-148.

[21] Low C R, Li R K, Chang C M. Integrated scheduling of production and delivery with time windows[J]. International Journal of Production Research, 2013,51(3):897-909.

[22] 冯鑫, 郑斐峰. 面对单客户的生产与配送二级供应链协同调度探讨[J]. 运筹与管理, 2014, 23(4):19-24.

[23] Leung J Y T, Chen Zhilong. Integrated production and distribution with fixed delivery departure dates[J]. Operations Research Letters, 2013, 41(3):290-293.

[24] Zhong Weiya, Chen Zhilong, Chen Ming. Integrated production and distribution scheduling with committed delivery dates[J].Operations Research Letters, 2010, 38(2):133-138.

[25] Armentano V A, Shiguemoto A L, Løkketangen A. Tabu search with path relinking for an integrated production-distribution problem[J]. Computers & Operations Research, 2011, 38(8):1199-1209.

[26] Lam C H Y, Choy K L, Ho G T S, et al. An order-picking operations system for managing the batching activities in a warehouse[J]. International Journal of Systems Science, 2014, 45(6):1283-1295.

[27] 王旭坪, 张珺, 马骏. 考虑完成期限的电子商务在线订单分批模型及算法[J]. 管理科学,2014, 27(6):103-113.

[28] 朱杰, 周丽, 郭键. 分类存储人工拣选随机服务系统效率研究[J]. 管理科学学报,2012,15(2):59-71.

[29] 陈方宇, 王红卫, 祁超, 等. 考虑多拣货员堵塞的仓库拣选路径算法[J]. 系统工程学报, 2013, 28(5):581-591.

[30] Papadimitrious C H. The Euclidean traveling salesman problem is NP-complete[J]. Theoretical Computer Science, 1977, 4(3):237-244.

[31] Ruan Junhu, Wang Xuping, Shi Yan. Developing fast predictors for large-scale time series using fuzzy granular support vector machines[J]. Applied Soft Computing, 2012, 13(9):3981-4000.