Branch-And-Cut and a Sequential Heuristic for Multimodal Multi-Demand Routing

Abstract

We study multimodal multi-demand routing with coupled capacities on a formal/informal urban network, modeled by the compact MILP Pext. We compare two complementary solution paradigms—an exact branch-and-cut algorithm (BAC) and a greedy sequential construction heuristic (SEQ)—in a scalability study on 1000 instances (20 groups × 50), measuring CPU time, primal quality relative to the certified optimum, and structural growth of the compact model. Both methods use the same elementary-path decoder, so that the reported time–quality trade-off isolates the algorithmic paradigm rather than incidental modeling differences.