Or-tools: Problem with VRPTW no solution find/ assignement = none

[tapafe]

Hello,

I try to work with OR-tools. When I start my program, I often do not have a solution. The assignement result is "none". I think the problem comes from my random generation of my matrix.
Here my data generator:

# Data generator
nt = rng.randint(4,5)  # Number of trucks
nc = rng.randint(15,20) # Number of cities
print(str(nt) + " trucks,", str(nc) + " cities")

# Cities
cities = [x for x in range(1,nc+1)]
node = [0] + cities # Base + cities

# Create time window
for i in range(0,nc+1):
    if i ==0:
        timewindows.append((0,24))
    else:
        begin = rng.randint(0,14)
        end = rng.randint(begin+8,24)
        timewindows.append((begin,end))

# Create coord
def new_city_position():
    nbx = rng.randint(0, countrysize)
    nby = rng.randint(0, countrysize)
    if (nbx, nby) not in ccoord:
        ccoord.append((nbx, nby))
        return [nbx, nby]
    else:
        return new_city_position()

for x in range(0,nc+1):
    (x, y) = new_city_position()
    loc_x.append(x)
    loc_y.append(y)


arc={(i,j) for i in node for j in node if i!=j}
fill_duration_list()

# Matrix
for i in range(0,nc+1):
    l = []
    for j in range(0,nc+1):
        if i!=j:
            l.append(distance[(i, j)])
        else:
            l.append(0)
    matrix.append(l)

And the solver is the same of or-tools tutorial

def main():
    global truck_routing
    """Solve the VRP with time windows."""
    data = create_data_model()
    manager = pywrapcp.RoutingIndexManager(len(data['time_matrix']), data['num_vehicles'], data['depot'])
    routing = pywrapcp.RoutingModel(manager)

    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)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
    time = 'Time'
    routing.AddDimension(
        transit_callback_index,
        86400,  # allow waiting time
        604800,  # maximum time per vehicle
        True,  # Don't force start cumul to zero.
        time)
    time_dimension = routing.GetDimensionOrDie(time)
    # 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['time_windows'][0][0],
                                                data['time_windows'][0][1])
    for i in range(data['num_vehicles']):
        print("> rooting." + ("."*i))
        routing.AddVariableMinimizedByFinalizer(
            time_dimension.CumulVar(routing.Start(i)))
        routing.AddVariableMinimizedByFinalizer(
            time_dimension.CumulVar(routing.End(i)))
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
    print("> solving...")
    assignment = routing.SolveWithParameters(search_parameters)

    if assignment:
        global truck_routing
        truck_routing = print_solution(data, manager, routing, assignment)
    else:
        print(assignment)

Kind Regards

[lperron]

Start by relaxing max time, max waiting time, number of vehicles,
then restrict until you cannot find a solution anymore.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le mer. 3 juil. 2019 à 10:58, tapafe [e-mail] a écrit :

Hello,

I try to work with OR-tools. When I start my program, I often do not have
a solution. The assignement result is "none". I think the problem comes
from my random generation of my matrix.
Here my data generator:

Data generator

nt = rng.randint(4,5) # Number of trucks
nc = rng.randint(15,20) # Number of cities
print(str(nt) + " trucks,", str(nc) + " cities")

Cities

cities = [x for x in range(1,nc+1)]
node = [0] + cities # Base + cities

Create time window

for i in range(0,nc+1):
if i ==0:
timewindows.append((0,24))
else:
begin = rng.randint(0,14)
end = rng.randint(begin+8,24)
timewindows.append((begin,end))

Create coord

def new_city_position():
nbx = rng.randint(0, countrysize)
nby = rng.randint(0, countrysize)
if (nbx, nby) not in ccoord:
ccoord.append((nbx, nby))
return [nbx, nby]
else:
return new_city_position()

for x in range(0,nc+1):
(x, y) = new_city_position()
loc_x.append(x)
loc_y.append(y)

arc={(i,j) for i in node for j in node if i!=j}
fill_duration_list()

Matrix

for i in range(0,nc+1):
l = []
for j in range(0,nc+1):
if i!=j:
l.append(distance[(i, j)])
else:
l.append(0)
matrix.append(l)

And the solver is the same of or-tools tutorial

def main():
global truck_routing
"""Solve the VRP with time windows."""
data = create_data_model()
manager = pywrapcp.RoutingIndexManager(len(data['time_matrix']), data['num_vehicles'], data['depot'])
routing = pywrapcp.RoutingModel(manager)

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)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
time = 'Time'
routing.AddDimension(
    transit_callback_index,
    86400,  # allow waiting time
    604800,  # maximum time per vehicle
    True,  # Don't force start cumul to zero.
    time)
time_dimension = routing.GetDimensionOrDie(time)
# 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['time_windows'][0][0],
                                            data['time_windows'][0][1])
for i in range(data['num_vehicles']):
    print("> rooting." + ("."*i))
    routing.AddVariableMinimizedByFinalizer(
        time_dimension.CumulVar(routing.Start(i)))
    routing.AddVariableMinimizedByFinalizer(
        time_dimension.CumulVar(routing.End(i)))
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
print("> solving...")
assignment = routing.SolveWithParameters(search_parameters)

if assignment:
    global truck_routing
    truck_routing = print_solution(data, manager, routing, assignment)
else:
    print(assignment)

Kind Regards

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1397?email_source=notifications&email_token=ACUPL3K2BDIVWM3NCEH2MXDP5RS2ZA5CNFSM4H5DPYO2YY3PNVWWK3TUL52HS4DFUVEXG43VMWVGG33NNVSW45C7NFSM4G5CNWCA,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3LIQYJDRGGAB2SQVPDP5RS2ZANCNFSM4H5DPYOQ
.

[tapafe]

So you mean replace:

routing.AddDimension(
        transit_callback_index,
        86400,  # allow waiting time
        604800,  # maximum time per vehicle
        True,  # Don't force start cumul to zero.
        time)

with something like

routing.AddDimension(
        transit_callback_index,
        9999999,  # allow waiting time
        9999999,  # maximum time per vehicle
        True,  # Don't force start cumul to zero.
        time)

then reduce time and/or vehices?

Sorry I don't do very well English

[lperron]

yes

add more vehicles too
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le mer. 3 juil. 2019 à 11:14, tapafe [e-mail] a écrit :

So you mean replace:

routing.AddDimension(
transit_callback_index,
86400, # allow waiting time
604800, # maximum time per vehicle
True, # Don't force start cumul to zero.
time)

with something like

routing.AddDimension(
transit_callback_index,
9999999, # allow waiting time
9999999, # maximum time per vehicle
True, # Don't force start cumul to zero.
time)

then reduce time and/or vehices?

Sorry I don't do very well English

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1397?email_source=notifications&email_token=ACUPL3JQKA57UN3TT2XC3SLP5RUYNA5CNFSM4H5DPYO2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODZD2LYA#issuecomment-508012000,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3KP3BDTUDAZXT35KQTP5RUYNANCNFSM4H5DPYOQ
.

[jmarca]

Also, the solver by default is all or nothing---that is, every node is served, or no nodes are served. You can relax this constraint by adding a penalty if a node is dropped. For example, if the penalty is P and the solver can generate a solution if it drops 5 nodes, the total "drop" penalty would be 5 * P. If P is very large, then the solver will try harder to keep nodes in. If P is very small, then it might be cheaper to drop the node than serve it, so make sure P is large enough.

To see how to do that, check out the docs here: https://developers.google.com/optimization/routing/penalties#add-the-capacity-constraints-and-penalties