解决旅行商背包绑定的策略
Strategy to tackle knapsack binded with travelling salesman
我被分配了以下问题作为暑假的研究课题。但是，我一直未能成功找到相关问题，除了它似乎是旅行商与背包的组合，尽管我不确定是否是这种情况。语句为：
你是一辆卡车driver，赢得了一份大合同，现在你必须
运送很多包裹。有N个包裹要送，每一个
必须在城市的某个地址 (x,y) 交付。
此外，每个包裹 i 都有一个重量 Wi.
为简单起见，假设分布区域是矩形，你
总是从点 (0,90) 开始。
您只有一辆卡车，限载1000辆（不包括
卡车重量）。卡车基重为10.
路途遥远，所以距离
使用 Haversine 距离的计算机。
承包给你的公司会提供足够的燃料，所以
您可以无限次旅行。
但是，您在递送包裹时必须非常小心，因为
你必须交付每一个，如果你选择挑选
旅途中带了包裹，无论如何都要送，你
不能在旅途中离开它们。
因为你有点吝啬，你同意条件，但你知道
如果你不采取接近最优的策略，你的卡车可以
穿多了，合同不全，
这会让你被起诉，让你没有卡车和钱。
所以，根据你的经验，你知道要最大限度地提高生存机会
你的卡车，你必须最小化以下功能：
http://goo.gl/jQxXzN（对不起，我不能post图片，因为我没有足够的声誉）。
其中m为旅行次数，n为每次旅行j的包裹数量，wij为i-th本次旅行i-th礼物的重量，Dist表示之间的半正矢距离两个点，Loc(i)是i-th礼物的位置，Loc(0)和Loc(n)是(0,90)点（起点），wnj（最后一次旅行的权重）始终是卡车重量（基本重量）。
所以，基本上，这些就是我得到的研究课题的限制。
我一直在想，也许某些元启发式算法（例如蚁群算法或遗传算法）可能会有所帮助，但我必须更好地了解这个问题。欢迎任何想法或信息（论文、书籍等）。
这听起来像是容量车辆路径问题 (CRVP) 的变体，特别是针对单车辆和单站点（但使用非统一包装）。有关此问题的一些参考，请参见例如：
- On the Capacitated Vehicle Routing Problem (T.K. Ralphs, L. Kopman, W.R. Pulleyblank, and L.E. Trotter, Jr)
- Modeling and Solving the Capacitated Vehicle Routing Problem on Trees（B.Chandran 和 S.Raghavan）
我认为您的元启发式想法——尤其是蚁群优化 (ACO)——将是一种明智的方法。请注意，对于 TSP 相关问题，通常 ACO 优于遗传算法 (GA)。
可能下面的知名文章 (1) 可以让您开始研究 ACO 方法可能带来的好处。 (2) 扩展 (1) 的结果。请注意，这涵盖了常规 VHP（无能力），但作为起点应该证明是有价值的，至少能提供灵感。
- SavingsAnts for the Vehicle Routing Problem（K.Doerner 等人）
- An improved ant colony optimization for vehicle routing problem (余斌等)
似乎也有专门针对ACO和CVRP的文献，但我无法评论这些的质量，但我会列出它们供您自行检查。请注意，(3) 是 (1) 作者的扩展。
- Parallel Ant Systems for the Capacitated Vehicle Routing Problem（K.Doerner 等人）
- Ant Colony Optimization for Capacitated Vehicle Routing Problem (W.F. Tan 等人)
听起来是个有趣的研究课题，祝你好运！
我被分配了以下问题作为暑假的研究课题。但是，我一直未能成功找到相关问题，除了它似乎是旅行商与背包的组合，尽管我不确定是否是这种情况。语句为：
你是一辆卡车driver，赢得了一份大合同，现在你必须 运送很多包裹。有N个包裹要送，每一个 必须在城市的某个地址 (x,y) 交付。 此外，每个包裹 i 都有一个重量 Wi.
为简单起见，假设分布区域是矩形，你 总是从点 (0,90) 开始。
您只有一辆卡车，限载1000辆（不包括
卡车重量）。卡车基重为10.路途遥远，所以距离 使用 Haversine 距离的计算机。
承包给你的公司会提供足够的燃料，所以 您可以无限次旅行。
但是，您在递送包裹时必须非常小心，因为 你必须交付每一个，如果你选择挑选 旅途中带了包裹，无论如何都要送，你
不能在旅途中离开它们。因为你有点吝啬，你同意条件，但你知道
如果你不采取接近最优的策略，你的卡车可以
穿多了，合同不全，
这会让你被起诉，让你没有卡车和钱。所以，根据你的经验，你知道要最大限度地提高生存机会 你的卡车，你必须最小化以下功能：
http://goo.gl/jQxXzN（对不起，我不能post图片，因为我没有足够的声誉）。
其中m为旅行次数，n为每次旅行j的包裹数量，wij为i-th本次旅行i-th礼物的重量，Dist表示之间的半正矢距离两个点，Loc(i)是i-th礼物的位置，Loc(0)和Loc(n)是(0,90)点（起点），wnj（最后一次旅行的权重）始终是卡车重量（基本重量）。
所以，基本上，这些就是我得到的研究课题的限制。 我一直在想，也许某些元启发式算法（例如蚁群算法或遗传算法）可能会有所帮助，但我必须更好地了解这个问题。欢迎任何想法或信息（论文、书籍等）。
这听起来像是容量车辆路径问题 (CRVP) 的变体，特别是针对单车辆和单站点（但使用非统一包装）。有关此问题的一些参考，请参见例如：
- On the Capacitated Vehicle Routing Problem (T.K. Ralphs, L. Kopman, W.R. Pulleyblank, and L.E. Trotter, Jr)
- Modeling and Solving the Capacitated Vehicle Routing Problem on Trees（B.Chandran 和 S.Raghavan）
我认为您的元启发式想法——尤其是蚁群优化 (ACO)——将是一种明智的方法。请注意，对于 TSP 相关问题，通常 ACO 优于遗传算法 (GA)。
可能下面的知名文章 (1) 可以让您开始研究 ACO 方法可能带来的好处。 (2) 扩展 (1) 的结果。请注意，这涵盖了常规 VHP（无能力），但作为起点应该证明是有价值的，至少能提供灵感。
- SavingsAnts for the Vehicle Routing Problem（K.Doerner 等人）
- An improved ant colony optimization for vehicle routing problem (余斌等)
似乎也有专门针对ACO和CVRP的文献，但我无法评论这些的质量，但我会列出它们供您自行检查。请注意，(3) 是 (1) 作者的扩展。
- Parallel Ant Systems for the Capacitated Vehicle Routing Problem（K.Doerner 等人）
- Ant Colony Optimization for Capacitated Vehicle Routing Problem (W.F. Tan 等人)
听起来是个有趣的研究课题，祝你好运！