Abstract: In order to fulfill the multi-commodity sales demand of fast-fashion chain stores, load capacity restriction of vehicles, multiple commodities, transshipment, service time window of stores and other factors should be considered. In this paper, the multi-commodity pickup and delivery vehicle routing problem with time windows and transshipment is studied. In order to effectively reduce inventory management and transshipment cost, it is usually encouraged to allocate goods between stores and control the number of vehicles used. In view of this, this paper first tries to minimize the number of vehicles used. Then, it minimizes the transshipment cost (transportation cost and warehouse handling cost). After that, it formulates a mixed integer programming model and designed a two-stage search algorithm by utilizing the shortest route insertion rule to generate the initial solution, and combining 8 neighborhood operators to generate neighborhood solutions. The results of benchmark instances indicate that the algorithm outperforms other existing algorithms in literature. Furthermore, 72 test instances are generated based on the actual operation data of a female shoe chain store. The computational results show that the quality of the solution and efficiency of the algorithm are better than those of the mixed integer programming model.

Key words: multi-commodity, pickup and delivery, transshipment, time windows, neighborhood search

摘要： 为了满足快时尚品连锁门店多品类的销售需求，综合考虑载重限制、多货品、门店相互调货和服务时间窗等因素，研究了同时取送货车辆路径问题。为了有效降低库存管理和运输成本，通常鼓励门店间的货品相互调配，且需要控制用车数。为此，以最小化车辆数为第一优化目标，最小化转运成本（运输成本和仓库处理成本）为第二优化目标，构建了混合整数规划模型，并设计了两阶段启发式求解算法。算法采用最短路径插入规则生成初始解，并配合8个邻域操作算子进行迭代搜索。采用该算法求解标准算例，对比文献中结果表明，其具有较好的寻优能力。基于某女鞋连锁门店的实际运营数据设计了72个算例，计算分析表明，该算法的求解能力与效率均优于整数规划模型。

关键词: 多货品, 取送货, 调货, 时间窗, 邻域搜索