Optaplanner:扩展VRP示例以解决多次旅行案例 [英] Optaplanner: extending the vrp example to tackle multi trip case

问题描述

在我公司，我们目前正在使用optaplanner来解决车辆路线问题，并取得了丰硕的成果，我们构建了一个Web应用程序来管理车辆，客户，位置，仓库以及显示解决方案的图形表示(包括显示解决方案中的位置)一张地图).我们将求解器包装在带有rest接口的spring java应用程序中，以接收请求并解决问题.我们正在使用Google地图获取距离-时间数据.现在我们需要实现multirip ....

要解决多程旅行问题，我正在采用这种方法:

1.-我在Vehicle类中添加了readyTime，endOfTrip和DueTime成员

2.-我创建了一个规则，以防止在Vehicle-> dueTime之后到达客户

3.-我修改了ArrivalTimeUpdateListener，以在计算车辆的发车时间时考虑车辆-> readyTime(使用Math.max(depot-> readyTime，vehicle-> readyTime)

4.-此时，我开始使用车辆类，就好像它是车辆旅行而不是车辆(我仍然不更改名称，但这是个主意)

5.-我在车辆中创建了一个nextVehicle成员来代表下一次旅行

6.-出于测试目的，我手动将两辆车(或车辆行程)链接起来，然后将其发送到solver-> solve

7.-在ArrivalTimeUpdatingVariableListener类中，我扩展了用于更新到达时间的方法，以考虑更新nextVehicle-> readyTime，因此将属于下一次行程的客户的到达时间更新(以此类推.超过两次)

我确信这不是最优雅的解决方案，但是我尝试了其他方法(例如，在Vehicle上使用自定义阴影变量)，但无法使其正常工作. 我现在面临的问题是，调用ArrivalTimeUpdatingVariableListener时，我不了解模型的状态，也许有人遇到了类似的问题，可以为我提供帮助.我发现(尝试并出错后)是:

• customer.getVehice()方法并不总是返回一个值(与空值不同)，它似乎在前一个"Standstill"更改触发了侦听器"updateArrivalTime"方法之后的某个时间得到了更新.
  • 在建设中，当客户分配给车辆时，customer.getVehice()方法返回null(来自未分配")
  • 在建设中，当客户被释放"时，customer.getVehice()方法返回先前的车辆"
  • 在本地搜索中，当客户分配给车辆时，customer.getVehice()方法返回先前车辆"(原始车辆)
  • 在本地搜索中，当客户返回原始车辆时，customer.getVehice()方法返回先前的分配车辆"

对此有何想法?我在做正确的假设吗? (因为最初我将customer.getVehicle()视为实际"工具，而解决方案则完全错误...)

• 触发上一个"Standstill"更改的顺序，这对我来说很难理解.我的意思是说，在移动客户或在车辆之间交换客户时...关于查找信息的任何想法或提示?

• 求解器移动时是否可以从模型的先前状态"访问某些变量?因为我认为如果继续使用此方法(更新vehicle-> endOfTrip，则将需要该变量)例如，当客户是链上的最后一个客户时，这就是nextVehicle-> readyTime.

最后...我在概念上做错了什么吗?

任何评论将不胜感激(对不起，我的语法是母语为西班牙语)

解决方案

您描述的影子变量的混沌触发在optaplanner 6.3.0.Final或更高版本中不再发生，因为它现在提供了如下所示的保证. /p>

但是较旧的版本(optaplanner 6.2和更早版本)遭受那种混乱的触发行为(由PLANNER-252修复-是的，我确实知道该问题的编号-是的，我不是唯一的一个)可以驱使开发人员(正在处理具有多个阴影变量的复杂模型)疯狂，并提供庇护的单程票.

幸运的是，它已在几个月前修复，因此请升级到6.3.0.Final或更高版本，并保持理智.

At my company we are currently using optaplanner to solve a vehicle routing problem with great results, we built a web app to manage vehicles, clientes, locations, depots and to show a graphic representation of the solution (including showing the locations in a map). We wrapped the solver in a spring java app with a rest interface to receive request and solve the problem. We are using Google maps to get distance-time data. Now we need to implement multirip....

To tackle the multitrip part I am following this approach:

1.- I added readyTime, endOfTrip and dueTime members to Vehicle class

2.- I created a rule to prevent arrivals at customers after vehicle->dueTime

3.- I modified the ArrivalTimeUpdateListener to consider the vehicle->readyTime when calculating the departureTime from a vehicle (using Math.max(depot->readyTime, vehicle->readyTime)

4.- At this point I started using the vehicle class as if it were a vehicle trip instead of a vehicle (I still don´t change the name but that is the idea )

5.- I created a member nextVehicle in vehicle to represent the next trip

6.- For testing purposes I manually link two vehicles (or vehicle trips) before sending it to solver->solve

7.- In the ArrivalTimeUpdatingVariableListener class I extended the method that updates the arrival times to consider updating the nextVehicle->readyTime and by consequence the arrival times of the customers that belong to the next trip (and so on when there are more than two trips)

I am sure this is not the most elegant solution, but I tried other approaches (using custom shadow variable on Vehicle for instance) but it couldn´t make it work. The problem I am facing right now is that I don´t get to understand the state of the model when ArrivalTimeUpdatingVariableListener is called, maybe someone faced similar problem and can help me. What i found (after try and error) is:

• the customer.getVehice() method not always returns a value (distinct from null value), it seems to get updated some time after the previousStandstill change triggers the listener "updateArrivalTime" method.
  • In construction fase when a customer get assign to a vehicle the customer.getVehice() method returns null (it came from "not assigned")
  • In construction fase when a customer "is freed" the customer.getVehice() method returns the "previous vehicle"
  • In local search fase when a customer get assign to a vehicle the customer.getVehice() method returns the "previous vehicle" (original vehicle)
  • In local search fase when a customer go back to the original vehicle the customer.getVehice() method returns the "previous assign vehicle"

Any thoughts on this? Am I making right assumptions? (because originally I considered customer.getVehicle() as the "actual" vehicle and the solutions were completely wrong...)

• The order of triggering the previousStandstill change it´s kind of difficult to understand (for me). I mean when moving customers or swapping them between vehicles...any thoughts or hints on were to find info?

• Can I access some variables from the "previous state of the model" when the solver makes a move?, because I am thinking I will need that if I continue with this approach (to update the vehicle->endOfTrip that is the nextVehicle->readyTime when the customer is the last one on the chain for instance)

and finally...am i doing something completely wrong conceptually ?

Any comments will be greatly appreciated (and sorry my grammar, I am native spanish speaker)

解决方案

The chaotic triggering of shadow vars that you describe should not happen any more in optaplanner 6.3.0.Final or higher because it now gives the guarantee shown below.

But older versions (optaplanner 6.2 and earlier) suffer from that chaotic trigger behaviour (as fixed by PLANNER-252 - yes I know that issue number by heart - and yes, I am not the only one) could drive a developer (who's working on a complex model with multiple shadow variable(s)) insane and provide a one way ticket to the asylum.

Fortunately it has been fixed a few months ago, so upgrade to 6.3.0.Final or later and keep your sanity.

这篇关于Optaplanner:扩展VRP示例以解决多次旅行案例的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！