Sequence and Speed Optimization

Schaudt, Stefan and Bektaş, Tolga ORCID: 0000-0003-0634-144X (2026) Sequence and Speed Optimization INFORMS Journal on Computing. ISSN 0899-1499, 1526-5528

Text SchaudtBektas_IJOC.pdf - Author Accepted Manuscript Available under License Creative Commons Attribution. Download (910kB) | Preview

Abstract

Sequencing and timing decisions frequently arise interdependently in combinatorial optimization problems. This study concerns a speed optimization problem (SOP) that determines optimal speeds to minimize a strictly convex cost function on a fixed sequence of nodes with time window constraints and a joint routing and speed optimization problem, finding an optimal sequence of nodes and speeds on each route. The paper describes two polynomial-time algorithms for the SOP, one to solve the SOP and another to compute all possible completion times for a sequence, along with proofs of optimality, and a branch-and-price algorithm, incorporating a new dominance rule, for the joint routing and speed optimization problem. Computational experiments show the proposed algorithm achieves an average 17.5-fold improvement in computational time over the state-of-the-art for benchmark instances solved to optimality (ranging from 4.9-fold on road to 73-fold on maritime instances). History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.1047 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.1047 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Item Type:	Article
Uncontrolled Keywords:	4901 Applied Mathematics, 46 Information and Computing Sciences, 49 Mathematical Sciences, Bioengineering
Divisions:	Faculty of Humanities & Social Sciences Faculty of Humanities & Social Sciences > School of Management Faculty of Humanities & Social Sciences > Faculty of Humanities & Social Sci (All T&R Staff) Faculty of Humanities & Social Sciences > School of Management > School of Management (T&R Staff) Faculty of Humanities & Social Sciences > School of Management > Operations and Supply Chain Management
Depositing User:	Symplectic Admin
Date Deposited:	11 May 2026 08:30
Last Modified:	26 Aug 2026 12:04
DOI:	10.1287/ijoc.2024.1047
Related Websites:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3198348
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.