Untitled
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}