Formulations and Benders decomposition algorithms for multidepot salesmen problems with load balancing
Formulations and Benders decomposition algorithms for multidepot salesmen problems with load balancing
复制标题
多仓库销售员负载平衡问题的公式和 Benders 分解算法
DOI：
10.1016/j.ejor.2011.07.020
复制
发表时间：
2012
影响因子：
6.4
通讯作者：
Bektas T
中科院分区：
文献类型：
--
作者：
Bektas T
本文描述了定义在n结点图上的固定目的地多点销售员问题的新模型和精确解算法，其中每个销售员要访问的结点数被限制在预定范围内。当访问节点的时间与节点之间的旅行时间相比花费相当长的时间时，就会出现这样的问题，在这种情况下，销售员巡视中访问的节点的数量是其负载的决定因素。新的模型是具有O(N2)个二元变量的新的多商品流公式，这与通常包含O(N3)个二元变量的相同(或类似)问题的现有公式相反。文中还描述了基于新公式的Bders分解算法，以求准确地解决该问题。在TSPLIB算例上的计算实验结果表明，在用最先进的优化代码求解的公式在合理的计算时间内不能产生最优解的情况下，所提出的算法具有很好的性能。
This paper describes new models and exact solution algorithms for the fixed destination multidepot salesmen problem defined on a graph with n nodes where the number of nodes each salesman is to visit is restricted to be in a predefined range. Such problems arise when the time to visit a node takes considerably longer as compared to the time of travel between nodes, in which case the number of nodes visited in a salesman’s tour is the determinant of their ‘load’. The new models are novel multicommodity flow formulations with O(n2) binary variables, which is contrary to the existing formulations for the same (and similar) problems that typically include O(n3) binary variables. The paper also describes Benders decomposition algorithms based on the new formulations for solving the problem exactly. Results of the computational experiments on instances derived from TSPLIB show that some of the proposed algorithms perform remarkably well in cases where formulations solved by a state-of-the-art optimization code fail to yield optimal solutions within reasonable computation time.
影响因子：
2.7
作者：
Fischetti, Matteo;Salvagnin, Domenico;Zanette, Arrigo
通讯作者：
Zanette, Arrigo
DOI：
--
发表时间：
2009
期刊：
American Control Conference
影响因子：
--
作者：
Paul Oberlin;S. Rathinam;S. Darbha
通讯作者：
S. Darbha