Pickup and delivery with Time Windows (PDPTW) with custom start/end locations - python

[Karan Jagdale]

Hi,

I am trying to implement pick up and delivery problem time window and capacity constraints with custom start and end locations and vehicle time windows

I am attaching the code below, which works. It has total of 9 nodes of which 0,7,8 are used for start and stop locations and others are pick up and delivery locations. The problem is, when I use,

data['starts'] = [7,0]

data['ends'] = [8,0]

it does not works, and I get, Segmentation fault (core dumped) and in Spyder the kernel dies. I am using python 3.5.2 and or tools 7.7

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, 9, 8, 7, 3, 6, 2, 3],
        [6, 0, 8, 3, 2, 6, 8, 4, 8],
        [9, 8, 0, 11, 10, 6, 3, 9, 5],
        [8, 3, 11, 0, 1, 7, 10, 6, 10],
        [7, 2, 10, 1, 0, 6, 9, 4, 8],
        [3, 6, 6, 7, 6, 0, 2, 3, 2],
        [6, 8, 3, 10, 9, 2, 0, 6, 2],
        [2, 4, 9, 6, 4, 3, 6, 0, 4],
        [3, 8, 5, 10, 8, 2, 2, 4, 0],
       
      
    ]
    data['time_windows'] = [
        (200, 200),  # depot
        (0, 1800),  # 1
        (0, 1800),  # 2
        (0, 1800),  # 3
        (0, 1800),  # 4
        (0, 1800),  # 5
        (0, 1800),  # 6
        (0, 1800),  # 7
        (0, 1800),  # 8
       
      
    ]
    data['start_time'] = [
    (200,200),
    (300,300),   
    ]
    data['stop_time'] = [
    290, 390
    ]
    data['pickups_deliveries'] = [
        [1, 6],     #2
        [2, 5],    #4
        [4, 3],     #1
       # [6, 4],    #0    
       
     
    ]
    data['demands'] = [0,2,4,-1,1,-4,-2,0,0]
    data['starts'] = [7,8]
    data['ends'] = [0,0]
    data['vehicle_capacities'] = [10,10]
    data['num_vehicles'] = 2
    data['depot'] = 0
    return data


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


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

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

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


    # Create and register a 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)

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

    # Add Time Windows constraint.
    time = 'Time'
    routing.AddDimensionWithVehicleCapacity(
        transit_callback_index,
        2,  # allow waiting time
        data['stop_time'],  # maximum time per vehicle
        False,  # Don't force start cumul to zero.
        time)
    time_dimension = routing.GetDimensionOrDie(time)
    #time_dimension.SetGlobalSpanCostCoefficient(1000)
    routing.SetFixedCostOfAllVehicles(100)
    # Add time window constraints for each location except depot.
    for location_idx, time_window in enumerate(data['time_windows']):
        if location_idx == 0:
            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.
    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        time_dimension.CumulVar(index).SetRange(data['start_time'][vehicle_id][0],
                                                data['start_time'][vehicle_id][1])

    # Instantiate route start and end times to produce feasible times.
    for i in range(data['num_vehicles']):
        routing.AddVariableMinimizedByFinalizer(
            time_dimension.CumulVar(routing.Start(i)))
        routing.AddVariableMinimizedByFinalizer(
            time_dimension.CumulVar(routing.End(i)))
    # Define Transportation Requests.
    for request in data['pickups_deliveries']:
        pickup_index = manager.NodeToIndex(request[0])
        delivery_index = manager.NodeToIndex(request[1])
        routing.AddPickupAndDelivery(pickup_index, delivery_index)
        routing.solver().Add(
            routing.VehicleVar(pickup_index) == routing.VehicleVar(
                delivery_index))
        routing.solver().Add(
            time_dimension.CumulVar(pickup_index) <=
            time_dimension.CumulVar(delivery_index))
   
   
    def demand_callback(from_index):
        """Returns the demand of the node."""
        # Convert from routing variable Index to demands NodeIndex.
        from_node = manager.IndexToNode(from_index)
        return data['demands'][from_node]
   
    demand_callback_index = routing.RegisterUnaryTransitCallback(
        demand_callback)
    routing.AddDimensionWithVehicleCapacity(
        demand_callback_index,
        0,  # null capacity slack
        data['vehicle_capacities'],  # vehicle maximum capacities
        True,  # start cumul to zero
        'Capacity')
    print('costvar',routing.CostVar())
    # 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)

    print("Status", routing.status())
if __name__ == '__main__':
    main()

Anyone has any idea why it is not working?

Thanks,

Karan Jagdale.

[Laurent Perron]

Maybe you cannot use the same node for start and end ?

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/227dd223-43d8-4005-946d-728a37078975n%40googlegroups.com.

[Mizux Dev]

not sure NodeToIndex is defined for 7 and 8

so please replace

```python

 for location_idx, time_window in enumerate(data['time_windows']):
        if location_idx == 0:
            continue
        index = manager.NodeToIndex(location_idx)

```

by something like this (blind fix)

```python

 for location_idx, time_window in enumerate(data['time_windows']):

        if location_idx == 0 or location_idx == 7 or location_idx == 8:
            continue
        index = manager.NodeToIndex(location_idx)

```

[Mizux Dev]

maybe this is more pythonic

if location_idx in [0, 7, 8]:

  continue

[Karan Jagdale]

Hi,

Thanks for your reply.

We can use same nodes, I have checked a code where instead of using depot node I made start and end lists with same node(depot), and it worked.

Thanks,

Karan Jagdale.

[Karan Jagdale]

Hi,

@Mizux it worked after changing the code according to your suggestion. Thanks! Can you tell why NodeToIndex is not defined for 7 and 8?

Thanks,

Karan Jagdale.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/8abe8460-1a17-450b-ab60-25ad5418ec2cn%40googlegroups.com.