Or-tools: VRP with multiple starts/ends

[colacolalove]

Hope for your reply ! Thank you
My problem:

1. 4 vehicles starting from different points need to finish the tasks of 10 cities and finally go back to their startpoints. Actully, i also want to know the method about not going back.
2. every cities has own time-window
3. add pickup and delivery constraint
   i don't know how to deal with different startpoint

[Mizux]

Hi,
Most of it is on optimization documentation:
1) Simply pass an array of starts and ends points
https://developers.google.com/optimization/routing/routing_tasks#setting-start-and-end-locations-for-routes
no comming back is equivalent to send them to a "dummy" point distance of 0 from any other point
https://developers.google.com/optimization/routing/routing_tasks#allowing-arbitrary-start-and-end-locations
master samples: https://github.com/google/or-tools/blob/master/ortools/constraint_solver/doc/VRP.md#multiple-starts-ends

2) https://developers.google.com/optimization/routing/cvrptw
master samples: https://github.com/google/or-tools/blob/master/ortools/constraint_solver/doc/VRP.md#time-window-constraints

3) You must now the pair (pickup point, delivery point)
https://github.com/google/or-tools/blob/master/ortools/constraint_solver/doc/PDP.md
note: samples, on master, i.e. PickupDeliveryPolicy is no available on last stable version v6.10.

[colacolalove]

Thank you for your reply! Due to my negligence, I have not seen any solution in this regard. I will first look at this aspect.

[colacolalove]

嗨，
大部分是关于优化文档：

1. 只需传递一系列起点和终点
   https://developers.google.com/optimization/routing/routing_tasks#setting-start-and-end-locations-for-routes
   没有回复相当于将它们发送给“假人” “与任何其他点的点距离为0
   https://developers.google.com/optimization/routing/routing_tasks#allowing-arbitrary-start-and-end-locations
   主样本：https：//github.com/google/or -tools /斑点/主/ ortools / constraint_solver / DOC / VRP.md＃多开始-端
2. https://developers.google.com/optimization/routing/cvrptw
   主样本：https：//github.com/google/or-tools/blob/master/ortools/constraint_solver/doc/VRP.md#time-window-限制
3. 你现在必须这对（提货点，交货点）
   https://github.com/google/or-tools/blob/master/ortools/constraint_solver/doc/PDP.md
   注意：样品，在主机上，即PickupDeliveryPolicy是否最新稳定版本v6.10。

Hello, here is a problem:
In the case of no coming back, i determine 4 different starting points, but the ending point can be arbitrary, how to deal with this situation? Thank for your help

[paultrow]

Good question. Change the the distance matrix so that just the return distance from any location to the depot is 0, but leave the distances from the depot to all other locations unchanged. That is, make the first column all 0s, but not the first row. Then just the end points will be arbitrary. This should have been mentioned in the example - I'll add a note about it. Thanks.

[colacolalove]

I have a question:
if i want to use ortools to solve my problem, but i don't know what algorithm to say .Thank you

[CognitiveClouds-Prasad]

How/why is this an open issue? Google OR-Tools is quite awesome for all the scenarios OP has mentioned and I believe there is adequate documentation about the same as well.

[shandilya1998]

Hey i have a similar problem, but without the pickup and delivery constraint. When i try to implement a time window constraint on a different starting and ending point vrp, i am getting the following error-

`RuntimeError: SWIG std::function invocation failed.

The above exception was the direct cause of the following exception:

Traceback (most recent call last):
  File "/Users/travelapp/PycharmProjects/TravelApp/venv/lib/python3.7/site-packages/ortools/constraint_solver/pywrapcp.py", line 2136, in <lambda>
    __setattr__ = lambda self, name, value: _swig_setattr(self, Assignment, name, value)
  File "/Users/travelapp/PycharmProjects/TravelApp/venv/lib/python3.7/site-packages/ortools/constraint_solver/pywrapcp.py", line 71, in _swig_setattr
    return _swig_setattr_nondynamic(self, class_type, name, value, 0)
  File "/Users/travelapp/PycharmProjects/TravelApp/venv/lib/python3.7/site-packages/ortools/constraint_solver/pywrapcp.py", line 55, in _swig_setattr_nondynamic
    if type(value).__name__ == 'SwigPyObject':
SystemError: <class 'type'> returned a result with an error set

The above exception was the direct cause of the following exception:

Traceback (most recent call last):
  File "/Users/travelapp/PycharmProjects/TravelApp/travelapp.py", line 213, in <module>
    from travelapp import TripPlanner
  File "/Users/travelapp/PycharmProjects/TravelApp/travelapp.py", line 215, in <module>
    ob.plan_trip
  File "/Users/travelapp/PycharmProjects/TravelApp/travelapp.py", line 206, in plan_trip
    solution = routing.SolveWithParameters(search_parameters)
  File "/Users/travelapp/PycharmProjects/TravelApp/venv/lib/python3.7/site-packages/ortools/constraint_solver/pywrapcp.py", line 3464, in SolveWithParameters
    return _pywrapcp.RoutingModel_SolveWithParameters(self, search_parameters, solutions)
SystemError: <built-in function RoutingModel_SolveWithParameters> returned a result with an error set` 

Here is the code i am writing for reference -

"""Simple Vehicles Routing Problem."""

from __future__ import print_function
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp


def create_data_model():
    """Stores the data for the problem."""
    data = {}
    data['time_matrix'] = [
        [0, 6, 7, 9, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7, 0],
        [6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 12, 14, 6],
        [7, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9, 15],
        [9, 3, 11, 0, 3, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16, 14],
        [7, 2, 10, 3, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14, 9],
        [3, 6, 6, 7, 6, 0, 2, 8, 2, 2, 7, 9, 7, 7, 6, 12, 8, 3],
        [6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 11, 5, 10],
        [2, 4, 9, 6, 4, 8, 6, 0, 4, 4, 8, 5, 4, 13, 7, 8, 10, 12],
        [3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6, 5],
        [2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5, 8],
        [6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4, 9],
        [6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 13, 10, 11],
        [4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 16, 4, 8, 1],
        [4, 8, 13, 9, 8, 7, 10, 13, 7, 4, 8, 3, 2, 0, 4, 5, 6, 2],
        [5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 16, 4, 0, 9, 12, 4],
        [9, 12, 18, 6, 8, 12, 11, 8, 13, 9, 13, 13, 4, 5, 9, 0, 9, 10],
        [7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 12, 9, 0, 13],
        [0, 6, 15, 14, 9, 3, 10, 12, 5, 8, 9, 11, 1, 2, 4, 10, 13, 0]
    ]
    data['time_windows'] = [
        (0, 22),  # depot
        (7, 12),  # 1
        (10, 15),  # 2
        (6, 8),  # 3
        (10, 13),  # 4
        (0, 5),  # 5
        (5, 10),  # 6
        (0, 4),  # 7
        (5, 7),  # 8
        (0, 3),  # 9
        (10, 16),  # 10
        (10, 15),  # 11
        (0, 9),  # 12
        (5, 10),  # 13
        (7, 10),  # 14
        (10, 15),  # 15
        (11, 15),  # 16
        (18, 25)  # 17
    ]
    data['num_days'] = 4
    data['start'] = [0, 0, 0, 0]  # ,17,0,17]
    data['end'] = [17, 17, 17, 17]
    return data

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


def main():
    """Entry point of the program."""
    # Instantiate the data problem.
    data = create_data_model()

    # Create the routing index manager.
    manager = pywrapcp.RoutingIndexManager(len(data['time_matrix']), data['num_days'], data['start'], data['end'])

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


    # Create and register a transit callback.
    def time_callback(from_index, to_index):
        """Returns the distance between the two nodes."""
        # Convert from routing variable Index to distance 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)

    # Add time constraint.
    dimension_name = 'time'
    routing.AddDimension(
        transit_callback_index,
        20,  # no slack
        30,  # vehicle maximum travel distance
        True,  # start cumul to zero
        dimension_name)
    time_dimension = routing.GetDimensionOrDie(dimension_name)
    # add time window constraints

    time_dimension.SetGlobalSpanCostCoefficient(10)

    # Setting first solution heuristic.
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

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

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


if __name__ == '__main__':
    main()

[lperron]

There are documented examples for this. Please read them, and open an issue if they do not work,