# Untitled

unknown
python
12 days ago
1.9 kB
1
Indexable
Never
```class VRPHeuristic(scip.Heur):
def __init__(self, model, distance_matrix):
scip.Heur.__init__(self, model=model, name="VRPHeuristic", desc="Greedy Heuristic for VRP")
self.distance_matrix = distance_matrix

def heurexec(self, heurtiming, result):
# Tạo giải pháp ban đầu bằng heuristic tham lam (greedy)
num_customers, num_vehicles = self.distance_matrix.shape
routes = [[] for _ in range(num_vehicles)]
remaining_capacity = [capacity] * num_vehicles
current_node = 0  # Bắt đầu từ trạm

for _ in range(num_customers):
best_distance = float("inf")
best_vehicle = None
best_node = None

for k in range(num_vehicles):
if demand[current_node] <= remaining_capacity[k]:
for j in range(1, num_customers + 1):
if j not in routes[k]:
if self.distance_matrix[current_node, j] < best_distance:
best_distance = self.distance_matrix[current_node, j]
best_vehicle = k
best_node = j

if best_node is not None:
routes[best_vehicle].append(best_node)
remaining_capacity[best_vehicle] -= demand[best_node]
current_node = best_node

# Xây dựng giải pháp từ các routes
sol = self.model.createSol(self)
for k, route in enumerate(routes):
for i in range(len(route)):
for j in range(len(route)):
sol[x[route[i], route[j], k]] = 1

# Kiểm tra và cập nhật giải pháp nếu tốt hơn
accepted = self.model.trySol(sol)
if accepted:
return {"result": scip.SCIP_RESULT.FOUNDSOL}
else:
return {"result": scip.SCIP_RESULT.DIDNOTFIND}
```