Is it possible to create a VRP solution using NetworkX?

Question

Please refer to the dummy network created using networkX.

1. I have created a dummy network of 50 nodes (incomplete graph) in Python using the networkX package. The dummy network of nodes is represented by the above diagrams diagrams.

2. I have randomly chosen Nodes AJ, A, G, R as vehicle starting points/depots.

3. I have randomly chosen F, AQ, AA as the dumping zones.

4. Each edge has certain weights, which is a representation of the amount of waste a vehicle can collect from that node.

5. Each depot has fixed number of vehicles, and each vehicle have a fixed carrying capacity, beyond which it will dump the waste to the nearest dumping zone. After dumping the waste, the vehicle can return to the original start depot (if there's no more waste left to clean)

Here the fixed conditions are as follow:

1. Network is fixed.
2. Depot & Dumping zone locations are fixed.
3. Number of vehicle in each dumping zone is fixed.
4. Carrying capacity of each vehicle is fixed for now.
5. Edge weight represents the amount/volume of waste present in a edge.

How to build this solution using OptaPy ?

EDIT:

Let's stay, a vehicle starts from Node R. Based on the waste accumulation, let's say it traverses this path -- R - Q - O - N - L - K - J. Let's say that at Node J, the vehicle capacity will max out, then it should check from J which is the nearest dumping zone. The vehicle will see that F is the nearest dumping zone, so it will go to F, dump the waste and re-start it's operation from F. Let's say from F, the vehicle takes another path -- F - G - U - V - W - X. Let's say that the same vehicles capacity is maxed out at X. Then it will see that the nearest dumping zone from Z is AA, hence it will go there and dump the waste. Now if there's no longer waste left to be cleaned, the vehicle can get back to its starting position which is R.

Answer 1

I would model the problem as below using OptaPy:

• The edges that can be collected from will be an @problem_fact with graph_nodes ids (assuming str) and weight fields:

@optapy.problem_fact
class Edge:
    graph_from_node: str
    graph_to_node: str
    weight: int
    
    def __init__(self, graph_from_node: str, graph_to_node: str, weight: int):
        self.graph_from_node = graph_from_node
        self.graph_to_node = graph_to_node
        self.weight = weight
    

• The @planning_entity is a vehicle, with a fixed depot and carrying capacity, and a @planning_list_variable of Edge:

@optapy.planning_entity
class Vehicle:
    capacity: int
    depot: str
    visited_edges_list: List[Edge]

    def __init__(self, capacity: int, depot: str, visited_edges_list=None):
        self.capacity = capacity
        self.depot = depot
        self.visited_edges_list = [] if visited_edges_list is None else visited_edges_list

    @optapy.planning_list_variable(Edge, ['edge_range'])
    def get_visited_edges_list(self):
        return self.visited_edges_list

    def set_visited_edges_list(self, visited_edges_list):
        return self.visited_edges_list

• There would be a NetworkInfo @problem_fact, which can be used to query dumping zones and get the full network:

@optapy.problem_fact
class NetworkInfo:
    graph: Graph
    dumping_zones: List[str]

    def __init__(self, graph: Graph, dumping_zones: List[str]):
        self.graph = graph
        self.dumping_zones = dumping_zones

• The @planning_solution would store the NetworkInfo, Edge, Vehicle and the solution's score:

from optapy.score import HardSoftScore

@optapy.planning_solution
class VRPSolution:
    def __init__(self, network_info: NetworkInfo, vehicle_list: List[Vehicle], edge_list: List[Edge], score=None):
        self.network_info = network_info
        self.vehicle_list = vehicle_list
        self.edge_list = edge_list
        self.score = score
    
    @problem_fact_property(NetworkInfo)
    def get_network_info(self):
        return self.network_info

    @planning_entity_collection_property(Vehicle)
    def get_vehicle_list(self):
        return self.vehicle_list

    @problem_fact_collection_property(Edge)
    @value_range_provider('edge_range')
    def get_customer_list(self):
        return self.edge_list

    @planning_score(HardSoftScore)
    def get_score(self):
        return self.score

    def set_score(self, score):
        self.score = score

You would create the initial planning problem like this:

problem = VRPSolution(NetworkInfo(my_graph, ['F', 'AQ', 'AA']),
                      [
                        Vehicle(10, 'AJ'),
                        Vehicle(15, 'A'),
                        Vehicle(5, 'G'),
                        Vehicle(15, 'R'),
                        # ...
                      ],
                      [
                        Edge('AM', 'AN', 3),
                        Edge('AW', 'AV', 4),
                        Edge('P', 'Q', 1),
                        # ...
                      ])

You would put your constraints into a @constraint_provider function:

@optapy.constraint_provider
def vehicle_routing_constraints(constraint_factory: ConstraintFactory):
    return [
        over_capacity(constraint_factory),
        # other constraints
    ]

for example, over_capacity would be written like this:

def get_vehicle_total_weight(vehicle: Vehicle):
    total = 0
    for edge in vehicle.visited_edges_list:
        total += edge.weight
    return total
        

def over_capacity(constraint_factory: ConstraintFactory):
    return (
        constraint_factory.for_each(Vehicle)
             .filter(lambda vehicle: get_vehicle_total_weight(vehicle) > vehicle.capacity)
             .penalize('Over Capacity', HardSoftScore.ONE_HARD,
                       lambda vehicle: get_vehicle_total_weight(vehicle) - vehicle.capacity)
    )

My guess is you also want to minimize distance. I will assume the distance function = shortest path between edges as given by networkx:

def get_vehicle_path_total_distance(vehicle: Vehicle, network_info: NetworkInfo):
    current_node = vehicle.depot
    total = 0
    G = network_info.graph
    for edge in vehicle.visited_edges_list:
        total += nx.shortest_path_length(G, source=current_node, target=edge.graph_from_node)
        current_node = edge.graph_to_node
    shortest_path_length_from_current = nx.shortest_path_length(G, source=current_node)
    best_dumping_zone = None
    # best_dumping_zone_path_length = float('inf')
    # Workaround for https://github.com/optapy/optapy/issues/134
    best_dumping_zone_path_length = 999999999999.999
    for dumping_zone in network_info.dumping_zones:
        if shortest_path_length_from_current[dumping_zone] < best_dumping_zone_path_length:
              best_dumping_zone_path_length = shortest_path_length_from_current[dumping_zone]
              best_dumping_zone = dumping_zone
    total += best_dumping_zone_path_length
    total += nx.shortest_path_length(G, source=best_dumping_zone, target=vehicle.depot)
    return total
        

def minimize_distance(constraint_factory: ConstraintFactory):
    return (
        constraint_factory.for_each(Vehicle)
             .join(NetworkInfo)
             .penalize('Minimize Distance', HardSoftScore.ONE_SOFT,
                       get_vehicle_path_total_distance)
    )

(note: this does not take into consideration the "Number of vehicle in each dumping zone is fixed." constraint. If you want the dumping zone to be a planning variable, you currently need to use a chained model (https://www.optapy.org/docs/latest/planner-configuration/planner-configuration.html#chainedPlanningVariable) until https://issues.redhat.com/browse/PLANNER-2755 is fixed). If you are doing overconstrained planning (i.e. not enough vehicles to pick up all the garbage in one run), you can change the score type to HardMediumSoftScore, and add a new field to vehicle is_extra. If the field is_extra is True, the vehicle is ignored by the over_capacity and minimize_distance constraints, and you'll add a new constraint that penalize by HardMediumSoftScore.ONE_MEDIUM for each edge in the extra vehicle's visited_edge_list.

Answer 2

Thank you so much for providing a detailed implementation. I have slightly modified your code, but while running the solver, I am getting an error message as below :

*** RuntimeError: An error occurred during solving. This can occur when functions take the wrong number of parameters (ex: a setter that does not take exactly one parameter) or by a function returning an incompatible return type (ex: returning a str in a filter, which expects a bool). This can also occur when an exception is raised when evaluating constraints/getters/setters.

I have created a NetworkX graph object, and I am currently trying to build the solution on top it. Below is the code for the same. Can you kindly run this code and check if you are able to replicate the same at your end as well? I also have a question related to this implementation.

1. How are you handling the distance matrices? In the implementation, will it automatically take into consideration the distances based on the NetworkX graph object that we create? Or do we need to write a function to compute the distances explicitly?

2. For 'visited_edges_list', what should be the expected input? For each vehicle, do we need to provide a constant list of all the edges? Or we must provide only those edge list which the vehicle can visit?

NOTE : The edge weights represent the waste that needs to be collected from that edge.

EDIT: The runtime error problem was solved, based on the changes suggested by you. I am pasting the latest code, and some outputs to get more clarity on certain questions.

import networkx as nx
from networkx.classes.graph import Graph
import matplotlib.pyplot as plt
import numpy as np
import optapy
from optapy.score import HardMediumSoftScore
from optapy.constraint import ConstraintFactory
from optapy.types import Duration
from optapy import solver_factory_create
from typing import List

random_seed = 43
rnd = np.random
rnd.seed(random_seed)


#Configure the nodes and edges of Graph G
nodes_list = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z',
              'AA','AB','AC','AD','AE','AF','AG','AH','AI','AJ','AK','AL','AM','AN','AO','AP','AQ','AR','AS','AT','AU','AV','AW','AX']

weights = [('A', 'B', 1), 
          ('B', 'C', 2), 
          ('C', 'D', 5),('C', 'AD', 1) ,
          ('D', 'E', 7), 
          ('E', 'F', 4), ('E', 'AX', 1),
          ('F', 'G', 1), 
          ('G', 'H', 1), ('G', 'U', 8),
          ('H', 'I', 1),
          ('I', 'J', 1),
          ('J', 'K', 1), ('J', 'P', 1),
          ('K', 'L', 1),
          ('L', 'M', 1), ('L', 'N', 1),
          ('N', 'O', 1), 
          ('O', 'P', 1),
          ('P', 'Q', 1),
          ('Q', 'R', 1), ('Q', 'S', 1),
          ('P', 'Q', 1),
          ('S', 'T', 1),
          ('U', 'V', 9),
          ('V', 'W', 1), ('V', 'AU', 1),
          ('W', 'X', 1),
          ('X', 'Y', 1), ('X', 'AB', 1),
          ('Y', 'Z', 1),
          ('Z', 'AA', 1),
          ('AB', 'AC', 1),
          ('AD', 'AE', 1),
          ('AE', 'AF', 10),
          ('AF', 'AG', 15),
          ('AG', 'AH', 1),
          ('AH', 'AI', 1), ('AH', 'AK', 1),
          ('AI', 'AJ', 1),
          ('AK', 'AL', 3),
          ('AL', 'AM', 1),
          ('AM', 'AN', 3), ('AM', 'AV', 1),
          ('AN', 'AO', 1), ('AN', 'AQ', 1),
          ('AO', 'AP', 1),
          ('AQ', 'AR', 1),
          ('AR', 'AS', 1),
          ('AV', 'AT', 1),
          ('AT', 'AU', 1),
          ('AV', 'AW', 4),
          ('AW', 'AX', 6)]

def create_graph_network(nodes_list, weights):
    """
    This function generates and plots a graph object by taking nodes list and edges as input.
    """
    G = nx.Graph()
    G.add_nodes_from(nodes_list)
    G.add_weighted_edges_from(weights)
    pos=nx.spring_layout(G, seed=random_seed)
    nx.draw(G, pos, with_labels=True)
    edge_weight =(nx.get_edge_attributes(G,'weight'))
    nx.draw_networkx_edge_labels(G, pos, edge_labels = edge_weight)
    plt.axis('on')
    plt.show()
    return G, pos


#The edges from where sand can be collecyed from, will be an @problem_fact with graph_nodes ids and weight fields:
@optapy.problem_fact
class Edge:
    graph_from_node: str
    graph_to_node: str
    weight: int
    
    def __init__(self, graph_from_node: str, graph_to_node: str, weight: int):
        self.graph_from_node = graph_from_node
        self.graph_to_node = graph_to_node
        self.weight = weight
    

#The @planning_entity is a vehicle, with a fixed depot and carrying capacity, and a @planning_list_variable of Edge:
@optapy.planning_entity
class Vehicle:
    idx : int
    capacity: int
    depot: str
    visited_edges_list: List[Edge]

    def __init__(self, capacity: int, depot: str, visited_edges_list=None):
        self.capacity = capacity
        self.depot = depot
        self.visited_edges_list = [] if visited_edges_list is None else visited_edges_list

    @optapy.planning_list_variable(Edge, ['edge_range'])
    def get_visited_edges_list(self):
        return self.visited_edges_list

    def set_visited_edges_list(self, visited_edges_list):
        return self.visited_edges_list
    
#There would be a NetworkInfo @problem_fact, which can be used to query dumping zones and get the full network:
@optapy.problem_fact
class NetworkInfo:
    graph: Graph
    dumping_zones: List[str]

    def __init__(self, graph: Graph, dumping_zones: List[str]):
        self.graph = graph
        self.dumping_zones = dumping_zones
        
#The @planning_solution would store the NetworkInfo, Edge, Vehicle and the solution's score:
@optapy.planning_solution
class VRPSolution:
    def __init__(self, network_info: NetworkInfo, vehicle_list: List[Vehicle], edge_list: List[Edge], score=None):
        self.network_info = network_info
        self.vehicle_list = vehicle_list
        self.edge_list = edge_list
        self.score = score
    
    @optapy.problem_fact_property(NetworkInfo)
    def get_network_info(self):
        return self.network_info

    @optapy.planning_entity_collection_property(Vehicle)
    def get_vehicle_list(self):
        return self.vehicle_list

    @optapy.problem_fact_collection_property(Edge)
    @optapy.value_range_provider('edge_range')
    def get_customer_list(self):
        return self.edge_list

    @optapy.planning_score(HardMediumSoftScore)
    def get_score(self):
        return self.score

    def set_score(self, score):
        self.score = score


def get_vehicle_total_weight(vehicle: Vehicle):
    total = 0
    for edge in vehicle.visited_edges_list:
        total += edge.weight
    return total
        
#Constraint to specify that the waste collected by the vehicle should not exceed the maximum carrying capacity for each vehicle
def over_capacity(constraint_factory: ConstraintFactory):
    return (
        constraint_factory.for_each(Vehicle)
             .filter(lambda vehicle: get_vehicle_total_weight(vehicle) > vehicle.capacity)
             .penalize('Over Capacity', HardMediumSoftScore.ONE_HARD,
                       lambda vehicle: get_vehicle_total_weight(vehicle) - vehicle.capacity)
    )

#Constraint to specify that the priority for a vehilce is to clear the maximum waste.
def maximize_waste_collection(constraint_factory: ConstraintFactory):
    return (
        constraint_factory.for_each(Vehicle)
             .reward('maximize weight', HardMediumSoftScore.ONE_SOFT, lambda vehicle: get_vehicle_total_weight(vehicle))
    )

#Constraint to specify that the vehicle travel distance is minimized
def get_vehicle_path_total_distance(vehicle: Vehicle, network_info: NetworkInfo):
    current_node = vehicle.depot
    total = 0
    G = network_info.graph
    for edge in vehicle.visited_edges_list:
        total += nx.shortest_path_length(G, source=current_node, target=edge.graph_from_node)
        current_node = edge.graph_to_node
    shortest_path_length_from_current = nx.shortest_path_length(G, source=current_node)
    best_dumping_zone = None
    best_dumping_zone_path_length = 999999999999.999
    for dumping_zone in network_info.dumping_zones:
        if shortest_path_length_from_current[dumping_zone] < best_dumping_zone_path_length:
              best_dumping_zone_path_length = shortest_path_length_from_current[dumping_zone]
              best_dumping_zone = dumping_zone
    total += best_dumping_zone_path_length
    total += nx.shortest_path_length(G, source=best_dumping_zone, target=vehicle.depot)
    return total
        
#Constraint to specify that the vehicle travel distance is minimized
def minimize_distance(constraint_factory: ConstraintFactory):
    return (
        constraint_factory.for_each(Vehicle)
             .join(NetworkInfo)
             .penalize('Minimize Distance', HardMediumSoftScore.ONE_SOFT, get_vehicle_path_total_distance)
    )

#Constraint to specify that vehicles should only travel between adjacent nodes.
def is_invalid_path(vehicle: Vehicle):
    current = vehicle.depot
    for edge in vehicle.visited_edges_list:
        if edge.graph_from_node != current: 
            return True
        current = edge.graph_to_node
    return False
    
#Constraint to specify that vehicles should only travel between adjacent nodes.
def force_adjacent_nodes(constraint_factory: ConstraintFactory):
    return(
        constraint_factory.for_each(Vehicle)
        .filter(lambda vehicle: is_invalid_path(vehicle))
        .penalize('invalid path', HardMediumSoftScore.ONE_HARD)
        )

@optapy.constraint_provider
def vehicle_routing_constraints(constraint_factory: ConstraintFactory):
    return [
        force_adjacent_nodes(constraint_factory),
        over_capacity(constraint_factory),
        minimize_distance(constraint_factory),
        #maximize_waste_collection(constraint_factory),
    ]


#Configurations

#Configure Dumping Zones
dumping_zones_list = ['F', 'AQ', 'AA']

#Configure Graph
G, pos = create_graph_network(nodes_list, weights)
node_list = list(G.nodes())
NetworkInfo_obj = NetworkInfo(G, dumping_zones_list)

#Configure Vehicles and their corresponding capacitites and depots
v1 = Vehicle(25, 'AS')
v2 = Vehicle(25,'AS')
v3 = Vehicle(25, 'A')
v4 = Vehicle(25, 'A')
v5 = Vehicle(25, 'R')
v6 = Vehicle(25, 'R')

# v1 = Vehicle(75, 'AS')
# v2 = Vehicle(75,'A')

#veh_list = [v1, v2, v4, v5, v7, v10, v11, v12]
veh_list = [v1, v2, v3, v4, v5, v6]

e1 = Edge('A', 'B', 1)
e2 = Edge('B', 'C', 2)
e3 = Edge('C', 'D', 5)
e4 = Edge('C', 'AD', 1)
e5 = Edge('D', 'E', 7)
e6 = Edge('E', 'F', 4)
e7 = Edge('E', 'AX', 1)
e8 = Edge('F', 'G', 1)
e9 = Edge('G', 'H', 1)
e10 = Edge('G', 'U', 8)
e11 = Edge('H', 'I', 1)
e12 = Edge('I', 'J', 1)
e13 = Edge('J', 'K', 1)
e14 = Edge('J', 'P', 1)
e15 = Edge('K', 'L', 1)
e16 = Edge('L', 'M', 1)
e17 = Edge('L', 'N', 1)
e18 = Edge('N', 'O', 1)
e19 = Edge('O', 'P', 1)
e20 = Edge('P', 'Q', 1)
e21 = Edge('Q', 'R', 1)
e22 = Edge('Q', 'S', 1)
e23 = Edge('S', 'T', 1)
e24 = Edge('U', 'V', 9)
e25 = Edge('V', 'W', 1)
e26 = Edge('V', 'AU', 1)
e27 = Edge('W', 'X', 1)
e28 = Edge('X', 'Y', 1)
e29 = Edge('X', 'AB', 1)
e30 = Edge('Y', 'Z', 1)
e31 = Edge('Z', 'AA', 1)
e32 = Edge('AB', 'AC', 1)
e33 = Edge('AD', 'AE', 1)
e34 = Edge('AE', 'AF', 10)
e35 = Edge('AF', 'AG', 15)
e36 = Edge('AG', 'AH', 1)
e37 = Edge('AH', 'AI', 1)
e38 = Edge('AH', 'AK', 1)
e39 = Edge('AI', 'AJ', 1)
e40 = Edge('AK', 'AL', 3)
e41 = Edge('AL', 'AM', 1)
e42 = Edge('AM', 'AN', 3)
e43 = Edge('AM', 'AV', 1)
e44 = Edge('AN', 'AO', 1)
e45 = Edge('AN', 'AQ', 1)
e46 = Edge('AO', 'AP', 1)
e47 = Edge('AQ', 'AR', 1)
e48 = Edge('AR', 'AS', 1)
e49 = Edge('AT', 'AV', 1)
e50 = Edge('AT', 'AU', 1)
e51 = Edge('AV', 'AW', 4)
e52 = Edge('AW', 'AX', 6)

edge_list = [e1, e2, e3, e4, e5, e6, e7, e8, e9, e10, e11, e12, e13, e14, e15, e16, e17, e18, e19, e20, e21, 
              e22, e23, e24, e25, e26, e27, e28, e29, e30, e31, e32, e33, e34, e35, e36, e37, e38, e39, e40, 
              e41, e42, e43, e44, e45, e46, e47, e48, e49, e50, e51, e52]


# edge_list = [e1, e2, e3, e4, e5, e6, e7, e8, e9, e10, e11]

problem = VRPSolution(NetworkInfo_obj, veh_list, edge_list)

#Print the solution
#timeout = 36000
timeout = 1800
solver_config = optapy.config.solver.SolverConfig()
solver_config.withSolutionClass(VRPSolution).withEntityClasses(Vehicle).withConstraintProviderClass(vehicle_routing_constraints).withTerminationSpentLimit(Duration.ofSeconds(timeout))

all_edges = list(G.edges())
total_weights = []

for edge in all_edges:
    total_weights.append(G.get_edge_data(edge[0], edge[1])['weight'])
        
total_weights = sum(total_weights)
print("Total Volume of Waste: ", total_weights)


total_capacity_of_vehicles = sum([v.capacity for v in veh_list])

if total_capacity_of_vehicles < total_weights:
    print("Solution is not feasible. Please assign more vehicles or more carrying capacity")
else:
    solution = solver_factory_create(solver_config).buildSolver().solve(problem)
    
    print("Final Score --------------------------- ")
    print(solution.get_score())
    
    
#OUTPUT

vehicle_visited_edges = []
vehicle_visited_nodes = []
vehicle_predicted_route = []

ctr = 1
for vehicle in solution.get_vehicle_list():
    print("Vehicle : ", ctr)
    ctr += 1
    print("Depot : ", vehicle.depot)
    print("Vehicle Capacity : ", vehicle.capacity)

    edges  = vehicle.visited_edges_list
    
    route_path = []
    total_weight = []
    edge_list = []
    visited_node_list = []

    
    for edge in edges:
        print("Edge : ({},{}), Weight : {}".format(edge.graph_from_node, edge.graph_to_node, edge.weight))
        edge_list.append(("{}".format(edge.graph_from_node), "{}".format(edge.graph_to_node)))
        visited_node_list.append(edge.graph_from_node)
        visited_node_list.append(edge.graph_to_node)
        total_weight.append(edge.weight)
        
    print("Visited Edges : ", edge_list)
    print("Visited Nodes : ", visited_node_list)
        
    visited_node_list = list(set(visited_node_list))
    veh_depot = vehicle.depot
    path_dict = dict()
    
    for d_zone in dumping_zones_list:
        all_paths = nx.all_simple_paths(G, veh_depot, d_zone)
        for p in list(all_paths):
            ctr_ele = 0
            for ele in visited_node_list:
                if(ele in p):
                    ctr_ele += 1
            
            path_dict[ctr_ele] = p
        
    predicted_route = path_dict[max(path_dict.keys())]
    vehicle_visited_edges.append(edge_list)
    vehicle_visited_nodes.append(visited_node_list)
    vehicle_predicted_route.append(predicted_route)

    print("Vehicle Route : ", predicted_route)
    print("Total Weight of Collected Waste : ", sum(total_weight))
    print()
    
    
vehicle_num = 2

#Run the below two blocks separately

#BLOCK 1 : Display all the visited edges by the vehicle
visited_nodes = vehicle_visited_nodes[vehicle_num-1]
visited_edges = vehicle_visited_edges[vehicle_num-1]
pos=nx.spring_layout(G, seed=random_seed)
nx.draw(G,pos,with_labels = True)
nx.draw_networkx_nodes(G,pos,nodelist=visited_nodes,node_color='g')
nx.draw_networkx_edges(G,pos,edgelist=visited_edges,edge_color='r',width=3)

#BLOCK 2 : Display the predicted route for a vehicle
pos=nx.spring_layout(G, seed=random_seed)
nx.draw(G,pos,with_labels = True)
predicted_route = vehicle_predicted_route[vehicle_num-1]
nx.draw_networkx_nodes(G,pos,nodelist=predicted_route,node_color='g')

OUTPUT :

Vehicle :  1
Depot :  AJ
Vehicle Capacity :  25
Edge : AI-AJ, Weight : 1
Edge : AH-AI, Weight : 1
Edge : AF-AG, Weight : 15
Edge : AG-AH, Weight : 1
Edge : AH-AK, Weight : 1
Edge : AK-AL, Weight : 3
Edge : AL-AM, Weight : 1
Edge : AN-AO, Weight : 1
Edge : AO-AP, Weight : 1
Edge : AN-AQ, Weight : 1
Edge : AQ-AR, Weight : 1
Edge : AR-AS, Weight : 1
Vehicle Route :  ['AI', 'AH', 'AF', 'AG', 'AH', 'AK', 'AL', 'AN', 'AO', 'AN', 'AQ', 'AR']
Total Weight of Collected Waste :  28

Vehicle :  2
Depot :  A
Vehicle Capacity :  15
Edge : A-B, Weight : 1
Edge : B-C, Weight : 2
Edge : C-D, Weight : 5
Edge : D-E, Weight : 7
Vehicle Route :  ['A', 'B', 'C', 'D']
Total Weight of Collected Waste :  15

Vehicle :  3
Depot :  R
Vehicle Capacity :  10
Edge : J-K, Weight : 1
Edge : I-J, Weight : 1
Edge : H-I, Weight : 1
Edge : G-H, Weight : 1
Edge : F-G, Weight : 1
Edge : E-AX, Weight : 1
Edge : E-F, Weight : 4
Vehicle Route :  ['J', 'I', 'H', 'G', 'F', 'E', 'E']
Total Weight of Collected Waste :  10

Vehicle :  4
Depot :  R
Vehicle Capacity :  50
Edge : Q-S, Weight : 1
Edge : S-T, Weight : 1
Edge : Q-R, Weight : 1
Edge : C-AD, Weight : 1
Edge : P-Q, Weight : 1
Edge : O-P, Weight : 1
Edge : K-L, Weight : 1
Edge : L-N, Weight : 1
Edge : N-O, Weight : 1
Edge : L-M, Weight : 1
Edge : J-P, Weight : 1
Edge : G-U, Weight : 8
Edge : U-V, Weight : 9
Edge : W-X, Weight : 1
Edge : X-AB, Weight : 1
Edge : AB-AC, Weight : 1
Edge : X-Y, Weight : 1
Edge : Y-Z, Weight : 1
Edge : Z-AA, Weight : 1
Edge : V-AU, Weight : 1
Edge : AT-AU, Weight : 1
Edge : V-W, Weight : 1
Edge : AT-AV, Weight : 1
Edge : AM-AN, Weight : 3
Edge : AM-AV, Weight : 1
Edge : AV-AW, Weight : 4
Edge : AW-AX, Weight : 6
Edge : AD-AE, Weight : 1
Edge : AE-AF, Weight : 10
Vehicle Route :  ['Q', 'S', 'Q', 'C', 'P', 'O', 'K', 'L', 'N', 'L', 'J', 'G', 'U', 'W', 'X', 'AB', 'X', 'Y', 'Z', 'V', 'AT', 'V', 'AT', 'AM', 'AM', 'AV', 'AW', 'AD', 'AE']
Total Weight of Collected Waste :  63

If you look at the above outputs,

For Vehicle 1, I have assigned a maximum carrying capacity of 25 units. So that means as soon as the vehicle capacity is reached, it should not collect any further waste. But in this case, Vehicle 1 is collecting 28 units of waste (where it's defined capacity is 25 units). I have added the over_capacity constraint according to your suggestion, to handle this scenario. However, the total waste collected by the vehicle is exceeding it's carrying capacity. Same happens for Vehicle 4, the total capacity of the vehicle is 50, however it is seen to collect 63 units of waste.

1. What changes do I need to perform, to make sure that the total waste collected by the vehicle strictly doesn't exceed it's carrying capacity?

2. Is there any way to prioritize the order of the usage of constraints? For example, if I have a choice between minimizing the distance travelled by vehicle versus maximizing the amount of waste clearance (even if the distance is more), how do I prioritize the constraints so that the vehicle decides to pick up more waste rather than minimizing the distance? A workaround may be to use one constraint and not use the other. But if we want to use both the constraints and want to prioritize one over the other, how do we deal with it?

3. If you look at the outputs for Vehicle 4, the start depot is R, but the first edge visited by the vehicle is given as Q-S, then S-T, and then Q-R and so on. But if you look at the NetworkX graph, if the vehicle starts from Node R, then the first visited edge will have to be Q-R (or R-Q). In our case, Q-R is the 3rd edge that the vehicle is visiting. How can we make sure that from depot R, the first edge that the vehicle need to travel through is Q-R before it traverses the later edges? To put more context, let's say R-Q doesn't have any weights, but Q-P has a weight, the vehicle will definitely visit Q-P to pickup the weights but it cannot directly go to Q-P from R, before that it should pass through R-Q. So the ideal route in this case, if the vehicle starts from depot R will be R-Q-P. How can I model this constraint and what changes do I need to perform to ensure that vehicles can only travel to adjacent nodes or adjacent edges?

4. Also how can we prioritize the edges? For example, consider this scenario, a vehicle starts from Node A, it can either take the path A-B-C-D-E-.. or it can take another path A-B-C-AD-AE. Let's say decide to give higher priority to edge D-E over edge AD-AE, so the vehicle will be forced to clear the waste in the route A-B-C-D-E than A-B-C-AD-AE, even if A-B-C-AD-AE has more waste accumulation than A-B-C-D-E.

UPDATE: Output for a different iteration.

Vehicle :  6
Depot :  R
Vehicle Capacity :  25
Edge : (AN,AQ), Weight : 1
Edge : (Q,R), Weight : 1
Edge : (N,O), Weight : 1
Edge : (AM,AN), Weight : 3
Edge : (C,AD), Weight : 1
Edge : (V,AU), Weight : 1
Edge : (AM,AV), Weight : 1
Edge : (AN,AO), Weight : 1
Edge : (AB,AC), Weight : 1
Edge : (G,U), Weight : 8
Edge : (AH,AK), Weight : 1
Edge : (I,J), Weight : 1
Edge : (AR,AS), Weight : 1
Edge : (S,T), Weight : 1
Edge : (Q,S), Weight : 1
Visited Edges :  [('AN', 'AQ'), ('Q', 'R'), ('N', 'O'), ('AM', 'AN'), ('C', 'AD'), ('V', 'AU'), ('AM', 'AV'), ('AN', 'AO'), ('AB', 'AC'), ('G', 'U'), ('AH', 'AK'), ('I', 'J'), ('AR', 'AS'), ('S', 'T'), ('Q', 'S')]
Visited Nodes :  ['AN', 'AQ', 'Q', 'R', 'N', 'O', 'AM', 'AN', 'C', 'AD', 'V', 'AU', 'AM', 'AV', 'AN', 'AO', 'AB', 'AC', 'G', 'U', 'AH', 'AK', 'I', 'J', 'AR', 'AS', 'S', 'T', 'Q', 'S']
Vehicle Route :  ['R', 'Q', 'P', 'O', 'N', 'L', 'K', 'J', 'I', 'H', 'G', 'U', 'V', 'AU', 'AT', 'AV', 'AW', 'AX', 'E', 'D', 'C', 'AD', 'AE', 'AF', 'AG', 'AH', 'AK', 'AL', 'AM', 'AN', 'AQ']
Total Weight of Collected Waste :  24

If you look at the above outputs, you will see that the visited edges by vehicle 6 are not adjacent to each other. What might be possibly wrong in the implementation? Because, since it's a graph network, it's assumed that the vehicle will traverse node by node. ar travel only through adjacent nodes.

EDIT : 10th Jan, 2023.

I have executed the latest code present at this GIST, and I am analyzing the output with the below code. I am not sure if I am interpreting the results correctly or not using the below piece of code. Can you let me know if I am following the right way to get the results? If not, what changes would you suggest to make in the code?

ctr = 1    
for vehicle in solution.get_vehicle_list():
    print("Vehicle : ", ctr)
    ctr += 1
    print("Depot : ", vehicle.depot)
    print("Vehicle Capacity : ", vehicle.capacity)
    print("Visited Edge List : ", vehicle.visited_edges_list)
    print()    

OUTPUT :

Final Score --------------------------- 
0hard/83medium/-250soft
Vehicle :  1
Depot :  AS
Vehicle Capacity :  25
Visited Edge List :  ['F', 'E', 'D', 'C', 'AD']

Vehicle :  2
Depot :  AS
Vehicle Capacity :  25
Visited Edge List :  ['T', 'S', 'AA', 'K']

Vehicle :  3
Depot :  A
Vehicle Capacity :  25
Visited Edge List :  ['AE', 'AF', 'AG']

Vehicle :  4
Depot :  A
Vehicle Capacity :  25
Visited Edge List :  ['B', 'A', 'AI', 'AJ', 'AX', 'AW', 'AV', 'AT']

Vehicle :  5
Depot :  R
Vehicle Capacity :  25
Visited Edge List :  ['G', 'U', 'V', 'AU']

Vehicle :  6
Depot :  R
Vehicle Capacity :  25
Visited Edge List :  ['Q', 'R', 'J', 'I', 'H', 'AR', 'AQ', 'AN', 'AM', 'AL', 'AK', 'AH', 'AO', 'AP', 'W', 'X', 'AB', 'AC', 'Z', 'Y', 'P', 'O', 'N', 'L', 'M', 'AS']

If you look at the above outputs for all the vehicles, the nodes are not ordered yet. Attaching the visited nodes for Vehicle 4 & 6 below for your reference.

Questions :

1. Based on your experience, is 60 seconds enough for solving this particular instance of the Graph with 50 nodes? Based on the complexity of this problem, any guesstimate?

2. What changes would you suggest on top of your gist, so that for every vehicle, it will move only across adjacent nodes?

3. If you look at the outputs, for each depot, none of the vehicle starts from that particular depot. Same with vehicle 4 and 6 as well if you look at the diagrams. What would you recommend in this scenario?

Answer 3

How can I visualize the solution? For example, I have used the below code to solve the problem, but is there any way we can visualize the results. The output results should contain the path for the optimal vehicle routes and the volume of sand that is cleared in the path.

Expected Output:

Vehicle 1 Route: A - B - C - D - E - F
Vehicle 1 Waste cleared : 16 Units

Vehicle 2 Route: AS - AJ - AH - AK - AL - AM - AW - AQ
Vehicle 2 Waste cleared : 3 Units

from optapy.types import Duration
from optapy import solver_factory_create

solver_config = optapy.config.solver.SolverConfig()
solver_config.withSolutionClass(VRPSolution).withEntityClasses(Vehicle).withConstraintProviderClass(vehicle_routing_constraints).withTerminationSpentLimit(Duration.ofSeconds(30))
solution = solver_factory_create(solver_config).buildSolver().solve(problem)
print(solution)

ctr = 1
for vehicle in solution.get_vehicle_list():
    print("Vehicle : ", ctr)
    ctr += 1
    print("Depot : ", vehicle.depot)
    print("Vehicle Capacity : ", vehicle.capacity)
    edges  = vehicle.visited_edges_list
    
    route_path = []
    total_weight = []
    
    for edge in edges:
        print("Edge : {}-{}, Weight : {}".format(edge.graph_from_node, edge.graph_to_node, edge.weight))     
        route_path.append(edge.graph_from_node)
        total_weight.append(edge.weight)

    print("Vehicle Route : ", route_path)
    print("Total Weight of Collected Waste : ", sum(total_weight))
    print()

Output :

Vehicle :  1
Depot :  AJ
Vehicle Capacity :  15
Edge : AI-AJ, Weight : 1
Edge : AK-AL, Weight : 3
Edge : AL-AM, Weight : 1
Edge : AM-AN, Weight : 3
Edge : AN-AQ, Weight : 1
Edge : AR-AS, Weight : 1
Edge : AM-AV, Weight : 1
Edge : AT-AU, Weight : 1
Edge : V-W, Weight : 1
Edge : W-X, Weight : 1
Edge : AB-AC, Weight : 1
Edge : X-Y, Weight : 1
Edge : Y-Z, Weight : 1
Edge : Z-AA, Weight : 1
Edge : X-AB, Weight : 1
Edge : V-AU, Weight : 1
Edge : AT-AV, Weight : 1
Vehilce Route :  ['AI', 'AK', 'AL', 'AM', 'AN', 'AR', 'AM', 'AT', 'V', 'W', 'AB', 'X', 'Y', 'Z', 'X', 'V', 'AT']
Total Weight of Collected Waste :  21

Vehicle :  2
Depot :  AJ
Vehicle Capacity :  10
Edge : AF-AG, Weight : 15
Edge : AN-AO, Weight : 1
Vehilce Route :  ['AF', 'AN']
Total Weight of Collected Waste :  16

Vehicle :  3
Depot :  A
Vehicle Capacity :  7
Edge : A-B, Weight : 1
Edge : C-AD, Weight : 1
Edge : C-D, Weight : 5
Vehilce Route :  ['A', 'C', 'C']
Total Weight of Collected Waste :  7

Vehicle :  4
Depot :  A
Vehicle Capacity :  15
Edge : B-C, Weight : 2
Edge : AE-AF, Weight : 10
Edge : AD-AE, Weight : 1
Edge : AG-AH, Weight : 1
Edge : AH-AI, Weight : 1
Edge : AH-AK, Weight : 1
Edge : AO-AP, Weight : 1
Edge : AQ-AR, Weight : 1
Edge : AV-AW, Weight : 4
Vehilce Route :  ['B', 'AE', 'AD', 'AG', 'AH', 'AH', 'AO', 'AQ', 'AV']
Total Weight of Collected Waste :  22

Vehicle :  5
Depot :  G
Vehicle Capacity :  10
Edge : D-E, Weight : 7
Edge : AW-AX, Weight : 6
Edge : E-AX, Weight : 1
Edge : F-G, Weight : 1
Vehilce Route :  ['D', 'AW', 'E', 'F']
Total Weight of Collected Waste :  15

Vehicle :  6
Depot :  R
Vehicle Capacity :  5
Edge : P-Q, Weight : 1
Edge : E-F, Weight : 4
Vehilce Route :  ['P', 'E']
Total Weight of Collected Waste :  5

Vehicle :  7
Depot :  R
Vehicle Capacity :  15
Edge : I-J, Weight : 1
Edge : J-K, Weight : 1
Edge : K-L, Weight : 1
Edge : L-M, Weight : 1
Edge : L-N, Weight : 1
Edge : N-O, Weight : 1
Edge : J-P, Weight : 1
Edge : U-V, Weight : 9
Vehilce Route :  ['I', 'J', 'K', 'L', 'L', 'N', 'J', 'U']
Total Weight of Collected Waste :  16

Vehicle :  8
Depot :  R
Vehicle Capacity :  10
Edge : Q-R, Weight : 1
Edge : Q-S, Weight : 1
Edge : S-T, Weight : 1
Edge : O-P, Weight : 1
Edge : G-U, Weight : 8
Edge : G-H, Weight : 1
Edge : H-I, Weight : 1
Vehilce Route :  ['Q', 'Q', 'S', 'O', 'G', 'G', 'H']
Total Weight of Collected Waste :  14

Here, if you look at the solution for each vehicle, we get the list of edges visited by those vehicles, if we take an example of Vehicle 8, the vehicle should start from Node R (which is the depot), the vehicle will visit these edges -- Q-R, Q-S, S-T, O-P, G-U, G-H, H-I. But what I am looking for is the optimal path of each vehicle such that they cover all the list of visited edges. Is there any other way, we should model the problem to get the exact routes?

Also, is there any way to model the problem in a way, in which the vehicle will start from Node R, collect all the waste till it's capacity has reached, and then it will go to the dumping zone to drop the waste?

Let's stay, a vehicle starts from Node R. Based on the waste accumulation, let's say it traverses this path -- R - Q - O - N - L - K - J. Let's say that at Node J, the vehicle capacity will max out, then it should check from J which is the nearest dumping zone. The vehicle will see that F is the nearest dumping zone, so it will go to F, dump the waste and re-start it's operation from F. Let's say from F, the vehicle takes another path -- F - G - U - V - W - X. Let's say that the same vehicles capacity is maxied out at X. Then it will see thay the nearest dumping zone from Z is AA, hence it will go there and dump the waste. Now if there's no longer waste left to be cleaned, the vehicle can get back to it's starting position which is R.

Can you kindly check if the implementation for point 4 is correct? I have created this function called force_adjacent_nodes() in which my primary goal is to ensure that vehicles will travel to their adjacent nodes only? For example, if a vehicle start from Node A, it can only travel to Node B and not Node C. If the vehicle has to go to Node C, it has to mandatorily pass through Node B. So the vehicle should only travel between nodes which has direct edge between them.

def is_invalid_path(vehicle: Vehicle):
    current = vehicle.depot
    for edge in vehicle.visited_edges_list:
        if edge.graph_from_node != current: 
            return True
        elif current == edge.graph_to_node:
            return False
    
def force_adjacent_nodes(constraint_factory: ConstraintFactory):
    return(
        constraint_factory.for_each(Vehicle)
        .filter(lambda vehicle: is_invalid_path(vehicle))
        .penalize('invalid path', HardSoftScore.ONE_HARD)
        )

@optapy.constraint_provider
def vehicle_routing_constraints(constraint_factory: ConstraintFactory):
    return [
        over_capacity(constraint_factory),
        minimize_distance(constraint_factory),
        maximize_weight(constraint_factory),
        force_adjacent_nodes(constraint_factory)
    ]

While implementing the above changes, I am getting below error:

RuntimeError: An error occurred during solving. This can occur when functions take the wrong number of parameters (ex: a setter that does not take exactly one parameter) or by a function returning an incompatible return type (ex: returning a str in a filter, which expects a bool). This can also occur when an exception is raised when evaluating constraints/getters/setters.

Wanted to check what am I missing or doing wrong from an implementation point of view? I can provide the updated code in a new answer section for your reference.