期刊
OPERATIONS RESEARCH
卷 60, 期 1, 页码 123-127出版社
INFORMS
DOI: 10.1287/opre.1110.0967
关键词
-
资金
- NSF [CCF-0729022, CCF-0728841]
- Alfred P. Sloan Fellowship
- Division of Computing and Communication Foundations [1016799] Funding Source: National Science Foundation
We consider the vehicle routing problem with stochastic demands (VRPSD). We give randomized approximation algorithms achieving approximation guarantees of 1 + alpha for split-delivery VRPSD, and 2 + alpha for unsplit-delivery VRPSD; here alpha is the best approximation guarantee for the traveling salesman problem. These bounds match the best known for even the respective deterministic problems [Altinkemer, K., B. Gavish. 1987. Heuristics for unequal weight delivery problems with a fixed error guarantee. Oper Res. Lett. 6(4) 149-158; Altinkemer, K., B. Gavish. 1990. Heuristics for delivery problems with constant error guarantees. Transportation Res. 24(4) 294-297] We also show that the cyclic heuristic for split-delivery VRPSD achieves a constant approximation ratio, as conjectured in Bertsimas [Bertsimas, D. J. 1992. A vehicle routing problem with stochastic demand. Oper Res. 40(3) 574-585].
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据