温 昆 ,郭 鹏,2 ,裴 霞 ,吴 晓,2

(1.西南交通大学 机械工程学院,成都 610031;2.轨道交通运维技术与装备四川省重点实验室,成都 610031)

快时尚品(譬如女鞋、女装等)款式更新快且上架展示周期短,需要零售管理方主动控制门店库存,尽可能保证门店销售需求得到满足。管理人员基于门店以往的销售数据对时下流行货品进行销量预测,估算出每种货品未来时段的销售量。以此为基础并结合每个门店现有的库存,对每个门店的每种货品进行补货和调货。当预测的销量小于现有的存量时,为了防止门店此类货品积压,需及时将多余的货品运走;当预测的销量大于现有的存量时,需对门店的此类货品进行补充。提倡门店之间货品互补,以降低调配成本。此外,门店取送货服务时段存在差异。为保证取送货的顺利进行,对配送车辆到达门店的时间也有限制。为此,本文提出带时间窗和调货特性的多品类取送货问题(Multi-commodity Pickup and Delivery Problem with Time Window and Transshipment,M-PDPTWT),以帮助快时尚零售企业降低成本、提高作业效率。M-PDPTWT是带时间窗车辆路径问题(Vehicle Routing Problem with Time Windows,VRPTW)更一般的描述。VRPTW 旨在考虑各个门店可配送的时间窗,在满足仓库辐射范围内各个门店货品需求和不超过车辆最大载容量的前提下,以实现配送车辆数最小化、车辆行驶距离最短、车辆装载均衡等目标。

Braekers等[1]对VRP进行了综述,讨论了精确算法与启发式算法应用情况。针对VRPTW,精确算法有基于集划分的分支定价与切割算法[2]、基于集合覆盖的列生成算法[3]、改进分支切割算法[4]等,启发式算法有遗传算法[5]、大规模邻域搜索算法[6]、进化学习算法[7]、融合禁忌搜索和人工蜂群算法的混合算法[8]、混合蚁群算法[9]以及混合遗传算法[10]等。……