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 have10 + 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