TL;DR
This paper introduces a novel set-covering model for a complex container transportation problem involving multiple shifts and bidirectional routes. By developing a three-stage hybrid approach that includes pre-processing, solving a reduced problem, and post-processing, the authors demonstrate a method that can effectively solve real-world instances, achieving solutions close to a derived lower bound.
What Problem Does This Paper Address?
The paper tackles a specific type of freight transportation problem: the bidirectional multi-shift full truckload vehicle routing problem (FTL VRP) for container drayage at a large international port. This problem is distinct from standard VRPs due to several key characteristics:
- Bidirectional Movement: Trucks can pick up and deliver containers, meaning nodes can act as both origins and destinations.
- Multi-Shift Operations: The planning horizon spans multiple shifts (12 hours each), and routes must be completed within these shifts, with trucks returning to a depot between shifts for driver changes.
- Operation-Dependent Service Times: The time spent at a node (loading or unloading) is comparable to travel time and is not negligible.
- Short Distances, High Frequency: Docks are close together, and the volume of containers to be moved is high (up to 2000 per day).
- Short Time Windows: Commodity time windows can be as short as 1-2 hours, adding significant complexity.
Existing VRP models and solution methods are often unsuitable or inefficient for this problem due to its unique combination of features, particularly the long planning horizons and the need to manage operations across multiple shifts. The authors highlight that the company's current practice results in a high percentage of empty truck mileage, indicating a need for more efficient routing.
Methods
The authors propose a three-stage hybrid approach:
- Pre-processing: To manage the computational complexity arising from a large number of feasible routes, the original problem is reduced. This involves merging nearby docks into "super nodes" and excluding shipments related to nodes with very few demands.
- Solving the Reduced Problem: A set-covering integer linear programming (ILP) model is formulated for the reduced problem. This model aims to minimize total travel distance by selecting a subset of feasible truck routes that cover all transportation demands within the given shifts. The key innovation here is representing commodities as flows to be covered by routes, rather than treating each commodity as a node in a network, which helps reduce the search space.
- Post-processing: Commodities and nodes excluded during pre-processing are heuristically inserted back into the solution obtained from the reduced problem. If a commodity cannot be inserted into an existing route, a new route is opened. This stage also involves recovering the detailed flow distribution on shared route arcs by solving a system of linear equations.
A lower bound for the problem is also derived by relaxing time window constraints and formulating it as a service network design problem.
Datasets
The authors evaluated their approach using two types of datasets:
- Real-life Instances: 15 instances were extracted from real-world data provided by a company, covering a three-month period. These instances vary in planning horizon (4, 6, or 8 shifts) and commodity size.
- Artificial Instances: 17 instances were created with controlled demand parameters, including commodity quantity, load balance, and time window tightness (tight vs. loose, balanced vs. unbalanced). These were designed to test the algorithm's performance under various conditions.
The data for these instances is available online.
Key Insights and Ideas
- Set-Covering for Container Drayage: The paper demonstrates the effectiveness of a set-covering formulation for a complex, multi-shift container drayage problem, which is a novel application.
- Commodity Flow Representation: Representing commodities as flows rather than individual nodes in the ILP model significantly reduces the search space, making the problem more tractable.
- Three-Stage Hybrid Approach: The combination of pre-processing, ILP solving on a reduced problem, and post-processing is crucial for handling the scale and complexity of real-world instances.
- Demand Imbalance as a Key Factor: The analysis suggests that unbalanced demand distribution (in space and time) is a primary driver of low transportation efficiency (low HLDR), more so than tight time windows, especially for real-life instances.
- Trade-off Between Constraint Tightness and Performance: Tightly constrained instances (tight time windows) can sometimes lead to faster computation for the ILP solver, while "loose" instances can be more challenging.
Key Results
- The proposed hybrid method achieved results very close to the derived lower bound for real-life instances, with gaps typically below 2%.
- For most real-life instances, the hybrid method outperformed existing metaheuristic approaches (VNS and SAHH) in terms of the Heavy Load Distance Rate (HLDR), a key performance indicator. For example, on NP4-1, the improvement was up to 6.0%, translating to nearly 1000km saving over two days.
- The method showed strong performance on "tight" instances but struggled with "loose" instances, requiring more computational time.
- For very large instances (over 2000 commodities), the proposed hybrid method failed to solve the problem within a reasonable time, while VNS and SAHH could still produce feasible solutions, suggesting the hybrid method is a complement rather than a replacement for metaheuristics in such cases.
Limitations and Future Work
- Computational Time for Loose Instances: The hybrid method can be computationally expensive for instances with loose time windows.
- Approximations in Pre/Post-processing: The merging of nodes in the pre-processing stage (using mean service times) can lead to suboptimal solutions or infeasibility, although this is mitigated in later stages.
- Large Instances: The proposed method struggles with extremely large instances, where metaheuristics might be more suitable.
Future work suggested includes:
- Investigating other techniques to address the problem, particularly for "loose" instances.
- Exploring multi-threading parallel computing and novel integer optimization techniques to speed up the solution process.
- Developing tighter lower bounds, especially for real-life instances where the current bound might be too loose.
- Further analysis of demand imbalance and its impact on transportation efficiency.
Summary updated