OptMATH

Problem Analysis:

We are tasked with solving a Traveling Salesman Problem (TSP) variant where a logistics company needs to deliver packages to four cities (City 0, City 1, City 2, and City 3) with the objective of minimizing the total delivery cost. The company must ensure that each city is visited exactly once, and the route forms a continuous loop without subtours. The delivery costs between cities are provided, and we need to use binary decision variables to indicate whether a route is used and assign position variables to each city to prevent subtours.

Mathematical Formulation:

Decision Variables:

• x_ij : Binary variable indicating whether the route from City i to City j is used.
• u_i : Position variable for City i, where u₀ = 0 and u_i is an integer between 0 and 3 for i = 1, 2, 3.

Objective Function:

where c_ij is the cost of traveling from City i to City j.

Constraints:

1. Each city is visited exactly once:
   ∑_{j=0, j≠i}³ x_ij = 1    ∀i ∈ {0, 1, 2, 3}
2. Each city is departed exactly once:
   ∑_{i=0, i≠j}³ x_ij = 1    ∀j ∈ {0, 1, 2, 3}
3. Subtour elimination constraints:
   u_i - u_j + 4x_ij ≤ 3    ∀i, j ∈ {1, 2, 3}, i ≠ j
4. Position variable bounds:
   u₀ = 0
   1 ≤ u_i ≤ 3    ∀i ∈ {1, 2, 3}

Python Code:

import gurobipy as gp
        from gurobipy import GRB
          
        # Define the cities and the cost matrix
        cities = [0, 1, 2, 3]
        cost = {
        (0, 1): 616, (0, 2): 567, (0, 3): 143,
        (1, 0): 388, (1, 2): 947, (1, 3): 628,
        (2, 0): 495, (2, 1): 650, (2, 3): 604,
        (3, 0): 77, (3, 1): 630, (3, 2): 23
        }
          
        # Create the model
        model = gp.Model("TSP")
          
        # Decision variables
        x = model.addVars(cities, cities, vtype=GRB.BINARY, name="x")
        u = model.addVars(cities, vtype=GRB.INTEGER, name="u")
          
        # Set the objective function
        model.setObjective(gp.quicksum(cost[i, j] * x[i, j] for i, j in cost), GRB.MINIMIZE)
          
        # Constraints
        # Each city is visited exactly once
        model.addConstrs((gp.quicksum(x[i, j] for j in cities if j != i) == 1 for i in cities), name="visit_once")
          
        # Each city is departed exactly once
        model.addConstrs((gp.quicksum(x[i, j] for i in cities if i != j) == 1 for j in cities), name="depart_once")
          
        # Subtour elimination constraints
        model.addConstrs((u[i] - u[j] + 4 * x[i, j] <= 3 for i in cities if i != 0 for j in cities if j != 0 and i != j), name="subtour_elim")
          
        # Position variable bounds
        model.addConstr(u[0] == 0, name="u0")
        model.addConstrs((u[i] >= 1 for i in cities if i != 0), name="u_lower_bound")
        model.addConstrs((u[i] <= 3 for i in cities if i != 0), name="u_upper_bound")
          
        # Optimize the model
        model.optimize()
          
        # Print the solution
        if model.status == GRB.OPTIMAL:
        print("Optimal solution found!")
        print(f"Total delivery cost: {model.objVal}")
        print("Route:")
        for i in cities:
          for j in cities:
           if i != j and x[i, j].x > 0.5:
            print(f"City {i} -> City {j} (Cost: {cost[i, j]})")
        else:
        print("No optimal solution found.")

Explanation:

• Decision Variables: x[i, j] is a binary variable that indicates whether the route from City i to City j is used. u[i] is an integer variable representing the position of City i in the route.
• Objective Function: The objective is to minimize the total delivery cost, which is the sum of the costs of all selected routes.
• Constraints: The constraints ensure that each city is visited and departed exactly once, and that the route forms a single loop without subtours. The subtour elimination constraints are implemented using the position variables u[i].
• Optimization: The model is optimized using Gurobi, and the optimal route and total delivery cost are printed.