An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem
详细信息 查看全文
- 作者：Zhou Xu ; a ; lgtzx@polyu.edu.hk" class="auth_mail" title="E-mail the corresponding author ; Brian Rodriguesb ; brianr@smu.edu.sg" class="auth_mail" title="E-mail the corresponding author
- 关键词：Approximation algorithm ; Multiple depots ; Traveling salesman problem
- 刊名：European Journal of Operational Research
- 出版年：2017
- 出版时间：16 March 2017
- 年：2017
- 卷：257
- 期：3
- 页码：735-745
- 全文大小：983 K
文摘
- class="listitem" id="list_celist0003">
- class="label">•
We study how we can select and route at most k salesmen to service customers.
- class="label">•
We extend the Christofides heuristic and obtain a (2–0.5/k)-approximation algorithm.
- class="label">•
The new algorithm improves on the current best 2-approximation algorithms.
- class="label">•
The proof of the approximation ratio is novel.
- class="label">•
The results obtained can be applied to other vehicle routing problems.