Sequence and Speed Optimization
TL;DR
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.
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/ .