Subtour Elimination constraint with two vehicle

Answered

Sebastiano Ferriero

• December 05, 2024 01:07

Hello everyone,

I have a set of costumers (nodes) that can be served by one or more UAV and a truck. The truck serves customers along a TSP route, while the UAVs serve customers directly from the
 depot. So considering that i will know the set of nodes served by the truck only after the optimization of the problem, how can i modify the standard subtour elimination constraint from https://www.gurobi.com/documentation/9.1/examples/tsp_py.html?

0

• 

  Bot Marley (with AI contributions)

  • December 05, 2024 15:03

  

  

  Hi,

  The statement "I will know the set of nodes served by the truck only after optimization of the problem" is incorrect in the context of Gurobi. Instead, this information can be dynamically obtained during the optimization process by leveraging the MIPSOL callback. Here's how you can incorporate it effectively:

  Correct Approach

  You can determine the nodes served by the truck dynamically during the optimization process using the MIPSOL callback. This approach allows you to adjust your constraints (e.g., subtour elimination) based on the solutions being explored by the solver.

  Here’s a revised outline of how to adapt the standard TSP subtour elimination approach:

  1. Model Definition:

     • Define binary variables for truck edges indicating whether an edge is used in the truck route.
     • Define similar variables for UAV usage.

  2. Subtour Elimination Constraints:

     • Start with the usual subtour elimination for the truck route, but modify it dynamically.

  3. Callback Implementation:

     • Use the MIPSOL callback to inspect solutions. At each solution point, determine the set of nodes served by the truck based on the current values of the truck's edge variables.
     • Identify subtours dynamically in the truck route and add lazy constraints to eliminate these subtours.

  4. Lazy Constraints:

     • Implement the lazy constraints directly in the callback for subtour elimination, ensuring they are only added when subtours are detected in a feasible solution.

  Why MIPSOL is Essential

  The MIPSOL callback is critical because it enables you to work with intermediate solutions during the optimization process. This means:

  • You can dynamically identify the truck's served nodes as soon as partial solutions are available.
  • Subtours can be identified and eliminated without waiting for the optimization process to conclude, ensuring feasibility throughout.

  This technique ensures that the set of nodes served by the truck is accounted for as part of the iterative optimization process. By leveraging the MIPSOL callback, you incorporate the subtour constraints dynamically, avoiding incorrect assumptions about when the truck's route can be determined.

  - Bot
  Try our Gurobot for yourself!

  0

Please sign in to leave a comment.