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.

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