论文标题
多目的路由：新的观点和近似算法
Multi Purpose Routing: New Perspectives and Approximation Algorithms
论文作者
论文摘要
对于各种车辆路由的应用，例如医疗紧急情况，后勤操作和乘车共享，由于服务延迟而产生的成本可能在本质上有所不同。我们研究了旅行推销员问题的基本概括，即$ l_p $ tsp，其目的是最大程度地减少服务延迟的总体量度，该量子由Minkowski $ p $ norm的延迟向量量化。我们提供有效的组合和线性编程算法，用于近似于通用指标的$ L_P $ TSP。我们为$ l_p $ tsp问题提供了几种近似算法，包括$ 4.27 $＆$ 10.92 $ - 单车和多车辆$ l_2 $ tsp，称为旅行消防员问题。除其他贡献外，我们提供了$ 8 $的APPROXIMATION和1.78美元的全场TSP问题不适合性，解决了人们不知道理想成本功能或寻求与任何成本函数的同时近似的情况。
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.
