Routing in Line Networks with Handling Times
Abstract
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 inter-hub 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 (RLN-HT) 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 tradeoff 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.
Related
- Handling Customer Preferences in Last-Mile Location-Routing: A Bilevel Optimization Approach
- Network Coding Can Beat Routing in Undirected Multiple-Unicast Networks
- Multiplicative Path Weights in Networks: From Katz Connectivity to Mean First-Passage Times
- Graph-theoretic framework for semi-Markov networks: transient and stationary occupation probabilities, hitting times and weak ergodicity breaking
- A computational comparison of handling distance constraints in MINLP
BibTeX
@misc{deza2026routing,
title = {{Routing in Line Networks with Handling Times}},
author = {Gabriel Deza and Michal Tzur and Tal Raviv},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.01666},
eprint = {2610.01666},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.01666},
}
RIS
TY - UNPB
TI - Routing in Line Networks with Handling Times
AU - Gabriel Deza
AU - Michal Tzur
AU - Tal Raviv
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.01666
UR - https://arxiv.org/abs/2610.01666
AB - 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 inter-hub 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 (RLN-HT) 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 tradeoff 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.
ER -