具有约束和可选城市的类似旅行商的问题
Travelling salesman -like problem with constraints and optional cities
考虑旅行商问题，但进行了以下更改：
- 距离的度量是行进时间
- 不仅边有权重 - 因此不仅去城市旅行需要时间，游览城市也需要时间（最简单的方法是将在城市的时间添加到每个传入边)
- 每个城市都有一个奖励。一旦你访问了一个城市，你就会得到它的奖励。
- 可以访问的城市有最大时间段（例如，从 6 月 1 日到 6 月 17 日）。所以最大总距离（在本例中时间）是有限的。
- 访问城市的时刻可能受到限制（例如，您只能在 6 月访问芝加哥第四.)
- 某些城市可能被标记为强制性。您必须访问所有强制性城市和任意数量的非强制性城市（例如。必须访问拉斯维加斯）
- 终点城市可能与起点城市不同，但必须指定（例如起点必须是华盛顿，终点必须是洛杉矶）。所以路由可能是非循环的。
本例中的目标不是最小化旅行距离（时间），而是最大化总奖励并满足所有限制条件（总时间、访问时刻、强制性城市） .
我正在努力，但我不想重新发明轮子
- 上述问题有具体名称吗？ （例如 是的，那是 XYZ 问题）
- 或者是任何众所周知的问题的情况（例如，是的，属于 XYZ 优化问题）
目前我只知道与：
有关
- 旅行商问题，
- 约束满足问题，
- （整数）线性规划，
- 随时间变化的车辆路径问题Window
感谢您的回答和帮助。
Simple image for better understanding (case of 4 cities)
我找到了：上面描述的问题是旅游设计问题（TTDP），它是团队定向问题与时间Windows的扩展 (TOPTW).
完整描述、数学模型和推荐算法（ILS - 迭代局部搜索）可以在文章中找到：https://www.patatconference.org/patat2016/files/proceedings/paper_15.pdf
考虑旅行商问题，但进行了以下更改：
- 距离的度量是行进时间
- 不仅边有权重 - 因此不仅去城市旅行需要时间，游览城市也需要时间（最简单的方法是将在城市的时间添加到每个传入边)
- 每个城市都有一个奖励。一旦你访问了一个城市，你就会得到它的奖励。
- 可以访问的城市有最大时间段（例如，从 6 月 1 日到 6 月 17 日）。所以最大总距离（在本例中时间）是有限的。
- 访问城市的时刻可能受到限制（例如，您只能在 6 月访问芝加哥第四.)
- 某些城市可能被标记为强制性。您必须访问所有强制性城市和任意数量的非强制性城市（例如。必须访问拉斯维加斯）
- 终点城市可能与起点城市不同，但必须指定（例如起点必须是华盛顿，终点必须是洛杉矶）。所以路由可能是非循环的。
本例中的目标不是最小化旅行距离（时间），而是最大化总奖励并满足所有限制条件（总时间、访问时刻、强制性城市） .
我正在努力，但我不想重新发明轮子
- 上述问题有具体名称吗？ （例如 是的，那是 XYZ 问题）
- 或者是任何众所周知的问题的情况（例如，是的，属于 XYZ 优化问题）
目前我只知道与：
有关- 旅行商问题，
- 约束满足问题，
- （整数）线性规划，
- 随时间变化的车辆路径问题Window
感谢您的回答和帮助。 Simple image for better understanding (case of 4 cities)
我找到了：上面描述的问题是旅游设计问题（TTDP），它是团队定向问题与时间Windows的扩展 (TOPTW).
完整描述、数学模型和推荐算法（ILS - 迭代局部搜索）可以在文章中找到：https://www.patatconference.org/patat2016/files/proceedings/paper_15.pdf