Sort Vehicle On Multi Day Vehicle Routing Problem

[Wizard]

I tried to build a multi day vehicle routing based on optaplanner vanilla VRP example. I add a new class Day which represent the Day data e.g. Day 1 (Monday), Day 2 (Tuesday), etc. I also create a new class VehicleDay and moved Planning Entity from Vehicle class to this class. Here is my class looks like : 

@XStreamAlias("VrpDay")

public class Day extends AbstractPersistable {

protected int dayIndex;

protected int dayInt;

protected String day;

        ...

}

@XStreamAlias("VrpVehicle")

public class Vehicle extends AbstractPersistable {

    protected int capacity;

    protected Depot depot;

    ...

}

public class VehicleDay extends AbstractPersistable implements Standstill {

protected Vehicle vehicle;

protected Day day;

// Shadow variables

        protected Customer nextCustomer;

        ...

} 

Then I tried to run it with sample dataset, which consist of 72 customers, 4 vehicles, 2 days, and 8 vehicleDays. The vehicleDays data looks like this : 

1. Vehicle A Day 1
2. Vehicle B Day 1
3. Vehicle C Day 1
4. Vehicle D Day 1
5. Vehicle A Day 2
6. Vehicle B Day 2
7. Vehicle C Day 2
8. Vehicle D Day 2

The result was some vehicle on day 1 is empty, while there are some vehicle on day 2 is used. This is not the ideal solution, because what I want is planner to use all vehicle on Day 1 first, then after all vehicle on Day 1 is used, planner start to use vehicle on Day 2. 

I tried to use Sorted Selection by Comparator, and create VehicleDayDifficultyComparator class that look like this : 

public class VehicleDayDifficultyComparator implements Comparator<VehicleDay>, Serializable {

    @Override

    public int compare(VehicleDay a, VehicleDay b) {

    return new CompareToBuilder()

                .append(a.getDay().getDayIndex(), b.getDay().getDayIndex())

                .append(a.getId(), b.getId())

                .toComparison();      

    }

}

I also registered it at Customer class like this : 

@PlanningEntity(difficultyWeightFactoryClass = DepotAngleCustomerDifficultyWeightFactory.class)

@XStreamAlias("VrpCustomer")

@XStreamInclude({

        TimeWindowedCustomer.class

})

public class Customer extends AbstractPersistable implements Standstill {

    ....

    @PlanningVariable(valueRangeProviderRefs = {"vehicleDayRange", "customerRange"}, 

    strengthComparatorClass = VehicleDayDifficultyComparator.class, 

    graphType = PlanningVariableGraphType.CHAINED)

    public Standstill getPreviousStandstill() {

        return previousStandstill;

    }

    

    ....

}

But I still got the same result, it seems like the comparator not working as expected. Does anybody know how to do this? Any comment will be appreciated. 

[Wizard]

I manage to make it, but using a rule. The rule was a hard constraint where if there are a vehicle day is used, but the same vehicle in the day before unused, it will punish the score. But I still wonder, why the comparator not working for this purpose. Does anyone know why the comparator is not working to sort the vehicle?

[Geoffrey De Smet]

A difficultyComparator is only to guide some search algorithms (to find better solutions faster),
it in no way impacts the definition of the constraints. Several algorithms completely ignore it.

hth

With kind regards,
Geoffrey De Smet

--
You received this message because you are subscribed to the Google Groups "OptaPlanner development" group.
To unsubscribe from this group and stop receiving emails from it, send an email to optaplanner-d...@googlegroups.com.
To post to this group, send email to optapla...@googlegroups.com.
Visit this group at https://groups.google.com/group/optaplanner-dev.
For more options, visit https://groups.google.com/d/optout.

[Wizard]

Hi Geoffrey, 

Thanks for explain it more detail. So the only way to achieve this is write a rule as what I did now? Just want to clarify the method I use was already the correct one.

Thanks and kind regards.

[Geoffrey De Smet]

Yes, it's a constraint, so it should be in the score drl (if you're using the drools score director which is recommended).

Do note that I 've seen this trick, for what it might be worth:

rule
  Employee($c : violationCount() > 0)
then
  addHard...(..., - $c);
end

@PlanningEntity // SHADOW entity
class  Employee {

@InverseRelationShadowVariable
List<Shift> shiftList; // Shift is the genuine planning entity

public int violationCount() {
   int count = 0;
   // Iterate through shifts and check if they're in the desired order
   return count;
}

It doesn't combine easily with CHAINED vars though.

With kind regards,
Geoffrey De Smet

[kan200...@gmail.com]

Hi Mr, Wizard.

Could you please share your rule pseudo? I am working with same problem. It would be great if you could help me out on this

[Wizard]

Hi Kan,

Here is my pseudo rule : 

rule "Previous VehicleDay Less Used Than Current VehicleDay"
    when
        $vehicleDay : VehicleDay(
            nextCustomer != null,
            $vehicle : vehicle
        )
       
        $customerCount : Long() from accumulate (
            Customer(
                vehicleDay == $vehicleDay,
                $demand : demand),
            count($demand)
        )
       
        $vehicleDayBefore : VehicleDay(
            nextCustomer != null,
            vehicle == $vehicle,
            day.getDayIndex() < $vehicleDay.getDayIndex()
        )

        $customerCountBefore : Long(intValue < $customerCount) from accumulate (
            Customer(
                vehicleDay == $vehicleDayBefore,
                $demand : demand),
            count($demand)
        )
    then
        scoreHolder.addHardConstraintMatch(kcontext, $customerCountBefore.intValue() - $customerCount.intValue());
end

Hope this helps. 

Thanks and regards.