带时间窗和调货特性的多品类取送货优化算法  

Optimization Algorithm for Multi-commodity Pickup and Delivery Problem with Time Windows and Transshipment

作　　者：温昆 郭鹏[1,2] 裴霞 吴晓 WEN Kun;GUO Peng;PEI Xia;WU Xiao(School of Mechanical Engineering,Southwest Jiaotong University,Chengdu 610031,China;Technology and Equipment of Rail Transit Operation and Maintenance Key Laboratory of Sichuan Province,Chengdu 610031,China)

机构地区：[1]西南交通大学机械工程学院,成都610031 [2]轨道交通运维技术与装备四川省重点实验室,成都610031

出　　处：《系统管理学报》2021年第5期1005-1015,共11页Journal of Systems & Management

基　　金：国家重点研发计划资助项目(2020YFB1712200);中央高校基本科研业务费专项资金资助项目(2682018CX09)。

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

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] F717[自动化与计算机技术—控制科学与工程]