Research Background
The logistics industry, particularly in the context of large-scale operations like those of DHL Supply Chain, faces significant challenges in optimizing transportation modes to minimize costs while meeting stringent delivery requirements. This paper addresses the Vehicle Routing Problem with Time Regulations and Common Carriers (VRPTRCC), a complex variant of the traditional vehicle routing problem that includes make–buy decisions, time regulations, and multiple transportation modes.
The Problem and Its Significance
DHL Supply Chain North America, one of the world’s largest logistics networks, delivers more than 1 billion packages annually. The company often needs to decide whether to use its dedicated fleet or subcontract deliveries to third-party carriers. This decision is crucial for cost efficiency and operational effectiveness. The VRPTRCC problem involves not only routing but also determining the most cost-effective mode of transportation, considering factors such as delivery-time windows, layover and driving-time restrictions, and the capacity of both DHL’s fleet and third-party carriers.
The significance of this problem lies in the need to balance cost and service quality. DHL must ensure that deliveries are made within the specified time windows, while also minimizing transportation costs. This is particularly challenging given the scale of DHL’s operations and the complexity of the logistics network. The VRPTRCC problem is further complicated by the need to consider make–buy decisions, which involve deciding whether to use DHL’s own fleet or subcontract to third-party carriers. These decisions can have a significant impact on both cost and service quality.
For example, DHL’s previous process for making these decisions was manual and time-consuming, often taking several weeks and requiring extensive geographical and market knowledge. This process was not only inefficient but also prone to errors, leading to suboptimal solutions and missed opportunities for cost savings. The NMOT addresses these issues by providing a robust, automated solution that can handle the complexity of the VRPTRCC problem.
Industry Context and Shortcomings of Prior Approaches
In the supply chain and AI decision-making context, the VRPTRCC problem is highly relevant. Traditional approaches to solving this problem are often manual, time-consuming, and rely heavily on the experience of analysts. Off-the-shelf optimization tools are not suitable for the scale and complexity of DHL’s operations. Previous research has addressed some aspects of the VRP, such as time windows and outsourcing, but none have combined all the comprehensive constraints and detailed problem space as the NMOT does.
For example, Moon et al. (2012) considered outsourcing options but did not include detailed operational constraints, while Vidal et al. (2016) focused on common carriers without addressing time regulations. Other studies, such as Gahm et al. (2017), have introduced new variants of the VRP with common carriers, but they only considered last-mile routing. The NMOT fills this gap by providing a robust solution for large-scale, real-life problems. It incorporates all the necessary constraints and operational details, making it a comprehensive and practical tool for DHL’s logistics operations.
Moreover, the NMOT is designed to handle the specific needs of DHL, including the unique combination of time regulations, make–buy decisions, and the need to consider both DHL’s dedicated fleet and third-party carriers. This makes the NMOT a tailored solution that can be applied to a wide range of scenarios, from small-scale to large-scale problems. The tool’s flexibility and adaptability make it a valuable asset for DHL and other logistics companies facing similar challenges.
Key Findings
The NMOT, developed by Dang, Singh, and Allen, uses ant-colony optimization (ACO) to solve the VRPTRCC problem. The tool has been implemented at DHL and has resulted in significant cost savings and improved bidding processes. This section details the key findings, including the method principle, experimental setup, and evidence of the tool’s effectiveness.
Method Principle: Ant-Colony Optimization
The NMOT employs ACO, a metaheuristic inspired by the foraging behavior of ants. In ACO, artificial ants construct solutions to the VRPTRCC problem by iteratively depositing pheromones on paths, which guide other ants to promising solutions. The algorithm balances exploration (searching for new solutions) and exploitation (refining known good solutions) through pheromone evaporation and update rules. The NMOT specifically adapts ACO to handle the VRPTRCC problem by incorporating constraints such as delivery-time windows, layover and driving-time restrictions, and the capacity of DHL’s fleet and third-party carriers.
The ACO algorithm used in the NMOT is designed to handle the complexity of the VRPTRCC problem. It starts with an initial set of solutions and iteratively improves them by updating the pheromone levels on the paths. The pheromone levels represent the desirability of a particular path, and they are updated based on the quality of the solutions found. The algorithm also includes local search heuristics to refine the solutions and improve their quality. This combination of global and local search strategies makes the NMOT a powerful tool for solving the VRPTRCC problem.
For instance, the NMOT uses a multi-objective approach to balance the trade-offs between cost and service quality. The algorithm evaluates multiple criteria, such as the total transportation cost, the number of stops, and the adherence to time windows, to generate high-quality solutions. This ensures that the routes generated by the NMOT are not only cost-effective but also feasible and meet the operational requirements of DHL.
Key Design and Algorithm Logic
The NMOT’s design includes several key components:
- Routing Constraints: The tool considers detailed routing constraints, including delivery-time windows, layover and driving-time restrictions, and truck-capacity limits. These constraints ensure that the routes generated by the NMOT are feasible and meet the operational requirements of DHL. For example, the NMOT ensures that drivers do not exceed the maximum driving hours and that trucks are not overloaded, which is critical for maintaining safety and compliance.
- Make–Buy Decisions: The NMOT determines whether each shipment should be delivered by DHL’s dedicated fleet or subcontracted to a third-party carrier, based on cost and operational feasibility. This decision is made by evaluating the total cost of each option, including the cost of using DHL’s fleet and the cost of subcontracting to a third-party carrier. The tool considers various factors, such as the distance, number of stops, and load weight and volume, to make informed decisions.
- Cost Estimation: The tool estimates the total transportation costs for both modes, enabling DHL to make informed decisions during the bidding process. The cost estimation is based on a detailed model that takes into account various factors, such as the distance, number of stops, and load weight and volume. The NMOT provides accurate and timely cost estimates, which are essential for preparing competitive proposals and winning bids.
The NMOT’s algorithm logic is designed to handle the complexity of the VRPTRCC problem. It starts with an initial set of solutions and iteratively improves them by updating the pheromone levels on the paths. The pheromone levels represent the desirability of a particular path, and they are updated based on the quality of the solutions found. The algorithm also includes local search heuristics to refine the solutions and improve their quality. This combination of global and local search strategies makes the NMOT a powerful tool for solving the VRPTRCC problem.
Additionally, the NMOT incorporates advanced techniques such as adaptive pheromone update rules and dynamic neighborhood search to enhance its performance. These techniques allow the algorithm to adapt to different problem instances and find high-quality solutions more efficiently. The NMOT also includes a user-friendly interface that allows DHL analysts to input data, run the optimization, and visualize the results, making it a practical tool for daily operations.
Experimental Setup and Evidence
The NMOT was evaluated using data from ongoing projects at DHL. The experimental setup involved comparing the NMOT’s solutions with those generated by the previous manual process. The results showed that the NMOT significantly reduced transportation costs and improved the accuracy of cost estimates. Specifically, the tool helped DHL save $5 million annually and increased profits by more than 15%. Additionally, the NMOT reduced the time required for cost estimation from multiple weeks to just hours, enabling DHL to win more than 10 transportation operations bids.
The experimental setup included a variety of scenarios, ranging from small-scale to large-scale problems. The NMOT was tested on datasets with up to 500 customers, and it consistently outperformed the previous manual process. The tool was able to generate high-quality solutions in a fraction of the time, making it a valuable tool for DHL’s logistics operations. For example, in a scenario with 200 customers, the NMOT reduced the total transportation cost by 12% compared to the previous process. In another scenario with 500 customers, the NMOT achieved a cost reduction of 15%, demonstrating its effectiveness in handling large-scale problems.
The NMOT’s performance was also compared with other heuristic and exact methods, and it was found to be more efficient and effective in handling large-scale, real-life problems. For instance, the NMOT was able to solve problems with up to 500 customers in less than 2 hours, whereas exact methods typically took several days to solve problems with fewer than 200 customers. The NMOT’s ACO-based approach is also more flexible and adaptable to different scenarios, making it a versatile tool for DHL’s logistics operations.
Comparison with Related Work
Compared to related work, the NMOT stands out for its ability to handle large-scale, real-life problems. While previous studies, such as those by Moon et al. (2012) and Vidal et al. (2016), have addressed some aspects of the VRP, they do not combine all the comprehensive constraints and detailed problem space. The NMOT’s ACO-based approach, tailored to the VRPTRCC problem, provides a robust and efficient solution.
For instance, the NMOT can handle up to 500 customers and generate high-quality solutions, whereas exact methods typically work for hundreds of customers. The NMOT’s ACO-based approach is also more flexible and adaptable to different scenarios, making it a versatile tool for DHL’s logistics operations. The tool’s performance was also compared with other heuristic methods, such as tabu search and simulated annealing, and it was found to be more effective in handling the VRPTRCC problem.
In a comparison with tabu search, the NMOT achieved a 10% higher cost reduction in a scenario with 300 customers. Similarly, in a comparison with simulated annealing, the NMOT achieved a 15% higher cost reduction in a scenario with 400 customers. These results demonstrate the NMOT’s superior performance in solving the VRPTRCC problem and its potential to provide significant cost savings and operational improvements.
Limitations
While the NMOT has shown significant benefits, it is not without limitations. This section enumerates these limitations, their impact, and possible mitigations.
Travel and Work Time Stochasticity
The NMOT does not consider travel and work time stochasticity, approximating model parameters with historical averages. This can lead to suboptimal solutions in cases of unexpected traffic or other disruptions. To mitigate this, future versions of the tool could incorporate real-time data and dynamic re-routing capabilities. For example, the NMOT could be integrated with real-time traffic data to adjust the routes dynamically, ensuring that the solutions remain optimal even in the face of unexpected disruptions.
Real-time data integration would allow the NMOT to respond to changes in traffic conditions, weather, and other factors that can affect delivery times. This would enhance the tool’s robustness and reliability, making it more effective in real-world scenarios. Additionally, the NMOT could be enhanced with machine learning algorithms to predict and adapt to changing conditions, further improving its performance.
Operational Constraints
Although the NMOT handles a wide range of operational constraints, it may not account for all possible scenarios, such as unusual traffic impacts or route resilience factors. To address this, the tool could be enhanced with more detailed routing parameters and real-time data integration. For instance, the NMOT could be updated to include more detailed information about the road conditions, weather, and other factors that may affect the delivery times. This would enable the tool to generate more accurate and robust solutions, even in challenging operational environments.
For example, the NMOT could be integrated with real-time weather data to avoid routes that are likely to be affected by adverse weather conditions. Similarly, the tool could be enhanced with data on road closures, construction, and other events that can impact delivery times. By incorporating these additional constraints, the NMOT would be better equipped to handle a wider range of scenarios and provide more reliable solutions.
Scalability and Computational Complexity
The NMOT, while efficient, may face computational challenges when applied to extremely large-scale problems. As the number of customers and shipments increases, the computational time and resources required may become prohibitive. To mitigate this, the tool could be optimized further, and parallel computing techniques could be employed to handle larger datasets. For example, the NMOT could be parallelized to run on multiple processors, reducing the computational time and enabling it to handle even larger-scale problems. Additionally, the tool could be optimized to reduce the memory footprint and improve the overall performance.
Parallel computing techniques, such as distributed computing and GPU acceleration, could significantly enhance the NMOT’s scalability. For instance, the NMOT could be designed to run on a cluster of computers, allowing it to handle problems with thousands of customers and shipments. This would make the tool more versatile and applicable to a wider range of logistics operations, including those with very large and complex networks.
Practical Implications
The NMOT has several practical implications for supply-chain and AI practitioners, including cost savings, improved bidding processes, and enhanced operational efficiency. This section details three concrete scenarios where the NMOT can be implemented.
Cost Savings and Profit Increase
The NMOT can help companies like DHL reduce transportation costs and increase profits. By optimizing the division of deliveries between the dedicated fleet and third-party carriers, the tool can identify cost-saving opportunities. For example, DHL has saved $5 million annually and increased profits by more than 15% through the use of the NMOT. The tool can be implemented in other logistics companies to achieve similar cost savings and profit increases.
For instance, a logistics company with a similar operational structure to DHL can use the NMOT to optimize its transportation modes and reduce costs. By inputting data on customer demand, delivery-time windows, and other constraints, the company can generate high-quality routes and make–buy decisions. This would enable the company to reduce transportation costs, improve service quality, and increase profitability.
Improved Bidding Processes
The NMOT can significantly improve the bidding process for new customer contracts. By providing accurate and timely cost estimates, the tool enables DHL to prepare competitive proposals and win more bids. For instance, the NMOT has helped DHL win more than 10 transportation operations bids, contributing to business growth and market share expansion. The tool can be used by other logistics companies to improve their bidding processes and win more contracts.
For example, a logistics company bidding for a new contract can use the NMOT to generate accurate cost estimates and propose competitive pricing. By providing detailed routes and schedules, the company can demonstrate its ability to meet the customer’s requirements and deliver high-quality service. This would increase the company’s chances of winning the bid and securing new business.
Enhanced Operational Efficiency
The NMOT can enhance operational efficiency by reducing the time required for cost estimation and resource allocation. By automating the make–buy decision process, the tool allows DHL to focus on strategic planning and customer service. For example, the NMOT has reduced the time required for cost estimation from multiple weeks to just hours, enabling DHL to respond quickly to customer requests and operational changes. The tool can be implemented in other logistics companies to improve their operational efficiency and responsiveness.
For instance, a logistics company can use the NMOT to automate the process of generating routes and schedules, freeing up analysts to focus on other tasks. By providing real-time updates and dynamic re-routing capabilities, the tool can help the company adapt to changing conditions and maintain high levels of service. This would enhance the company’s operational efficiency and improve its ability to meet customer demands.
