The cost due to delay in services may be intrinsically different for various applications of vehicle routing such as medical emergencies, logistical operations, and ride-sharing. We study a fundamental generalization of the Traveling Salesman Problem, namely $L_p$ TSP, where the objective is to minimize an aggregated measure of the delay in services, quantified by the Minkowski $p$-norm of the delay vector. We present efficient combinatorial and Linear Programming algorithms for approximating $L_p$ TSP on general metrics. We provide several approximation algorithms for the $L_p$ TSP problem, including $4.27$ & $10.92$-approximation algorithms for single & multi vehicle $L_2$ TSP, called the Traveling Firefighter Problem. Among other contributions, we provide an $8$-approximation and a $1.78$ inapproximability for All-Norm TSP problem, addressing scenarios where one does not know the ideal cost function, or is seeking simultaneous approximation with respect to any cost function.
翻译：服务延误引起的费用在诸如医疗紧急情况、后勤业务和搭车等各种车辆路线应用方面可能本质上有所不同。我们研究了旅行销售商问题的基本概括性,即$L_p$TSP,其目标是最大限度地减少服务延误的综合计量,由延迟矢量的Minkowski $p$-norm量化。我们提出了在通用度量上接近$L_p$TSP的高效组合和线性编程算法。我们为TSP问题提供了几种近似算法,包括4.27美元和10.92美元的单部和多部车辆的通行算法,称为TSP,称为“消防员问题”。除其他贡献外,我们为全Norm TSP问题提供了8美元的配比值和1.78美元的配比值,以解决人们不知道理想成本功能或正在寻求与任何成本功能同时贴合的情况。
相关内容
微信扫码咨询专知VIP会员