[pickup and delivery problem]Constraint failure in PDP problem with one-to-many requirements #2342
Unanswered
Killajam
asked this question in
Routing (and legacy CP) questions
Replies: 2 comments 13 replies
-
for k, v in Conf.same.items():
for poi in v:
routing.solver().Add(
routing.VehicleVar(k) == routing.VehicleVar(
poi))It seems that after commenting out this code, the maximum distance limit function can be implemented normally. The operation of this step is mainly because I have some requirements that are one-to-many or many-to-one. I split the dots into multiple dots and made sure they are in the same car. Is there a problem with the code written here? |
Beta Was this translation helpful? Give feedback.
2 replies
-
|
Are you storing solver index ? otherwise you should use for k, v in Conf.same.items():
for poi in v:
routing.solver().Add(
routing.VehicleVar(manager.NodeToIndex(k)) ==
routing.VehicleVar(manager.NodeToIndex(poi)))note: |
Beta Was this translation helpful? Give feedback.
-
|
I tried this method but nothing changed. The maximum range of 100000 is too much, which leads to a very long range for my car.But when I limit the maximum driving distance to 50,000-100,000, I can't find a feasible solution.I wonder what caused it? |
Beta Was this translation helpful? Give feedback.
-
So, you should try this instead: # Setting first solution heuristic.
# [START parameters]
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
search_parameters.local_search_metaheuristic = (
routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.FromSeconds(100)
# [END parameters] |
Beta Was this translation helpful? Give feedback.
11 replies
-
|
dismatrix: # The model doesn't have depots,so i set a virtual depot.
[[ 0 0 0 0 0 0 0 0 0]
[ 0 0 10703 8717 8717 3183 3183 6078 1947]
[ 0 10703 0 2748 2748 8519 8519 16781 12232]
[ 0 8717 2748 0 0 6123 6123 14730 10018]
[ 0 8717 2748 0 0 6123 6123 14730 10018]
[ 0 3183 8519 6123 6123 0 0 8765 3969]
[ 0 3183 8519 6123 6123 0 0 8765 3969]
[ 0 6078 16781 14730 14730 8765 8765 0 4803]
[ 0 1947 12232 10018 10018 3969 3969 4803 0]]pickups_deliveries: [[1, 5], [2, 6], [3, 7], [4, 8]]
num_vehicles = 9
vehicles_capacity = 20
demands: array([ 0, 1, 2, 1, 3, -1, -2, -1, -3])code: from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
import pickle
import pandas as pd
import time
import os
import numpy as np
from src.pre_process.conf import Conf
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
import matplotlib.pyplot as plt
def create_data_model():
"""Stores the data for the problem."""
Conf.get_vrp_data()
data = dict()
data['pickups_deliveries'] = Conf.pickup_relation
data['distance_matrix'] = Conf.od_dismat
data['num_vehicles'] = len(Conf.od_dismat)
# data['num_vehicles'] = len(Conf.od_dismat)
data['vehicle_capacities'] = [20 for i in range(data['num_vehicles'])]
data['depot'] = 0
data['demands'] = Conf.demand
# data['nodes_limit'] = [4 for i in range(data['num_vehicles'])]
print(data)
print(Conf.same)
return data
def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
total_distance = 0
plt.figure(figsize=(10, 10), dpi=100)
result = []
for vehicle_id in range(data['num_vehicles']):
point = []
index = routing.Start(vehicle_id)
plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
route_distance = 0
distance = 0
while not routing.IsEnd(index):
plan_output += ' {} -> '.format(manager.IndexToNode(index))
if manager.IndexToNode(index) != 0:
point.append(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))
result.append(point)
x_list = [Conf.od_point[Conf.od_point.idx == i]['lng'].values[0] for i in point]
y_list = [Conf.od_point[Conf.od_point.idx == i]['lat'].values[0] for i in point]
plt.plot(x_list, y_list, linewidth=2)
for i in range(1, len(point)):
distance += Conf.od_dismat[point[i - 1]][point[i]]
plan_output += 'Distance of the route: {}m\n'.format(route_distance)
plan_output += 'Distance of the route: {}m\n'.format(distance)
print(plan_output)
total_distance += route_distance
print('Total Distance of all routes: {}m'.format(total_distance))
# plt.show()
print(os.getcwd())
with open('../data/test_result/vrp_result.pkl', 'wb') as f:
pickle.dump(result, f)
print(f)
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['distance_matrix']),
data['num_vehicles'], data['depot'])
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
for vehicle_id in range(data['num_vehicles']):
routing.SetFixedCostOfVehicle(100000, vehicle_id)
# Define cost of each arc.
def distance_callback(from_index, to_index):
"""Returns the manhattan 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['distance_matrix'][from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(distance_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# # Add Distance constraint.
dimension_name = 'Distance'
routing.AddDimension(
transit_callback_index,
0, # no slack
1000000, # vehicle maximum travel distance
True, # start cumul to zero
dimension_name)
distance_dimension = routing.GetDimensionOrDie(dimension_name)
distance_dimension.SetGlobalSpanCostCoefficient(100)
# add capacity
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')
# # add number of visited locations constraint
# def counter_callback(from_index):
# """Returns 1 for any locations except depot."""
# # Convert from routing variable Index to user NodeIndex.
# from_node = manager.IndexToNode(from_index)
# return 1 if (from_node != 0) else 0
#
# counter_callback_index = routing.RegisterUnaryTransitCallback(counter_callback)
# print(data['nodes_limit'])
# routing.AddDimensionWithVehicleCapacity(
# counter_callback_index,
# 0, # null slack
# data['nodes_limit'], # maximum locations per vehicle
# True, # start cumul to zero
# 'Counter')
# 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(
distance_dimension.CumulVar(pickup_index) <=
distance_dimension.CumulVar(delivery_index))
# print(Conf.same)
i = 0
penalty = 100000
for k, v in Conf.same.items():
for poi in v:
i += 1
pickup_index = manager.NodeToIndex(k)
delivery_index = manager.NodeToIndex(poi)
# print(Conf.od_point[Conf.od_point.idx == k])
# print(Conf.od_point[Conf.od_point.idx == poi])
print(pickup_index, delivery_index)
routing.solver().Add(
distance_dimension.CumulVar(pickup_index) ==
distance_dimension.CumulVar(delivery_index))
routing.solver().Add(
routing.VehicleVar(pickup_index) == routing.VehicleVar(
delivery_index))
# routing.AddDisjunction([manager.NodeToIndex(pickup_index),manager.NodeToIndex(delivery_index)], penalty, 2)
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION)
# search_parameters.local_search_metaheuristic = (
# routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
# search_parameters.time_limit.seconds = 200
# search_parameters.log_search = True
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
# Print solution on console.
print(routing.status())
if solution:
print_solution(data, manager, routing, solution)
if __name__ == '__main__':
start = time.time()
main()
end = time.time()
print(end - start)
# create_data_model()
# Conf.get_vrp_data()Here is my model and code.To put it simply, my model is based on the original PDP, plus the restriction of one-to-many distribution, that is, the same demand must be in one vehicle.Since OrTools doesn't support direct one-to-many input, I split the same points into multiple points.In my code, point 3 is the same point as point 4, and point 5 is the same point as point 6.So I added this restriction(same thing with point 5:6): But once I add this limit, my limit on the number of stops and distance I can drive doesn't take effect.Or you just don't get a solution.So what's the problem?:( |
Beta Was this translation helpful? Give feedback.
-
|
You can take a look at https://gist.github.com/Mizux/9e37c370a459bd472a6ac13c304f0b54
In your case something like this: index_3 = manager.NodeToIndex(3)
index_4 = manager.NodeToIndex(4)
# Allow node to be dropped
routing.AddDisjunction([index_3], 1000)
routing.AddDisjunction([index_4], 1000)
# if both nodes active then add the "same vehicle" constraint
active_n3_n4 = routing.ActiveVar(index_3) * routing.ActiveVar(index_4)
routing.solver().Add(
active_n3_n4 * routing.VehicleVar(index_3) ==
active_n3_n4 * routing.VehicleVar(index_4)) |
Beta Was this translation helpful? Give feedback.
-
|
It still doesn't work. :( |
Beta Was this translation helpful? Give feedback.
-
|
im currently working on a similar project and facing the same problem. Is thera any solution? The package is going to considerate the one to many case in a more usable way instead of this hacky thing? |
Beta Was this translation helpful? Give feedback.
-
|
hi gabtorr，have you solved this problem? |
Beta Was this translation helpful? Give feedback.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
-
In my PDP problem, there was a one-to-many transportation requirement and they had to be on the same vehicle.My specific approach is to divide points with multiple requirements into multiple points, such as :(A,B) (A,C) (A,D).
So I change the demand pair to (A1,B) (A2,C) (A3,D).
Then add A1,A2, and A3 to the constraints at the same point, for example:
But once I add this constraint, my distance constraint or my number constraint doesn't work, and the solver can't find a viable solution.But I'm pretty sure there must be a solution because I'm giving a big enough number of vehicles.Is there a problem with the constraints I added above?I have been perplexed by this problem for many days. Is there anyone who can give me some advice?
Here is my code:
Beta Was this translation helpful? Give feedback.
All reactions