WA11 - Routing and Logistics

Modern on-demand mobility and logistics systems increasingly operate under three realities that classical routing models often simplify: (i) travel times depend on departure time, (ii) requests can be served at multiple nearby candidate stops, each with its own time window, and (iii) routing decisions must respect the structure of a physical road network rather than a complete customer graph. This work introduces the Generalized Route Planning and Scheduling problem with time-dependent travel times on road networks (GRPS-TD-RN). Each request induces two clusters (pickup and drop-off), and a feasible plan selects one stop per cluster while scheduling vehicle routes over a continuous planning horizon.

For a fixed generalized route (a sequence of clusters), the route-scheduling core, the Generalized Route Scheduling Problem with time-dependent travel times on road networks (GRSP-TD-RN), is formulated as a Bellman-Ford dynamic program. We establish strong NP-completeness of feasibility and NP-hardness of optimization (even under restricted settings), motivating a three-phase solution pipeline.

Preprocessing: we derive closed-form, continuous piecewise-linear (CPL) travel, arrival, and departure profiles on road networks. We propose a lower-envelope algorithm based on point–line duality, and develop two exact solvers for the time-dependent quickest path problem (TDQPP) to compute stop-to-stop closed-form profiles and their dominant envelopes.

Optimization: we design two exact dynamic-programming (DP) schedulers, Linear Forward Propagation (LFP) and Post-order Binary Tree Propagation (PO-BTP), with recursive and iterative variants, that optimally propagate departure-time envelopes along the route. To enable large-scale search, we introduce (i) fast feasibility screening and lower bounds to filter non-promising moves, and (ii) exact move cost updates using the cached CPL function blocks from the DP, avoiding depot-to-depot rescheduling after each local modification. Building on these components, we propose a DP-embedded Adaptive Large Neighborhood Search with Simulated Annealing acceptance (DP-ALNS-SA) that embeds the exact schedulers to optimally schedule routes throughout the search.

Postprocessing: we recover the optimal stop choice within each cluster and reconstruct path and timing attributes (arrivals, waits) via two exact procedures, including a label-setting method.

Computational experiments on 30 sparse and 30 dense road networks show that our time-dependent quickest-path solvers outperform a recent state-of-the-art method with speedups up to 16×. On instances of the Generalized Dial-a-Ride Problem with time-dependent travel times on road networks (GDARP-TD-RN) with 20 to 3,000 requests, the recursive Post-order Binary Tree Propagation scheduler is consistently the fastest at larger scales, and a precomputed execution mode yields additional 1.8–2.3× speedups. The DP-ALNS-SA runs end-to-end on the full 60-instance set and delivers substantial improvements over initial solutions while maintaining exact route scheduling within the metaheuristic.

Weather routing for maritime vessels is complex. The weather information is available as forecasts for wind, waves, and currents. The routing problem is solved on a large and detailed network model. We analyze the impact from different planning strategies and the balance between cost and safety.

Metro train operations are becoming more challenging due to overcrowding and irregular pas-
senger demand. To avoid passenger dissatisfaction, metro operators employ various operational
strategies to increase the number of train services using limited number of trains. This paper in-
tegrates metro timetabling with several operational strategies to improve passenger services with
limited number of trains. We propose three optimization models for timetable planning during
both peak and off-peak hours. While the first and second models minimize operational costs,
and passenger waiting and travel times, respectively, the third model is a multi-objective model
that considers both the objectives simultaneously. These models integrate operational strategies
such as rolling-stock assignment, short-turning, and skip-stopping to increase the number of
services with limited trains on a bidirectional metro line. To solve the multi-objective model,
we propose a Hybrid epsilon-Constraint Logic-Based Benders Decomposition (Hybrid ε-LBBD)
approach, which achieves orders-of-magnitude reduction in computation time when compared
to the classical epsilon-constraint method. Further, we perform computational experiments for
both time-invariant and time-dependent demand arrival patterns. Finally, we also establish re-
lationship of our model with classical queueing theory and thereby propose a Queue-Integrated
Fixed-Point Algorithm to reduce congestion. The proposed framework is tested on a simplified
version of Santiago Metro Line 1.

We study an auction-based truckload procurement in which multiple shippers collaborate through a centralized platform. Carriers submit combinatorial bids, and the platform selects winners. Incorporating carrier reputation to capture service risk, we propose a carrier selection model and a novel cost allocation method supporting a lasting collaboration.
Keywords: centralized procurement; carrier reputation; cost allocation