期刊
COMPUTERS & OPERATIONS RESEARCH
卷 38, 期 2, 页码 550-558出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2010.07.016
关键词
Traveling purchaser problem; Dynamic programming; State space relaxation; Discretized (time-dependent) formulation
类别
资金
- Portuguese Science and Technology Foundation [POCTI-ISFL-1-152]
The traveling purchaser problem (TPP) is the problem of determining a tour of a purchaser that needs to buy several items in different shops such that the total amount of travel and purchase costs is minimized. Motivated by an application in machine scheduling, we study a variant of the problem with additional constraints, namely, a limit on the maximum number of markets to be visited, a limit on the number of items bought per market and where only one copy per item needs to be bought. We present an integer linear programming (ILP) model which is adequate for obtaining optimal integer solutions for instances with up to 100 markets. We also present and test several variations of a Lagrangian relaxation combined with a subgradient optimization procedure. The relaxed problem can be solved by dynamic programming and can also be viewed as resulting from applying a state space relaxation technique to a dynamic programming formulation. The Lagrangian based method is combined with a heuristic that attempts to transform relaxed solutions into feasible solutions. Computational results for instances with up to 300 markets show that with the exception of a few cases, the reported differences between best upper bound and lower bound values on the optimal solutions are reasonably small. (C) 2010 Elsevier Ltd. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据