蔬果商品B2C直销的拣货包装序列优化研究
|
摘要
针对蔬果类商品B2C直销模式拣货包装环节存在的拣货节拍柔性、订单个性化强、配送时间性要求高、需满足装车时间窗和装车顺序等问题,引入JIT(just in time)准时制生产思想,基于流水作业和生产作业调度原理,以"准时拣货、准时装车"为目标,建立考虑装车时间窗、装车链顺序的拣货包装序列优化模型。基于定性定量相结合的思想,以降低搜索空间范围和提高算法计算速度为突破口,引入人工经验设计了以优先规则算法生成初始种群和修订递推式算法求解适应度的混合遗传算法。最后,通过应用实例分析和算法比较证明模型和算法的有效性。结果表明,本文的模型和算法比作业顺序有链优先约束模型和不考虑人工经验的遗传算法,能大大降低拣货包装时间和提早延迟成本,为B2C直销模式下的拣货包装方案生成提供了新手段。
Since 2010, vegetables' online direct-sales mode has appeared in Beijing, Shanghai and other cities, which opens a new chapter of vegetables' B2 C e-commerce mode in China. The core link of this mode is order pick-packing and 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 a very short time. However, vegetables are perishable, orders are strong personalized, and delivery time is urgent. These characteristics bring huge challenges to order pick-packing of vegetables. In the pick-packing mode of traditional manual mills,pick-packing is independent from other operations. 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' B2 C e-commerce mode. The order pick-packing mode which introduces JIT 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 for vegetable distribution center. This paper first reviews the academic literature of pick-packing sequence optimization and proposes 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. In terms of the order pick-packing mode based on JIT, if putting each pick-packing line as a parallel machine and 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 precedence constraints. The parallel machine scheduling problem is reviewed from two aspects: the due window and chain precedence constraints. We also distinguish the chain precedence constraint in our paper and in the current literatures. In this paper, the chain precedence constraint is completion time's precedence constraint, and the current literature is about processing time. The previous machine scheduling research, having time window constraints, or having chain precedence constraints, are all considered NP-hard problem. After considering the due window and chain precedence constraints, parallel machine scheduling is more complicated and its solution is more difficult. During B2 C vegetable marketing mode, a wide variety of orders are in small quantity and delivery is very urgent. Thus, order pick-packing should consider loading time window and sequence simultaneously. These characteristics make the existing research conclusion and method not applicable to vegetables' order pick-packing sequence optimization. Therefore, order pick-packing sequence optimization under vegetables B2 C mode needs to be further studied. Thirdly, the vegetables pick-packing background is described in this paper and flexible pick-packing time is defined. In order to reduce scheduling units to lower optimization complexity, based on "same destination, delivery together", orders in the same residential district are considered as a whole in this paper. Fourthly, based on the model assumption and parameters setting, given the loading chain precedence constraints and due window, we establish a mathematical model which minimizes the total cost of pick-packing and earliness/tardiness introducing the JIT manufacturing and machine scheduling principles. The complexity of the model is proved NP-hard. Fifthly, in order 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. The proposed revised recursive algorithm to solve the fitness relies on artificial experience. The corresponding pseudo code is presented. Lastly, based on numerical experiments of different-scale examples and algorithm comparison analysis with the conventional genetic algorithm, the hybrid genetic algorithm has more advantages to solve order pick-packing sequence optimization problems under vegetable B2 C mode in computation time and cost aspects. This paper provides a theoretical guidance for the pick-packing plan formation in vegetable B2 C marketing mode.
Since 2010, vegetables' online direct-sales mode has appeared in Beijing, Shanghai and other cities, which opens a new chapter of vegetables' B2 C e-commerce mode in China. The core link of this mode is order pick-packing and 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 a very short time. However, vegetables are perishable, orders are strong personalized, and delivery time is urgent. These characteristics bring huge challenges to order pick-packing of vegetables. In the pick-packing mode of traditional manual mills,pick-packing is independent from other operations. 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' B2 C e-commerce mode. The order pick-packing mode which introduces JIT 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 for vegetable distribution center. This paper first reviews the academic literature of pick-packing sequence optimization and proposes 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. In terms of the order pick-packing mode based on JIT, if putting each pick-packing line as a parallel machine and 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 precedence constraints. The parallel machine scheduling problem is reviewed from two aspects: the due window and chain precedence constraints. We also distinguish the chain precedence constraint in our paper and in the current literatures. In this paper, the chain precedence constraint is completion time's precedence constraint, and the current literature is about processing time. The previous machine scheduling research, having time window constraints, or having chain precedence constraints, are all considered NP-hard problem. After considering the due window and chain precedence constraints, parallel machine scheduling is more complicated and its solution is more difficult. During B2 C vegetable marketing mode, a wide variety of orders are in small quantity and delivery is very urgent. Thus, order pick-packing should consider loading time window and sequence simultaneously. These characteristics make the existing research conclusion and method not applicable to vegetables' order pick-packing sequence optimization. Therefore, order pick-packing sequence optimization under vegetables B2 C mode needs to be further studied. Thirdly, the vegetables pick-packing background is described in this paper and flexible pick-packing time is defined. In order to reduce scheduling units to lower optimization complexity, based on "same destination, delivery together", orders in the same residential district are considered as a whole in this paper. Fourthly, based on the model assumption and parameters setting, given the loading chain precedence constraints and due window, we establish a mathematical model which minimizes the total cost of pick-packing and earliness/tardiness introducing the JIT manufacturing and machine scheduling principles. The complexity of the model is proved NP-hard. Fifthly, in order 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. The proposed revised recursive algorithm to solve the fitness relies on artificial experience. The corresponding pseudo code is presented. Lastly, based on numerical experiments of different-scale examples and algorithm comparison analysis with the conventional genetic algorithm, the hybrid genetic algorithm has more advantages to solve order pick-packing sequence optimization problems under vegetable B2 C mode in computation time and cost aspects. This paper provides a theoretical guidance for the pick-packing plan formation in vegetable B2 C marketing mode.
引文
[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.
[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.