有容量的车辆路径问题（cvrp）的随机解

解答动态

• 

  “随机解”表示随机选择决策变量。它通常并不意味着忽略可行性约束。因此，在CVRP的情况下，它意味着为给定的路线随机选择城市，以及他们在路线上的顺序。处理容量的方法有很多种——例如，如果下一个随机选择的城市将违反当前路线的容量，则启动一条新路线。或者，如果下一个随机选择的城市违反了通行能力，那么继续检查所有城市（以随机顺序），直到找到一个通行能力可行的城市，或者直到检查了所有剩余的城市。
  
• 

  通常这样的语句意味着您应该设置一个依赖于某种程度的随机性的构造启发式。也就是说，如果您运行两次构造过程，您不应该（必然）得到相同的解决方案。在大多数情况下，如果没有明确说明，我会期望解决方案对问题是可行的（在您的情况下，它可能应该尊重容量）。
  一个简单的，可能不是很好的，CVRP的随机构造启发式可能是沿着2的路线的东西，通过在车辆段放置一辆车来启动一条新路线。让站点成为当前节点创建一个$k\geq 1$有希望的节点列表，这些节点不属于任何其他路由（需求小于车辆剩余容量的节点）。生成一个介于1和$k$之间的随机数$l$，并使用列表中的第$l$个节点扩展路由。让第$l$个节点成为当前节点节点。如果所有节点都属于一个路由，返回解决方案。如果路线不能再延长了，返回车辆段，前往1。如果我同意其他的答案，我认为值得一提的是随机初始解不一定是可行的。当使用（元）启发式时，在搜索空间中经常使用不可行解，尽管成本函数中的冲突数量（违反约束的次数）最小化。
  例如，本文中的情况就是这样，作者为CVRP开发了一种称为TABUROUTE的禁忌搜索启发式算法，在整个过程中使用了不可行路径（关于长度或容量）。
  
• End