利润最大化的算法：解决方法/方法？ （高级 NP 完全）
这很难，所以非常感谢所有帮助！
我知道它是 NP-Complete，因此无法在多项式时间内解决，但在分析中寻求帮助，它简化为什么类型的 NP-Complete 问题，它让你想起类似的问题，等等。
故事如下。我拥有一家冰淇淋车公司，拥有n辆卡车。我有 m 个送货站。每个位置mi都有pi个人在等我。买完冰淇淋后，大家就离开了。 pi 随着时间的推移，随着越来越多的人排队购买冰淇淋而增加。
我怎样才能知道接下来要把卡车发往哪里，以便在某一天最大化我的利润？
需要记住的事情：
- 两辆卡车在相似的时间停在同一地点只会获得一次利润，即人们在一辆卡车到达后离开
- 卡车从一个地点到达另一个地点需要时间
- p i 在每个站点随着时间的推移而增加，但有些站点比其他站点增加得更快，即某些位置靠近购物中心（位置，位置，位置）
我尝试将其减少为多机调度问题，旅行销售人员问题、ILP等，但主要问题是每个位置的pi（即TSP中的距离或调度问题中的作业长度）不断增加。
提前致谢！
This one's hard, so all help really appreciated!
I know it is NP-Complete and thus cannot be solved in polynomial time, but looking for help in analysis, what type of NP-Complete problem it reduces to, similar problems it reminds you of, etc.
The story goes as follows. I own an ice cream truck business with n trucks. There are m stops where I make deliveries. Each location mi has pi people waiting for me. After buying their ice cream, everyone leaves. pi increases over time as more people line up to get ice cream.
How can I figure out where to send the trucks next in order to maximize my profit in any given day?
Things to keep in mind:
- Two trucks that stop in the same spot at similar times will only get the profit once, i.e. the people leave after one truck arrives
- The trucks take time to get from one location to another
- pi increases over time at each stop, but some stops increase faster than others, i.e. some locations are near malls (location, location, location)
I've tried reducing this to a multimachine scheduling problem, traveling sales person problem, ILP etc., but the main issue is that the pi at every location (i.e. the distance in the TSP or the job length in the scheduling problem) is constantly increasing.
Thanks in advance!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
听起来像是分配问题的变体。因此，您可能没有考虑过的一种方法是拍卖算法（其优点是可以轻松并行化）或匈牙利算法。
我意识到您的问题很复杂（总是如此！），但拍卖算法非常灵活。您的卡车和客户之间可能存在相当复杂的成本函数。您还可以调整算法，让多辆卡车在容量限制的情况下为多个客户提供服务。
Sounds like a variant of the Assignment Problem. So one approach you may not have considered is an Auction Algorithm (which has the advantage it can be parallelized easily) or Hungarian algorithm.
I realize there are complications in your problem (there always are!) but the Auction algorithm is pretty flexible. You can have quite a complicated cost function between your trucks and customers. You can also tweak the algorithm to have multiple trucks service multiple customers subject to capacity constraints.