supermarket_opt.py

from ortools.sat.python import cp_model


# Problem Data
NODES = [
"start",
"end",
"safeway_10",
"birite_10",
"whole_foods_10",
"foods_co_10",
"gus_10",
"richmond_nmw_20",
"gross_out_20",
"tj_20",
"ms_20",
"safeway_20",
"lucky_30",
"safeway_30",
"lucky_dc_30",
"smart_and_final_30",
"tj_30",
"gross_out_40",
"lucky_40"
]  # Nodes in the graph

# Start and end nodes
S = 'start'  # Starting node
E = 'end'  # Ending node

t = {('start', 'end'): 19,
 ('start', 'safeway_10'): 18,
 ('start', 'birite_10'): 19,
 ('start', 'whole_foods_10'): 26,
 ('start', 'foods_co_10'): 17,
 ('start', 'gus_10'): 20,
 ('start', 'richmond_nmw_20'): 40,
 ('start', 'gross_out_20'): 48,
 ('start', 'tj_20'): 34,
 ('start', 'ms_20'): 28,
 ('start', 'safeway_20'): 48,
 ('start', 'lucky_30'): 59,
 ('start', 'safeway_30'): 49,
 ('start', 'lucky_dc_30'): 61,
 ('start', 'smart_and_final_30'): 61,
 ('start', 'tj_30'): 58,
 ('start', 'gross_out_40'): 75,
 ('start', 'lucky_40'): 73,
 ('end', 'safeway_10'): 34,
 ('end', 'birite_10'): 28,
 ('end', 'whole_foods_10'): 24,
 ('end', 'foods_co_10'): 15,
 ('end', 'gus_10'): 12,
 ('end', 'richmond_nmw_20'): 43,
 ('end', 'gross_out_20'): 50,
 ('end', 'tj_20'): 37,
 ('end', 'ms_20'): 32,
 ('end', 'safeway_20'): 34,
 ('end', 'lucky_30'): 43,
 ('end', 'safeway_30'): 40,
 ('end', 'lucky_dc_30'): 45,
 ('end', 'smart_and_final_30'): 44,
 ('end', 'tj_30'): 41,
 ('end', 'gross_out_40'): 59,
 ('end', 'lucky_40'): 60,
 ('safeway_10', 'birite_10'): 10,
 ('safeway_10', 'whole_foods_10'): 29,
 ('safeway_10', 'foods_co_10'): 25,
 ('safeway_10', 'gus_10'): 28,
 ('safeway_10', 'richmond_nmw_20'): 25,
 ('safeway_10', 'gross_out_20'): 32,
 ('safeway_10', 'tj_20'): 24,
 ('safeway_10', 'ms_20'): 14,
 ('safeway_10', 'safeway_20'): 55,
 ('safeway_10', 'lucky_30'): 56,
 ('safeway_10', 'safeway_30'): 52,
 ('safeway_10', 'lucky_dc_30'): 71,
 ('safeway_10', 'smart_and_final_30'): 71,
 ('safeway_10', 'tj_30'): 58,
 ('safeway_10', 'gross_out_40'): 85,
 ('safeway_10', 'lucky_40'): 93,
 ('birite_10', 'whole_foods_10'): 22,
 ('birite_10', 'foods_co_10'): 15,
 ('birite_10', 'gus_10'): 17,
 ('birite_10', 'richmond_nmw_20'): 23,
 ('birite_10', 'gross_out_20'): 32,
 ('birite_10', 'tj_20'): 21,
 ('birite_10', 'ms_20'): 10,
 ('birite_10', 'safeway_20'): 45,
 ('birite_10', 'lucky_30'): 54,
 ('birite_10', 'safeway_30'): 45,
 ('birite_10', 'lucky_dc_30'): 61,
 ('birite_10', 'smart_and_final_30'): 61,
 ('birite_10', 'tj_30'): 53,
 ('birite_10', 'gross_out_40'): 75,
 ('birite_10', 'lucky_40'): 84,
 ('whole_foods_10', 'foods_co_10'): 6,
 ('whole_foods_10', 'gus_10'): 9,
 ('whole_foods_10', 'richmond_nmw_20'): 22,
 ('whole_foods_10', 'gross_out_20'): 29,
 ('whole_foods_10', 'tj_20'): 19,
 ('whole_foods_10', 'ms_20'): 16,
 ('whole_foods_10', 'safeway_20'): 31,
 ('whole_foods_10', 'lucky_30'): 38,
 ('whole_foods_10', 'safeway_30'): 28,
 ('whole_foods_10', 'lucky_dc_30'): 47,
 ('whole_foods_10', 'smart_and_final_30'): 47,
 ('whole_foods_10', 'tj_30'): 38,
 ('whole_foods_10', 'gross_out_40'): 61,
 ('whole_foods_10', 'lucky_40'): 72,
 ('foods_co_10', 'gus_10'): 4,
 ('foods_co_10', 'richmond_nmw_20'): 33,
 ('foods_co_10', 'gross_out_20'): 41,
 ('foods_co_10', 'tj_20'): 27,
 ('foods_co_10', 'ms_20'): 23,
 ('foods_co_10', 'safeway_20'): 32,
 ('foods_co_10', 'lucky_30'): 45,
 ('foods_co_10', 'safeway_30'): 33,
 ('foods_co_10', 'lucky_dc_30'): 48,
 ('foods_co_10', 'smart_and_final_30'): 47,
 ('foods_co_10', 'tj_30'): 43,
 ('foods_co_10', 'gross_out_40'): 62,
 ('foods_co_10', 'lucky_40'): 72,
 ('gus_10', 'richmond_nmw_20'): 33,
 ('gus_10', 'gross_out_20'): 40,
 ('gus_10', 'tj_20'): 29,
 ('gus_10', 'ms_20'): 23,
 ('gus_10', 'safeway_20'): 31,
 ('gus_10', 'lucky_30'): 43,
 ('gus_10', 'safeway_30'): 32,
 ('gus_10', 'lucky_dc_30'): 46,
 ('gus_10', 'smart_and_final_30'): 46,
 ('gus_10', 'tj_30'): 41,
 ('gus_10', 'gross_out_40'): 60,
 ('gus_10', 'lucky_40'): 68,
 ('richmond_nmw_20', 'gross_out_20'): 9,
 ('richmond_nmw_20', 'tj_20'): 12,
 ('richmond_nmw_20', 'ms_20'): 14,
 ('richmond_nmw_20', 'safeway_20'): 36,
 ('richmond_nmw_20', 'lucky_30'): 32,
 ('richmond_nmw_20', 'safeway_30'): 35,
 ('richmond_nmw_20', 'lucky_dc_30'): 52,
 ('richmond_nmw_20', 'smart_and_final_30'): 55,
 ('richmond_nmw_20', 'tj_30'): 34,
 ('richmond_nmw_20', 'gross_out_40'): 65,
 ('richmond_nmw_20', 'lucky_40'): 82,
 ('gross_out_20', 'tj_20'): 17,
 ('gross_out_20', 'ms_20'): 20,
 ('gross_out_20', 'safeway_20'): 42,
 ('gross_out_20', 'lucky_30'): 26,
 ('gross_out_20', 'safeway_30'): 40,
 ('gross_out_20', 'lucky_dc_30'): 55,
 ('gross_out_20', 'smart_and_final_30'): 56,
 ('gross_out_20', 'tj_30'): 32,
 ('gross_out_20', 'gross_out_40'): 64,
 ('gross_out_20', 'lucky_40'): 81,
 ('tj_20', 'ms_20'): 10,
 ('tj_20', 'safeway_20'): 37,
 ('tj_20', 'lucky_30'): 36,
 ('tj_20', 'safeway_30'): 31,
 ('tj_20', 'lucky_dc_30'): 54,
 ('tj_20', 'smart_and_final_30'): 56,
 ('tj_20', 'tj_30'): 35,
 ('tj_20', 'gross_out_40'): 66,
 ('tj_20', 'lucky_40'): 84,
 ('ms_20', 'safeway_20'): 44,
 ('ms_20', 'lucky_30'): 44,
 ('ms_20', 'safeway_30'): 39,
 ('ms_20', 'lucky_dc_30'): 59,
 ('ms_20', 'smart_and_final_30'): 59,
 ('ms_20', 'tj_30'): 43,
 ('ms_20', 'gross_out_40'): 73,
 ('ms_20', 'lucky_40'): 84,
 ('safeway_20', 'lucky_30'): 17,
 ('safeway_20', 'safeway_30'): 19,
 ('safeway_20', 'lucky_dc_30'): 26,
 ('safeway_20', 'smart_and_final_30'): 28,
 ('safeway_20', 'tj_30'): 15,
 ('safeway_20', 'gross_out_40'): 40,
 ('safeway_20', 'lucky_40'): 54,
 ('lucky_30', 'safeway_30'): 29,
 ('lucky_30', 'lucky_dc_30'): 27,
 ('lucky_30', 'smart_and_final_30'): 30,
 ('lucky_30', 'tj_30'): 7,
 ('lucky_30', 'gross_out_40'): 38,
 ('lucky_30', 'lucky_40'): 56,
 ('safeway_30', 'lucky_dc_30'): 33,
 ('safeway_30', 'smart_and_final_30'): 33,
 ('safeway_30', 'tj_30'): 19,
 ('safeway_30', 'gross_out_40'): 47,
 ('safeway_30', 'lucky_40'): 58,
 ('lucky_dc_30', 'safeway_30'): 41,
 ('smart_and_final_30', 'safeway_30'): 43,
 ('tj_30', 'safeway_30'): 26,
 ('gross_out_40', 'safeway_30'): 64,
 ('lucky_40', 'safeway_30'): 79,
 ('lucky_dc_30', 'smart_and_final_30'): 4,
 ('lucky_dc_30', 'tj_30'): 20,
 ('lucky_dc_30', 'gross_out_40'): 18,
 ('lucky_dc_30', 'lucky_40'): 33,
 ('smart_and_final_30', 'tj_30'): 22,
 ('smart_and_final_30', 'gross_out_40'): 17,
 ('smart_and_final_30', 'lucky_40'): 31,
 ('tj_30', 'gross_out_40'): 36,
 ('tj_30', 'lucky_40'): 53,
 ('gross_out_40', 'lucky_40'): 17}

# Add flipped pairs if they don't exist
for (loc1, loc2), time in list(t.items()):
    if (loc2, loc1) not in t:
        t[(loc2, loc1)] = time

# Now strip out any edges STARTING from end
t = {k: v for k, v in t.items() if k[0] != 'end'}
# Also trim edges ending at START
t = {k: v for k, v in t.items() if k[1] != 'start'}
print(t)

# Google maps time is slow. speed it up
TIME_MULTIPLIER = 0.8
t = {k: round(v * TIME_MULTIPLIER) for k, v in t.items()}

EDGES = list(t.keys())
M = 5 # default value
# node_times = {'start': 0, 'end': 0}
# for node in NODES:
#     if node not in node_times:
#         node_times[node] = MINUTES_PER_NODE
# # Special case for foods_co_10
# node_times['foods_co_10'] = 10

P = {
"safeway_10": 10,
"birite_10": 10,
"whole_foods_10": 10,
"foods_co_10": 10,
"gus_10": 10,
"richmond_nmw_20": 20,
"gross_out_20": 20,
"tj_20": 20,
"ms_20": 20,
"safeway_20": 20,
"lucky_30": 30,
"safeway_30": 30,
"lucky_dc_30": 30,
"smart_and_final_30": 30,
"tj_30": 30,
"gross_out_40": 40,
"lucky_40": 40,
}
VOLUME_PER_NODE = 1
volumes = {
"safeway_10": VOLUME_PER_NODE,
"birite_10": VOLUME_PER_NODE,
"whole_foods_10": VOLUME_PER_NODE,
"foods_co_10": VOLUME_PER_NODE,
"gus_10": VOLUME_PER_NODE,
"richmond_nmw_20": VOLUME_PER_NODE,
"gross_out_20": VOLUME_PER_NODE,
"tj_20": VOLUME_PER_NODE,
"ms_20": VOLUME_PER_NODE,
"safeway_20": VOLUME_PER_NODE,
"lucky_30": VOLUME_PER_NODE,
"safeway_30": VOLUME_PER_NODE,
"lucky_dc_30": VOLUME_PER_NODE,
"smart_and_final_30": VOLUME_PER_NODE,
"tj_30": VOLUME_PER_NODE,
"gross_out_40": VOLUME_PER_NODE,
"lucky_40": VOLUME_PER_NODE,
}
Time_limit = 240  # Maximum total time budget in min
V_max = 100000  # Maximum bag volume


# Create the model
model = cp_model.CpModel()

# Variables

# Binary variables x_{ij} for edges
x = {}
for (i, j) in EDGES:
    x[(i, j)] = model.NewBoolVar(f'x_{i}_{j}')

# Binary variables y_i for nodes (excluding start and end nodes)
nodes_without_SE = [i for i in NODES if i not in [S, E]]
y = {}
for i in nodes_without_SE:
    y[i] = model.NewBoolVar(f'y_{i}')

# Arrival times s_i at nodes (integer variables)
s = {}
for i in NODES:
    s[i] = model.NewIntVar(0, Time_limit, f's_{i}')

# Objective function: Maximize total points collected
model.Maximize(sum(P[i] * y[i] for i in nodes_without_SE))

# Constraints

# Flow conservation constraints
for i in NODES:
    if i == S:
        # Exactly one outgoing edge from the start node
        model.Add(sum(x[(i, j)] for j in NODES if (i, j) in EDGES) == 1)
    elif i == E:
        # Exactly one incoming edge to the end node
        model.Add(sum(x[(j, i)] for j in NODES if (j, i) in EDGES) == 1)
    else:
        # If node is visited, flow in equals flow out
        model.Add(
            sum(x[(j, i)] for j in NODES if (j, i) in EDGES) ==
            y[i]
        )
        model.Add(
            sum(x[(i, j)] for j in NODES if (i, j) in EDGES) ==
            y[i]
        )

# Time constraints
BigM = Time_limit + max(t.values()) + M  # Big M for time constraints
for (i, j) in EDGES:
    # s_j >= s_i + t_{ij} + M - BigM * (1 - x_{ij})
    model.Add(s[j] >= s[i] + t[(i, j)] + M - BigM * (1 - x[(i, j)]))

# Time limit constraint
model.Add(s[E] <= Time_limit)

# Arrival time at start node
model.Add(s[S] == 0)

# Volume constraint
model.Add(sum(volumes[i] * y[i] for i in nodes_without_SE) <= V_max)

# Subtour elimination constraints (MTZ constraints)
u = {}
for i in NODES:
    u[i] = model.NewIntVar(0, len(NODES), f'u_{i}')

for (i, j) in EDGES:
    if i != S and j != S and i != E and j != E:
        model.Add(u[i] - u[j] + (len(NODES)) * x[(i, j)] <= len(NODES) - 1)


# Custom solution callback
class RouteSolutionPrinter(cp_model.CpSolverSolutionCallback):
    def __init__(self, x_vars, y_vars, s_vars, NODES, EDGES, nodes_without_SE, P, volumes):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self.x_vars = x_vars
        self.y_vars = y_vars
        self.s_vars = s_vars
        self.NODES = NODES
        self.EDGES = EDGES
        self.nodes_without_SE = nodes_without_SE
        self.P = P
        self.volumes = volumes
        self.best_objective = float('-inf')
    
    def OnSolutionCallback(self):
        current_objective = self.ObjectiveValue()
        if current_objective > self.best_objective:
            self.best_objective = current_objective
            print(f"\nNew solution found with objective value: {current_objective}\n")
            print("Route:")
            for (i, j) in self.EDGES:
                if self.Value(self.x_vars[(i, j)]):
                    print(f"Travel from {i} to {j}")
            print("\nItem pickups:")
            for i in self.nodes_without_SE:
                if self.Value(self.y_vars[i]):
                    print(f"At node {i}, picked up item with volume {self.volumes[i]}.")
            print("\nArrival times at nodes:")
            for i in self.NODES:
                arrival_time = self.Value(self.s_vars[i])
                print(f"Node {i}: Arrival time {arrival_time} minutes")

# Create the solver
solver = cp_model.CpSolver()

# Set a time limit (optional)
# solver.parameters.max_time_in_seconds = 60.0

# Create an instance of the custom callback
solution_printer = RouteSolutionPrinter(
    x_vars=x,
    y_vars=y,
    s_vars=s,
    NODES=NODES,
    EDGES=EDGES,
    nodes_without_SE=nodes_without_SE,
    P=P,
    volumes=volumes
)

# Solve the problem with the callback
status = solver.SolveWithSolutionCallback(model, solution_printer)

# Final status check
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print(f"\nFinal solution with objective value: {solver.ObjectiveValue()}\n")
else:
    print("No solution found.")