TL;DR
This paper tackles the complex problem of optimizing liquefied petroleum gas (LPG) cylinder replacement logistics. By integrating smart meter data for more accurate gas consumption forecasting and employing a multi-step optimization approach, their system significantly reduces gas shortages, unnecessary visits, and overall delivery time, demonstrating a practical application of advanced optimization in a real-world service industry.
What Problem Does This Paper Address?
The traditional process of replacing LPG cylinders relies on manual checks, leading to frequent, often unnecessary, customer visits and a risk of gas shortages. Determining the exact remaining gas level without a physical inspection is challenging. While smart meters offer a solution by providing daily consumption data, integrating this data into an efficient, long-term delivery plan that considers factors like customer risk, delivery routes, and staff availability is a significant logistical puzzle. This paper addresses the "Cylinder Replacement Problem" (CRP), aiming to create an optimal plan that minimizes gas shortages and operational costs.
Methods
The proposed solution is a three-step system:
- Estimating Replacement Date:
- For smart meter customers, daily gas consumption is directly available.
- For conventional meter customers, gas usage is extrapolated using a novel k-nearest neighbor (kNN) approach that leverages data from similar smart meter customers. This is a key innovation for handling legacy infrastructure.
- A risk function is then defined to quantify the "emergency" of a gas shortage, considering forecast gas usage and its uncertainty. This function categorizes customers into high, moderate, and low-risk groups.
- Acquiring Customer Lists for Multiple Dates:
- This step aims to create a customer list for replacement, prioritizing high-risk customers and considering moderate-risk ones to prevent future shortages and smooth out daily workloads.
- A bounding-box based model is used to define a rectangular area covering customers needing replacement. This is optimized to minimize the area, thus potentially reducing travel distance.
- A multi-period optimization model is employed to simultaneously acquire lists for multiple days, preventing the concentration of deliveries on specific days and avoiding large delivery areas that could impact future routes.
- Determining Delivery Route:
- This involves two sequential optimization problems:
- Maximizing Deliveries: Prioritizes visiting moderate-risk customers while ensuring high-risk customers are served, aiming to maximize the number of deliveries.
- Minimizing Working Duration: Once the set of customers to visit is determined, this step optimizes the order of visits to minimize the total travel and service time.
- The actual route optimization between customers is handled by an external service (MapBox), focusing the paper's contribution on the planning and ordering aspects.
Datasets
- Real-world data from over 1,000 LPG customers in Chiba prefecture, Japan, was used for a large-scale field test.
- This dataset included both customers with smart meters and those with conventional meters.
- For numerical experiments in the appendix, data was generated by intentionally omitting smart meter readings to simulate conventional meter behavior.
Key Insights and Ideas
- Bridging the Smart Meter Gap: The kNN-based extrapolation of gas usage for conventional meters is a crucial innovation, allowing the system to provide benefits even when not all customers have smart meters.
- Proactive Risk Management: The risk function, which considers forecast uncertainty, allows for proactive replacement scheduling, preventing shortages and smoothing demand.
- Multi-Day Planning: Simultaneously planning for multiple days, rather than sequentially, is key to optimizing delivery routes and preventing future logistical bottlenecks.
- Bounding Box Optimization: Using a bounding box to cover customers, without necessarily including the depot, leads to more efficient delivery routes, especially when the depot is geographically distant from customer clusters.
Key Results
A large-scale field test with over 1,000 customers demonstrated significant improvements:
- Zero gas shortages were reported during the test period.
- Nonreplacement visits (visits where no replacement was needed) were reduced to zero.
- Average travel time per day was reduced by approximately 20% (from 2h 52m to 2h 06m).
- Average travel time per customer was reduced by about 36% (from 3m 46s to 2m 34s).
- The system achieved these improvements even with a significant portion of customers (about one-third) not having smart meters.
- Experimental results showed that the proposed system outperformed the gas provider's existing methods across various metrics, including success rate and fail-over events.
Limitations and Future Work
- Smart Meter Adoption: The system's effectiveness is enhanced by smart meters, and the paper acknowledges that wider adoption will further improve gas shortage prediction.
- Customer Aggregation: Feedback suggests that grouping customers for replacement more effectively (e.g., those in close proximity) could further reduce workload. This is identified as a key area for future research.
- Customer Prioritization for Smart Meters: Determining which customers should be prioritized for smart meter installation is another avenue for future work to maximize the impact of the system.
- Generalization to Other Industries: The framework's potential application to other delivery-based industries (e.g., grocery delivery) is highlighted as a future direction.
- Hyperparameter Sensitivity: While experiments explored parameter tuning, further refinement of parameters like
qhighandqmdrcould potentially improve results.
Summary updated