travelling salesman problem with precedence constraints

Stronger Multi-Commodity Flow Formulations of the (Capacitated) Sequential Ordering Problem

  • Adam N. Letchford
  • Juan-José Salazar-González
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Network Optimization Tags , , , ,

    The “sequential ordering problem” (SOP) is the generalisation of the asymmetric travelling salesman problem in which there are precedence relations between pairs of nodes. Hernández & Salazar introduced a “multi-commodity flow” (MCF) formulation for a generalisation of the SOP in which the vehicle has a limited capacity. We strengthen this MCF formulation by fixing variables … Read more