خوارزمية حل مشكلة البائع المتجول باستخدام البرمجة الصحيحة المختلطة - كتاب الذكاء الإصطناعي - الصف 12 - الفصل 1 - المملكة العربية السعودية

على سبيل المثال، فكر في الطريق 1 ← 2 ← 1 الوارد في الحل المكون من طريقتين لنسخة مشكلة البائع المتجول الموضحة في الشكل السابق، حيث يتطلب قيد الاتصال أن تكون 1 + V2 ≥ V1، و V2 ≥ V1، وهذا مستحيل، فلذلك سيتم استبعاد الحل.

في المقابل، يتطلب الحل الصحيح 0 ← 3 ← 4 ← 1 ← 2 ← 0 أن تكون 1 + V4 ≥ V3، و V4 ≥ V3، وأن تكون 1 + V2 ≥ V1، و V2 ≥ V1، ويمكن تحقيق ذلك بضبط قيم V كما يأتي: 0 = V1 و 1 = V2 و 3 = V3 و 2 = V4، ولا تنطبق قيود الاتصال على الانتقالات التي تشمل موقع startstop (الانطلاق والتوقف).

تجمع الدالة التالية كل الأشياء معًا لإنشاء خوارزمية حل برمجة الأعداد الصحيحة المختلطة لمشكلة البائع المتجول.

from itertools import product from mip import BINARY, INTEGER from mip import Model from mip import xsum, minimize def MIP_solver(dist_matrix, location_ids, startstop): solver = Model()#creates a solver solver.verbose = 0 #setting this to 1 will print info on the progress of the solver #creates every transition from every location to every other location transitions = list(product(location_ids,location_ids)) N = len(location_ids) #number of locations #create an empty square matrix full of 'None' values x = numpy.full((N, N), None) #adds binary decision variables indicating if transition (i->j) is included in the route for i, j in transitions: x[i, j]=solver.add_var(var_type = BINARY) #objective function: minimizes the distance solver.objective = minimize(xsum(dist_matrix[i,j]*x[i][j] for i,j in transitions)) #Arrive/Depart Constraints for i in location_ids: solver += xsum(x[i,j] for j in location_ids - {i}) == 1 #exactly 1 arrival solver += xsum(x[j,i] for j in location_ids - {i}) == 1 #exactly 1 departure #adds a binary decision variable for each location y = [solver.add_var(var_type=INTEGER) for i in location_ids] #adds connectivity constraints for transitions that do not include the startstop for (i, j) in product(location_ids - {startstop}, location_ids - {startstop}): if i != j: #ignores transitions from a location to itself solver += y[j] - y[i] >=(N+1)*x[i,j] - N solver.optimize() #solves the problem #prints the solution if solver.num_solutions: #if a solution was found best_route = [startstop] #stores the best route curr_loc = startstop #the currently visited location while True: for next_loc in location_ids:# for every possible next location if x[curr_loc,next_loc].x == 1: #if x value for the curr_loc->next_loc transition is 1 best_route.append(next_loc) #appends the next location to the route curr_loc=next_loc #visits the next location break if next_loc == startstop: #exits if route returns to the startstop break return best_route, solver.objective_value #returns the route and its total distance

وزارة التعليم Ministry of Education 2023 - 1447

292

على سبيل المثال، فكر في الطريق 1 ← 2 ← 1 الوارد في الحل المكون من طريقتين لنسخة مشكلة البائع المتجول الموضحة في الشكل السابق، حيث يتطلب قيد الاتصال أن تكون 1 + V2 ≥ V1، و V2 ≥ V1، وهذا مستحيل، فلذلك سيتم استبعاد الحل.في المقابل، يتطلب الحل الصحيح 0 ← 3 ← 4 ← 1 ← 2 ← 0 أن تكون 1 + V4 ≥ V3، و V4 ≥ V3، وأن تكون 1 + V2 ≥ V1، و V2 ≥ V1، ويمكن تحقيق ذلك بضبط قيم V كما يأتي: 0 = V1 و 1 = V2 و 3 = V3 و 2 = V4، ولا تنطبق قيود الاتصال على الانتقالات التي تشمل موقع startstop (الانطلاق والتوقف).تجمع الدالة التالية كل الأشياء معًا لإنشاء خوارزمية حل برمجة الأعداد الصحيحة المختلطة لمشكلة البائع المتجول.from itertools import product from mip import BINARY, INTEGER from mip import Model from mip import xsum, minimize def MIP_solver(dist_matrix, location_ids, startstop): solver = Model()#creates a solver solver.verbose = 0 #setting this to 1 will print info on the progress of the solver #creates every transition from every location to every other location transitions = list(product(location_ids,location_ids)) N = len(location_ids) #number of locations #create an empty square matrix full of 'None' values x = numpy.full((N, N), None) #adds binary decision variables indicating if transition (i->j) is included in the route for i, j in transitions: x[i, j]=solver.add_var(var_type = BINARY) #objective function: minimizes the distance solver.objective = minimize(xsum(dist_matrix[i,j]*x[i][j] for i,j in transitions)) #Arrive/Depart Constraints for i in location_ids: solver += xsum(x[i,j] for j in location_ids - {i}) == 1 #exactly 1 arrival solver += xsum(x[j,i] for j in location_ids - {i}) == 1 #exactly 1 departure #adds a binary decision variable for each location y = [solver.add_var(var_type=INTEGER) for i in location_ids] #adds connectivity constraints for transitions that do not include the startstop for (i, j) in product(location_ids - {startstop}, location_ids - {startstop}): if i != j: #ignores transitions from a location to itself solver += y[j] - y[i] >=(N+1)*x[i,j] - N solver.optimize() #solves the problem #prints the solution if solver.num_solutions: #if a solution was found best_route = [startstop] #stores the best route curr_loc = startstop #the currently visited location while True: for next_loc in location_ids:# for every possible next location if x[curr_loc,next_loc].x == 1: #if x value for the curr_loc->next_loc transition is 1 best_route.append(next_loc) #appends the next location to the route curr_loc=next_loc #visits the next location break if next_loc == startstop: #exits if route returns to the startstop break return best_route, solver.objective_value #returns the route and its total distance2023 - 1447