Global Journal of Engineering and Technology Research (GJETR)

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

Oumar, KONE, Aristide, EDI Y. F., Hilaire, EDI K., Matthias, TAKOUDA P. L.

29 August 2026 · Vol. 2, Issue 8, pp. 366-373

DOI: 10.65150/EP-gjetr/V2E8/2026-06

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.

Keywords: multimodal transport, formal and informal transit, MILP, branch-and-cut, constructive heuristic, scalability, operations research

Read the full text on Global Journal of Engineering and Technology Research →The full peer-reviewed article and PDF are hosted on the journal's site (the version of record).

Oumar, KONE, Aristide, EDI Y. F., Hilaire, EDI K., Matthias, & TAKOUDA P. L. (2026). Branch-And-Cut and a Sequential Heuristic for Multimodal Multi-Demand Routing. Global Journal of Engineering and Technology Research, 2(8), 366-373. https://doi.org/10.65150/EP-gjetr/V2E8/2026-06

@article{Oumar2026,
  title   = {Branch-And-Cut and a Sequential Heuristic for Multimodal Multi-Demand Routing},
  author  = {Oumar and KONE and Aristide and EDI Y. F. and Hilaire and EDI K. and Matthias and TAKOUDA P. L.},
  journal = {Global Journal of Engineering and Technology Research},
  year    = {2026},
  volume  = {2},
  number  = {8},
  pages   = {366-373},
  doi     = {10.65150/EP-gjetr/V2E8/2026-06},
  url     = {https://doi.org/10.65150/EP-gjetr/V2E8/2026-06}
}

← Back to all articles