蔬果商品B2C直销的拣货包装序列优化研究 本期目录 >>
Title: Vegetables’ Order Pick-packing Optimization under B2C Marketing Mode
作者 冯晓春;胡祥培
Author(s): FENG Xiao-chun; HU Xiang-pei
摘要: 针对蔬果类商品B2C直销模式拣货包装环节存在的拣货节拍柔性、订单个性化强、配送时间性要求高、需满足装车时间窗和装车顺序等问题,引入JIT(just in time)准时制生产思想,基于流水作业和生产作业调度原理,以“准时拣货、准时装车”为目标,建立考虑装车时间窗、装车链顺序的拣货包装序列优化模型。基于定性定量相结合的思想,以降低搜索空间范围和提高算法计算速度为突破口,引入人工经验设计了以优先规则算法生成初始种群和修订递推式算法求解适应度的混合遗传算法。最后,通过应用实例分析和算法比较证明模型和算法的有效性。结果表明,本文的模型和算法比作业顺序有链优先约束模型和不考虑人工经验的遗传算法,能大大降低拣货包装时间和提早延迟成本,为B2C直销模式下的拣货包装方案生成提供了新手段。
Abstract: Since 2010, vegetables online direct-sales mode appears in Beijing, Shanghai and other cities one after another, which opens a new chapter of the vegetables’ B2C e-commerce mode in China. The core linkof this mode is order pick-packingand delivery in the distribution center. To meet "One-day Delivery" and "Half-day Delivery" and guarantee customers to eat fresh vegetables, companies have to pick a large number of orders in very short time. However, vegetables are perishable, orders are strong personalized and delivery is timeliness.These bring huge challenges to order pick-packing. Inthe traditional manual mill pick-packing mode,pick-packing is independent with other operation. Order buffer is huge and pick-packing cost is high. It no longer meets vegetables pick-packing demand. Order pick-packing has become the bottleneck of vegetables’ B2C e-commerce mode. The order pick-packing mode whichintroducesJIT is no longer an independent operation link, and should meet loading time window and sequence to reduce vegetable buffer and vegetable corruption. Therefore, how to generate the pick-packing order plan to satisfy the loading demands is urgent to the vegetables distribution center. This paper first reviews the academic literature of pick-packing sequence optimization and puts forward that pick-packing sequence optimization is closely associated with pick-packing mode. Order pick-packing modes in the current literatures are from specific industrial environment and do not apply to vegetables pick-packing. The order pick-packing mode based on JIT, if putting each pick-packing line as a parallel machine and a pick-packing task as a job, vegetables order pick-packing sequence optimization considering loading time window and loading sequence can be seen a parallel machine scheduling problem satisfying due window and chain preference constraint. Then, the parallel machine scheduling problem is reviewed from two aspects: the due window and chain preference constraints. We also distinguish the chain preference constraint in our paper and in the current literatures. In this paper, the chain preference constraint is the completed time’s preference constraint, and the current literatures’ is about processing time. The previous machine scheduling research, or having time window constraints, or having chain preference constraints, and all each is a NP-hard problem. If both considering the time window and chain preference constraints, parallel machine scheduling is more complicated and the solution is more difficult. During B2C vegetables marketing mode, orders aremany species small quantity and delivery is very urgent. Thus pick-packing should consider loading time window and sequence simultaneously. These characteristics make the existing research conclusion and method is not applicable to vegetables’ order pick-packing sequence optimization. Therefore, order pick-packing sequence optimization under vegetables B2C mode needs to be further studied. Thirdly, the vegetable pick-packing mode background is described in this paper and the flexible pick-packing time is defined. In order to reduce the scheduling units to lower optimization complexity, based on “same destination, delivery together”, this paper considers the orders in the same village as a whole. Fourthly, based on the model assumption and parameters setting, given the loading chain preference constraints and due window, we establish the mathematical model which minimizes the total of the pick-packing cost and earliness/tardiness cost introducing the JIT manufacturing and machine scheduling principle. The complexity of the model is proved NP-hard. Fifthly, to solve this difficult problem effectively, based on the combination of qualitative quantitative, a hybrid genetic algorithm is proposed which includes the priority rule-based heuristic algorithm to generate the initial population and the proposed revised recursive algorithm to solve the fitness relying on artificial experience. The corresponding pseudo code is presented. Lastly, by numerical experiments of different-scale examples and algorithm comparison analysis with the conventional genetic algorithm, the hybrid genetic algorithm has more advantage to solve order pick-packing sequence optimization under vegetables B2C mode in time and cost aspects. This paper provides a theoretical guidance for the pick-packing plan formation in vegetables B2C marketing mode.
关键词: 蔬菜B2C直销;拣货包装序列优化;混合遗传算法;交货期窗口;链优先约束
Keywords: Vegetables B2C Marketing Mode; Pick-packing Sequence Optimization; the Hybrid Genetic Algorithm; Due Window; Chain Precedence Constraints
基金项目: 国家自然科学基金面上项目;创新研究群体科学基金;国家自然科学基金面上项目
发表期数: 2018年 第3期
中图分类号: 文献标识码: 文章编号:
参考文献/References:

[1] Moeller K. Increasing warehouse order picking performance by sequence optimization[J]. Procedia-Social and Behavioral Sciences, 2011, 20: 177-185.

[2] Liu C M. Clustering techniques for stock location and order-picking in a distribution center[J]. Computers & Operations Research, 1999, 26(10): 989-1002.

[3] Van Den Berg J P. Multiple order pick sequencing in a carousel system: a solvable case of the rural postman problem[J]. Journal of the Operational Research Society, 1996: 1504-1515.

[4] Zhang P, Jia L, Tian G. Pick sequencing optimization problem in the rotary rack S/R system[J]. Journal of Control Theory and Applications, 2004, 2(3): 229-238.

[5] 李晓春,钟雪灵,王雄志,王国庆.配送中心动态分区拣货系统优化设计[J].华南师范大学学报(自然科学版),2011,03:54-60.

[6] 李晓春,王国庆,钟雪灵,王雄志.双旋转货架拣货路径优化策略[J].系统管理学报,2012,01(21):76-82.

[7] 李艳茹.基于遗传算法的订单拣货实时排序问题研究[J].包装工程,2011,13(32):97-101.

[8] Chu C, Proth J M. Single machine scheduling with chain: structured precedence constraints and separation time windows[J]. Robotics and Automation, IEEE Transactions on, 1996, 12(6): 835-844.

[9] Brucker P, Hurink J, Kubiak W. Scheduling identical jobs with chain precedence constraints on two uniform machines[J]. Mathematical Methods of Operations Research, 1999, 49(2): 211-219.

[10] Yuan J, Li W, Yuan J. A best possible online algorithm for scheduling equal-length jobs on two machines with chain precedence constraints[J]. Theoretical Computer Science, 2012, 457: 174-180.

[11] Agnetis A, Kellerer H, Nicosia G, et al. Parallel dedicated machines scheduling with chain precedence constraints[J]. European journal of operational research, 2012, 221(2): 296-305.

[12] Behnamian J, Zandieh M, Ghomi S M T F. Due window scheduling with sequence-dependent setup on parallel machines using three hybrid metaheuristic algorithms[J]. The International Journal of Advanced Manufacturing Technology, 2009, 44(7-8): 795-808.

[13] Yin Y, Cheng T C E, Hsu C J, et al. Single-machine batch delivery scheduling with an assignable common due window[J]. Omega, 2013, 41(2): 216-225.

[14] Chen Z L, Lee C Y. Parallel machine scheduling with a common due window[J]. European Journal of Operational Research, 2002, 136(3): 512-527.

[15] Mosheiov G, Sarig A. Scheduling with a common due-window: polynomially solvable cases[J]. Information Sciences, 2010, 180(8): 1492-1505.

[16] Gerstl E, Mosheiov G. Due-window assignment with identical jobs on parallel uniform machines[J]. European Journal of Operational Research, 2013, 229(1): 41-47.

[17] 王莉,李大卫,王梦光.交货期窗口下的并行机调度问题的遗传算法[J].系统工程学报,2002,01(45):49-55.

[18] 赵传立,张庆灵,唐恒永.任务具有链约束的平行机调度问题[J].控制与决策,2001,16(S1):697-699.

[19] Liu C. A hybrid genetic algorithm to minimize total tardiness for unrelated parallel machine scheduling with precedence constraints[J]. Mathematical Problems in Engineering, 2013, http://www.hindawi.com/journals/mpe/2013/537127/.

[20] 张焱,裘聿皇.基于遗传算法的考虑优先约束和负载平衡的多任务调度[J].计算机工程与应用,2003,12:86-88.