How to solve the Cumulative Traveling Salesman Problem using or-tools in python?

Question

The objective of the Cumulative Traveling Salesman Problem (CTSP) is to minimize the sum of arrival times at customers, instead of the total travelling time. This is different than minimizing the overall time of travel. For example, if one has unlimited vehicles (# vehicles is the same as # of locations) and the objective is to minimize the overall time to locations, one would send one vehicle per location, for it is the fastest way to satisfy said demands. One can see that the or-tools routing module focuses mainly on minimizing the overall travel time (not the time to locations). Is there a way to solve the CTSP, and, even better, have a balance (maybe using weights) between minimizing time to locations vs. minimizing travelling time?

Let me show an analytical example. Let's say we have a depot (0) and two customers (1 and 2). Let's consider the following time matrix:

[[0, 10, 20],
[10, 0, 15],
[20, 15, 0]]

Let's assume we have a number of vehicles equal to the number of locations (2 vehicles). Let's consider the following two situations:

Objective 1: if we want to minimize overall travel time

The solution is 0 -> 1 -> 2 -> 0 (one vehicle is used), where:

• travel time is 45. 0 -> 1: 10 + 1 -> 2: 15 + 2 -> 0: 20 = 10 + 15 + 20 = 45.
• locations time is 35. For location 1: 0 -> 1: 10. For location 2 (note that we have to pass through location 1): 0 -> 1: 10 + 1 -> 2: 15. In summation, we have: 10 + 10 + 15 = 35.

Objective 2: if we want to minimize time to locations

The solution is 0 -> 1 -> 0 and 0 -> 2 -> 0 (two vehicles are used), where:

• travel time is 60. For vehicle 1: 0 -> 1: 10 + 1 -> 0: 10. For vehicle 2: 0 -> 2: 20 + 2 -> 0: 20. In summation, we have 10 + 10 + 20 + 20 = 60.
• locations time is 30. For location 1: 0 -> 1: 10. For location 2 (note that we do not have to pass through location 1): 0 -> 2: 20. In summation, we have: 10 + 20 = 30.

So... Can this be done? Can one solve the CTSP (objective 2)? Is it possible to have an objective function such that we could balance both of these objectives (i.e. min alpha * overall_travel_time + beta * time_to_locations, such that alpha and beta are weights). Python code is much appreciated. Thank you!

Working code for objective 1: minimizing the overall travel time

"""Vehicles Routing Problem (VRP)."""

from __future__ import print_function

from ortools.constraint_solver import pywrapcp


def create_data_model():
    """Stores the data for the problem."""
    data = {}
    data['time_matrix'] = [
        [0, 10, 20],
        [10, 0, 15],
        [20, 15, 0]
    ]
    data['num_vehicles'] = 2
    data['depot'] = 0
    return data


def print_solution(data, manager, routing, solution):
    """Prints solution on console."""
    max_route_time = 0
    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
        route_time = 0
        while not routing.IsEnd(index):
            plan_output += ' {} -> '.format(manager.IndexToNode(index))
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            route_time += routing.GetArcCostForVehicle(
                previous_index, index, vehicle_id)
        plan_output += '{}\n'.format(manager.IndexToNode(index))
        plan_output += 'time of the route: {}\n'.format(route_time)
        print(plan_output)
        max_route_time = max(route_time, max_route_time)
    print('Maximum of the route times: {}'.format(max_route_time))


def main():
    """Solve the CVRP problem."""
    # Instantiate the data problem.
    data = create_data_model()

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

    # Create Routing Model.
    routing = pywrapcp.RoutingModel(manager)

    # Create and register a transit callback.
    def time_callback(from_index, to_index):
        """Returns the 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)

    # Define cost of each arc.
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # Setting first solution heuristic.
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()

    # Solve the problem.
    solution = routing.SolveWithParameters(search_parameters)

    # Print solution on console.
    if solution:
        print_solution(data, manager, routing, solution)


if __name__ == '__main__':
    main()

Results for the above code

Route for vehicle 0:
 0 -> 0
time of the route: 0

Route for vehicle 1:
 0 ->  1 ->  2 -> 0
time of the route: 45

Maximum of the route times: 45

Answer 1

This is a heuristic approach to the problem you describe using OR tools. Consider a procedure in which you “guess” what the maximum route duration is (across all routes), and will find this in a binary search fashion. Your guess, $G$, is between $L$ and $U$, and for a particular iteration, set it to $G=\frac{U+L}{2}$. At iteration 0, $L=0$and $U=\texttt{max duration vrp}$ (45 in your example). Now add a constraint to the problem using routing.AddDimension() that says that routes should have a duration less or equal to $G$. If the problem is feasible, then $U=G$ and update $G$. Otherwise, $L=G$ and update $G$. You do this until the $L$ and $U$ are arbitrarily close. Note that every time you update $G$, you need to update the constraint you added to the routing object (or create a new object from scratch).