Abstract
This paper considers a generalization of the network design problem for On-Demand Multimodal Transit Systems (ODMTS). An ODMTS consists of a selection of hubs served by high frequency buses, and passengers are connected to the hubs by on-demand shuttles which serve the first and last miles. This paper generalizes prior work by including three additional elements that are critical in practice. First, different frequencies are allowed throughout the network. Second, additional modes of transit (e.g., rail) are included. Third, a limit on the number of transfers per passenger is introduced. Adding a constraint to limit the number of transfers has a significant negative impact on existing Benders decomposition approaches as it introduces non-convexity in the subproblem. Instead, this paper enforces the limit through transfer-expanded graphs, i.e., layered graphs in which each layer corresponds to a certain number of transfers. A real-world case study is presented for which the generalized ODMTS design problem is solved for the city of Atlanta. The results demonstrate that exploiting the problem structure with transfer-expanded graphs results in significant computational improvements.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aneja, Y.P., Nair, K.P.K.: The constrained shortest path problem. Naval Res. Logistics Q. 25(3), 549–555 (1978). https://doi.org/10.1002/nav.3800250314
Benders, J.F.: Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 4(1), 238–252 (1962)
Boland, N., Hewitt, M., Marshall, L., Savelsbergh, M.: The continuous-time service network design problem. Oper. Res. 65(5), 1303–1321 (2017). https://doi.org/10.1287/opre.2017.1624
Codato, G., Fischetti, M.: Combinatorial Benders’ cuts for mixed-integer linear programming. Oper. Res. 54(4), 756–766 (2006). https://doi.org/10.1287/opre.1060.0286
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. The MIT Press (2009)
Dahl, G., Realfsen, B.: The cardinality-constrained shortest path problem in 2-graphs. Networks 36(1), 1–8 (2000)
Fischetti, M., Ljubić, I., Sinnl, M.: Redesigning Benders decomposition for large-scale facility location. Manag. Sci. 63(7), 2146–2162 (2017). https://doi.org/10.1287/mnsc.2016.2461
Gouveia, L., Leitner, M., Ruthmair, M.: Layered graph approaches for combinatorial optimization problems. Comput. Oper. Res. 102, 22–38 (2019). https://doi.org/10.1016/j.cor.2018.09.007
Hasan, M.H., Van Hentenryck, P.: A column-generation algorithm for evacuation planning with elementary paths. In: Beck, J.C. (ed.) CP 2017. LNCS, vol. 10416, pp. 549–564. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66158-2_35
Laporte, G., Louveaux, F.V., Van Hamme, L.: An integer L-shaped algorithm for the capacitated vehicle routing problem with stochastic demands. Oper. Res. 50(3), 415–423 (2002). https://doi.org/10.1287/opre.50.3.415.7751
Mahéo, A., Kilby, P., Van Hentenryck, P.: Benders decomposition for the design of a hub and shuttle public transit system. Transp. Sci. 53(1), 77–88 (2019). https://doi.org/10.1287/trsc.2017.0756
Moccia, L., Cordeau, J.F., Monaco, M.F., Sammarra, M.: A column generation heuristic for a dynamic generalized assignment problem. Comput. Oper. Res. 36(9), 2670–2681 (2009). https://doi.org/10.1016/j.cor.2008.11.022
Pillac, V., Cebrian, M., Van Hentenryck, P.: A column-generation approach for joint mobilization and evacuation planning. Constraints 20(3), 285–303 (2015). https://doi.org/10.1007/s10601-015-9189-7
Pillac, V., Van Hentenryck, P., Even, C.: A conflict-based path-generation heuristic for evacuation planning. Transp. Res. Part B: Methodol. 83, 136–150 (2016). https://doi.org/10.1016/j.trb.2015.09.008
Acknowledgements
This research is partly supported by NSF Leap HI proposal NSF-1854684.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Dalmeijer, K., Van Hentenryck, P. (2020). Transfer-Expanded Graphs for On-Demand Multimodal Transit Systems. In: Hebrard, E., Musliu, N. (eds) Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2020. Lecture Notes in Computer Science(), vol 12296. Springer, Cham. https://doi.org/10.1007/978-3-030-58942-4_11
Download citation
DOI: https://doi.org/10.1007/978-3-030-58942-4_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-58941-7
Online ISBN: 978-3-030-58942-4
eBook Packages: Computer ScienceComputer Science (R0)