Stronger multi-commodity flow formulations of the (capacitated) sequential ordering problem

DOI10.1016/j.ejor.2015.11.001zbMath1346.90709OpenAlexW2116871384WikidataQ57702120 ScholiaQ57702120MaRDI QIDQ322625

Juan-José Salazar-González, Adam N. Letchford

Publication date: 7 October 2016

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://eprints.lancs.ac.uk/id/eprint/76444/1/mcf_csop_rev.pdf

zbMATH Keywords

metricspolyhedral combinatoricsmulti-commodity flowssequential orderingtravelling salesman problem with precedence constraints

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27)

Related Items (8)

An exact dynamic programming algorithm for the precedence-constrained class sequencing problem ⋮ Exact algorithms for the multi-pickup and delivery problem with time windows ⋮ Formulations for the clustered traveling salesman problem with \(d\)-relaxed priority rule ⋮ The multi-pickup and delivery problem with time windows ⋮ Revisiting dynamic programming for precedence-constrained traveling salesman problem and its time-dependent generalization ⋮ An MDD-Based Lagrangian Approach to the Multicommodity Pickup-and-Delivery TSP ⋮ Strong cuts from compatibility relations for the dial-a-ride problem ⋮ Pickup and delivery problem with incompatibility constraints

Cites Work

• Stronger multi-commodity flow formulations of the capacitated vehicle routing problem
• Load-dependent and precedence-based models for pickup and delivery problems
• The multi-commodity one-to-one pickup-and-delivery traveling salesman problem
• An inexact algorithm for the sequential ordering problem
• A result on projection for the vehicle routing problem
• A Lagrangian relax-and-cut approach for the sequential ordering problem with precedence relationships
• Quasi-semi-metrics, oriented multi-cuts and related polyhedra
• A branch \& cut algorithm for the asymmetric traveling salesman problem with precedence constraints
• The precedence-constrained asymmetric traveling salesman polytope
• New cutting-planes for the time- and/or precedence-constrained ATSP and directed VRP
• Projection results for vehicle routing
• Maximal Flow Through a Network
• Exact And Heuristic Procedures For The Traveling Salesman Problem With Precedence Constraints, Based On Dynamic Programming
• A Cutting Plane Approach to the Sequential Ordering Problem (with Applications to Job Scheduling in Manufacturing)
• On extended formulations for the precedence constrained asymmetric traveling salesman problem
• Unnamed Item
• Unnamed Item

This page was built for publication: Stronger multi-commodity flow formulations of the (capacitated) sequential ordering problem