车辆路径/资源调度算法设计
我在这里的第一篇文章 - 希望你能帮助我设计一个我已经考虑了一段时间的算法 - 不确定采取什么方法（VRPTW 或资源调度或完全其他的东西！？）
将其付诸实践例如，我们在少数地点（通常少于 5 个）有大量花园垃圾。废物必须在规定的时间内全部运往其他地点。为了移动花园垃圾，我们有拖车，必须由汽车牵引。花园垃圾只能在特定时间（时间窗口）扔到垃圾站。在某些地点，我们可以将拖车交给那里的人来装满或清空，但在其他地点，汽车司机必须自己完成，并且汽车必须留在那里。所有时间都可以计算（即装载/卸载时间、运输时间等）。汽车可以在没有拖车的情况下在站点之间移动，拖车可以空拖，但拖车不能在站点之间自行移动。
我们的目标是确保运输所有拖车装载的废物，同时
- 最大限度地减少使用中的拖车和汽车的数量，
- 满足所有时间窗口的要求，以“平衡”拖车投放废物
- ——即在一天结束时，我们每个地方都有尽可能多的拖车位置就像今天开始时一样，
我想将其作为资源调度算法来处理，但我不确定如何处理拖车的“平衡”。
我考虑的另一种方法是首先考虑汽车。然后我可以选择最早的任务并构建此后所有可行任务的图表。如果我选择图表中最长的路径，该路径将服务于最大数量的拖车负载。然后，我可以从任务列表中删除这些任务并重复，直到所有任务都得到服务。然后，我需要查看这些拖车负载列表，以计算出所需的拖车数量。
任何有关方法的想法将不胜感激！
My first post here – hoping you can help me with designing an algorithm that I’ve been considering for a little while now – not sure what approach to take (VRPTW or resource scheduling or something else entirely!?)
To put it into a real word example, we have a whole lot of garden waste at a small number of locations (usually less than 5). The waste must all be transported to other locations within given time frames. To move the garden waste we have trailers, which must be towed by cars. Garden waste can only be dropped at the waste depot at certain times (time windows). At some sites we can drop off the trailer to be filled up or emptied by people there, but at other locations the driver of the car has to do it himself and the car must remain there. All timings can be calculated (i.e. loading / unloading times, transit times etc). Cars can move between sites without a trailer, trailers can be towed empty but trailers cannot move themselves between locations.
Our objective is to ensure all trailer loads of waste are transported whilst
- minimising the number of trailers and cars in use
- meeting all time windows for dropping off waste
- “balancing” the trailers – i.e. at the end of the day we have as many trailers at each location as were there at the start of the day
I thought of approaching this as a resource scheduling algorithm but I’m unsure how to handle the “balancing” of trailers.
One other method I considered was to consider the cars first. I could then select the earliest task and build a graph of all feasible tasks after that. If I then picked the longest path through the graph that would service the maximum number of trailer loads. I could then remove these tasks from the list of tasks and repeat until all tasks were serviced. I would then need to run over these list of trailer loads to work out the number of trailers required.
Any thoughts as to approach would be appreciated!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
我同意 Jiri 的观点……你想要一种启发式算法，能够快速合理地接近可接受的解决方案，然后从那里进行改进。
我之前曾在拥有交付路由软件的公司工作过，他们采取的方法是使用遗传算法来解决非常相似但规模更大的问题。如果您不熟悉该方法，请查看此处。从该站点：
[新群体] 通过重复创建一个新群体按照步骤进行，直到新种群完成
【选择】根据适应度从群体中选择两条亲本染色体（适应度越好，被选择的机会越大）
【交叉】以交叉概率将父母交叉，形成新的后代（孩子）。如果没有进行交叉，后代就是父母的精确副本。
[突变]以突变概率在每个基因座（染色体中的位置）突变新的后代。
[接受]将新的后代放入新种群
这样做的技巧是将您的约束编码为“染色体”并编写“适应度”函数。适应度函数必须输入潜在解决方案的结果，并给出解决方案的好坏程度的分数，或者如果它违反任何约束则将其丢弃。
正如 Jiri 所提到的，这个解决方案的优点是它能很快地给出一个可行的答案，尽管可能不是最好的，而且让它运行的时间越长，解决方案就越好。
I agree with Jiri...you want a heuristic algorithm that gets reasonably close with an acceptable solution quickly and then refines from there.
I've worked at companies before that had delivery routing software and the approach they took was to use a genetic algorithm to solve very similar, though much larger scale, problem. Take a look here if you're not familiar with the approach. From that site:
[New population] Create a new population by repeating following steps until the new population is complete
[Selection] Select two parent chromosomes from a population according to their fitness (the better fitness, the bigger chance to be selected)
[Crossover] With a crossover probability cross over the parents to form a new offspring (children). If no crossover was performed, offspring is an exact copy of parents.
[Mutation] With a mutation probability mutate new offspring at each locus (position in chromosome).
[Accepting] Place new offspring in a new population
The trick to this is encoding your constraints into a "chromosome" and writing the "fitness" function. The fitness function has to take inputs of the results of a potential solution and spit out a score of how good a solution that is or throw it out if it violates any of the constraints.
As mentioned by Jiri, the advantage of this solution is that it comes up with a workable, though maybe not the best, answer very quickly and the longer you let it run, the better the solution gets.
我们在这里肯定谈论的是 NP 完整算法，除了一定数量的汽车和拖车之外，这不会是一个任务，您可以从所有可能的解决方案中获得最佳解决方案，然后能够放弃它并再次避免正如你所建议的最长的路径。如果您以这种方式设计算法，很可能有一天您添加了更多的汽车和拖车，并且它永远无法完成解决方案的计算。
您可能想要使用能够相当快速地生成足够好的问题解决方案的算法。确保为解决方案的质量创建一个指标，您有一个很好的方法来估计理想解决方案的指标值，然后为自己设置一些百分比，在该百分比内您希望您的解决方案来自理想解决方案，然后简单地采取第一个在范围内具有度量的解决方案。这样做的另一个好处是，如果该算法计算时间过长而您中止它，您仍然可以使用具有最低计算指标的解决方案，即使它不在您的预期范围内。
但我不确定采取什么方法来解决问题本身。我建议在 acm Portal 上搜索后阅读几篇文章。我认为 UPS 和 Fedex 可能也有类似的问题，如果你将它们作为关键字添加到谷歌搜索中，你可能会得到一些更有用的结果。
We are talking a NP complete algorithm here for sure, beyond some number of cars and trailers this is not gonna be a task where you would get a best solution out of all possible solutions and then be able to discard that and go again to avoid the longest path as you suggest. If you design your algorithm in that way, its very likely that one day you add a bit more cars and trailers and it will never finish computing the solution.
You probably want to go with algorithm that can reasonably fast generate good enough solution of the problem. Make sure you create a metric for quality of the solution, you get a good way to estimate the value of the metric for an ideal solution, then set yourself some % within which you'd like your solution to be from an ideal solution and simply take the first solution that has metric within the bounds. This has the added benefit of if this algorithm is taking too long to compute and you abort it, you can still use the solution with the lowest computed metric, even if it is not in your expected bounds.
I'm not sure what approach to take the solving the problem itself though. I would suggest to read few articles after searching on acm portal. I would assume UPS and Fedex probably have similar problems, if you add them as keywords to a search in google, you could get some more useful results.
我倾向于同意罗伯特的观点。在我看来，这对于进化优化技术（例如他描述的遗传算法实现）来说是一个非常好的候选者。
我在粒子群优化 (PSO) 的某些问题上也取得了非常好的成功。基本上，您可以将每个基因组视为某个多维空间中的一个粒子。粒子的坐标是计算的参数（适应度函数）。每个粒子以随机速度随机启动。对于模拟的每次迭代，您使用每个粒子的当前行进向量更新其位置，然后添加其他向量的分量，例如：迄今为止最佳粒子的方向、有史以来最佳粒子的方向、局部组的方向最好等...
一开始实现 GA 或 PSO 似乎相当令人畏惧，但我向您保证，编写一个小型框架很容易，该框架可以从您尝试解决的实际问题域中抽象出算法（GA/PSO）优化。您可以随时返回维基百科来了解算法的详细信息。
一旦我有了一个框架，我通常会从一个 2 参数问题开始（可能是问题的简化，或者图像上的 X 和 Y 位置），这样我就可以轻松地可视化和调整算法，从而获得良好的集群行为。然后我将其放大到更多维度。
我喜欢这种方法，因为它使我能够轻松优化实际问题陈述中具有相当复杂和复杂部分的问题（例如汽车和拖车）。
此外，进化技术之所以有吸引力，是因为您可以投入固定的时间进行模拟，并在决定停止时获得迄今为止的最佳答案。
根据我的经验，您往往会花费与编写硬编码启发式解决方案一样多的时间来调整 GA 或 PSO 的参数（一旦实现），但这样做的好处是可以更改通常寻找解决方案的策略仅需要更改参数或将定义明确的算法替换为另一种实现，而不是编写完全不同的策略来从头开始启发式解决问题。
如果您需要为这两种算法设计通用框架的指导，请告诉我。我必须指出，您也可以获得一些很好的免费第三方框架。有时我喜欢自己编写代码，因为我了解算法的各个方面，并且知道可以在哪里调整策略。
I tend to agree with Robert. This sounds to me like a really great candidate for an evolutionary optimisation technique like the Genetic Algorithm implementation that he describes.
I have also had very good success on certain problems with the Particle Swarm Optimisation (PSO).Basically, you can think of each genome as a particle in some multi dimensional space. The coordinates of the particle are the paramters to your calculation (fitness function). Each particle is started of randomly with a random velocity. For each iteration of the simulation, you update the position of each particle with its current travel vector, and then you add components of other vectors like: direction to the best particle so far, direction to the best particle ever, direction to a local group best etc...
It may seem rather daunting at first to implement a GA or PSO but I assure you that it is easy to write a small framework that abstracts the algorithm (GA/PSO) from the actual problem domain that you are trying to optimise. You can always fall back to Wikipedia for details of the algorithms.
Once I have a framework, I normally start with a 2 parameter problem (probably a simplification of your problem, or X and Y locations on an image), so that I can easily visualise and tweak the algorithm so that I get good swarming behaviour. Then I scale it up to more dimensions.
I like this approach because it allows me to easily optimise for problems that have rather complex and intricate parts to the actual problem statement (like the cars and trailers).
Also, why the evolutionary techniques are attractive is because you can dedicate a fixed portion of time to the simulation and take the best answer so far when you decide to stop.
In my experience, you tend to take as much time tweaking the parameters to the GA or PSO (once you have an implementation) as you would writing a hard coded heuristic solution, but the benefit is that to change the strategy for finding the solution typically requires parameter changes only or swapping out very well defined algorithms with another implementation, as opposed to coding a completely different strategy to solving the problem heuristically from scratch.
Please give me a shout if you need guidance on designing the generic frameworks for either of the two algorithms. I must point out, that you get several good free 3rd party frameworks out there too. I sometimes like to code my own because I understand every aspect of the algorithm then and I know where I can adjust the strategy.
一般方法：
由于问题很小，我建议您添加汽车和拖车，直到获得可行的解决方案，而不是尝试最小化汽车和拖车。
解决：
我在具有约束的 GA 上取得的成功较少，在具有整数变量（例如某个位置的拖车数量）约束的 GA 上取得的成功更少。约束规划可能是一种更好的方法，因为您只想为给定数量的汽车和拖车生成可行的解决方案，而不是试图最小化行驶距离。
观察：
您正在解决网络上的问题，其中最后一步可能是重新定位空拖车。
祝你好运 ！
General Approach:
Since the problem is small, I would suggest an approach where you add cars and trailers until you get a feasible solution rather than trying to minimize cars and trailers.
Solving:
I've had less success on GAs with constraints and even less success on GAs with constraints on integer variables (e.g. the number of trailers in a location). It may be that constraint programming is a better approach since you just want to generate a feasible solution for a given number of cars and trailers rather than trying to minimize distance travelled.
Observation:
You're solving the problem on a network where the last moves may be to relocate an empty trailer.
Good luck !
本地搜索是遗传算法的替代方案。在2007年国际时间表竞赛中，本地搜索算法（例如禁忌搜索和模拟退火）明显击败了遗传算法参赛者（在赛道1中，LS获得第1至第4名，而GA则获得第5名） 80 名参赛者 IIRC)。
另外，看看那里的一些库，例如 OptaPlanner （禁忌搜索、模拟退火、延迟接受，开源，java），JGap（遗传算法，开源，java），OpenTS（禁忌搜索，...
Local Search are an alternative to genetic algorithms. In the International Timetabling Competition 2007, local search algorithms (such as tabu search and simulated annealing) clearly beat the genetic algorithm entries (1 to 4th place for LS versus 5th place for GA in track 1 out of about 80 competitors IIRC).
Also, take a look at some of the libraries out there, such as OptaPlanner (Tabu Search, Simulated Annealing, Late Acceptance, open source, java), JGap (genetic algorithms, open source, java), OpenTS (Tabu Search, ...