OptaPlanner- TSPTW 最小化总时间

Question

我正在使用 OptaPlanner 有效地解决旅行商时间问题 Windows (TSPTW)。我有一个基于 OptaPlanner 提供的 VRPTW 示例的有效初始解决方案。

我现在正在尝试解决偏离标准 TSPTW 的要求，这些要求是：

我试图尽量减少花费的总时间而不是总行进距离。因此，空闲时间对我不利。
除了标准时间 windowed 访问之外，我还必须支持不迟于 (NLT) 访问（即不要在 X 时间后访问）和不早于 (NET)访问（即不要在 X 时间之前访问）。

我当前的解决方案总是将第一次访问的到达时间设置为该访问的开始时间。这对我的要求有以下问题：

这可能会引入不必要的空闲时间，如果访问在其时间 window 之后的某个时间到达，则可以避免这种空闲时间 window。
NLT 的行为存在问题。如果我定义一个开始时间设置为 Long.MIN_VALUE 的 NLT（表示它是无界的而不求助于空值），那么这就是 NLT 访问到达的时间（与 #1 相同的问题）。我尝试通过将开始时间设置为 NLT 时间来解决这个问题。这导致正好赶上 NLT 访问，但超出了后续访问的时间 windows。

我应该如何解决 this/these 问题？我怀疑解决方案将涉及 ArrivalTimeUpdatingVariableListener，但我不知道该解决方案应该是什么样子。

如果相关，我已在下面粘贴了我当前的评分规则。需要注意的一件事是 "distance" 确实是旅行时间。此外，出于领域原因，我鼓励 NLT 和 NET 到达时间接近截止时间（NLT 的结束时间，NET 的开始时间）。

import org.optaplanner.core.api.score.buildin.hardsoftlong.HardSoftLongScoreHolder;

global HardSoftLongScoreHolder scoreHolder;

// Hard Constraints
rule "ArrivalAfterWindowEnd"
  when
    Visit(arrivalTime > maxStartTime, $arrivalTime : arrivalTime, $maxStartTime : maxStartTime)
  then
    scoreHolder.addHardConstraintMatch(kcontext, $maxStartTime - $arrivalTime);
end

// Soft Constraints
rule "MinimizeDistanceToPreviousEvent"
  when
    Visit(previousRouteEvent != null, $distanceFromPreviousRouteEvent : distanceFromPreviousRouteEvent)
  then
    scoreHolder.addSoftConstraintMatch(kcontext, -$distanceFromPreviousRouteEvent);
end

rule "MinimizeDistanceFromLastEventToHome"
  when
    $visit : Visit(previousRouteEvent != null)
    not Visit(previousRouteEvent == $visit)
    $home : Home()
  then
    scoreHolder.addSoftConstraintMatch(kcontext, -$visit.getDistanceTo($home));
end

rule "MinimizeIdle"
  when
    Visit(scheduleType != ScheduleType.NLT, arrivalTime < minStartTime, $minStartTime : minStartTime, $arrivalTime : arrivalTime)
  then
    scoreHolder.addSoftConstraintMatch(kcontext, $arrivalTime - $minStartTime);
end

rule "PreferLatestNLT"
  when
    Visit(scheduleType == ScheduleType.NLT, arrivalTime < maxStartTime, $maxStartTime : maxStartTime, $arrivalTime : arrivalTime)
  then
    scoreHolder.addSoftConstraintMatch(kcontext, $arrivalTime - $maxStartTime);
end

rule "PreferEarliestNET"
  when
    Visit(scheduleType == ScheduleType.NET, arrivalTime > minStartTime, $minStartTime : minStartTime, $arrivalTime : arrivalTime)
  then
    scoreHolder.addSoftConstraintMatch(kcontext, $minStartTime - $arrivalTime);
end

Answer 1

查看使用真实道路时间而不是道路距离的示例：在示例应用程序中，打开 Vehicle Routing，单击按钮导入，加载文件 roaddistance/capacitated/belgium-road-time-n50-k10.vrp .那些时间是 calculated with GraphHopper。

要查看使用时间 Windows 的示例，请打开车辆路径并快速打开名为 cvrptw 的数据集（tw 代表时间 Windows）。如果您查看 CVRPTW 的学术规范（从文档第 3 章 IIRC 链接），您会发现它已经有一个硬约束 "Do not arrive after time window closes" - 所以您会在分数规则 drl 中看到那个。至于过早到达（因此失去空闲时间）：复制粘贴那个硬约束，使其成为软约束，使其使用 readyTime 而不是 dueTime 并反转它的比较和惩罚计算。我实际上最初实现了它（因为这是合乎逻辑的事情），但因为我遵循学术规范（与学术结果进行比较）我不得不删除它。

Answer 2

我能够通过修改 ArrivalTimeUpdatingVariableListener 的 updateArrivalTime 方法向后到达并（尝试）改变之前的到达时间来解决我的问题。此外，我引入了一个 getPreferredStartTime() 方法来支持默认为尽可能晚的 NLT 事件。最后，为了代码整洁，我将 updateArrivalTime 方法从 ArrivalTimeUpdatingVariableListener 移到了 Visit class.

这里是访问class的相关代码：

public long getPreferredStartTime()
{
    switch(scheduleType)
    {
        case NLT:
            return getMaxStartTime();
        default:
            return getMinStartTime();
    }
}

public Long getStartTime()
{
    Long arrivalTime = getArrivalTime();
    if (arrivalTime == null)
    {
        return null;
    }

    switch(scheduleType)
    {
        case NLT:
            return arrivalTime;
        default:
            return Math.max(arrivalTime, getMinStartTime());
    }
}

public Long getEndTime()
{
    Long startTime = getStartTime();
    if (startTime == null)
    {
        return null;
    }
    return startTime + duration;
}

public void updateArrivalTime(ScoreDirector scoreDirector)
{
    if(previousRouteEvent instanceof Visit)
    {
        updateArrivalTime(scoreDirector, (Visit)previousRouteEvent);
        return;
    }

    long arrivalTime = getPreferredStartTime();
    if(Utilities.equal(this.arrivalTime, arrivalTime))
    {
        return;
    }

    setArrivalTime(scoreDirector, arrivalTime);
}

private void updateArrivalTime(ScoreDirector scoreDirector, Visit previousVisit)
{
    long departureTime = previousVisit.getEndTime();
    long arrivalTime = departureTime + getDistanceFromPreviousRouteEvent();

    if(Utilities.equal(this.arrivalTime, arrivalTime))
    {
        return;
    }

    if(arrivalTime > maxStartTime)
    {
        if(previousVisit.shiftTimeLeft(scoreDirector, arrivalTime - maxStartTime))
        {
            return;
        }
    }
    else if(arrivalTime < minStartTime)
    {
        if(previousVisit.shiftTimeRight(scoreDirector, minStartTime - arrivalTime))
        {
            return;
        }
    }

    setArrivalTime(scoreDirector, arrivalTime);
}

/**
 * Set the arrival time and propagate the change to any following entities.
 */
private void setArrivalTime(ScoreDirector scoreDirector, long arrivalTime)
{
    scoreDirector.beforeVariableChanged(this, "arrivalTime");
    this.arrivalTime = arrivalTime;
    scoreDirector.afterVariableChanged(this, "arrivalTime");

    Visit nextEntity = getNextVisit();
    if(nextEntity != null)
    {
        nextEntity.updateArrivalTime(scoreDirector, this);
    }
}

/**
 * Attempt to shift the arrival time backward by the specified amount.
 * @param requested The amount of time that should be subtracted from the arrival time.
 * @return Returns true if the arrival time was changed.
 */
private boolean shiftTimeLeft(ScoreDirector scoreDirector, long requested)
{
    long available = arrivalTime - minStartTime;
    if(available <= 0)
    {
        return false;
    }

    requested = Math.min(requested, available);
    if(previousRouteEvent instanceof Visit)
    {
        //Arrival time is inflexible as this is not the first event. Forward to previous event.
        return ((Visit)previousRouteEvent).shiftTimeLeft(scoreDirector, requested);
    }

    setArrivalTime(scoreDirector, arrivalTime - requested);
    return true;
}

/**
 * Attempt to shift the arrival time forward by the specified amount.
 * @param requested The amount of time that should be added to the arrival time.
 * @return Returns true if the arrival time was changed.
 */
private boolean shiftTimeRight(ScoreDirector scoreDirector, long requested)
{
    long available = maxStartTime - arrivalTime;
    if(available <= 0)
    {
        return false;
    }

    requested = Math.min(requested, available);
    if(previousRouteEvent instanceof Visit)
    {
        //Arrival time is inflexible as this is not the first event. Forward to previous event.
        //Note, we could start later anyways but that won't decrease idle time, which is the purpose of shifting right
        return ((Visit)previousRouteEvent).shiftTimeRight(scoreDirector, requested);
    }

    setArrivalTime(scoreDirector, arrivalTime + requested);
    return false;
}

OptaPlanner- TSPTW 最小化总时间

OptaPlanner- TSPTW minimizing total time

optaplanner