TL;DR
This paper tackles the complex challenge of real-time truckload pickup and delivery by introducing a new optimization-based policy (OPTUN) that significantly outperforms existing heuristic and re-optimization strategies. The work provides a robust simulation framework to evaluate these policies under various realistic conditions, offering valuable insights for improving fleet management efficiency.
What Problem Does This Paper Address?
Modern logistics and transportation heavily rely on real-time information to optimize operations, reduce costs, and improve efficiency. A key challenge is the dynamic nature of truckload pickup and delivery problems (TPDP), where customer requests arrive continuously, and decisions must be made quickly with incomplete information about future demands. Traditional approaches often struggle to adapt to this dynamic environment, leading to suboptimal routing, increased empty travel, delayed deliveries, and job rejections. This paper addresses this by developing and evaluating strategies for a generic real-time multi-vehicle TPDP, considering costs associated with empty travel, delayed deliveries, and job rejections, all within a dynamic setting.
Methods
The authors propose a mixed-integer programming formulation for the off-line version of the TPDP, which serves as a basis for developing real-time strategies. For the real-time problem, they compare five rolling-horizon strategies:
- BENCH: A simple, sequential heuristic that accepts or rejects jobs and assigns them to the truck with the lowest marginal cost, without considering future jobs.
- NS (Non-modifying Sequential): A local policy that evaluates pending jobs sequentially and inserts them into existing truck queues without altering the current order.
- SE (Sequential Evaluation): Another local policy that evaluates pending jobs by solving a one-truck off-line problem to determine optimal insertion and ordering.
- MYOPT: A re-optimization policy that solves the full off-line problem at each decision epoch, assuming no future jobs will arrive.
- OPTUN: A novel re-optimization policy that is similar to MYOPT but incorporates an "opportunity cost" for serving jobs, accounting for the probability of future job requests. This is the paper's main contribution.
The comparison of these policies is conducted using a comprehensive simulation framework that models various traffic intensities, degrees of advance information, and flexibility in job rejection.
Datasets
Not discussed in the paper. The paper uses a simulation framework with synthetically generated job requests and parameters.
Key Insights and Ideas
- Re-optimization Pays Off: Strategies that re-optimize the entire fleet's plan at each decision epoch (MYOPT and OPTUN) consistently outperform simpler, local heuristic policies, even when considering the computational cost. This highlights the value of a more holistic view of the system.
- Future Knowledge is Valuable: The OPTUN policy, which incorporates a probabilistic understanding of future job locations, demonstrates superior performance over MYOPT (which assumes no future jobs). This suggests that even limited probabilistic information can significantly improve decision-making.
- Urgency Matters: Tighter delivery windows (lower $T_{SLK}$) increase the performance gap between re-optimization policies and local heuristics, emphasizing the need for more sophisticated strategies when jobs are time-sensitive.
- Traffic Intensity Amplifies Differences: As system saturation (traffic intensity $\rho$) increases, the performance advantage of re-optimization policies becomes even more pronounced, indicating their robustness in busier scenarios.
Key Results
Under default simulation parameters, the OPTUN policy achieved the lowest average cost ($AvgCost = 0.166$), significantly outperforming BENCH ($0.213$), NS ($0.198$), SE ($0.199$), and MYOPT ($0.169$). This trend held across various scenarios, including increased delay penalties and higher traffic intensities. For instance, when delay penalties were more important ($\beta=1.0$), OPTUN achieved an $AvgCost$ of $0.043$, compared to $0.061$ for BENCH. The paper also shows that OPTUN's advantage over MYOPT increases with more advance information ($T^{ADV}$), suggesting it leverages this information more effectively.
Limitations and Future Work
- Computational Cost: While re-optimization policies perform better, they are computationally more intensive. The paper acknowledges this by imposing limits on optimization time ($T_{LIM}$) and the number of jobs considered ($N_B$) for SE and re-optimization policies, which can affect their performance at very high saturation rates.
- Probabilistic Assumptions: The analysis relies on specific probabilistic assumptions for job arrivals and characteristics. The robustness of the findings to different distributions might warrant further investigation.
- Future Research: The authors suggest future research should focus on developing better policies that more efficiently utilize information about future jobs. They believe there is significant potential for improvement beyond OPTUN, particularly in how probabilistic information is integrated.
Summary updated