VRP with break windows not working properly when fix_start_cumul_to_zero is false

[shiyuan]

I'm trying to use break intervals in VRP, it seems the method RoutingDimension::SetBreakIntervalsOfVehicle is not working properly.

version: v6.7.2
language: c++

Building a VRP of one vehicle(with break time of [100, 1100]) and one order(400 away to depot), the arrival time of the order node should be 1400, but the code below gives 1100, it seems the method has bugs.

#include <iostream>
#include <vector>

#include "ortools/constraint_solver/routing.h"
#include "ortools/constraint_solver/routing_flags.h"
#include "ortools/base/callback.h"

using namespace operations_research;

class MatrixCallback : public operations_research::BaseObject {
public:
    MatrixCallback(const std::vector<std::vector<int64>>& travel_time,
                   const std::vector<int64>& service_time): travel_time_(travel_time), service_time_(service_time) {
    }

    int64 ServiceTimePlusTravelTime(const RoutingModel::NodeIndex from, const RoutingModel::NodeIndex to) const {
      return TravelTime(from, to) + ServiceTime(from, to);
    }

    int64 TravelTime(const RoutingModel::NodeIndex from, const RoutingModel::NodeIndex to) const {
      return travel_time_[from.value()][to.value()];
    }

    int64 ServiceTime(const RoutingModel::NodeIndex from, const RoutingModel::NodeIndex to) const {
      return service_time_[from.value()];
    }

private:
    const std::vector<std::vector<int64>> &travel_time_;
    const std::vector<int64> &service_time_;
};

int main() {
  const int depot = 0;
  const int num_vehicles = 1;
  const int num_locations = 2;
  const int64 kHorizon = 24 * 3600;
  const bool fix_start_cumul_to_zero = false;
  std::vector<std::vector<int64> > time_between_locations = {{0, 400}, {0, 0}};
  std::vector<int64 > service_times = {0, 3000};

  std::unique_ptr<RoutingModel> routing_{new RoutingModel(num_locations, num_vehicles, RoutingModel::NodeIndex{depot})};
  std::unique_ptr<MatrixCallback> callback_{new MatrixCallback(time_between_locations, service_times)};

  routing_->AddDimension(NewPermanentCallback(callback_.get(), &MatrixCallback::ServiceTimePlusTravelTime),
                         kHorizon, kHorizon, fix_start_cumul_to_zero, "time");

  Solver* const solver = routing_->solver();
  RoutingDimension* const time_dimension = routing_->GetMutableDimension("time");

  IntervalVar* const break_interval = solver->MakeFixedInterval(100, 1000, "break 0");
  time_dimension->SetBreakIntervalsOfVehicle({break_interval}, 0); // set break time for vehicle 0

  RoutingSearchParameters parameters = RoutingModel::DefaultSearchParameters();
  parameters.set_first_solution_strategy(FirstSolutionStrategy::PATH_CHEAPEST_ARC);
  const Assignment* solution = routing_->SolveWithParameters(parameters);

  int64 node = routing_->Start(0);
  while(true) {
    IntVar* const node_cumul_time = time_dimension->CumulVar(node);

    int64 time_min = solution->Min(node_cumul_time);
    int64 time_value = solution->Value(node_cumul_time);
    int64 time_max = solution->Max(node_cumul_time);
    std::cout << "Min(" << time_min << ") Value(" << time_value << ") Max(" << time_max << ")" << std::endl;

    if (routing_->IsEnd(node)) {
      break;
    }
    node = solution->Value(routing_->NextVar(node));
  }

  return 0;
}

------------------------
output:
Min(0) Value(0) Max(83000)
Min(1100) Value(1100) Max(83400)
Min(4100) Value(4100) Max(86400)

But, if the fix_start_cumul_to_zero is set to true, It gives the correct solution

Min(0) Value(0) Max(0)
Min(1400) Value(1400) Max(83400)
Min(4400) Value(4400) Max(86400)

In more complicated scenes，the constraint of break intervals may end with no solution, actually there exist one, hope someone can help.

[Mizux]

Break are known to not work (#569) as expected in any v6.X. I see two possibilities

• You can take a look at #595 for a workaround...
• You can try the incoming v7.0 API (current master branch) which has a working cvrptw_with_breaks.cc

side note: a v7.0-beta.1 was released last week -> https://github.com/google/or-tools/releases/tag/v7.0-beta.1

[shiyuan]

@Mizux I tried the two ways, none of them works well.

• 595 workaround doesn't work on v6.7.2.

• while v7.0-beta.1 works on the case above, but it meets no solution in other cases.

Run the VRP_or-tools_v7.0-beta.1_test_vehicle_break_interval.cpp, you can get No solution sometimes.

I'm wondering whether I have a bad implementation or the bug is still unfixed.

[shiyuan]

#595 workaround doesn't work on v6.7.2.

It didn't work at first, for the interval from the depot to first order node was ignored. After changing it, It works for me now.

[GuyBenhaim]

So, for V7 breaks work? including or interval/segment from the depot, and with multiple-breaks per vehicle?

[shiyuan]

So, for V7 breaks work? including or interval/segment from the depot, and with multiple-breaks per vehicle?

@GuyBenhaim

1. Breaks didn't work properly in v7.0-beta.1

2. 595 provides a BreakConstraint, it worked if the interval from the depot to the first order node was considered (change this), or the first interval would overlap with breaks

[GuyBenhaim]

Hello, Can you update whether this was resolved in v7.x ?

For #595 what do you mean "interval from the depot to the first order node was considered"? Does travel time from start-point to the first-node (of each vehicle) will not be included in the time until the break is required to start?

Thx

[shiyuan]

@GuyBenhaim

Can you update whether this was resolved in v7.x ?

Breaks in v7.0-beta.1 not work for me

---

For #595, codes implemented here , not started from depot node

int64 current_index = model->NextVar(model->Start(vehicle_))->Value();

In my scene, which consider the interval from the depot node to first node with break constraint for example, the transport time to the first node is 3600, while the break interval is [1000, 2000), the supposed arrival time of the first node is 5600, after changing this:

int64 current_index = model->Start(vehicle_);

while the v7.0-beta.1 gives 4600 and sometimes results to no solution

you can try the toy code here

[lperron]

7.0 is out. Can you try with the official release ? Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00

Le jeu. 4 avr. 2019 à 08:34, Yuan notifications@github.com a écrit :

@GuyBenhaim https://github.com/GuyBenhaim

Can you update whether this was resolved in v7.x ?

Breaks in v7.0-beta.1 not work for me

For #595 https://github.com/google/or-tools/pull/595, codes implemented here https://github.com/pmateusz/or-tools/blob/c0a9ce80cde70e3df1db45ed904e63b47d37e7e9/examples/cpp/cvrptw_with_breaks_repro.cc#L173 , not started from depot node

int64 currentindex = model->NextVar(model->Start(vehicle))->Value();

In my scene, which consider the interval from the depot node to first node with break constraint for example, the transport time to the first node is 3600, while the break interval is [1000, 2000), the supposed arrival time of the first node is 5600, after changing this:

int64 currentindex = model->Start(vehicle);

while the v7.0-beta.1 gives 4600 and sometimes results to no solution

you can try the toy code here https://gist.github.com/shiyuan/30e7658df7687355a21bc0e59bd16bb9

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/994#issuecomment-479768936, or mute the thread https://github.com/notifications/unsubscribe-auth/AKj17QYj-W3_jT2bAP92qKFdgUovjgleks5vdZzygaJpZM4Zhl85 .

[shiyuan]

7.0 is out. Can you try with the official release ?

@lperron I tried v7.0 , still not work properly for the toy case above

[lperron]

can you post the new code (with 7.x) ?

[shiyuan]

@lperron VRP_or-tools_v7.0-beta.1_test_vehicle_break_interval.cpp

[gustav3d]

Any progress on fixing this issue ? fix_start_cumul_to_zero=False to work for fixed breaks. Using service time on disjunctioned node per break per car as workaround is not always good enough.