traveling-salesman - 如何在结果中考虑用户修改并在 VRP 中考虑它们

Question

我正在研究一个 VRP（车辆路线问题）来制定接送服务计划，因为 VRP 是 NP 难题，用户根据他们的要求编辑计划。现在我计划在准备计划时考虑他们的修改。我应该从哪里开始？

Answer 1

将专家知识整合到 VRP 优化器中的最简单方法可能是使用约束。如果您使用 JSprit，请查看JSprit 约束文档作为起点。如果可用的约束类型不足以模拟您的专家所拥有的知识，您可能需要更深入地挖掘并使用成本函数和搜索策略。

从专家对先前路线所做的改进中自动推断出约束是很困难的。路线的任何改变可能有很多原因——如果专家没有明确告诉你，就很难说出他们为什么做出改变。如果可能，请专家明确定义约束。例如，专家将告诉您的系统“地址 X 和地址 Y 始终必须由同一辆车提供服务”，而不是仅仅更改路线以使来自地址 X 的工作和来自地址 Y 的工作由车辆 1 提供服务。

顺便说一句，由于这是一个相当普遍的算法问题，您可以尝试将其发布在Compute Science Stack Exchange上。