Or-tools: PDPTW with Start/End Nodes Crashes

[bifra04]

Hi all,

I am experiencing an issue in which my simple PDPTW setup crashes for the starts and ends arrays below.

timeMatrix =
[[0, 0, 2, 3]
[0, 0, 2, 3]
[2, 0, 0, 5]
[3, 0, 5, 0]]

pickupsDeliveries = [[2, 3]]

timeWindows =
[[26097540, 26097840]
[26097540, 26097840]
[26097540, 26097780]
[26097840, 26098140]]

vehicleNumber = 1
starts = [0]
ends = [1]

I understand that nodes to be visited cannot be part of starts and ends arrays. I have 4 nodes (0, 1, 2, 3) where the pickup-delivery pair is 2->3. My start node is 0 and end node is 1. With this setup, the program crashes with "SIGSEGV" error. However, when both starts = [0] and ends = [0], it works. I'm not using the node 1 as part of any pickup-delivery pair. Why would having node 1 as the end node crash the program in this case? I appreciate any inputs.
@Mizux any idea?

PDPTW-Java-crash.txt

What version of OR-tools and what language are you using?
Version: 7.8.7959.
Language: /Java/Python/C#

Which solver are you using (e.g. CP-SAT, Routing Solver, GLOP, BOP, Gurobi)
Routing Solver
What operating system (Linux, Windows, ...) and version?
Ubuntu 20.04
What did you do?
Setup the problem with the datamodel having the data:

timeMatrix =
[[0, 0, 2, 3]
[0, 0, 2, 3]
[2, 0, 0, 5]
[3, 0, 5, 0]]

pickupsDeliveries = [[2, 3]]

timeWindows =
[[26097540, 26097840]
[26097540, 26097840]
[26097540, 26097780]
[26097840, 26098140]]

vehicleNumber = 1
starts = [0]
ends = [1]

What did you expect to see
An assignment 0-->2-->3-->1

What did you see instead?
The program crashed with:

# A fatal error has been detected by the Java Runtime Environment:
#
#  SIGSEGV 

[Mizux]

duplicate of #2091, don't add information to reproduce/help to debug it...
Please provide a full way to reproduce it or follow the mentioned issue
EDIT: not a duplicate bug

[Mizux]

side note: You can't use start or end node as node of a Pickup and Delivery pair (implementation limitation).
You can try to duplicate the end node instead...

[bifra04]

I'm sorry if things weren't clear enough, but I don't think this issue is a duplicate of #2091.

Neither start (0) or end node (1) is part of the pickup-delivery pair (2->3). Things only work when start and end nodes are the same. If they're different, I experience the crash.

[Mizux]

ok, my bad, did you try using master and compiling from source ?

[bifra04]

Yes, I used the maven dependency from https://github.com/panavis/google-or-tools-maven. The sample examples from documentation all work fine.
See the code I ran:

import com.google.ortools.Loader; 
import com.google.ortools.constraintsolver.Assignment; 
import com.google.ortools.constraintsolver.FirstSolutionStrategy; 
import com.google.ortools.constraintsolver.LocalSearchMetaheuristic; 
import com.google.ortools.constraintsolver.IntVar; 
import com.google.ortools.constraintsolver.RoutingDimension; 
import com.google.ortools.constraintsolver.RoutingIndexManager; 
import com.google.ortools.constraintsolver.RoutingModel; 
import com.google.ortools.constraintsolver.RoutingSearchParameters; 
import com.google.ortools.constraintsolver.Solver; 
import com.google.ortools.constraintsolver.main; 
import com.google.protobuf.Duration; 

import java.util.logging.Logger; 

public class VrpPickupDelivery { 
  static { 
    Loader.loadNativeLibraries(); 
  } 

  private static final Logger logger = Logger.getLogger(VrpPickupDelivery.class.getName()); 

  static class DataModel { 
    public final long[][] timeMatrix = { 
      {0, 0, 2, 3}, 
      {0, 0, 2, 3}, 
      {2, 0, 0, 5}, 
      {3, 0, 5, 0}, 
    }; 
    public final int[][] pickupsDeliveries = { 
      {2, 3}, 
    }; 
    public final long[][] timeWindows = { 
      {26097540, 26097840}, 
      {26097540, 26097840}, 
      {26097540, 26097780}, 
      {26097840, 26098140}, 
    };     
    public final int vehicleNumber = 1; 
    public final int[] starts = {0}; 
    public final int[] ends = {1}; 
  } 

  /// @brief Print the solution. 
  static void printSolution( 
      DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) { 
    // Inspect solution. 
    RoutingDimension timeDimension = routing.getMutableDimension("Time"); 
    long totalTime = 0; 
    for (int i = 0; i < data.vehicleNumber; ++i) { 
      long index = routing.start(i); 
      logger.info("Route for Vehicle " + i + ":"); 
      String route = ""; 
      while (!routing.isEnd(index)) { 
        IntVar timeVar = timeDimension.cumulVar(index); 
        route += manager.indexToNode(index) + " Time(" + solution.min(timeVar) + "," 
          + solution.max(timeVar) + ") -> "; 
        index = solution.value(routing.nextVar(index)); 
      } 
      IntVar timeVar = timeDimension.cumulVar(index); 
      route += manager.indexToNode(index) + " Time(" + solution.min(timeVar) + "," 
        + solution.max(timeVar) + ")"; 
      logger.info(route); 
      logger.info("Time of the route: " + solution.min(timeVar) + "min"); 
      totalTime += solution.min(timeVar); 
    } 
    logger.info("Total time of all routes: " + totalTime + "min"); 
  } 

  public static void main(String[] args) throws Exception { 
    // Instantiate the data problem. 
    final DataModel data = new DataModel(); 

    // Create Routing Index Manager
    RoutingIndexManager manager = new RoutingIndexManager(data.timeMatrix.length, data.vehicleNumber, data.starts, data.ends);

    // Create Routing Model.
    RoutingModel routing = new RoutingModel(manager);       

    // Create and register a transit callback.
    final int transitCallbackIndex =
      routing.registerTransitCallback((long fromIndex, long toIndex) -> {
          // Convert from routing variable Index to user NodeIndex.
          int fromNode = manager.indexToNode(fromIndex);
          int toNode = manager.indexToNode(toIndex);
          return data.timeMatrix[fromNode][toNode];
          });

    // Define cost of each arc.
    routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

    // Add Time dimension.
    routing.addDimension(transitCallbackIndex, // transit/ total time function callback callback
        5, // allow waiting time
        Long.MAX_VALUE, // the maximum value for time
        false, // start cumul to zero
        "Time");

    RoutingDimension timeDimension = routing.getMutableDimension("Time");

    // Add time window constraints at each node (location as well as vehicles)
    for (int i = 0; i < data.timeWindows.length; ++i) {
      long index = manager.nodeToIndex(i);
      timeDimension.cumulVar(index).setRange(data.timeWindows[i][0], data.timeWindows[i][1]);
    }

    // Instantiate route start and end times to produce feasible times.
    for (int i = 0; i < data.vehicleNumber; ++i) {
      routing.addVariableMinimizedByFinalizer(timeDimension.cumulVar(routing.start(i)));
      routing.addVariableMinimizedByFinalizer(timeDimension.cumulVar(routing.end(i)));
    }

    // Define Transportation Requests.
    Solver solver = routing.solver();
    for (int[] request : data.pickupsDeliveries) {
      long pickupIndex = manager.nodeToIndex(request[0]);
      long deliveryIndex = manager.nodeToIndex(request[1]);
      routing.addPickupAndDelivery(pickupIndex, deliveryIndex);
      solver.addConstraint(solver.makeEquality(routing.vehicleVar(pickupIndex), routing.vehicleVar(deliveryIndex)));
      solver.addConstraint(solver.makeLessOrEqual(timeDimension.cumulVar(pickupIndex), timeDimension.cumulVar(deliveryIndex)));
    }

    // Allow to drop nodes.
    long penalty = 1000;
    for (int i = 1; i < data.timeMatrix.length; ++i) {
      routing.addDisjunction(new long[] {manager.nodeToIndex(i)}, penalty);
    }

    // Setting first solution heuristic.
    RoutingSearchParameters searchParameters = main.defaultRoutingSearchParameters()
      .toBuilder()
      .setFirstSolutionStrategy(FirstSolutionStrategy.Value.PARALLEL_CHEAPEST_INSERTION) 
      .setLocalSearchMetaheuristic(LocalSearchMetaheuristic.Value.GUIDED_LOCAL_SEARCH)
      .setTimeLimit(Duration.newBuilder().setSeconds(30).build())
      .build();

    // Solve the problem.
    Assignment solution = routing.solveWithParameters(searchParameters);

    // Print solution on console.
    printSolution(data, routing, manager, solution);
  }
}

Am I doing something wrong especially here when adding time window constraints at each node?

// Add time window constraints at each node (location as well as vehicles) 
for (int i = 0; i < data.timeWindows.length; ++i) { 
  long index = manager.nodeToIndex(i); 
  timeDimension.cumulVar(index).setRange(data.timeWindows[i][0], data.timeWindows[i][1]); 
}

[bifra04]

@Mizux , did you get a chance of running this?

[Mizux]

I can reproduce it using the pom.xml (generated from ortools/java/pom-sample.xml)

<?xml version="1.0" encoding="UTF-8"?>
<project
  xmlns="http://maven.apache.org/POM/4.0.0"
  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
  xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
<modelVersion>4.0.0</modelVersion>

<groupId>com.google.ortools</groupId>
<artifactId>VrpPickupDelivery</artifactId>
<version>8.0</version>
<packaging>jar</packaging>

<name>${project.groupId}:${project.artifactId}</name>
<description>Google OR-Tools Java project.</description>
<url>https://github.com/google/or-tools</url>

<licenses>
  <license>
    <name>The Apache License, Version 2.0</name>
    <url>http://www.apache.org/licenses/LICENSE-2.0.txt</url>
  </license>
</licenses>

<developers>
  <developer>
    <name>Corentin "Mizux" Le Molgat</name>
    <email>[email protected]</email>
    <organization>Google LLC</organization>
    <organizationUrl>http://www.google.com</organizationUrl>
  </developer>
  <developer>
    <name>Laurent Perron</name>
    <email>[email protected]</email>
    <organization>Google LLC</organization>
    <organizationUrl>http://www.google.com</organizationUrl>
  </developer>
</developers>

<scm>
  <connection>scm:git:git://github.com/google/or-tools.git</connection>
  <developerConnection>scm:git:ssh://github.com:google/or-tools.git</developerConnection>
  <url>http://github.com/google/or-tools/tree/master</url>
  <tag>HEAD</tag>
</scm>

<issueManagement>
  <system>GitHub Issues</system>
  <url>http://github.com/google/or-tools/issues</url>
</issueManagement>

<properties>
  <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
  <exec.mainClass>VrpPickupDelivery</exec.mainClass>
  <maven.compiler.source>1.8</maven.compiler.source>
  <maven.compiler.target>1.8</maven.compiler.target>
</properties>

<dependencies>
  <dependency>
    <groupId>com.google.ortools</groupId>
    <artifactId>ortools-java</artifactId>
    <version>[8.0,)</version>
    <type>jar</type>
    <scope>compile</scope>
  </dependency>
</dependencies>

<build>
  <plugins>
    <plugin>
      <groupId>org.apache.maven.plugins</groupId>
      <artifactId>maven-source-plugin</artifactId>
      <version>3.2.0</version>
      <executions>
        <execution>
          <id>attach-sources</id>
          <goals>
            <goal>jar-no-fork</goal>
          </goals>
        </execution>
      </executions>
    </plugin>
    <plugin>
      <groupId>org.apache.maven.plugins</groupId>
      <artifactId>maven-javadoc-plugin</artifactId>
      <version>3.2.0</version>
      <executions>
        <execution>
          <id>attach-javadocs</id>
          <goals>
            <goal>jar</goal>
          </goals>
        </execution>
      </executions>
    </plugin>
  </plugins>
</build>
</project>

I'll try to find the issue...

[Mizux]

trace:

$ cat hs_err_pidXXXX.log
...
Java frames: (J=compiled Java code, j=interpreted, Vv=VM code)
j  com.google.ortools.constraintsolver.mainJNI.IntExpr_setRange(JLcom/google/ortools/constraintsolver/IntExpr;JJ)V+0
j  com.google.ortools.constraintsolver.IntExpr.setRange(JJ)V+7
j  VrpPickupDelivery.main([Ljava/lang/String;)V+129
j  java.lang.invoke.LambdaForm$DMH.invokeStaticInit(Ljava/lang/Object;Ljava/lang/Object;)V+10 [email protected]
j  java.lang.invoke.LambdaForm$MH.invoke_MT(Ljava/lang/Object;Ljava/lang/Object;Ljava/lang/Object;)V+18 [email protected]
j  org.codehaus.mojo.exec.ExecJavaMojo$1.run()V+85
j  java.lang.Thread.run()V+11 [email protected]
v  ~StubRoutines::call_stub

siginfo: si_signo: 11 (SIGSEGV), si_code: 1 (SEGV_MAPERR), si_addr: 0x000000000000003d

[Mizux]

ok found, few errors

1. You can't use nodeToIndex() for start and end so please rewrite it like this:

    // Add time window constraints at each node (only for locations)
    for (int i = 2; i < data.timeWindows.length; ++i) {
      long index = manager.nodeToIndex(i);
      timeDimension.cumulVar(index).setRange(data.timeWindows[i][0], data.timeWindows[i][1]);
    }
    for (int i = 0; i < data.vehicleNumber; ++i) {
      long start_index = manager.getStartIndex(i);
      timeDimension.cumulVar(start_index).setRange(data.timeWindows[0][0], data.timeWindows[0][1]);
      long end_index = manager.getEndIndex(i);
      timeDimension.cumulVar(end_index).setRange(data.timeWindows[1][0], data.timeWindows[1][1]);
    }

note: notice the first loop start from 2 since 0 and 1 are start and end nodes respectively....

1. Same for disjunction, you can add start/end node to a disjunction:

    for (int i = 2; i < data.timeMatrix.length; ++i) {
      routing.addDisjunction(new long[] {manager.nodeToIndex(i)}, penalty);
    }

1. You should offset your values

   public final long[][] timeWindows = {
      {7540, 7840},
      {7540, 7840},
      {7540, 7780},
      {7840, 8140},
    };
...
    routing.addDimension(transitCallbackIndex, // transit/ total time function callback callback
        5, // allow waiting time
        50000, // the maximum value for time

1. If your problem is infeasible, you should check it

    // Print solution on console.
    if (solution != null) {
      printSolution(data, routing, manager, solution);
    } else {
      logger.info("No solution found !");
    }

[Mizux]

note, if using:

   routing.addDimension(transitCallbackIndex, // transit/ total time function callback callback
        50, // allow waiting time
        50000, // the maximum value for time

output is:

Oct 06, 2020 11:02:53 AM VrpPickupDelivery printSolution
INFO: Route for Vehicle 0:
Oct 06, 2020 11:02:53 AM VrpPickupDelivery printSolution
INFO: 0 Time(7540,7540) -> 1 Time(7540,7540)
Oct 06, 2020 11:02:53 AM VrpPickupDelivery printSolution
INFO: Time of the route: 7540min
Oct 06, 2020 11:02:53 AM VrpPickupDelivery printSolution
INFO: Total time of all routes: 7540min

While using:

   routing.addDimension(transitCallbackIndex, // transit/ total time function callback callback
        55, // allow waiting time
        50000, // the maximum value for time

give:

Oct 06, 2020 11:04:31 AM VrpPickupDelivery printSolution
INFO: Route for Vehicle 0:
Oct 06, 2020 11:04:31 AM VrpPickupDelivery printSolution
INFO: 0 Time(7723,7723) -> 2 Time(7780,7780) -> 3 Time(7840,7840) -> 1 Time(7840,7840)
Oct 06, 2020 11:04:31 AM VrpPickupDelivery printSolution
INFO: Time of the route: 7840min
Oct 06, 2020 11:04:31 AM VrpPickupDelivery printSolution
INFO: Total time of all routes: 7840min

as parameter i've used:

   // Setting first solution heuristic.
    RoutingSearchParameters searchParameters = main.defaultRoutingSearchParameters()
      .toBuilder()
      .setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC)
    //.setFirstSolutionStrategy(FirstSolutionStrategy.Value.PARALLEL_CHEAPEST_INSERTION)
      .setLocalSearchMetaheuristic(LocalSearchMetaheuristic.Value.GUIDED_LOCAL_SEARCH)
      .setLogSearch(true)
      .setTimeLimit(Duration.newBuilder().setSeconds(5).build())
      .build();

ps: You should print the slackvar and objective value IMHO...