optaplanner - 每个客户具有多个位置的车辆路线

Question

我正在尝试解决车辆路线问题，其中每个客户都有多个位置，并且只需要访问其中一个位置。我获取了 optaplanner-master 并按以下方式修改了车辆路由示例:

客户.java:

/*
 * Copyright 2012 Red Hat, Inc. and/or its affiliates.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package org.optaplanner.examples.vehiclerouting.domain;

import com.thoughtworks.xstream.annotations.XStreamAlias;
import com.thoughtworks.xstream.annotations.XStreamInclude;
import org.optaplanner.core.api.domain.entity.PlanningEntity;
import org.optaplanner.core.api.domain.valuerange.CountableValueRange;
import org.optaplanner.core.api.domain.valuerange.ValueRangeFactory;
import org.optaplanner.core.api.domain.valuerange.ValueRangeProvider;
import org.optaplanner.core.api.domain.variable.AnchorShadowVariable;
import org.optaplanner.core.api.domain.variable.PlanningVariable;
import org.optaplanner.core.api.domain.variable.PlanningVariableGraphType;
import org.optaplanner.examples.common.domain.AbstractPersistable;
import org.optaplanner.examples.vehiclerouting.domain.location.Location;
import org.optaplanner.examples.vehiclerouting.domain.solver.DepotAngleCustomerDifficultyWeightFactory;
import org.optaplanner.examples.vehiclerouting.domain.timewindowed.TimeWindowedCustomer;

import java.util.List;

@PlanningEntity(difficultyWeightFactoryClass = DepotAngleCustomerDifficultyWeightFactory.class)
@XStreamAlias("VrpCustomer")
@XStreamInclude({
        TimeWindowedCustomer.class
})
public class Customer extends AbstractPersistable implements Standstill {

    protected int demand;

    // Planning variables: changes during planning, between score calculations.
    protected Standstill previousStandstill;

    // Shadow variables
    protected Customer nextCustomer;
    protected Vehicle vehicle;

    protected List<Location> locations;
    protected Integer selectedLocation = 0;

    public void setSelectedLocation(Integer selectedLocation){
        this.selectedLocation = selectedLocation;
    }

    @PlanningVariable(valueRangeProviderRefs = {"selectedLocation"})
    public Integer getSelectedLocation(){
        return selectedLocation;
    }

    @ValueRangeProvider(id = "selectedLocation")
    public CountableValueRange<Integer> getSelectableLocations(){
        return ValueRangeFactory.createIntValueRange(0, locations.size());
    }

    public void setLocations(List<Location> locations) {
        this.locations = locations;
    }

    public List<Location> getLocations(){
        return locations;
    }

    @Override
    public Location getLocation() {
        return locations.get(selectedLocation);
    }

    @Override
    public String toString() {
        return "Customer " + getId();
    }


    public int getDemand() {
        return demand;
    }

    public void setDemand(int demand) {
        this.demand = demand;
    }

    @PlanningVariable(valueRangeProviderRefs = {"vehicleRange", "customerRange"},
            graphType = PlanningVariableGraphType.CHAINED)
    public Standstill getPreviousStandstill() {
        return previousStandstill;
    }

    public void setPreviousStandstill(Standstill previousStandstill) {
        this.previousStandstill = previousStandstill;
    }

    @Override
    public Customer getNextCustomer() {
        return nextCustomer;
    }

    @Override
    public void setNextCustomer(Customer nextCustomer) {
        this.nextCustomer = nextCustomer;
    }

    @Override
    @AnchorShadowVariable(sourceVariableName = "previousStandstill")
    public Vehicle getVehicle() {
        return vehicle;
    }

    public void setVehicle(Vehicle vehicle) {
        this.vehicle = vehicle;
    }

    // ************************************************************************
    // Complex methods
    // ************************************************************************

    /**
     * @return a positive number, the distance multiplied by 1000 to avoid floating point arithmetic rounding errors
     */
    public long getDistanceFromPreviousStandstill() {
        if (previousStandstill == null) {
            throw new IllegalStateException("This method must not be called when the previousStandstill ("
                    + previousStandstill + ") is not initialized yet.");
        }
        return getDistanceFrom(previousStandstill);
    }

    /**
     * @param standstill never null
     * @return a positive number, the distance multiplied by 1000 to avoid floating point arithmetic rounding errors
     */
    public long getDistanceFrom(Standstill standstill) {
        return standstill.getLocation().getDistanceTo(getLocation());
    }

    /**
     * @param standstill never null
     * @return a positive number, the distance multiplied by 1000 to avoid floating point arithmetic rounding errors
     */
    public long getDistanceTo(Standstill standstill) {
        return getLocation().getDistanceTo(standstill.getLocation());
    }


}

在VehicleRoutingImporter.java中，读取客户位置的代码已更改为:

List<Location> locations = new ArrayList<>(lineTokens.length-2);
for (int j = 2; j < lineTokens.length; ++j){
    long locationId = Long.parseLong(lineTokens[j]);
    Location location = locationMap.get(locationId);
    if (location == null)
        throw new IllegalArgumentException("Missing location (id=" + locationId + ") specified for customer id=" + id);
        locations.add(location)
}
customer.setLocations(locations);

过去调用 Customer.setLocation(location) 的所有其他代码现在都调用 Customer.setLocations(Collections.singletonList(location))。我认为实际上没有任何一个被调用。

在vehicleRoutingSolverConfig.xml中，我删除了这些行(否则，它会提示多个变量):

  <subChainChangeMoveSelector>
    <selectReversingMoveToo>true</selectReversingMoveToo>
  </subChainChangeMoveSelector>
  <subChainSwapMoveSelector>
    <selectReversingMoveToo>true</selectReversingMoveToo>
  </subChainSwapMoveSelector>

tutorial-01-uncapacitated.vrp 现在是:

NAME : tutorial-01-uncapacitated
COMMENT : Geoffrey De Smet - OptaPlanner VRP demo 01
TYPE : CVRP
DIMENSION : 8
EDGE_WEIGHT_TYPE : EUC_2D 
CAPACITY : 100
NODE_COORD_SECTION 
 1 50 50
 2 45 100
 3 30 80
 4 70 85
 5 60 60
 6 35 10
 7 30 30
 8 45 20
DEMAND_SECTION
1 0
2 1 2 3
3 1 3 4
4 1 4 5
5 1 5 6
6 1 6 7
7 1 7 8
8 1 8 2
DEPOT_SECTION
 1  
 -1  
VEHICLES : 2
EOF

它似乎有效，并在小型测试用例中找到了最佳解决方案(并且在大型用例中看起来像是合理的解决方案)。但是，当我设置 FAST_ASSERT 模式时，它失败并出现以下错误:

Caused by: java.lang.IllegalStateException: Impossible VariableListener corruption: the expectedWorkingScore (0hard/-30000soft) is not the workingScore (0hard/-34142soft) after all VariableListeners were triggered without changes to the genuine variables. But all the shadow variable values are still the same, so this is impossible.

Answer 1

启用 FULL_ASSERT 而不是 FAST_ASSERT 可以更快地指出真正的问题。请参阅the PR comment这解释了如何帮助检测问题。