title: Using Optaplanner to solve VRPTWPD
body: <p>I'm new to optaplanner, and am hoping to use it to solve the VRPTW problem with pickups and deliveries (VRPTWPD).</p>
  
  <p>I started by taking the <a href="https://github.com/droolsjbpm/optaplanner/tree/master/optaplanner-examples/src/main/java/org/optaplanner/examples/vehiclerouting" rel="noreferrer">VRPTW code</a> from the examples repo. I am trying to add to it to solve my problem. However, I'm unable to return a solution that honors the precedence/vehicle constraints (pickups must be done before deliveries, and both must be done by the same vehicle).</p>
  
  <p>I am consistently returning a solution where the hard score is what I would expect for such a solution (i.e. I can add up all the violations in a small sample problem and see that the hard score matches the penalties I assigned for these violations).</p>
  
  <p>The <strong>first approach</strong> I tried was following the steps outlined by Geoffrey De Smet here - <a href="https://stackoverflow.com/a/19087210/351400">https://stackoverflow.com/a/19087210/351400</a></p>
  
  <p>Each <code>Customer</code> has a variable <code>customerType</code> that describes whether it is a pickup (PU) or a delivery (DO). It also has a variable called <code>parcelId</code> that indicates which parcel is either being picked up or delivered.</p>
  
  <p>I added a shadow variable to the <code>Customer</code> named <code>parcelIdsOnboard</code>. This is a HashSet that holds all the parcelIds that the driver has with him when he visits a given <code>Customer</code>.</p>
  
  <p>My <code>VariableListener</code> that keeps <code>parcelIdsOnboard</code> updated looks like this:</p>
  
  <pre><code>public void afterEntityAdded(ScoreDirector scoreDirector, Customer customer) {
      if (customer instanceof TimeWindowedCustomer) {
          updateParcelsOnboard(scoreDirector, (TimeWindowedCustomer) customer);
      }
  }
  
  public void afterVariableChanged(ScoreDirector scoreDirector, Customer customer) {
      if (customer instanceof TimeWindowedCustomer) {
          updateParcelsOnboard(scoreDirector, (TimeWindowedCustomer) customer);
      }
  }
  
  protected void updateParcelsOnboard(ScoreDirector scoreDirector, TimeWindowedCustomer sourceCustomer) {
      Standstill previousStandstill = sourceCustomer.getPreviousStandstill();
      Set&lt;Integer&gt; parcelIdsOnboard = (previousStandstill instanceof TimeWindowedCustomer)
              ? new HashSet&lt;Integer&gt;(((TimeWindowedCustomer) previousStandstill).getParcelIdsOnboard()) : new HashSet&lt;Integer&gt;();
  
      TimeWindowedCustomer shadowCustomer = sourceCustomer;
      while (shadowCustomer != null) {
          updateParcelIdsOnboard(parcelIdsOnboard, shadowCustomer);
          scoreDirector.beforeVariableChanged(shadowCustomer, "parcelIdsOnboard");
          shadowCustomer.setParcelIdsOnboard(parcelIdsOnboard);
          scoreDirector.afterVariableChanged(shadowCustomer, "parcelIdsOnboard");
          shadowCustomer = shadowCustomer.getNextCustomer();
      }
  }
  
  private void updateParcelIdsOnboard(Set&lt;Integer&gt; parcelIdsOnboard, TimeWindowedCustomer customer) {
      if (customer.getCustomerType() == Customer.PICKUP) {
          parcelIdsOnboard.add(customer.getParcelId());
      } else if (customer.getCustomerType() == Customer.DELIVERY) {
          parcelIdsOnboard.remove(customer.getParcelId());
      } else {
          // TODO: throw an assertion
      }
  }
  </code></pre>
  
  <p>I then added the following drool rule:</p>
  
  <pre><code>rule "pickupBeforeDropoff"
      when
          TimeWindowedCustomer((customerType == Customer.DELIVERY) &amp;&amp; !(parcelIdsOnboard.contains(parcelId)));
      then
          System.out.println("precedence violated");
          scoreHolder.addHardConstraintMatch(kcontext, -1000);
  end
  </code></pre>
  
  <p>For my example problem I create a total of 6 <code>Customer</code> objects (3 PICKUPS and 3 DELIVERIES). My fleet size is 12 vehicles. </p>
  
  <p>When I run this I consistently get a hard score of -3000 which matches my output where I see two vehicles being used. One vehicle does all the PICKUPS and one vehicle does all the DELIVERIES.</p>
  
  <p>The <strong>second approach</strong> I used was to give each <code>Customer</code> a reference to its counterpart <code>Customer</code> object (e.g. the PICKUP <code>Customer</code> for parcel 1 has a reference to the DELIVERY <code>Customer</code> for parcel 1 and vice versa).</p>
  
  <p>I then implemented the following rule to enforce that the parcels be in the same vehicle (note: does not fully implement precedence constraint).</p>
  
  <pre><code>rule "pudoInSameVehicle"
      when
          TimeWindowedCustomer(vehicle != null &amp;&amp; counterpartCustomer.getVehicle() != null &amp;&amp; (vehicle != counterpartCustomer.getVehicle()));
      then
          scoreHolder.addHardConstraintMatch(kcontext, -1000);
  end
  </code></pre>
  
  <p>For the same sample problem this consistently gives a score of -3000 and an identical solution to the one above.</p>
  
  <p>I've tried running both rules in <code>FULL_ASSERT</code> mode. The rule using <code>parcelIdsOnboard</code> does not trigger any exceptions. However, the rule <code>"pudoInSameVehicle"</code> does trigger the following exception (which is not triggered in <code>FAST_ASSERT</code> mode).</p>
  
  <pre><code>The corrupted scoreDirector has no ConstraintMatch(s) which are in excess.
  The corrupted scoreDirector has 1 ConstraintMatch(s) which are missing:
  </code></pre>
  
  <p>I'm not sure why this is corrupted, any suggestions would be much appreciated.</p>
  
  <p>It's interesting that both of these methodologies are producing the same (incorrect) solution. I'm hoping someone will have some suggestions on what to try next. Thanks!</p>
  
  <p><strong>UPDATE:</strong></p>
  
  <p>After diving into the asserts that were being triggered in FULL_ASSERT mode I realized that the problem was with the dependent nature of the PICKUP and DELIVERY <code>Customer</code>s. That is, if you make a move that removes the hard penalty on a DELIVERY <code>Customer</code> you also have to remove the penalty associated with the PICKUP <code>Customer</code>. In order to keep these in sync I updated my <code>VehicleUpdatingVariableListener</code> and my <code>ArrivalTimeUpdatingVariableListener</code> to trigger score calculation callbacks on both <code>Customer</code> objects. Here's the <code>updateVehicle</code> method after updating it to trigger score calculation on both the <code>Customer</code> that was just moved <em>and</em> the counterpart <code>Customer</code>.</p>
  
  <pre><code>protected void updateVehicle(ScoreDirector scoreDirector, TimeWindowedCustomer sourceCustomer) {
      Standstill previousStandstill = sourceCustomer.getPreviousStandstill();
      Integer departureTime = (previousStandstill instanceof TimeWindowedCustomer)
              ? ((TimeWindowedCustomer) previousStandstill).getDepartureTime() : null;
  
      TimeWindowedCustomer shadowCustomer = sourceCustomer;
      Integer arrivalTime = calculateArrivalTime(shadowCustomer, departureTime);
      while (shadowCustomer != null &amp;&amp; ObjectUtils.notEqual(shadowCustomer.getArrivalTime(), arrivalTime)) {
          scoreDirector.beforeVariableChanged(shadowCustomer, "arrivalTime");
          scoreDirector.beforeVariableChanged(((TimeWindowedCustomer) shadowCustomer).getCounterpartCustomer(), "arrivalTime");
          shadowCustomer.setArrivalTime(arrivalTime);
          scoreDirector.afterVariableChanged(shadowCustomer, "arrivalTime");
          scoreDirector.afterVariableChanged(((TimeWindowedCustomer) shadowCustomer).getCounterpartCustomer(), "arrivalTime");
          departureTime = shadowCustomer.getDepartureTime();
          shadowCustomer = shadowCustomer.getNextCustomer();
          arrivalTime = calculateArrivalTime(shadowCustomer, departureTime);
      }
  }
  </code></pre>
  
  <p>This solved the score corruption issue I had with my second approach, and, on a small sample problem, produced a solution that satisfied all the hard constraints (i.e. the solution had a hard score of 0).</p>
  
  <p>I next tried to run a larger problem (~380 Customers), but the solutions are returning very poor hard scores. I tried searching for a solution for 1 min, 5 mins, and 15 mins. The score seems to improve linearly with runtime. But, at 15 minutes, the solution is still so bad that it seems like it would need to run for at least an hour to produce a viable solution. 
  I need this to run in 5-10 minutes at the most.</p>
  
  <p>I learned about <a href="http://docs.jboss.org/drools/release/6.2.0.CR1/optaplanner-docs/html_single/index.html#filteredSelection" rel="noreferrer">Filter Selection</a>. My understanding is that you can run a function to check whether the move you are about to make would result in breaking a built in hard constraint, and if it would, then this move is skipped. </p>
  
  <p>This means that you don't have to re-run score calculations or explore branches that you know will not be fruitful. For example, in my problem I don't want you to ever be able to move a <code>Customer</code> to a <code>Vehicle</code> unless its counterpart is assigned to that Vehicle or not assigned a Vehicle at all.</p>
  
  <p>Here is the filter I implemented to check for that. It only runs for ChangeMoves, but I suspect I need this to implement a similar function for SwapMoves as well.</p>
  
  <pre><code>public class PrecedenceFilterChangeMove implements SelectionFilter&lt;ChangeMove&gt; { 
  
      @Override
      public boolean accept(ScoreDirector scoreDirector, ChangeMove selection) {
          TimeWindowedCustomer customer = (TimeWindowedCustomer)selection.getEntity();
          if (customer.getCustomerType() == Customer.DELIVERY) {
              if (customer.getCounterpartCustomer().getVehicle() == null) {
                  return true;
              }
              return customer.getVehicle() == customer.getCounterpartCustomer().getVehicle();
          }
          return true;
      }
  }
  </code></pre>
  
  <p>Adding this filter immediately led to worse scores. That makes me think I have implemented the function incorrectly, though it's not clear to me why it is incorrect.</p>
  
  <p><strong>Update 2:</strong></p>
  
  <p>A co-worker pointed out the problem with my PrecedenceFilterChangeMove. The correct version is below. I've also included PrecedenceFilterSwapMove implementation. Together, these have enabled me to find a solution to the problem where no hard constraints are violated in ~10 minutes. There are a couple of other optimizations I think I might be able to make to reduce this even further. </p>
  
  <p>I will post another update if those changes are fruitful. I'd still love to hear from someone in the optaplanner community about my approach and whether they think there are better ways to model this problem!</p>
  
  <p><strong>PrecedenceFilterChangeMove</strong></p>
  
  <pre><code>@Override
  public boolean accept(ScoreDirector scoreDirector, ChangeMove selection) {
      TimeWindowedCustomer customer = (TimeWindowedCustomer)selection.getEntity();
      if (customer.getCustomerType() == Customer.DELIVERY) {
          if (customer.getCounterpartCustomer().getVehicle() == null) {
              return true;
          }
          return selection.getToPlanningValue() == customer.getCounterpartCustomer().getVehicle();
      } 
      return true;
  }
  </code></pre>
  
  <p><strong>PrecedenceFilterSwapMove</strong></p>
  
  <pre><code>@Override
  public boolean accept(ScoreDirector scoreDirector, SwapMove selection) {
      TimeWindowedCustomer leftCustomer = (TimeWindowedCustomer)selection.getLeftEntity();
      TimeWindowedCustomer rightCustomer = (TimeWindowedCustomer)selection.getRightEntity();
      if (rightCustomer.getCustomerType() == Customer.DELIVERY || leftCustomer.getCustomerType() == Customer.DELIVERY) {      
          return rightCustomer.getVehicle() == leftCustomer.getCounterpartCustomer().getVehicle() ||
                  leftCustomer.getVehicle() == rightCustomer.getCounterpartCustomer().getVehicle();
      }
      return true;
  }
  </code></pre>