王 迪

（上海交通大学 安泰经济与管理学院，上海 200030）

0 引言

中国每年要产生300亿件以上的快递包裹，这得益于电子商务的快速发展。仓储物流日益成为电商发展中的瓶颈所在。订单拣选流程是仓储运营中最为关键的流程，占用了60%以上的运营成本。相较于传统的仓储中心，电商仓储中心的订单具有日均单量高、订单体量小、及时响应性高等特点。如何确定最优的订单批次，如何调度批次的分配和排序，如何在较短时间内完成订单的拣选，联合订单批次分配排序和路径问题引起了业界和学术界的关注。

客户订单通常会有一个确切的完成期限，一旦产生延误，会降低客户满意度并带来较高的成本。在多人拣选的场景下，是否发生延误以及延误程度，取决于批次的分配和先后排序、批次的订单组成和批次处理时间（主要是路径行走时间）等。一般的，由于不可能满足所有订单的完成期限，必须确定一个最优分配排序方案，以最小化订单的总延迟时间。

本文对最小化订单总延迟时间的联合订单批次分配排序和路径问题进行描述并建立数学模型，之后给出求初始解的方法，并用可变邻域下降算法改进订单分批、用2-opt方法改进行走路径，最终求得最小的订单总延迟时间。

1 联合订单批次分配排序和路径问题

1.1 问题描述

我们考虑的是一个人工拣选、低位货架的单库区，采用人到货的拣选方式。库区中货架有规则地编号，商品可以方便地被拣选员拣取。……