Branch-And-Cut and a Sequential Heuristic for Multimodal Multi-Demand Routing
DOI:
https://doi.org/10.65150/EP-gjetr/V2E8/2026-06Keywords:
multimodal transport, formal and informal transit, MILP, branch-and-cut, constructive heuristic, scalability, operations researchAbstract
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.
References
1) L. A. Wolsey. Integer Programming. Wiley, 1998.
2) R. K. Ahuja, T. L. Magnanti, J. B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.
3) T. L. Magnanti, R. T. Wong. Network design and transportation planning: models and algorithms. Transportation Science, 18(1):1–55, 1984.
4) T. G. Crainic. Service network design in freight transportation. European Journal of Operational Research, 122(2):272–288, 2000.
5) M. SteadieSeifi, N. P. Dellaert, W. Nuijten, T. Van Woensel, R. Raoufi. Multimodal freight transportation planning: a literature review. European Journal of Operational Research, 233(1):1–15, 2014.
6) R. Cervero and A. Golub, Informal transport: A global perspective. Transport Policy, 14(6):445–457, 2007.
7) Kumar and F. Barrett, Stuck in Traffic: Urban Transport in Africa. World Bank / Africa Infrastructure Country Diagnostic (AICD), Background Paper No. 1, 2008.
8) K. Gwilliam, Public transport in developing countries. Transport Reviews, 28(4):415–432, 2008.
9) Á. Marín and R. García-Ródenas, Rapid transit network design for optimal cost and origin– destination demand capture. Computers & Operations Research, 2013.
10) D. Canca, A. De-Los-Santos, G. Laporte, and J. A. Mesa, Integrated Railway Rapid Transit Network Design and Line Planning problem with maximum profit. Transportation Research Part E: Logistics and Transportation Review, 127:1–30, 2019.
11) Gao, Ma, He, and Dong, An exact approach for the transit route network design problem. European Journal of Operational Research, 334(1):111–127, 2026.
12) M. H. Baaj and H. S. Mahmassani, An AI-based approach for transit route system planning and design. Journal of Advanced Transportation, 25(2):187–209, 1991.
13) M. H. Baaj and H. S. Mahmassani, Hybrid route generation heuristic algorithm for the design of transit networks. Transportation Research Part C: Emerging Technologies, 3(1):31– 50, 1995.
14) Zarrinmehr, M. Saffarzadeh, S. Seyedabrishami, and Y. Nie, A path-based greedy algorithm for multi-objective transit routes design with elastic demand. Public Transport, 8(2):261–293, 2016.
15) A Heuristic Algorithm Based on Travel Demand for Transit Network Design. Sustainability, 14(17), art. 11097, 2022.
16) O. Koné, Y. F. A. Edi, K. H. Edi, and P. M. Takouda, MILP for Multimodal Urban Transport: Formal and Informal Sectors. International Journal of Advanced Computer Science and Applications (IJACSA), 17(5), 2026.
17) Y. F. A. Edi, O. Koné, and K. H. Edi, A new mixed-line programming approach to the problem of multimodal urban transit. Statistics, Optimization & Information Computing, 14(3):1458–1472, 2025.
Downloads
Published
Issue
Section
License
Copyright (c) 2026 KONE Oumar, EDI Y. F. Aristide, EDI K. Hilaire, TAKOUDA P. L. Matthias (Author)
This work is licensed under a Creative Commons Attribution 4.0 International License.
