Optaplanner时间窗口的约束条件

huangapple go评论76阅读模式
英文:

Optaplanner constraints for time windows

问题

以下是翻译好的内容:

我正在尝试使用OptaPlanner解决VRP问题。我有多个客户,每个客户都有不同的时间窗口。以下是我的约束提供者:

protected Constraint arrivalAfterDueTime(ConstraintFactory factory) {
    return factory.from(TimeWindowedCustomer.class)
            .filter(customer -> customer.getArrivalTime() >= customer.getDueTime())
            .penalizeLong("arrivalAfterDueTime",
                    HardSoftLongScore.ONE_HARD,
                    customer -> customer.getArrivalTime() - customer.getDueTime());
}

protected Constraint arrivalBeforeReadyTime(ConstraintFactory factory) {
    return factory.from(TimeWindowedCustomer.class)
            .filter(customer -> customer.getArrivalTime() > customer.getReadyTime()
            && customer.getArrivalTime() < customer.getDueTime() )
            .penalizeLong("arrivalBeforeReadyTime",
                    HardSoftLongScore.ONE_HARD,
                    customer -> customer.getReadyTime() - customer.getArrivalTime());
}

但是在解决方案中,我得到了到达时间早于准备时间的情况。我应该如何修复这个问题?提前谢谢您的帮助。

英文:

I am trying to solve VRP with OptaPlanner. I have multiple customers that have different time windows. Here are my constraint providers

protected Constraint arrivalAfterDueTime(ConstraintFactory factory) {
        return factory.from(TimeWindowedCustomer.class)
                .filter(customer -&gt; customer.getArrivalTime() &gt;= customer.getDueTime())
                .penalizeLong(&quot;arrivalAfterDueTime&quot;,
                        HardSoftLongScore.ONE_HARD,
                        customer -&gt; customer.getArrivalTime() - customer.getDueTime());
    }

protected Constraint arrivalBeforeReadyTime(ConstraintFactory factory) {
        return factory.from(TimeWindowedCustomer.class)
                .filter(customer -&gt; customer.getArrivalTime() &gt; customer.getReadyTime()
                &amp;&amp; customer.getArrivalTime() &lt; customer.getDueTime() )
                .penalizeLong(&quot;arrivalBeforeReadyTime&quot;,
                        HardSoftLongScore.ONE_HARD,
                        customer -&gt; customer.getReadyTime() - customer.getArrivalTime());
    }

But in the solution I get arrival times that are < ready time. How can I fix this? Thank you in advance.

答案1

得分: 1

一般有三种方法来处理提前到达的情况:

  • A) 等待直到时间窗口开启,虽然会浪费时间,但不会额外产生惩罚。因此,当车辆在9:30到达,服务时间为0:10,准备时间为10:00时,车辆会在10:10出发(而不是9:40!)。如果您设置了减少车辆总活动时间的一般性约束(或每辆车的最大活动时间与每天任务过多的组合),将自动避免此情况。
  • B) 与A)相同,但会额外产生轻微惩罚。如果没有全局约束来减少车辆总活动时间,这可能会很有用。
  • C) 与A)相同,但会额外产生严重惩罚。这很危险,因为考虑有两个任务,一个时间窗口是9:00到10:00,另一个是11:00到12:00,它们之间有10分钟的行驶时间,并且没有其他任务,这将阻止一个车辆同时执行这两个任务。

无论如何,使用ConstraintVerifier来单元测试您的约束条件!

英文:

There are generally three approaches when arriving too early:

  • A) Wait until the time windows open, losing that time but with no extra penalty. So when it arrives at 9:30, with a service time of 0:10 and ready time of 10:00, the vehicle departs at 10:10 (not 9:40!). This will automatically be avoided if you have a general constraint to reduce the total activity time of vehicles (or a combination of max activity time per vehicle with too many tasks per day).
  • B) Same as A), with an extra soft penalty. This can be useful if you don't have a global constraint to reduce the total activity time of vehicles.
  • C) Same as A) with an extra hard penalty. This is dangerous because given 2 tasks, one with a time window from 9:00 to 10:00 and one from 11:00 to 12:00, with a 10 minute drive in between, and no other tasks, you're not allowing one vehicle to do both those tasks.

In any case, use ConstraintVerifier to unit test your constraints!

huangapple
  • 本文由 发表于 2020年5月4日 00:00:05
  • 转载请务必保留本文链接:https://go.coder-hub.com/61577514.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定