TSPTW returns an infeasible solution?

[mjposs]

Hello

(I'm new to Python and or-tools, so I may have done something pretty silly.)

I'm solving an instance of the TSPTW problem with OR-tools, which seems to return an infeasible solution:

Objective: 0
Route for vehicle 0:
0 Time(0,0) -> 18 Time(105,131) -> 14 Time(105,131) -> 13 Time(105,159) -> 9 Time(105,200) -> 8 Time(165,266) -> 7 Time(246,266) -> 6 Time(246,266) -> 5 Time(246,266) -> 4 Time(246,266) -> 19 Time(344,388) -> 17 Time(344,388) -> 16 Time(344,388) -> 12 Time(397,446) -> 11 Time(397,446) -> 10 Time(440,455) -> 3 Time(440,455) -> 1 Time(440,455) -> 15 Time(566,566) -> 2 Time(566,566) -> 0 Time(566,566)
Time of the route: 566min

The time to travel along 0 -> 18 -> 14 -> 13 is given by 84.5104. Adding this to the leaving time of node 18 (105), we exceed the deadline of node 13 (159).

1. What have I done wrong?
2. How comes the objective is 0, despite the routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
3. or-tools takes 10 min to return this solution. Isn't this very long? (CPLEX returns the optimal solution in less than a second)

Here is the code (adapting the VRPTW example), and data is attached
TSPTW_python_rc_201.1.txt

#!/usr/bin/env python3
# Copyright 2010-2024 Google LLC
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

# [START program]
"""Vehicles Routing Problem (VRP) with Time Windows."""

# [START import]
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
import math
# [END import]


# [START data_model]
def create_data_model():
    """Stores the data for the problem."""
    datafile = "rc_201.1.txt"
    data = {}
    datafilefullename = "TSPTW_python_"+datafile
    exec(open(datafilefullename).read())
    data["num_vehicles"] = 1
    data["depot"] = 0
    return data
    # [END data_model]


# [START solution_printer]
def print_solution(data, manager, routing, solution):
    """Prints solution on console."""
    print(f"Objective: {solution.ObjectiveValue()}")
    time_dimension = routing.GetDimensionOrDie("Time")
    total_time = 0
    for vehicle_id in range(data["num_vehicles"]):
        index = routing.Start(vehicle_id)
        plan_output = f"Route for vehicle {vehicle_id}:\n"
        while not routing.IsEnd(index):
            time_var = time_dimension.CumulVar(index)
            plan_output += (
                f"{manager.IndexToNode(index)}"
                f" Time({solution.Min(time_var)},{solution.Max(time_var)})"
                " -> "
            )
            index = solution.Value(routing.NextVar(index))
        time_var = time_dimension.CumulVar(index)
        plan_output += (
            f"{manager.IndexToNode(index)}"
            f" Time({solution.Min(time_var)},{solution.Max(time_var)})\n"
        )
        plan_output += f"Time of the route: {solution.Min(time_var)}min\n"
        print(plan_output)
        total_time += solution.Min(time_var)
    print(f"Total time of all routes: {total_time}min")
    # [END solution_printer]


def main():
    """Solve the VRP with time windows."""
    # Instantiate the data problem.
    # [START data]
    data = create_data_model()
    # [END data]

    # Create the routing index manager.
    # [START index_manager]
    manager = pywrapcp.RoutingIndexManager(
        len(data["time_matrix"]), data["num_vehicles"], data["depot"]
    )
    # [END index_manager]

    # Create Routing Model.
    # [START routing_model]
    routing = pywrapcp.RoutingModel(manager)
    # [END routing_model]

    # Create and register a transit callback.
    # [START transit_callback]
    def time_callback(from_index, to_index):
        """Returns the travel time between the two nodes."""
        # Convert from routing variable Index to time matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data["time_matrix"][from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(time_callback)
    # [END transit_callback]

    # Define cost of each arc.
    # [START arc_cost]
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
    # [END arc_cost]

    # Add Time Windows constraint.
    # [START time_windows_constraint]
    max_waiting_time = math.ceil(max(x[1] for x in data["time_windows"])+max(max(sub_array) for sub_array in data["time_matrix"]))
    time = "Time"
    routing.AddDimension(
        transit_callback_index,
        max_waiting_time,  # allow waiting time
        max_waiting_time,  # maximum time per vehicle
        True,  # Don't force start cumul to zero.
        time,
    )
    time_dimension = routing.GetDimensionOrDie(time)
    # Add time window constraints for each location except depot.
    for location_idx, time_window in enumerate(data["time_windows"]):
        if location_idx == data["depot"]:
            continue
        index = manager.NodeToIndex(location_idx)
        time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
    # Add time window constraints for each vehicle start node.
    depot_idx = data["depot"]
    for vehicle_id in range(data["num_vehicles"]):
        index = routing.Start(vehicle_id)
        time_dimension.CumulVar(index).SetRange(
            data["time_windows"][depot_idx][0], data["time_windows"][depot_idx][1]
        )
    # [END time_windows_constraint]

    # Instantiate route start and end times to produce feasible times.
    # [START depot_start_end_times]
    for i in range(data["num_vehicles"]):
        routing.AddVariableMinimizedByFinalizer(
            time_dimension.CumulVar(routing.Start(i))
        )
        routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.End(i)))
    # [END depot_start_end_times]

    # Setting first solution heuristic.
    # [START parameters]
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    )
    # [END parameters]

    # Solve the problem.
    # [START solve]
    solution = routing.SolveWithParameters(search_parameters)
    # [END solve]

    # Print solution on console.
    # [START print_solution]
    if solution:
        print_solution(data, manager, routing, solution)
    else:
        print("No solution")
    # [END print_solution]


if __name__ == "__main__":
    main()
# [END program]

[sschnug]

A few remarks:

• the routing-solver only supports discrete-domains -> you must not use floating-point data (e.g. 45.1774) => consider multiplying everything with 10000 in your case
  • Documentation 1: Int!
  • Documentation 2: Scaling
  • see also Or-tools is not giving the best route for a matrix with floating point distances
• the routing-solver is conceptionally a metaheuristic (if not configured to do local-search only) with anytime-behaviour: it's not complete and without any stopping-condition (e.g. time-limit; local-convergence when no metaheuristic) it will run forever
  • CPLEX for this will be a complete method and happily stop when optimality is proven
  • the routing-solver is developed for instances of larger scale which cannot be tackled with CPLEX and math-opt in general
• exec in python code is somewhat a red flag: if you are learning python -> get rid of it eventually!

With the right keywords, you can find more information in the mailing-list or this repos issues/discussions.

[mjposs]

Thank you for the details.