Routing in Line Networks with Handling Times

Motivated by hyperconnected urban parcel networks for same-day and time-sensitive delivery, we study the fixed-line routing problem that arises when evaluating a candidate set of recurring interhub vehicle services. Vehicles follow predefined cyclic sequences of service points, or lines, and parcels may transfer between lines. Such transfers expand path choice but require loading and unloading operations that make vehicles dwell at service points. Because handled volumes are routing-dependent, dwell times become endogenous, linking routing decisions to line cycle times, effective service frequencies, and transfer waiting times. We introduce the routing in line networks with handling times problem and formulate it as a bilinear generalized capacity-flow assignment model. We characterize optimal dwell times and the resulting frequencies as functions of handling workloads, enabling a reformulation solely in terms of commodity flows. We exploit its convex substructure to derive two second order conic relaxations that preserve the original feasible region and, therefore, yield feasible incumbent solutions along with valid lower bounds. We also develop a residual-frontier framework that characterizes the trade-off between the convex relaxation objective and the remaining nonconvex residual, yielding a general mechanism for constructing lower bound certificates. Computational experiments show that ignoring handling times can yield poor or infeasible routing, whereas accounting for endogenous dwell times can improve average parcel travel times by up to 26.5%. In instances with up to 257 nodes and 25 lines, the relaxations solve quickly, yield near-optimal routing, and obtain small optimality gaps, whereas off-the-shelf spatial branch-and-bound struggles to produce useful bounds. Funding: This research was supported by the Israel Science Foundation [Grant 1460/20]; The first author was partially supported by the Ministry of Aliyah and Integration, the Shlomo Shmeltzer Institute for Smart Transportation and the Israeli Smart Transportation Research Center. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2026.0039 .