An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem

网站地图 | English | 公务邮箱

About the library

Background
History
Leadership
Organization

Opening Hours
Collections
Help Via Email

Electronic Information Resources

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 Rodrigues^b ; ^{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="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.

NGLC 2004-2010.National Geological Library of China All Rights Reserved.
Add:29 Xueyuan Rd,Haidian District,Beijing,PRC. Mail Add: 8324 mailbox 100083
For exchange or info please contact us via email.