Abstract: A supplier selection model in multi-product and multi-batch purchasing was proposed and its Tabu Search(TS)algorithm for the model was designed. To simplify the solving process, the four-dimension solution of the model was turned into one-dimension Open Vehicle Routing Problem(OVRP)by comparing the similarity between the two problems. Based on node pneighborhood, the exchange, move and self-increasing/decreasing neighborhood operations were designed. The hard constraints were used to control the number of suppliers and purchasing times for single product. And the initial solution as well as neighborhood operations were all conducted on the premise of satisfying these constraints. The penalty function was presented to handle purchasing quantity and using amount in each month of single product, and a dynamic penalty parameter was designed to transfer the constraints from soft to hard. The tabu search was applied to optimize the example and the results by different solution structure and heuristic algorithms were compared. Results and analysis demonstrated the validity of the proposed model and its algorithm.

Key words: purchasing, supplier selection, vehicle routing problem, tabu search, p neighborhood, model

摘要： 提出了多产品分批次采购的供应商选择模型，针对模型的特点设计了禁忌算法。通过比较与开放式车辆路径问题解的相似性，将模型的四维决策变量转化为一维的开放式车辆路径问题的解，简化了求解的复杂度。基于节点的p邻域，设计了交换、移动和自增/减三种邻域操作。对供应商数量限制和单种物资采购次数约束采用“硬”限制方法，初始解产生和邻域操作都在满足此约束的前提下进行；对于单种物资采购量约束和单种物资每月使用量约束，采用惩罚函数的方式进行处理，并设计动态系数将约束逐渐由软约束过渡到硬约束。采用所提禁忌算法对算例进行优化求解，并对采用不同解结构、不同启发式算法的算例结果进行了比较，结果表明了所提模型和算法的有效性。

关键词: 采购, 供应商选择, 车辆路径问题, 禁忌搜索, p邻域