论文标题
多目标旅行销售人员问题风险感知的suppodular优化
Risk-Aware Submodular Optimization for Multi-objective Travelling Salesperson Problem
论文作者
论文摘要
我们介绍了一种风险有风险的多目标旅行销售人员问题（TSP）变体，必须同时优化机器人旅行成本和旅行奖励。机器人沿图中的边缘获得奖励。我们研究了奖励和成本表现出的边际收益降低的情况，即supporular。与先前的工作不同，我们专注于成本和奖励不确定的方案，并试图最大程度地提高危险中的条件价值（CVAR）指标。我们提出了一种风险感知的贪婪算法（RAGA），以找到有界的附属算法。近似算法在多项式时间内运行，并且在取决于最佳解决方案的最佳和添加项的恒定因子之内。我们使用suppoular函数的曲率进一步改善近似结果，并通过模拟验证算法的性能。
We introduce a risk-aware multi-objective Traveling Salesperson Problem (TSP) variant, where the robot tour cost and tour reward have to be optimized simultaneously. The robot obtains reward along the edges in the graph. We study the case where the rewards and the costs exhibit diminishing marginal gains, i.e., are submodular. Unlike prior work, we focus on the scenario where the costs and the rewards are uncertain and seek to maximize the Conditional-Value-at-Risk (CVaR) metric of the submodular function. We propose a risk-aware greedy algorithm (RAGA) to find a bounded-approximation algorithm. The approximation algorithm runs in polynomial time and is within a constant factor of the optimal and an additive term that depends on the optimal solution. We use the submodular function's curvature to improve approximation results further and verify the algorithm's performance through simulations.
