PDPTW with Start/End Nodes Crashes #2167

fbirori · 2020-09-28T06:44:28Z

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

The text was updated successfully, but these errors were encountered:

Mizux · 2020-09-29T09:06:54Z

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 · 2020-09-29T09:10:11Z

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...

fbirori · 2020-09-29T15:15:05Z

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 · 2020-09-29T15:42:15Z

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

fbirori · 2020-09-30T04:15:36Z

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]); 
}

fbirori · 2020-10-06T03:39:21Z

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

Mizux · 2020-10-06T08:21:04Z

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>corentinl@google.com</email>
    <organization>Google LLC</organization>
    <organizationUrl>http://www.google.com</organizationUrl>
  </developer>
  <developer>
    <name>Laurent Perron</name>
    <email>lperron@google.com</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 · 2020-10-06T08:35:51Z

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 java.base@14.0.2
j  java.lang.invoke.LambdaForm$MH.invoke_MT(Ljava/lang/Object;Ljava/lang/Object;Ljava/lang/Object;)V+18 java.base@14.0.2
j  org.codehaus.mojo.exec.ExecJavaMojo$1.run()V+85
j  java.lang.Thread.run()V+11 java.base@14.0.2
v  ~StubRoutines::call_stub

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

Mizux · 2020-10-06T08:52:58Z

ok found, few errors

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....

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);
    }

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

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 · 2020-10-06T09:03:55Z

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...

Mizux added Bug Lang: Java Java wrapper issue labels Sep 28, 2020

Mizux closed this as completed Sep 29, 2020

Mizux added the Duplicate label Sep 29, 2020

Mizux added this to the v8.0 milestone Sep 29, 2020

Mizux added Solver: Routing Uses the Routing library and the original CP solver and removed Duplicate labels Sep 29, 2020

Mizux reopened this Sep 29, 2020

Mizux modified the milestones: v8.0, v8.1 Sep 29, 2020

Mizux self-assigned this Sep 30, 2020

Mizux closed this as completed Oct 6, 2020

Mizux modified the milestones: v8.1, v8.0 Oct 6, 2020

hj1234 mentioned this issue May 12, 2023

PDPTW with Start/End Nodes Crashes (python) #3782

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

PDPTW with Start/End Nodes Crashes #2167

PDPTW with Start/End Nodes Crashes #2167

fbirori commented Sep 28, 2020 •

edited

Loading

Mizux commented Sep 29, 2020 •

edited

Loading

Mizux commented Sep 29, 2020

fbirori commented Sep 29, 2020

Mizux commented Sep 29, 2020

fbirori commented Sep 30, 2020 •

edited

Loading

fbirori commented Oct 6, 2020

Mizux commented Oct 6, 2020 •

edited

Loading

Mizux commented Oct 6, 2020

Mizux commented Oct 6, 2020 •

edited

Loading

Mizux commented Oct 6, 2020 •

edited

Loading

PDPTW with Start/End Nodes Crashes #2167

PDPTW with Start/End Nodes Crashes #2167

Comments

fbirori commented Sep 28, 2020 • edited Loading

Mizux commented Sep 29, 2020 • edited Loading

Mizux commented Sep 29, 2020

fbirori commented Sep 29, 2020

Mizux commented Sep 29, 2020

fbirori commented Sep 30, 2020 • edited Loading

fbirori commented Oct 6, 2020

Mizux commented Oct 6, 2020 • edited Loading

Mizux commented Oct 6, 2020

Mizux commented Oct 6, 2020 • edited Loading

Mizux commented Oct 6, 2020 • edited Loading

fbirori commented Sep 28, 2020 •

edited

Loading

Mizux commented Sep 29, 2020 •

edited

Loading

fbirori commented Sep 30, 2020 •

edited

Loading

Mizux commented Oct 6, 2020 •

edited

Loading

Mizux commented Oct 6, 2020 •

edited

Loading

Mizux commented Oct 6, 2020 •

edited

Loading