How to solve the Cumulative Traveling Salesman Problem with or-tools

[sebastian-quintero]

Hi there! 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 = 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? 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

[lperron]

Duplicate of #1388 IMO.. Tell me if I am wrong.

Now, I do not think we have a good solution for that.

[jmarca]

Two items. First, searching google for "cumulative traveling salesman problem," I found this paper (https://hal.inria.fr/hal-00648451/document) which suggests that there is an exact algorithm for solving it. Just implement that algorithm.

Second, I found the above post cross-posted to stack overflow and stack exchange, which I understood to be somewhat rude. You should at least acknowledge on each platform that you've asked the same question in multiple forums.