{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:32:52Z","timestamp":1740123172676,"version":"3.37.3"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"2-3","license":[{"start":{"date-parts":[[2024,4,9]],"date-time":"2024-04-09T00:00:00Z","timestamp":1712620800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,4,9]],"date-time":"2024-04-09T00:00:00Z","timestamp":1712620800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-19-1-0177"],"award-info":[{"award-number":["FA9550-19-1-0177"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2024,7]]},"DOI":"10.1007\/s10479-024-05910-z","type":"journal-article","created":{"date-parts":[[2024,4,9]],"date-time":"2024-04-09T10:02:03Z","timestamp":1712656923000},"page":"1101-1126","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Arc-dependent networks: theoretical insights and a computational study"],"prefix":"10.1007","volume":"338","author":[{"given":"Alvaro","family":"Velasquez","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P.","family":"Wojciechowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5821-5117","authenticated-orcid":false,"given":"K.","family":"Subramani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthew","family":"Williamson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,4,9]]},"reference":[{"key":"5910_CR1","unstructured":"Aldous, D., & Fill, J. A. (2002). Reversible Markov chains and random walks on graphs. Unfinished monograph, recompiled 2014. https:\/\/www.stat.berkeley.edu\/users\/aldous\/RWG\/book.pdf"},{"key":"5910_CR2","unstructured":"AMPL Optimization Inc. (2017). AMPL Python API. https:\/\/amplpy.readthedocs.io\/en\/latest\/index.html"},{"issue":"3","key":"5910_CR3","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0191-2615(95)00024-0","volume":"30","author":"J A\u00f1ez","year":"1996","unstructured":"A\u00f1ez, J., De La Barra, T., & P\u00e9rez, B. (1996). Dual graph representation of transport networks. Transportation Research Part B: Methodological, 30(3), 209\u2013216.","journal-title":"Transportation Research Part B: Methodological"},{"key":"5910_CR4","volume-title":"Dynamic programming","author":"RE Bellman","year":"1957","unstructured":"Bellman, R. E. (1957). Dynamic programming. Princeton University Press."},{"issue":"1","key":"5910_CR5","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0890-5401(92)90056-L","volume":"96","author":"P Berman","year":"1992","unstructured":"Berman, P., & Schnitger, G. (1992). On the complexity of approximating the independent set problem. Information and Computation, 96(1), 77\u201394.","journal-title":"Information and Computation"},{"issue":"2","key":"5910_CR6","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1145\/366105.366184","volume":"4","author":"T Caldwell","year":"1961","unstructured":"Caldwell, T. (1961). On finding minimum routes in a network with turn penalties. Communications of the ACM, 4(2), 107\u2013108.","journal-title":"Communications of the ACM"},{"issue":"06","key":"5910_CR7","doi-asserted-by":"publisher","first-page":"1231002:1","DOI":"10.1142\/S0219720012310026","volume":"10","author":"KF Chong","year":"2012","unstructured":"Chong, K. F., & Leong, H. W. (2012). Tutorial on de novo peptide sequencing using MS\/MS mass spectrometry. Journal of Bioinformatics and Computational Biology, 10(06), 1231002:1-1231002:38.","journal-title":"Journal of Bioinformatics and Computational Biology"},{"key":"5910_CR8","volume-title":"Introduction to algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd ed.). MIT Press.","edition":"3"},{"key":"5910_CR9","unstructured":"CPLEX Manual. (2020). IBM ILOG CPLEX optimization studio V20.1.0 documentation."},{"issue":"3\u20134","key":"5910_CR10","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1089\/106652799318300","volume":"6","author":"V Danc\u00edk","year":"1999","unstructured":"Danc\u00edk, V., Addona, T. A., Clauser, K. R., Vath, J. E., & Pevzner, P. A. (1999). De novo peptide sequencing via tandem mass spectrometry. Journal of Computational Biology, 6(3\u20134), 327\u2013342.","journal-title":"Journal of Computational Biology"},{"issue":"3","key":"5910_CR11","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1002\/net.3230090304","volume":"9","author":"R Dial","year":"1979","unstructured":"Dial, R., Glover, F., Karney, D., & Klingman, D. (1979). A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees. Networks, 9(3), 215\u2013248.","journal-title":"Networks"},{"key":"5910_CR12","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269\u2013271.","journal-title":"Numerische Mathematik"},{"key":"5910_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-09471-6","volume-title":"Produktionsplanung - Ablauforganisatorische Aspekte","author":"W Domschke","year":"1993","unstructured":"Domschke, W., Scholl, A., & Vo\u00df, S. (1993). Produktionsplanung - Ablauforganisatorische Aspekte. Springer."},{"issue":"6","key":"5910_CR14","doi-asserted-by":"publisher","first-page":"1055","DOI":"10.1287\/opre.41.6.1055","volume":"41","author":"M Fischetti","year":"1993","unstructured":"Fischetti, M., Laporte, G., & Martello, S. (1993). The delivery man problem and cumulative matroids. Operations Research, 41(6), 1055\u20131064.","journal-title":"Operations Research"},{"key":"5910_CR15","unstructured":"Fox, K. R. (1973). Production scheduling on parallel lines with dependencies. Ph.D. thesis, Johns Hopkins University."},{"key":"5910_CR16","doi-asserted-by":"publisher","first-page":"964","DOI":"10.1021\/ac048788h","volume":"77","author":"A Frank","year":"2005","unstructured":"Frank, A., & Pevzner, P. (2005). PepNovo: De novo peptide sequencing via probabilistic network modeling. Analytical Chemistry, 77, 964\u2013973.","journal-title":"Analytical Chemistry"},{"issue":"1","key":"5910_CR17","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0377-2217(93)E0238-S","volume":"83","author":"L Gouveia","year":"1995","unstructured":"Gouveia, L., & Vo\u00df, S. (1995). A classification of formulations for the (time-dependent) traveling salesman problem. European Journal of Operational Research, 83(1), 69\u201382.","journal-title":"European Journal of Operational Research"},{"key":"5910_CR18","doi-asserted-by":"crossref","unstructured":"Hagberg, A. A., Schult, D. A., & Swart, P. J. (2008). Exploring network structure, dynamics, and function using NetworkX. In G. Varoquaux, T. Vaught, & J. Millman (Eds.), Proceedings of the 7th python in science conference (pp. 11\u201315), Pasadena, CA USA.","DOI":"10.25080\/TCWV9851"},{"issue":"3","key":"5910_CR19","doi-asserted-by":"publisher","first-page":"754","DOI":"10.1007\/s10878-017-0219-9","volume":"35","author":"H Hao","year":"2018","unstructured":"Hao, H., & Sotirov, R. (2018). Special cases of the quadratic shortest path problem. Journal of Combinatorial Optimization, 35(3), 754\u2013777.","journal-title":"Journal of Combinatorial Optimization"},{"issue":"2","key":"5910_CR20","first-page":"219","volume":"32","author":"H Hao","year":"2020","unstructured":"Hao, H., & Sotirov, R. (2020). On solving the quadratic shortest path problem. INFORMS Journal on Computing, 32(2), 219\u2013233.","journal-title":"INFORMS Journal on Computing"},{"issue":"4","key":"5910_CR21","doi-asserted-by":"publisher","first-page":"1051","DOI":"10.1007\/s10845-019-01518-4","volume":"31","author":"L He","year":"2020","unstructured":"He, L., de Weerdt, M., & Yorke-Smith, N. (2020). Time\/sequence-dependent scheduling: The design and evaluation of a general purpose tabu-based adaptive large neighbourhood search algorithm. Journal of Intelligent Manufacturing, 31(4), 1051\u20131078.","journal-title":"Journal of Intelligent Manufacturing"},{"key":"5910_CR22","first-page":"1","volume":"227","author":"M Kang","year":"2014","unstructured":"Kang, M., & Petrasek, Z. (2014). Random graphs: Theory and applications from nature to society to the brain. Internationale Mathematische Nachrichten, 227, 1\u201324.","journal-title":"Internationale Mathematische Nachrichten"},{"issue":"3","key":"5910_CR23","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1016\/S0041-1647(69)80022-5","volume":"3","author":"RF Kirby","year":"1969","unstructured":"Kirby, R. F., & Potts, R. B. (1969). The minimum route problem for networks with turn penalties and prohibitions. Transportation Research, 3(3), 397\u2013408.","journal-title":"Transportation Research"},{"issue":"6","key":"5910_CR24","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1002\/net.3230200605","volume":"20","author":"A Lucena","year":"1990","unstructured":"Lucena, A. (1990). Time-dependent traveling salesman problem: The deliveryman case. Networks, 20(6), 753\u2013763.","journal-title":"Networks"},{"key":"5910_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.5121\/jgraphoc.2016.8101","volume":"8","author":"M Moussa","year":"2016","unstructured":"Moussa, M., & Badr, E.-S. (2016). Ladder and subdivision of ladder graphs with pendant edges are odd graceful. International Journal on Applications of Graph Theory in wireless Ad Hoc Networks and Sensor Networks, 8, 1\u20138.","journal-title":"International Journal on Applications of Graph Theory in wireless Ad Hoc Networks and Sensor Networks"},{"key":"5910_CR26","doi-asserted-by":"crossref","unstructured":"Ning, K., Chong, K. F., & Leong, H. W. (2007). De novo peptide sequencing for mass spectra based on multi-charge strong tags. In Proceedings of the 5th Asia-Pacific bioinformatics conference (pp. 287\u2013296).","DOI":"10.1142\/9781860947995_0031"},{"issue":"1","key":"5910_CR27","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/S0893-9659(04)90003-1","volume":"17","author":"PM Pardalos","year":"2004","unstructured":"Pardalos, P. M., & Migdalas, A. (2004). A note on the complexity of longest path problems related to graph coloring. Applied Mathematics Letters, 17(1), 13\u201315.","journal-title":"Applied Mathematics Letters"},{"issue":"2","key":"5910_CR28","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/BF00138693","volume":"8","author":"NV Sahinidis","year":"1996","unstructured":"Sahinidis, N. V. (1996). BARON: A general purpose global optimization software package. Journal of Global Optimization, 8(2), 201\u2013205.","journal-title":"Journal of Global Optimization"},{"key":"5910_CR29","doi-asserted-by":"crossref","unstructured":"Shafiee, M., & Ghaderi, J (2021). Scheduling coflows with dependency graph. IEEE\/ACM Transactions on Networking.","DOI":"10.1109\/TNET.2021.3116133"},{"issue":"2","key":"5910_CR30","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1016\/j.ejor.2017.08.021","volume":"265","author":"L Shen","year":"2018","unstructured":"Shen, L., Dauz\u00e8re-P\u00e9r\u00e8s, S., & Neufeld, J. S. (2018). Solving the flexible job shop scheduling problem with sequence-dependent setup times. European Journal of Operational Research, 265(2), 503\u201351.","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"5910_CR31","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/s10817-009-9139-4","volume":"43","author":"K Subramani","year":"2009","unstructured":"Subramani, K. (2009). Optimal length resolution refutations of difference constraint systems. Journal of Automated Reasoning (JAR), 43(2), 121\u2013137.","journal-title":"Journal of Automated Reasoning (JAR)"},{"key":"5910_CR32","unstructured":"Tan, J. (2003). On path-dependent shortest path and its application in finding least cost path in transportation networks. Master\u2019s thesis, School of Computing, National University of Singapore."},{"key":"5910_CR33","unstructured":"Tan, J., & Leong, H. W. (2004). Least-cost path in public transportation systems with fare rebates that are path- and time-dependent. In Proceedings of the 7th international ieee conference on intelligent transportation systems (IEEE Cat. No.04TH8749) (pp. 1000\u20131005)."},{"key":"5910_CR34","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511815478","volume-title":"Social network analysis: Methods and applications","author":"S Wasserman","year":"1994","unstructured":"Wasserman, S., & Faust, K. (1994). Social network analysis: Methods and applications (Vol. 8). Cambridge University Press."},{"key":"5910_CR35","doi-asserted-by":"crossref","unstructured":"Wojciechowski, P. J., Subramani, K., Velasquez, A., & Williamson, M. D. (2022). On the approximability of path and cycle problems in arc-dependent networks. In N. Balachandran, & R. Inkulu (Eds.), Algorithms and discrete applied mathematics\u20148th international conference, CALDAM 2022, Puducherry, India, February 10\u201312, 2022, proceedings, volume 13179 of lecture notes in computer science (pp. 292\u2013304). Springer.","DOI":"10.1007\/978-3-030-95018-7_23"},{"key":"5910_CR36","doi-asserted-by":"crossref","unstructured":"Wojciechowski, P. J., Williamson, M., & Subramani, K. (2020). On finding shortest paths in arc-dependent networks. In M. Ba\u00efou, B. Gendron, O. G\u00fcnl\u00fck, A. R. Mahjoub (Eds.), Combinatorial optimization\u20146th international symposium, ISCO 2020, Montreal, QC, Canada, May 4\u20136 2020, revised selected papers, volume 12176 of lecture notes in computer science (pp 249\u2013260). Springer.","DOI":"10.1007\/978-3-030-53262-8_21"},{"key":"5910_CR37","doi-asserted-by":"publisher","first-page":"100729","DOI":"10.1016\/j.disopt.2022.100729","volume":"45","author":"P Wojciechowski","year":"2022","unstructured":"Wojciechowski, P., Williamson, M., & Subramani, K. (2022). On the analysis of optimization problems in arc-dependent networks. Discrete Optimization, 45, 100729.","journal-title":"Discrete Optimization"},{"issue":"5","key":"5910_CR38","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1016\/0191-2615(96)00001-X","volume":"30","author":"AK Ziliaskopoulos","year":"1996","unstructured":"Ziliaskopoulos, A. K., & Mahmassani, H. S. (1996). A note on least time path computation considering delays and prohibitions for intersection movements. Transportation Research Part B: Methodological, 30(5), 359\u2013367.","journal-title":"Transportation Research Part B: Methodological"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-024-05910-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10479-024-05910-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-024-05910-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,15]],"date-time":"2024-11-15T23:10:42Z","timestamp":1731712242000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10479-024-05910-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,9]]},"references-count":38,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["5910"],"URL":"https:\/\/doi.org\/10.1007\/s10479-024-05910-z","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"type":"print","value":"0254-5330"},{"type":"electronic","value":"1572-9338"}],"subject":[],"published":{"date-parts":[[2024,4,9]]},"assertion":[{"value":"3 May 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 February 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 April 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflicts of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}